32 Midterm Review (CSS 343)

33 Midterm Review (CSS 343)

Week 5, Session 2. CSS 343.

The 343 midterm covers chapters 21–29 (with assumed 342 background). Structure same as the 342 midterm: rapid review, common wrong answers, top-5 study targets.

33.1 What this midterm covers

Topic	Chapter	Question style
Tree operations	22, 23	Trace insert/delete, write recursive method
Template BST	24	Write or fix code
Huffman coding	24	Build tree, encode, decode
Heaps	25	Trace insert/extract, build heap
Graphs	26	BFS/DFS trace, connected components
Shortest paths	27	Dijkstra distance table
MST	27	Prim or Kruskal trace
Topological sort	27	Kahn’s trace, identify cycle
Hash tables	28	Collision resolution, custom hash
Balanced trees	29	AVL rotation identification

33.2 BST delete — trace

Given the tree:

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

Delete 30. Two children → in-order successor (40). Replace 30’s value with 40. Delete the old 40 (leaf, trivial).

Result:

        50
       /  \
     40    70
    /      / \
   20     60  80

In-order: 20, 40, 50, 60, 70, 80. Sorted. ✓

33.3 Heaps — trace

Array [10, 5, 8, 3, 12, 7]. Is it a max-heap? Index 0 (10) has children at 1 (5), 2 (8). Then 1 has children at 3 (3), 4 (12). Index 4 (12) > parent (5). Violation. Not a heap.

Build max-heap via heapify: starting from the last non-leaf (index 2: value 8). Sift-down (already at top of its subtree of size 1). Index 1 (5): children 3 (3), 4 (12). 12 > 5, swap → [10, 12, 8, 3, 5, 7]. Now index 4 (5) has no children — done. Index 0 (10): children 1 (12), 2 (8). 12 > 10, swap → [12, 10, 8, 3, 5, 7]. Now index 1 (10): children 3 (3), 4 (5). All smaller — done.

Final max-heap: [12, 10, 8, 3, 5, 7].

33.4 BFS / DFS — trace

Graph (undirected, adjacency list):

0: [1, 2]
1: [0, 3]
2: [0, 3]
3: [1, 2, 4]
4: [3]

BFS from 0: queue {0} → visit 0, enqueue [1, 2] → visit 1, enqueue [3] → visit 2, enqueue [3] dedup → visit 3, enqueue [4] → visit 4. Order: 0, 1, 2, 3, 4.

DFS from 0 (recursive, neighbors in given order): 0 → 1 → 3 → 2 (already visited from 3?) → 4. Actually depends on order. Recursion enters first neighbor first. From 0: enter 1. From 1: enter 0 (visited) then 3. From 3: enter 1 (visited) then 2 then 4. From 2: enter 0 (visited) then 3 (visited). Back. From 3 continue: 4. Order: 0, 1, 3, 2, 4.

33.5 Dijkstra — trace

Graph: 0 → 1 (cost 4), 0 → 2 (cost 1), 2 → 1 (cost 2), 1 → 3 (cost 1), 2 → 3 (cost 5).

Source 0. Dist table starts: [0, ∞, ∞, ∞].

Settle 0 (dist 0). Relax: 1 → 4, 2 → 1.
Settle 2 (dist 1). Relax: 1 → min(4, 1+2)=3. 3 → 1+5=6.
Settle 1 (dist 3). Relax: 3 → min(6, 3+1)=4.
Settle 3 (dist 4).

Final: [0, 3, 1, 4].

33.6 AVL rotation identification

Insert sequence {30, 20, 10} into an empty AVL tree:

After 30: tree is {30}. Balance 0. After 20: 30/20. Balance at 30: +1. OK. After 10: 30/20/10 — left-spine. Balance at 30: +2. LL case. Rotate right at 30.

Result:

    20
   /  \
  10   30

33.7 Hash table — separate chaining trace

Insert {10, 22, 31, 4, 15, 28, 17, 88} into table of size 7 with key % 7:

10 % 7 = 3
22 % 7 = 1
31 % 7 = 3
4 % 7 = 4
15 % 7 = 1
28 % 7 = 0
17 % 7 = 3
88 % 7 = 4

Table:

0: [28]
1: [22, 15]
2: []
3: [10, 31, 17]
4: [4, 88]
5: []
6: []

Load factor = 8/7 ≈ 1.14. Should have triggered rehash if threshold is 0.75.

33.8 Common wrong answers (from past 343 midterms)

Identifying an LR case as LL because the imbalanced node is reached via a left child first. The case is about the path to the inserted node, not just the direction at the imbalanced node.
Running Dijkstra on a graph with negative edges and getting a wrong answer; not noticing the constraint was violated.
Forgetting that BFS shortest-path works only on unweighted graphs (or equivalently, all-equal weights).
Drawing a level-order traversal in DFS order.
Saying std::unordered_map is “always faster than std::map.” It is faster on average, but map has guaranteed O(log n) and supports lower_bound.

33.9 Top 5 things to review tonight

BST delete two-child case: replace value with in-order successor, recursively delete successor.
Heap parent/child arithmetic: parent = (i-1)/2, children = 2i+1 and 2i+2.
Dijkstra: settle minimum, relax outgoing edges, repeat. Non-negative weights required.
AVL rotation case identification: LL/LR/RL/RR by the path from imbalanced node to the offender.
Hash table load factor: > threshold ⇒ rehash, doubling capacity. Amortized O(1) insert.

33.10 Try it

Pick the chapter (22–29) you feel weakest on. Re-solve two of its challenges from scratch under exam conditions (no notes, 15 minutes each). That is your read on whether you are ready.

33.11 Where this fits

After the midterm we shift gears from data structures to algorithm design. Same problems, different framings.

You are here	Coming up
Midterm review (343 part 1)	Chapter 31: divide and conquer