Data Structures and Algorithms Lecture Notes

Comprehensive practice flashcards covering Graphs, Trees, AVL & Red-Black Trees, Heaps, Hashing, and String Pattern Matching algorithms from the lecture notes.

How do linear and non-linear data structures differ in terms of arrangement and traversal paths?

In linear data structures, elements are arranged sequentially in a single level and traversal is performed sequentially. In non-linear data structures, elements are arranged hierarchically or interconnected across multiple levels and traversal can follow multiple paths.

How is a graph formally defined mathematically?

A graph is defined as an ordered set $G(V, E)$, where $V(G)$ represents the set of vertices (or nodes) and $E(G)$ represents the set of edges (or arcs) used to connect these vertices.

What are the three main types of graphs based on edge properties?

1. Directed Graph: Every edge has a specific direction shown by arrows, representing a one-way relationship.
2. Undirected Graph: Edges do not have direction; connections work in both directions.
3. Weighted Graph: Each edge is assigned a numerical cost or weight representing distance, time, or expense.

What are the primary differences in time and space complexity between an Adjacency Matrix and an Adjacency List for representing graphs?

An Adjacency Matrix requires $O(V^2)$ memory, allows edge existence checking in $O(1)$ time, and finding adjacent vertices takes $O(V)$ time. An Adjacency List requires less memory for sparse graphs, checking edge existence takes $O(\text{degree of vertex})$ time, and it is more efficient for traversals.

What graph representation and corresponding graph are shown in the image?

An Adjacency Matrix representation for an undirected 4-vertex cycle graph where vertices $A, B, C, D$ have edges between adjacent pairs.

What traversal method is demonstrated in the diagram, and what is its traversal sequence?

Depth-First Search (DFS), producing the traversal sequence $A D F C E B$.

What traversal method is shown in the diagram, and what is its traversal sequence?

Breadth-First Search (BFS), producing the level-by-level traversal sequence $A B C D E F$.

What underlying data structure does Breadth-First Search (BFS) use, and what does Depth-First Search (DFS) use?

BFS uses a Queue (FIFO list), whereas DFS uses a Stack (LIFO list) or recursion.

What concept is shown in the graph with the highlighted blue edges?

A Minimum Spanning Tree (MST), connecting all vertices with minimum total edge weight and no cycles.

What are the key properties of a Minimum Spanning Tree (MST)?

1. It connects all vertices of a connected, undirected, weighted graph.
2. It contains exactly $V - 1$ edges (where $V$ is the number of vertices).
3. It contains no cycles.
4. It has the minimum possible total edge weight.

How do Kruskal's and Prim's algorithms differ in edge selection and graph growth?

Kruskal's algorithm sorts all edges and selects edges in increasing order of weight from anywhere in the graph using Disjoint Set (Union-Find) for cycle detection (running in $O(E \log E)$). Prim's algorithm starts from a single vertex and greedily grows a single connected tree by selecting the minimum-weight adjacent edge connecting a visited vertex to an unvisited vertex (running in $O(V^2)$ with an adjacency matrix).

What is the edge relaxation formula used in Dijkstra's Shortest Path Algorithm, and what weight constraint does it impose?

The relaxation formula is $d[v] = \min(d[v], d[u] + w(u, v))$. Dijkstra's algorithm requires all edge weights to be non-negative.

What is the ordering property of a Binary Search Tree (BST)?

For any node, the left subtree contains values smaller than the root node, the right subtree contains values greater than the root node, and both left and right subtrees must also be BSTs.

What data structure is illustrated in the diagram?

A Binary Search Tree (BST) constructed with root node $50$, left child $30$, right child $70$, and leaf nodes $20$, $40$, $60$, and $80$.

What are the average-case and worst-case time complexities for searching, insertion, and deletion in a Binary Search Tree?

Average case: $O(\log n)$. Worst case (when the tree becomes skewed): $O(n)$.

Which BST deletion case is illustrated in the diagram, and how is it executed?

Case 1: Deletion of a leaf node (node $20$). Its parent's corresponding pointer is set to NULL, and the node is deleted directly.

Which BST deletion case is illustrated in the diagram, and how is it executed?

Case 2: Deletion of a node with a single child (node $70$). The node's parent is connected directly to its child (node $80$), and the node is deleted.

Which BST deletion case is illustrated in the diagram, and how is it executed?

