SEN2212 · Week 14 · Review.

Final review: which structure, which algorithm, which Big-O

The whole term on one page: a table for choosing a structure/algorithm by problem type, a Big-O summary of all operations and one mixed final question from each topic.

time complexityworst caseaverage caseamortizedbinary search treeAVL treered-black treeB-treebinary heappriority queuehash tableload factorgraph traversaltopological sortshortest pathminimum spanning treegreedycomparison sort lower bound

This page is the last round before the final. There is no topic explanation; it collects, for each topic, the “do not enter the exam without knowing this” part, the decision tables and the Big-O summary. The details of each section are in its own week. Final questions are generally of two kinds: tracing questions (tree, heap array, hash table, graph order, Dijkstra table, Huffman code, MST edges) and choice questions (“which structure for this problem, why, what is the complexity?”). The 12 questions below are one from each topic.

Golden rules:

In a tracing question, write every step. The intermediate state earns points even if the final answer is wrong.
Write the tie rule. If the question does not specify one, add a line such as “ties by smallest label”.
When asked for Big-O, ask whether it is the worst case or the average. In BST and hash the two are very different.
Do not forget the balanced/unbalanced distinction. “Search in a BST is O(log n)” is correct only if it is balanced.

Problem → structure / algorithm decision table

Need	Choose	Why
Search/insert/delete by key, order does not matter	Hash table	Average $O(1)$
Keep sorted, range queries, min/max, k-th element	AVL / red-black tree	Worst case $O(\log n)$ , inorder is sorted
Very large sorted data on disk (a database index)	B-tree	Many keys per node, few disk accesses
Repeated access to recently accessed items	Splay tree	The accessed node comes to the root, amortized $O(\log n)$
Always take the smallest / the most urgent	Binary heap (PriorityQueue)	findMin $O(1)$ , deleteMin $O(\log n)$
The k smallest of n elements	A max-heap of size k, or buildHeap + k deleteMin	$O(n \log k)$ or $O(n + k \log n)$
General sorting, stable	Merge sort	$O(n \log n)$ guaranteed
In-place sorting, fastest on average	Quicksort	$O(n \log n)$ average
Integers in a small range	Counting / radix sort	$O(n + k)$ , $O(d(n+b))$
Unweighted shortest path	BFS	$O(V + E)$
Shortest path with weights ≥ 0	Dijkstra	$O(E \log V)$
Negative edges possible	Bellman-Ford	$O(VE)$
Task order, dependencies	Topological sort (Kahn / DFS)	$O(V + E)$
Connect all vertices at the lowest cost	Prim / Kruskal	$O(E \log V)$
Are two vertices in the same component	Union-find	Almost $O(1)$
Compress text	Huffman	$O(n \log n)$
The most non-overlapping activities	Greedy: earliest finish	$O(n \log n)$

Big-O summary

Sorting

Algorithm	Best	Average	Worst	Extra memory	Stable
Insertion	$n$	$n^2$	$n^2$	$1$	yes
Merge	$n \log n$	$n \log n$	$n \log n$	$n$	yes
Quick	$n \log n$	$n \log n$	$n^2$	$\log n$	no
Heap	$n \log n$	$n \log n$	$n \log n$	$1$	no
Counting	$n + k$	$n + k$	$n + k$	$n + k$	yes
Radix (LSD)	$d(n+b)$	$d(n+b)$	$d(n+b)$	$n + b$	yes

The worst case of every comparison-based sort is $\Omega(n \log n)$ : the decision tree has $n!$ leaves, and its height is at least $\log_2 n! \approx n \log n$ .

Trees, heap, hash

Structure	Search	Insert	Delete	Note
BST	avg. $\log n$ , worst $n$	same	same	Becomes a chain on sorted input
AVL	$\log n$	$\log n$	$\log n$	Height ≈ $1.44 \log n$
Red-black	$\log n$	$\log n$	$\log n$	Height ≤ $2\log(n+1)$ , fewer rotations
B-tree (order m)	$\log_m n$ disk accesses	same	same	All leaves at the same level
Splay	amortized $\log n$	same	same	A single operation can be $n$
Binary heap	$n$	$\log n$	deleteMin $\log n$	findMin $1$ , buildHeap $n$
Hash table	avg. $1$ , worst $n$	same	same	Rehash $O(n)$ , amortized $O(1)$

