Data Structures & Algorithms

Flashcards for reviewing data structures and algorithms concepts.

What are Data Structures?

Programmatic ways of storing data for efficient use.

What is the purpose of this tutorial?

To provide a great understanding of Data Structures needed to understand the complexity of enterprise-level applications and the need for algorithms.

What should one know before proceeding with this tutorial?

A basic understanding of C programming language, text editor, and execution of programs.

What is an Algorithm?

A step-by-step procedure defining instructions to be executed in a certain order to get the desired output.

List the characteristics of an Algorithm

Unambiguous, Input, Output, Finiteness, Feasibility, Independent

Define Priori Analysis

Theoretical analysis of an algorithm, assuming constant factors like processor speed.

Define Posteriori Analysis

Empirical analysis of an algorithm, involving implementation and execution on a target computer.

Define Time Complexity

A measure of the amount of time required for an algorithm to run to completion.

Explain Big Oh Notation

A formal way to express the upper bound of an algorithm's running time, measuring worst-case time complexity.

What are common Asymptotic Notations?

Constant - Ο(1), logarithmic - Ο(log n), linear - Ο(n), n log n - Ο(n log n), quadratic - Ο(n^2), cubic - Ο(n^3), polynomial - n^Ο(1), exponential - 2^Ο(n)

Define Greedy Algorithm

An algorithm that makes decisions from the given solution domain by choosing the closest solution that seems to provide an optimum solution.

What is the main concept of Divide & Conquer?

Breaking down a problem into smaller sub-problems, solving each independently, and then merging the solutions.

What is the main concept of Dynamic Programming?

Breaking down a problem into smaller overlapping sub-problems, solving each only once, and storing the results for future use.

What are built-in Data Types?

Those data types for which a language has built-in support (e.g., Integers, Boolean, Floating-point numbers, Characters and Strings)

What are Derived Data Types used in data structures?

Data types which are implementation independent, using combination of primary data types (e.g., List, Array, Stack, Queue)

List the Basic Array Operations

Traverse, Insertion, Deletion, Search, Update

What is a Linked List?

A sequence of data structures (links) connected together, where each link contains an item and a connection to another link.

List the Basic Operations for a Linked List

Insertion, Deletion, Display, Search, Delete

What is a Stack?

An abstract data type that follows the Last-In-First-Out (LIFO) principle.

List the Basic Stack Operations

push(), pop(), peek(), isFull(), isEmpty()

What is a Queue?

An abstract data structure that is open at both ends, following the First-In-First-Out (FIFO) principle.

What are the Basic Queue Operations?

enqueue(), dequeue(), peek(), isfull(), isempty()

Describe Linear Search

A simple search algorithm that sequentially checks each item in a collection until a match is found.

Describe Binary Search

A fast search algorithm that works on the divide and conquer principle, requiring the data collection to be sorted.

How does Binary Search work?

Compares the target value to the middle element of the array; if they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half

Describe Interpolation Search

An improved variant of binary search that works on the probing position of the required value, requiring sorted and equally distributed data.

What is Hashing?

A technique to convert a range of key values into a range of indexes of an array, often using the modulo operator.

List the Basic Sorting Algorithm Terms

Increasing Order, Decreasing Order, Non-Increasing Order, Non-Decreasing Order

Describe Bubble Sort

A comparison-based sorting algorithm where each pair of adjacent elements is compared and swapped if they are not in order.

Describe Insertion Sort

An in-place comparison-based sorting algorithm that maintains a sorted sub-list and inserts unsorted items into their appropriate positions.

Describe Selection Sort

An in-place comparison-based algorithm that divides the list into sorted and unsorted parts, repeatedly selecting the smallest element from the unsorted part and swapping it with the leftmost element.

Describe Merge Sort

A sorting technique that divides the array into equal halves and then combines them in a sorted manner, based on the divide and conquer technique.

What is the work flow of Merge Sort?

Divides an array in two, calls itself for the two halves, and the merges the two sorted halves.

Describe Shell Sort

An efficient sorting algorithm that uses insertion sort on widely spaced elements, first sorting them and then sorting the less widely spaced elements.

Describe Quick Sort

An efficient sorting algorithm based on partitioning an array into smaller arrays, with one holding values smaller than a pivot and another holding values greater than the pivot.

Describe Depth First Search (DFS) algorithm

Traverses a graph in a depthward motion and uses a stack, employing rules to visit adjacent unvisited vertices, mark them as visited, and display them.

Describe Breadth First Search (BFS) algorithm

Traverses a graph in a breadthward motion and uses a queue, employing rules to visit adjacent unvisited vertices, mark them as visited, and display them.