Case 3: Deletion of a node with both children (root node $50$). The node's value is replaced with its in-order successor (the smallest node in the right subtree, $60$), and the in-order successor is deleted from its original position.

What is the difference between a Binary Tree and a Binary Search Tree regarding inorder traversal?

In a Binary Tree, inorder traversal does not necessarily produce sorted data. In a Binary Search Tree, inorder traversal always yields the elements in sorted order.

What multiway search tree index structure is shown in the diagram?

A B-Tree Index, featuring a root node ($43$), internal nodes ($25$, $61$), and leaf nodes ($16$, $34$, $52$, $70$).

What tree structure is illustrated in the diagram, and what feature enables its efficient sequential range queries?

A B+ Tree; all actual values are held in leaf nodes that are linked sequentially, allowing range queries without jumping back up the tree.

What are three major structural differences between a B-Tree and a B+ Tree?

1. In a B-Tree, keys and records can be stored in internal and leaf nodes; in a B+ Tree, records are stored only at leaf nodes while internal nodes store only keys and child pointers.
2. In a B-Tree, leaf nodes are not linked; in a B+ Tree, leaf nodes are linked together.
3. In a B-Tree, search keys appear only once; in a B+ Tree, search keys may be duplicated in internal nodes and leaf nodes.

Why is a B+ Tree preferred over a B-Tree for database indexing?

Because internal nodes store only keys and child pointers, giving them higher fan-out and reducing overall tree height (fewer disk I/O operations). Furthermore, linked leaf nodes make sequential access and range-based queries much faster.

How is the Balance Factor (BF) defined in an AVL tree, and which values represent a balanced state?

Balance Factor is defined as: $\text{BF} = \text{Height(Left)} - \text{Height(Right)}$ Balanced states are $\text{BF} = 0$, $\text{BF} = +1$ (left-heavy), and $\text{BF} = -1$ (right-heavy). Values of $+2$ or $-2$ indicate an unbalanced node.

What single rotations correct Left-Left (LL) and Right-Right (RR) imbalances in an AVL tree?

LL Case is corrected using a single right rotation on the unbalanced node. RR Case is corrected using a single left rotation on the unbalanced node.

What double rotations correct Left-Right (LR) and Right-Left (RL) imbalances in an AVL tree?

LR Case is corrected using: (1) a left rotation on the left child, followed by (2) a right rotation on the unbalanced node. RL Case is corrected using: (1) a right rotation on the right child, followed by (2) a left rotation on the unbalanced node.

What data structure is illustrated in the diagram?

A Red-Black Tree, displaying black root ($13$), red internal nodes ($8$, $17$, $6$, $22$, $27$), and black NIL leaf nodes satisfying the equal black-height property.

What are the primary color and path rules of a Red-Black Tree?

1. Every node is either Red or Black.
2. The root node must be Black.
3. All NIL leaves are Black.
4. Red Property: A Red node cannot have a Red parent or Red child (no consecutive red nodes).
5. Black Height Property: Every path from a node to its descendant NIL leaves must contain the same number of Black nodes.

What operations are depicted in the splaying cases diagram?

Splaying cases in a Splay Tree: the zig-zig rotation (same direction double rotation), the zig-zag rotation (opposite direction double rotation), and the zig rotation (single rotation).

What is the defining mechanism and amortized time complexity of a Splay Tree?

A Splay Tree adjusts its structure by moving the most recently accessed node to the root via rotations (a process called Splaying). It requires no balance factors or colors, and has an amortized time complexity of $O(\log n)$ per operation.

What practical application of tree data structures is represented in this diagram?

A hierarchical File System, where the topmost node is the Root directory, directories act as parent nodes, and files/subdirectories act as child nodes.

How do Binomial Heaps and Fibonacci Heaps compare in terms of insertion and decrease-key time complexities?

In a Binomial Heap, insertion takes $O(\log n)$ and decrease-key takes $O(\log n)$. In a Fibonacci Heap, insertion takes $O(1)$ amortized time and decrease-key takes $O(1)$ amortized time.

Why is a Fibonacci Heap preferred over a Binary Heap in Dijkstra's shortest path algorithm?

Because its decrease-key operation takes $O(1)$ amortized time compared to $O(\log V)$ in a Binary Heap, improving the overall running time of Dijkstra's algorithm from $O((V + E) \log V)$ to $O(V \log V + E)$.