Graph and greedy

Algorithm	Time	Reminder
BFS / DFS	$O(V + E)$	$O(V^2)$ with a matrix
Topological sort	$O(V + E)$	Only a DAG
Dijkstra (heap)	$O(E \log V)$	No negative edges
Bellman-Ford	$O(VE)$	V−1 rounds, the V-th is the negative cycle test
Prim (heap)	$O(E \log V)$	A single tree grows
Kruskal	$O(E \log E)$	Sorting + union-find
Huffman	$O(n \log n)$	n−1 merges
Activity selection	$O(n \log n)$	Sort by finish

PITFALL · “search in a heap is O(log n)”. A heap guarantees order only for the root. Searching for an arbitrary key is $O(n)$ . If you need search, use a balanced BST or a hash.

Topic-by-topic checklist

Trees (weeks 2-4). Preorder: root-left-right. Inorder: left-root-right, sorted in a BST. Postorder: left-right-root. Level-order: with a queue. Height: an empty tree is −1, a single node is 0. Three cases in BST deletion: leaf (delete), one child (link the child), two children (copy the successor, delete the successor).

Balanced trees (5-6). In AVL, rotate at the first unbalanced node on the insertion path. If the new key is in the left of the left child of the unbalanced node it is LL (single right rotation), in the right of the right child it is RR (single left), on the inner sides it is LR/RL (double). Red-black: the root is black, a red node’s child cannot be red, the same number of blacks on every path. If the uncle is red, recolor; if black, rotate.

Heap and priority queue (7-8). Structure property: a complete tree. Order property: parent ≤ child (min-heap). Insertion starts at the end and moves up; deleteMin puts the last element at the root and sinks it with the smaller child. buildHeap is percolateDown from n/2 to 1, $O(n)$ . Java’s PriorityQueue is a min-heap by default.

Hashing (9). Load factor $\lambda = n / M$ . Separate chaining works well with $\lambda \approx 1$ . In open addressing keep $\lambda \le 0.5$ . Linear probing causes primary clustering, quadratic probing causes secondary clustering. In double hashing the second function must never return 0. When the table fills, rehash to a prime size about twice as large.

Graphs (10-11). BFS uses a queue, DFS a stack/recursion. Dijkstra picks the smallest unknown at each step. Directed cycle = an edge to a gray node.

Greedy and MST (12-13). The wrongness of a greedy is shown with a single counterexample. Kruskal rejects an edge that forms a cycle. In Prim’s table the value is the edge weight, not the path total.

Tips for the morning of the exam

1. min-heap or max-heap? root at 0 or 1?
2. Hash: M, h(k), type of probing?
3. Graph: directed? neighbor order? start?
4. Huffman/Kruskal: tie rule?
5. Write the intermediate states, box the answer

Common mistakes

Wrong idea	The truth
Search in a BST is always $O(\log n)$	Only if balanced; worst case $O(n)$
In AVL, rotate at the root	At the first unbalanced node on the insertion path
In deleteMin swap with the larger child	In a min-heap, with the SMALLER child
buildHeap is $O(n \log n)$	Floyd’s method is $O(n)$
In a hash, empty the deleted cell	In open addressing a “deleted” mark (lazy deletion)
Dijkstra works with negative edges	Use Bellman-Ford
d[v] + w in Prim’s table	Only w in Prim
Radix sort can use any sort in each pass	The passes must be STABLE
Counting sort is also bounded by $\Omega(n \log n)$	It makes no comparisons, so it is not subject to the bound

Test yourself

Exam-style questions. Solve them on paper first, then reveal the answer.

Question 1medium

Insert 50, 30, 70, 20, 40, 60, 80, 35 into an empty BST. Give the preorder traversal. Then delete 30 (two children: replace with the inorder successor) and give the new preorder.

Show answer

Before: 50 30 20 40 35 70 60 80; after: 50 35 20 40 70 60 80

        50
      /    \
    30      70
   /  \    /  \
  20  40  60  80
      /
     35