List the properties of what a Binary Search Tree (BST) all the nodes must follow

The left sub-tree of a node has a key less than or equal to its parent node's key; The right sub-tree of a node has a key greater than or equal to its parent node's key

Describe in-order Tree Traversal

The left subtree is visited first, then the root, and later the right sub-tree.

Describe pre-order Tree Traversal

The root node is visited first, then the left subtree, and finally the right subtree.

Describe post-order Tree Traversal

The root node is visited last: first the left subtree, then the right subtree, and finally the root node.

Describe AVL Trees

Height balancing binary search tree; checks the height of the left and the right sub-trees and assures that the difference is not more than 1.

List the AVL Rotations

Left rotation, Right rotation, Left-Right rotation, Right-Left rotation

Describe Spanning Tree

A subset of Graph G, which has all the vertices covered with the minimum possible number of edges; does not have cycles and it cannot be disconnected.

Describe the Kruskal's Spanning Tree Algorithm

Uses the greedy approach, treats the graph as a forest, connects trees only if it has the least cost and does not violate MST properties.

Describe the Prim's Spanning Tree Algorithm

Uses the greedy approach, treats nodes as a single tree, and keeps adding new nodes to the spanning tree from the given graph.

Describe Heaps

Special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. Has two types: Min-Heap; Max-Heap

Define Recursion

Technique in which a module or function calls itself.

What is the Tower of Hanoi?

A mathematical puzzle which consists of three towers (pegs) and more than one rings stacked upon in an ascending order.

What is the procedure to solve the Tower of Hanoi?

Move n-1 disks from source to aux, move nth disk from source to dest, move n-1 disks from aux to dest

Summarize Fibonacci Series

Number sequence that generates the subsequent number by adding two previous numbers. Fibonacci series starts from two numbers (F0 & F1= 0, 1; Fn = Fn-1 + Fn-2).

Describe Linear Search

A simple search algorithm that sequentially checks each item in a collection until a match is found.

Describe Binary Search

A fast search algorithm that works on the divide and conquer principle, requiring the data collection to be sorted.

How does Binary Search work?

Compares the target value to the middle element of the array; if they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half

Describe Interpolation Search

An improved variant of binary search that works on the probing position of the required value, requiring sorted and equally distributed data.

Describe Bubble Sort

A comparison-based sorting algorithm where each pair of adjacent elements is compared and swapped if they are not in order.

Describe Insertion Sort

An in-place comparison-based sorting algorithm that maintains a sorted sub-list and inserts unsorted items into their appropriate positions.

Describe Selection Sort

An in-place comparison-based algorithm that divides the list into sorted and unsorted parts, repeatedly selecting the smallest element from the unsorted part and swapping it with the leftmost element.

Describe Merge Sort

A sorting technique that divides the array into equal halves and then combines them in a sorted manner, based on the divide and conquer technique.

What is the work flow of Merge Sort?

Divides an array in two, calls itself for the two halves, and the merges the two sorted halves.

Describe Shell Sort

An efficient sorting algorithm that uses insertion sort on widely spaced elements, first sorting them and then sorting the less widely spaced elements.

Describe Quick Sort

An efficient sorting algorithm based on partitioning an array into smaller arrays, with one holding values smaller than a pivot and another holding values greater than the pivot.

Describe Depth First Search (DFS) algorithm

Traverses a graph in a depthward motion and uses a stack, employing rules to visit adjacent unvisited vertices, mark them as visited, and display them.

Describe Breadth First Search (BFS) algorithm

Traverses a graph in a breadthward motion and uses a queue, employing rules to visit adjacent unvisited vertices, mark them as visited, and display them.

List the properties of what a Binary Search Tree (BST) all the nodes must follow

The left sub-tree of a node has a key less than or equal to its parent node's key; The right sub-tree of a node has a key greater than or equal to its parent node's key

Describe in-order Tree Traversal

The left subtree is visited first, then the root, and later the right sub-tree.

Describe pre-order Tree Traversal

The root node is visited first, then the left subtree, and finally the right subtree.

Describe post-order Tree Traversal

The root node is visited last: first the left subtree, then the right subtree, and finally the root node.

Describe AVL Trees

Height balancing binary search tree; checks the height of the left and the right sub-trees and assures that the difference is not more than 1.

List the AVL Rotations

Left rotation, Right rotation, Left-Right rotation, Right-Left rotation

Describe Spanning Tree

A subset of Graph G, which has all the vertices covered with the minimum possible number of edges; does not have cycles and it cannot be