What specific data structure is depicted in the diagram, and what is its defining property?

A Max Heap; every parent node is greater than or equal to its children, meaning root element $50$ has the highest priority.

How do a Heap-Based Priority Queue and an Unsorted Array-Based Priority Queue compare for insertion and deletion of the highest-priority element?

Heap-based: insertion takes $O(\log n)$ and deletion takes $O(\log n)$. Unsorted array-based: insertion takes $O(1)$ and deletion takes $O(n)$.

What algorithm and tree structure are illustrated in the diagram, showing an expected encoding cost of $2.24$?

Huffman Coding / Huffman Tree, which assigns variable-length prefix-free binary codes to characters based on frequency.

What heap is used in Huffman Coding, and what are its total construction time and space complexities?

A Min Heap (Minimum Priority Queue) is used. The total construction time complexity is $O(n \log n)$ and space complexity is $O(n)$, where $n$ is the number of distinct characters.

What are the time and auxiliary space complexities of Heap Sort?

Time complexity is $O(n \log n)$ in all cases (Best, Average, and Worst); building the heap takes $O(n)$; auxiliary space complexity is $O(1)$ (an in-place, unstable sort).

What is a hash collision, and what formula defines a standard modulo division hash function?

A collision occurs when two or more distinct keys produce the same hash table index. The standard division hash function formula is: $h(\text{key}) = \text{key} \bmod \text{table size}$

Which collision resolution technique is shown in the example table where keys mapping to the same index form a list?

Separate Chaining, where each hash table location maintains a linked list of elements mapped to that index.

Which open addressing probing method is illustrated in the diagram resolving a collision at index 6?

Linear Probing, where the next consecutive index is checked using $(6 + 1) \bmod 7 = 0$ to place the element at index 0.

What is the probing formula for Quadratic Probing, and what problem of linear probing does it reduce?

The formula is: $h_i(k) = (h(k) + i^2) \bmod m$ It reduces primary clustering, though secondary clustering can still occur.

What is the probing formula for Double Hashing?

The formula is: $h_i(k) = (h_1(k) + i \times h_2(k)) \bmod m$ where $h_1(k)$ is the primary hash function and $h_2(k)$ is the secondary hash function providing variable intervals.

What process is illustrated in the diagram when the load factor becomes $5/7$ and the table size increases to 17?

Rehashing, where existing elements are re-inserted into a new, larger hash table of size 17 using $h(x) = x \bmod 17$ to reduce collisions.

How is the load factor (\alpha) of a hash table defined?

The load factor is defined as: $\alpha = \frac{\text{Number of elements}}{\text{Size of Hash Table}}$

What are the common hash function design methods mentioned in the notes?

1. Division Method: $h(k) = k \bmod m$
2. Mid-Square Method: Square the key and extract middle digits.
3. Folding Method: Divide the key into equal parts and sum them.
4. Digit Extraction Method: Extract specific digit positions.
5. Multiplication Method: Multiply the key by a constant between 0 and 1, extract fractional part, and multiply by table size.

What is a Dictionary ADT, and how does its access method differ from an Array?

A Dictionary ADT is an abstract data type that stores unique key-value pairs, accessing data by key lookup (often $O(1)$ using hashing). An Array stores elements in contiguous memory and accesses data using an integer index.

What are the best-case, average-case, and worst-case time complexities of the Brute-Force pattern matching algorithm?

Let $n$ be text length and $m$ be pattern length: Best case: $O(n)$ Average/Worst case: $O(nm)$ Space complexity: $O(1)$.

How does the Boyer-Moore pattern matching algorithm compare characters, and which two heuristics does it use to determine shift distance?

It compares characters from right to left (starting from the end of the pattern). It uses the Bad Character Heuristic and the Good Suffix Heuristic, shifting by the larger valid shift.

What is an LPS array in the Knuth-Morris-Pratt (KMP) algorithm, and what is its value for the pattern 'ABABAC'?

LPS stands for 'Longest Proper Prefix which is also Suffix'. For pattern 'ABABAC', the LPS array is: $[0, 0, 1, 2, 3, 0]$

What are the total time and space complexities of the Knuth-Morris-Pratt (KMP) algorithm?

Let $n$ be text length and $m$ be pattern length: LPS array construction takes $O(m)$; pattern searching takes $O(n)$; total time complexity is $O(n + m)$ with $O(m)$ auxiliary space.