30 has two children. Its successor is the smallest of the right subtree: 35. 35 is written in place of 30, and 35 is deleted from its old place (a leaf). The new preorder: 50 35 20 40 70 60 80. The inorder is always sorted: 20 35 40 50 60 70 80.

Question 2hard

Insert 10, 20, 30, 40, 50, 25 into an empty AVL tree. Which rotations happen, and what is the final preorder traversal?

Show answer

RR at 10, RR at 30, RL at 20; preorder 30 20 10 25 40 50

When 30 is inserted, the BF of 10 is -2, right-right: a single left rotation at 10, the root is 20.
When 50 is inserted, the BF of 30 is -2, right-right: a left rotation at 30, 20(10, 40(30, 50)).
When 25 is inserted, the BF of 20 is h(10) - h(40) = 0 - 2 = -2. 25 went into the LEFT subtree of 40: right-left (RL). First a right rotation at 40, then a left rotation at 20:

        30
       /  \
     20    40
    /  \     \
   10  25    50

Question 3medium

Insert 15, 9, 12, 4, 7, 10, 2 one by one into an empty binary min-heap (array, root at index 1). Give the final array.

Show answer

[2, 7, 4, 15, 9, 12, 10]

At each insertion put it at the end and move up while it is smaller than its parent (percolate up):

15          [15]
9           [9, 15]
12          [9, 15, 12]
4           [4, 9, 12, 15]
7           [4, 7, 12, 15, 9]
10          [4, 7, 10, 15, 9, 12]
2           [2, 7, 4, 15, 9, 12, 10]

In the last step 2 enters at index 7, and swaps with its parent at 3 (10), then with its parent at 1 (4).

Question 4medium

On the heap [2, 7, 4, 15, 9, 12, 10], perform deleteMin twice. Give the array after each.

Show answer

[4, 7, 10, 15, 9, 12] then [7, 9, 10, 15, 12]

1st deleteMin: 2 is removed, the last element 10 comes to the root and sinks with the smaller child: it swaps with 4, then is compared with 12, 10 < 12 so it stops. 2nd deleteMin: 4 is removed, 12 comes to the root; the children are 7 and 10, 7 moves up; the new children of 12 are 15 and 9, 9 moves up. Result [7, 9, 10, 15, 12].

Question 5hard

Run buildHeap (min-heap, Floyd's method, root at index 1) on [9, 4, 7, 1, 8, 2, 6]. Give the array after each percolateDown call and the final heap.

Show answer

down(3): [9, 4, 2, 1, 8, 7, 6]; down(2): [9, 1, 2, 4, 8, 7, 6]; down(1): [1, 4, 2, 9, 8, 7, 6]

percolateDown going backward from n/2 = 3 to 1. Index 3 (7): the children are 2 and 6, 2 moves up. Index 2 (4): the children are 1 and 8, 1 moves up. Index 1 (9): the children are 1 and 2, 1 moves up; 9 is at index 2, the children are 4 and 8, 4 moves up; 9 is a leaf at index 4. The total time is $O(n)$ ; inserting one by one would be $O(n \log n)$ .

Question 6medium

Hash table of size M = 11, h(k) = k mod 11, linear probing. Insert 22, 13, 35, 4, 46, 15. At which index does each key end up?

Show answer

22→0, 13→2, 35→3, 4→4, 46→5, 15→6

The h values: 22→0, 13→2, 35→2, 4→4, 46→2, 15→4. 35: 2 is full, 3. 46: 2, 3, 4 are full, 5. 15: 4, 5 are full, 6. Linear probing formed a cluster (primary clustering) between 2 and 6.

Question 7hard

Same keys and table, but quadratic probing (h(k) + i², i = 0, 1, 2, ...). Where do 46 and 15 go?

Show answer

46→6, 15→5

46: 2 is full, 2+1 = 3 is full, 2+4 = 6 is empty. 15: 4 is full, 4+1 = 5 is empty. The others are the same as linear: 22→0, 13→2, 35→3, 4→4. Quadratic probing breaks up the cluster; when M is prime and λ ≤ 0.5, finding an empty place is guaranteed.

Question 8medium

LSD radix sort (base 10) on [213, 85, 402, 77, 160, 39, 518]. Give the array after the first pass (ones digit) and after the second pass (tens digit).

Show answer

Pass 1: [160, 402, 213, 85, 77, 518, 39]; pass 2: [402, 213, 518, 39, 160, 77, 85]

Each pass is a STABLE bucket distribution. Ones: 0 (160), 2 (402), 3 (213), 5 (85), 7 (77), 8 (518), 9 (39). Tens: 0 (402), 1 (213, 518), 3 (39), 6 (160), 7 (77), 8 (85). The third pass gives the sorted array: 39 77 85 160 213 402 518. Time $O(d(n + b))$ .

Question 9medium

DAG on 0..6 with edges 0→2, 1→2, 1→3, 2→4, 3→4, 4→5, 3→6, 6→5. Run Kahn's algorithm, always removing the smallest vertex with in-degree 0. Give the topological order.

Show answer

0 1 2 3 4 6 5

At the start the vertices with in-degree 0 are 0, 1. 0 is removed (the degree of 2 becomes 1). 1 is removed: 2 and 3 drop to zero. 2 is removed (4 → 1). 3 is removed: 4 and 6 become zero. 4 is removed (5 → 1). 6 is removed: 5 becomes zero. 5 is removed.

Question 10medium

Directed graph: S→A 7, S→B 2, B→A 3, A→C 1, B→C 8, C→D 2, B→D 9. Dijkstra from S: final distances to A, B, C, D?

Show answer

A=5, B=2, C=6, D=8

The order is S, B, A, C, D. B (2) lowers A from 7 to 5, and sets C to 10 and D to 11. A (5) lowers C to 6. C (6) lowers D to 8. The direct edges (S→A 7, B→D 9) are more expensive.

Question 11medium

Huffman coding with frequencies 3, 5, 6, 8, 20. What is the total number of encoded bits?

Show answer

The merges: 3+5 = 8, 6+8 = 14, 8+14 = 22, 20+22 = 42. Total bits = the sum of the internal node weights = 8+14+22+42 = 86. On a tie (which 8 merges with 6) the codes can change, the total bits do not.

Question 12easy

Choose the best structure for each task: (a) repeatedly get the most urgent job, (b) check membership of a word in a dictionary in average O(1), (c) keep keys sorted with guaranteed O(log n) insert and search, (d) print all keys in sorted order and find the k-th smallest quickly.

Show answer

(a) binary heap / priority queue, (b) hash table, (c) AVL or red-black tree, (d) balanced BST

(a) findMin $O(1)$ , deleteMin $O(\log n)$ . (b) A hash table is $O(1)$ on average but does not keep order. (c) A plain BST degrades to $O(n)$ on sorted input; a balanced tree is $O(\log n)$ in the worst case. (d) An inorder traversal gives sorted order; a heap and a hash do not give sorted output.

Verification: All trace answers (BST insert/delete traversals, AVL rotations, heap insert/deleteMin/buildHeap arrays, hash tables with linear and quadratic probing, LSD radix passes, Kahn topological order, Dijkstra distances, Huffman total bits) were run with verify/SEN2212/W14.java and taken from the output (java W14.java).

Review card

Sorting lower bound (comparison): Ω(n log n); counting/radix are not subject to this bound merge O(n log n) stable, extra array | quick avg n log n, worst n² | heap n log n in place BST avg O(log n), worst O(n) | AVL, RB worst O(log n) BST delete with 2 children: inorder successor (the smallest of the right) AVL: BF = h(L) - h(R), |BF| > 1 → LL/RR single, LR/RL double rotation heap 1-indexed: children 2i, 2i+1, parent i/2; insert/deleteMin O(log n), buildHeap O(n) hash avg O(1); linear → primary clustering; quadratic → M prime, λ ≤ 0.5 graph: matrix O(V²) space, list O(V+E); BFS/DFS/topo O(V+E) Dijkstra O(E log V), weights ≥ 0 | Bellman-Ford O(VE), negative edges Prim O(E log V), Kruskal O(E log E), V-1 edges in an MST Huffman: the two smallest merge, total bits = sum of the internal nodes Greedy correct: activity (earliest finish), fractional knapsack; WRONG: 0/1 knapsack, odd coins