# ADS Endterm Study Plan (Recency-Weighted)

## Exam Overview

CSE1305 Algorithms & Data Structures — Endterm format:

| Exam part       | Number of questions | Points | Grade |
|-----------------|---------------------|--------|-------|
| Multiple-choice | 15 questions (equal weights) | 15 | 50% |
| Open questions  | 3 questions (multiple parts) | 15 | 50% |

Based on 16 past exams (2018-2025): 5 Midterms, 6 Endterms, 5 Resits. The endterm heavily tests the same patterns as midterms but with more focus on data structure internals, tree operations, and recurrence analysis.

---

## Tier 1: Very High frequency (10+ appearances) — study these first

| # | Topic | 2025 Endterm Q | Pattern | Lectures | Done |
|---|-------|---------------|---------|----------|------|
| 1 | Asymptotic Notation (Big-O / Omega / Theta) | Q1, Q3 | P1 | L01-L04 | [ ] |
| 2 | Sorting Algorithm Properties & Comparisons | Q7, Q8, Q14 | P2 | L05-L08 | [ ] |
| 3 | Closed Form Derivation by Repeated Unfolding | O3 | P3 | L09-L12 | [ ] |
| 4 | Recurrence Relation Setup (Base & Recursive) | O1, O2 | P4 | L09-L12 | [ ] |
| 5 | Heap Operations & Heap Sort | Q5 | P5 | L08, L13 | [ ] |
| 6 | Array vs Linked List Complexity Comparison | Q6 | P6 | L14-L16 | [ ] |
| 7 | Dynamic Array Resizing & Amortized Analysis | Q4 | P7 | L14-L16 | [ ] |
| 8 | Tree Traversals (Preorder, Inorder, Postorder, BFS) | Q9 | P8 | L17-L19 | [ ] |
| 9 | Hash Table Operations (Linear Probing / Separate Chaining) | Q10 | P9 | L20-L22 | [ ] |
| 10 | Space Complexity Analysis (Iterative & Recursive) | Q2 | P10 | L09-L12 | [ ] |
| 11 | Recursion Analysis (Type, Tail Calls, Optimization) | — | P11 | L09-L12 | [ ] |

---

## Tier 2: High frequency (5-9 appearances)

| # | Topic | 2025 Endterm Q | Pattern | Lectures | Done |
|---|-------|---------------|---------|----------|------|
| 12 | (2,4) Tree Operations (Insert / Delete / Overflow / Underflow) | O2 | P12 | L23-L25 | [ ] |
| 13 | Red-Black Tree Operations & (2,4) Tree Correspondence | O3 | P13 | L23-L25 | [ ] |
| 14 | Dijkstra's Algorithm Execution | Q14 | P14 | L26-L28 | [ ] |
| 15 | Linked List Operations (SLL / DLL / CLL) | — | P15 | L14-L16 | [ ] |
| 16 | AVL Tree Operations (Insert / Delete / Rotations) | Q11 | P16 | L23-L25 | [ ] |
| 17 | Minimum Spanning Trees (Kruskal's / Prim's) | Q15 | P17 | L26-L28 | [ ] |
| 18 | Data Structure Choice for Application | O3 | P18 | L05-L08 | [ ] |
| 19 | Priority Queue Implementations Comparison | — | P19 | L08, L13 | [ ] |
| 20 | Non-Comparison Sorting (Bucket / Radix / Counting Sort) | — | P20 | L05-L08 | [ ] |
| 21 | Formal Big-O / Big-Omega Proof | — | P21 | L01-L04 | [ ] |
| 22 | Identify Data Structure from Code | — | P22 | L14-L16 | [ ] |
| 23 | Stack / Queue Behavior Tracing | Q3 | P23 | L14-L16 | [ ] |
| 24 | Topological Ordering | Q9 (2024) | P24 | L26-L28 | [ ] |
| 25 | Graph Representation Comparison | — | P25 | L26-L28 | [ ] |
| 26 | Iterator Behavior (Snapshot vs Lazy) | — | P26 | L14-L16 | [ ] |
| 27 | Explain What Algorithm Does | — | P27 | L09-L12 | [ ] |
| 28 | Merge Sort Execution & Recursion Tree | — | P28 | L05-L08 | [ ] |
| 29 | Quicksort / Quickselect | — | P29 | L05-L08 | [ ] |
| 30 | Positional List Operations (DLL with Sentinels) | Q6 | P30 | L14-L16 | [ ] |

---

## Tier 3: Low frequency (1-4 appearances) — review if time permits

| # | Topic | Lectures | Pattern | Done |
|---|-------|----------|---------|------|
| 31 | Time Complexity Polynomial for Iterative Method | L09-L12 | P31 | [ ] |
| 32 | BST Properties & Operations | — | P32 | [ ] |
| 33 | Array-Based Tree Representation | L17-L19 | P33 | [ ] |
| 34 | Deep Copy / Shallow Copy / Clone Behavior | L14-L16 | P34 | [ ] |

---

## Endterm 2025 Questions (15 April 2025)

### Multiple-Choice (Questions 1-15)

| Q# | Topic | Pattern | Lectures | Done |
|----|-------|---------|----------|------|
| 1 | Asymptotic notation — false statement about Big-O of f(n)=2^n+5n^4+3n^2, g(n)=n^2+1000, h(n)=7n+20n^{3/2} | P1 | L01-L04 | [ ] |
| 2 | Space complexity recurrence — binary recursion with ArrayList allocations at each call | P10 | L09-L12 | [ ] |
| 3 | Stack behavior — even/odd split with iterator (sum of even elements, remove odd) | P23 | L14-L16 | [ ] |
| 4 | Dynamic array — worst-case time complexity of insert at end | P7 | L14-L16 | [ ] |
| 5 | Heap — minimum swaps to convert array to max-heap | P5 | L08, L13 | [ ] |
| 6 | Positional list — count next/prev references used by removeFirst in DLL with sentinels | P30 | L14-L16 | [ ] |
| 7 | Sorting — which algorithm is unstable | P2 | L05-L08 | [ ] |
| 8 | Sorting — minimum comparisons on nearly-sorted array | P2 | L05-L08 | [ ] |
| 9 | Priority Queue — merge k=|log n| sorted lists using heap | P19 | L08, L13 | [ ] |
| 10 | Hash table — worst-case probes for get in linear probing with DEFUNCT markers | P9 | L20-L22 | [ ] |
| 11 | AVL tree — tri-node restructurings when deleting root | P16 | L23-L25 | [ ] |
| 12 | (2,4) tree & RB tree correspondence — operations caused by (2,4) delete in RB tree | P13 | L23-L25 | [ ] |
| 13 | BFS vs DFS — shortest paths property | P25 | L26-L28 | [ ] |
| 14 | Dijkstra's algorithm — count distinct non-infinite labels for vertex F | P14 | L26-L28 | [ ] |
| 15 | MST — count distinct MSTs for graph with distinct edge weights | P17 | L26-L28 | [ ] |

### Open Questions (Q16-Q18)

| Q# | Pts | Topic | Pattern | Lectures | Done |
|----|-----|-------|---------|----------|------|
| O1 | 5 | Recurrence setup — runtime complexity of methodZ (nested loops, sort, recursion) | P4 | L09-L12 | [ ] |
| O2 | 5 | Closed form derivation — T(n) = c1 + T(n-1) + T(n/2) by unfolding | P3 | L09-L12 | [ ] |
| O3 | 4 | Data structure choice — hashmap vs AVL tree for k-th lowest-paid employee removal | P18 | L05-L08 | [ ] |

---

## Endterm 2024 Questions (29 January 2024)

### Multiple-Choice (Questions 1-15)

| Q# | Topic | Pattern | Lectures | Done |
|----|-------|---------|----------|------|
| 1 | Asymptotic notation — false statement about Big-O/Omega | P1 | L01-L04 | [ ] |
| 2 | Dynamic array — worst-case insert at end | P7 | L14-L16 | [ ] |
| 3 | Circularly-linked list — reference for O(1) enqueue/dequeue | P15 | L14-L16 | [ ] |
| 4 | Stack with dynamic array — push/pop worst-case complexity | P7 | L14-L16 | [ ] |
| 5 | Heap — minimum swaps to build max-heap | P5 | L08, L13 | [ ] |
| 6 | Sorting worst-case on sorted input | P2, P29 | L05-L08 | [ ] |
| 7 | Selection sort — maximum number of swaps | P2 | L05-L08 | [ ] |
| 8 | Non-comparison sorting — tightest bound for sorting with bounded range | P20 | L05-L08 | [ ] |
| 9 | Topological ordering — invalid ordering check | P24 | L26-L28 | [ ] |
| 10 | MST — false statement about distinct edge weights | P17 | L26-L28 | [ ] |
| 11 | Hash table — max elements in single bucket (separate chaining) | P9 | L20-L22 | [ ] |
| 12 | BST — valid inorder traversal | P32 | L17-L19 | [ ] |
| 13 | AVL tree — max height with 7 nodes | P16 | L23-L25 | [ ] |
| 14 | (2,4) tree — count 3-nodes after deleting root's child | P12 | L23-L25 | [ ] |
| 15 | Red-black tree — count red nodes after deleting leaf child | P13 | L23-L25 | [ ] |

### Open Questions (Q16-Q18)

| Q# | Pts | Topic | Pattern | Lectures | Done |
|----|-----|-------|---------|----------|------|
| O1 | 6 | Recurrence setup — runtime and space complexity of methodZ (recursive with LinkedList) | P4 | L09-L12 | [ ] |
| O2 | 5 | Closed form derivation — T(1)=c0, T(n)=c1+T(n-1)+T(n/2) by unfolding | P3 | L09-L12 | [ ] |
| O3 | 4 | Data structure choice — hashmap vs AVL for k-th element + removal | P18 | L05-L08 | [ ] |

---

## Resit 2025 Questions (19 June 2025)

### Multiple-Choice (Questions 1-15)

| Q# | Topic | Pattern | Lectures | Done |
|----|-------|---------|----------|------|
| 1 | Asymptotic notation — false statement about Big-O of p(n), q(n)=2^n+n^4, r(n) | P1 | L01-L04 | [ ] |
| 2 | Space complexity — binary recursion space recurrence S(n)=c1+S(n/2) | P10 | L09-L12 | [ ] |
| 3 | SLL vs DLL delete given node reference | P6 | L14-L16 | [ ] |
| 4 | Heap PQ — EXTRACT-MIN and INSERT worst-case time | P5, P19 | L08, L13 | [ ] |
| 5 | Dynamic array vs SLL with tail — ADDLAST worst-case | P6, P7 | L14-L16 | [ ] |
| 6 | ADT implementation — PQ cannot be built with SimpleList in O(1) | P22 | L14-L16 | [ ] |
| 7 | Sorting — O(n log n) stable in-place? No, answer: Merge Sort | P2 | L05-L08 | [ ] |
| 8 | Insertion sort on nearly-sorted array — minimum comparisons | P2 | L05-L08 | [ ] |
| 9 | Merge log n lists with heap — O(n log log n) | P19 | L08, L13 | [ ] |
| 10 | Hash table — worst-case probes in linear probing | P9 | L20-L22 | [ ] |
| 11 | AVL delete — count tri-node restructurings | P16 | L23-L25 | [ ] |
| 12 | (2,4) delete — corresponding RB tree operations | P13 | L23-L25 | [ ] |
| 13 | BFS vs DFS — BFS finds shortest paths | P25 | L26-L28 | [ ] |
| 14 | Dijkstra — count distinct non-infinite labels | P14 | L26-L28 | [ ] |
| 15 | MST — count distinct MSTs | P17 | L26-L28 | [ ] |

### Open Questions

| Q# | Pts | Topic | Pattern | Lectures | Done |
|----|-----|-------|---------|----------|------|
| O1 | 5 | Recurrence setup — runtime complexity of methodZ | P4 | L09-L12 | [ ] |
| O2 | 5 | Closed form derivation — T(n)=c1+c2*n+2*T((n+1)/2) | P3 | L09-L12 | [ ] |
| O3 | 4 | Data structure choice — hashmap vs AVL | P18 | L05-L08 | [ ] |

---

## How to Solve Each Pattern

### P1 -- Asymptotic Notation Concepts (Big-O / Omega / Theta) (Very High: 15 appearances)

**How to recognize:** True/false statements about Big-O, Big-Omega, and Big-Theta relationships. Compare asymptotic growth rates, determine tightest bounds for piecewise or composite functions.

**Steps:**
1. **Definitions:** O(g(n)) means f(n) <= c*g(n) for all n >= n0; Omega is the lower bound (>=); Theta means both O and Omega
2. **Growth rate hierarchy:** 1 < log n < sqrt(n) < n < n log n < n^2 < n^3 < 2^n < n!
3. **Dominant term:** For sums, the fastest-growing term determines the Big-O (e.g., n^2 + n log n is O(n^2))
4. **Big-O is NOT about best/worst case:** Big-O, Omega, Theta are bounds on a function, not case indicators. Any case can use any notation
5. **Piecewise functions:** Big-O concerns behavior as n -> infinity, so only the branch for large n matters
6. **Constant factors and lower-order terms** can be ignored: 5n^2 + 3n is Theta(n^2)
7. **Log base does not matter:** log_2 n and log_10 n differ by a constant factor
8. **Time vs space relationship:** If time is Theta(f(n)) and space is Theta(g(n)), then g(n) is O(f(n)) because you need at least as much time as space used

**2025 exam tip:** Watch for 2^n vs n^4 traps — exponential ALWAYS dominates polynomial for large n. Statement C "g(n) >= n^3" is FALSE because g(n)=n^2+1000 is O(n^2).

---

### P2 -- Sorting Algorithm Properties & Comparisons (Very High: 15 appearances)

**How to recognize:** True/false statements about sorting algorithms: stability, in-place property, time/space complexity, comparison-based nature. Trace execution on given arrays.

**Steps:**
1. **Know the complexity table:**
   - Insertion sort: O(n^2) worst, O(n) best, stable, in-place, O(1) space
   - Selection sort: O(n^2) always, NOT stable (with swaps), in-place, O(n) swaps worst-case
   - Merge sort: O(n log n) always, stable, NOT in-place, O(n) space
   - Heap sort: O(n log n) always, NOT stable, in-place, O(1) space
   - Quicksort: O(n^2) worst / O(n log n) expected, NOT stable, in-place, O(log n) space
2. **Stability:** A sort is stable if equal elements maintain their relative order. Merge sort and insertion sort are stable; selection sort (with swaps) and heap sort are NOT
3. **In-place:** Uses O(1) extra space. Merge sort cannot be implemented in-place with its optimal O(n log n) time
4. **PQ connection:** Selection sort = unsorted list PQ; Insertion sort = sorted list PQ; Heap sort = heap PQ
5. **Comparison-based lower bound:** Any comparison-based sort requires Omega(n log n) comparisons in worst case
6. **For tracing:** Step through the algorithm iteration by iteration, tracking swaps and comparisons

**2025 exam tip:** Nearly-sorted array = Insertion Sort does fewest comparisons (8 vs 24-28 for others). Already-sorted array: Insertion sort = O(n) best case.

---

### P3 -- Closed Form Derivation by Repeated Unfolding (Very High: 15 appearances)

**How to recognize:** "Derive the closed form of the following recurrence equation by using the unfolding procedure"

**Steps:**
1. **Step 1 -- Unfold 2-3 times:** Substitute T(n) into itself: T(n) = c1 + 2*T(n/2) = c1 + 2(c1 + 2*T(n/4)) = 3c1 + 4*T(n/4)
2. **Step 2 -- Identify the pattern:** After k steps, express coefficients in terms of k (e.g., (2^k - 1)c1 + 2^k*T(n/2^k))
3. **Step 3 -- Substitute base case:** Set n/2^k = base case size to solve for k (e.g., k = log_2 n), then replace T(base) with c0
4. **Step 4 -- Simplify:** Use identities like 2^(log n) = n, geometric series sum(2^i) = 2^k - 1, arithmetic series sum(i) = k(k+1)/2
5. **Common results:** T(n) = a*T(n/2) + c -> O(n) if a=2, O(log n) if a=1; T(n) = T(n-1) + cn -> O(n^2); T(n) = 2T(n/2) + cn -> O(n log n)
6. **Alternative:** Guess the closed form and prove by induction (base case + inductive step)

**2025 exam tip:** T(n) = c1 + T(n-1) + T(n/2). Unfold T(n-1) first (it's the simpler recurrence), then T(n/2). After k steps: (2^k-1)c1 + (2^k-1)c2 + 2^k*T(n/2^k). Let k = log(n)-1.

---

### P4 -- Recurrence Relation Setup (Base & Recursive Case) (Very High: 15 appearances)

**How to recognize:** "State the base and recurrence equations for the worst-case runtime/space complexity" with Java code provided.

**Steps:**
1. **Identify the input size n:** Usually the length of the array/list, or a parameter like (a.length - i)
2. **Base case:** Find the termination condition (e.g., n == 1 or list.isEmpty()) and assign T(base) = c0 for all constant-time operations
3. **Recursive case:** For each recursive call, determine (1) how many calls, (2) the size of input to each call
4. **Non-recursive work:** Count loops (c*n), constant operations (c1), and data structure operations (e.g., sort = O(n log n))
5. **Justify each term:** Map c0 to specific lines (method call, conditional, return), c1*n to loop iterations, T(n/2) to recursive call
6. **Common patterns:** Linear recursion: T(n) = c + T(n-1); Binary split: T(n) = c + 2T(n/2); With loop: T(n) = c*n + T(n-1)

**2025 exam tip:** methodZ has two nested for loops (O(n^2)), Collections.sort (O(n^2 log n)), list.get (O(n) for LinkedList), and one recursive call on list.removeLast() -> T(n-1). Total: T(n) = c1 + c2*n + c3*n^2 + c4*n^2*log(n^2) + c5*n^3 + c6*n^4 + T(n-1).

---

### P5 -- Heap Operations & Heap Sort (Very High: 15 appearances)

**How to recognize:** "Minimum number of swap operations to convert array to max-heap", "Trace heapify", "removeMin with down-heap bubbling"

**Steps:**
1. **Array indexing:** For node at index i: left child = 2i+1, right child = 2i+2, parent = floor((i-1)/2)
2. **Insert:** Add at last position (index n), then **up-heap bubble**: swap with parent while smaller (min-heap) or larger (max-heap)
3. **RemoveMin:** Replace root with last element, decrease size, then **down-heap bubble**: swap with smallest child while violating heap order
4. **Heapify (bottom-up):** Start from last internal node (index floor(n/2)-1), perform down-heap on each node moving toward root. Time: O(n)
5. **In-place heap sort (decreasing order):** Build min-heap with heapify, then repeatedly removeMin and place at end of array
6. **In-place heap sort (increasing order):** Build max-heap with heapify, then repeatedly swap root with last unsorted element and down-heap
7. **Min swaps for add:** 0 (element larger than parent). **Min swaps for remove:** 1 (must swap with one child at minimum)
8. **Heapify time:** O(n), NOT O(n log n). Individual insert/remove: O(log n)

**2025 exam tip:** Heapify [90, 20, 52, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100] to max-heap: swap 100 with 15 (index 12->5), 100 with 52 (index 5->2), 100 with 90 (index 2->0). Total: 3 swaps.

---

### P6 -- Array vs Linked List Complexity Comparison (Very High: 15 appearances)

**How to recognize:** "Worst-case time complexity of delete when list is SLL vs DLL", "Array vs linked list for specific operations"

**Steps:**
1. **Array strengths:** O(1) random access by index, O(1) add/remove at end (amortized with dynamic array)
2. **Array weaknesses:** O(n) insert/remove at beginning or middle (shifting required)
3. **SLL strengths:** O(1) add/remove at head. O(1) add at tail (if tail reference maintained)
4. **SLL weaknesses:** O(n) access by index, O(n) remove at tail (must traverse to second-to-last), no backward traversal
5. **DLL strengths:** O(1) add/remove at both head and tail, O(1) remove given a reference to the node
6. **Reverse sequence:** Array O(n) with two-pointer swap; SLL O(n) with removeFirst+addFirst on second list; SLL with node access O(n) by flipping pointers
7. **Remove middle element repeatedly:** Array O(n^2) total (n shifts each time); SLL O(n^2) total (n traversal to find middle each time)

---

### P7 -- Dynamic Array Resizing & Amortized Analysis (Very High: 15 appearances)

**How to recognize:** "Amortized worst-case time complexity of adding one element", "Worst-case time of insert in dynamic array"

**Steps:**
1. **Geometric growth (multiply by factor >= 2):** Amortized O(1) per operation. Total cost of n operations is O(n)
2. **Arithmetic growth (add constant k):** Amortized O(n) per operation. Total cost of n operations is O(n^2)
3. **Why geometric works:** Copy cost for n elements is at most n + n/2 + n/4 + ... = O(n) total (geometric series)
4. **Why arithmetic fails:** Copy cost is n + (n-k) + (n-2k) + ... which sums to O(n^2/k) = O(n^2)
5. **Shrinking strategy:** To maintain O(1) amortized for both add and remove, shrink to C/2 when n < C/4 (NOT when n < C/2, which causes thrashing)
6. **Amortized meaning:** Average over a sequence of n operations is O(1), not each individual operation. Some single operations may take O(n)

**2025 exam tip:** Single insert at end: worst-case O(n) (when array is full and must resize). Amortized O(1).

---

### P8 -- Tree Traversals (Preorder, Inorder, Postorder, BFS) (Very High: 15 appearances)

**How to recognize:** "Which traversal outputs this sequence", "Last node visited in which traversal"

**Steps:**
1. **Preorder:** Visit node FIRST, then left subtree, then right subtree (root, L, R)
2. **Inorder:** Visit left subtree, then node, then right subtree (L, root, R). For BST, gives sorted order
3. **Postorder:** Visit left subtree, then right subtree, then node LAST (L, R, root). Root is always last
4. **BFS (level-order):** Visit level by level, left to right. Uses a queue
5. **Last visited node:** Preorder = rightmost leaf on deepest right path; Inorder = rightmost node; Postorder = root; BFS = last node at deepest level (rightmost)
6. **Complete binary tree:** Postorder visits all leaves before any internal node only for trees of height 1
7. **Line tree:** Preorder and BFS give the same order (only one path to traverse)
8. **Reconstruct from postorder:** Last element is root; for complete tree, use the structure constraint to assign values level by level

---

### P9 -- Hash Table Operations (Linear Probing / Separate Chaining) (Very High: 15 appearances)

**How to recognize:** "Maximum number of cells probed", "Bucket contents after insertions", "Maximum elements in single bucket"

**Steps:**
1. **Hash function:** h(k) = k mod N gives the home bucket. If occupied, probe linearly: (h(k)+1) mod N, (h(k)+2) mod N, ...
2. **Insert (linear probing):** Find first empty or DEFUNCT cell starting from h(k)
3. **Delete (linear probing):** Mark cell as DEFUNCT (do NOT leave empty, or search will break)
4. **Search:** Start at h(k), probe until finding the key, an empty cell (not found), or wrapping around
5. **Separate chaining:** Each bucket stores a list. Insert at end of list. Expected time O(1+lambda) where lambda = n/N
6. **Load factor lambda:** lambda < 1 required for linear probing. For O(1) expected time, keep lambda < 0.5-0.75. Resize when threshold exceeded
7. **hashCode/equals contract:** If a.equals(b), then a.hashCode() == b.hashCode(). Converse is NOT required

**2025 exam tip:** Hash table size 9, separate chaining. Keys 5, 28, 19, 15, 20, 33, 12, 17, 10. h(28)=1, h(19)=1, h(10)=1. Max bucket size = 3 (bucket 1 has 3 elements).

---

### P10 -- Space Complexity Analysis (Iterative & Recursive) (Very High: 15 appearances)

**How to recognize:** "Recurrence equation for space complexity", "Worst-case space complexity of method"

**Steps:**
1. **Iterative methods:** Usually O(1) extra space (variables only), unless new arrays/structures are allocated
2. **Linear recursion (1 call, depth d):** O(d) stack frames. If each frame allocates O(k) space, total is O(d * k)
3. **Binary recursion (2 calls, depth d):** Space is O(d), NOT O(2^d), because only one branch is active at a time on the call stack
4. **Arrays passed by reference:** Passing an array to a method does NOT copy it -- no extra space for the array
5. **Tail recursion optimization:** Reuses the current stack frame, reducing space from O(n) to O(1). The recursive call must be the LAST operation
6. **New array allocation in each recursive call:** If each call allocates an array of size n, n-1, n-2, ..., total space is O(n^2)
7. **Local variables:** Deallocated when method returns, so only count the maximum depth of active frames

**2025 exam tip:** methodX creates two ArrayLists per call but makes two sequential recursive calls. Space = c1 + S(n/2) because stack depth = log(n) and each frame is O(1) extra (arrays are created but only one branch's space is active at a time).

---

### P11 -- Recursion Analysis (Type, Tail Calls, Optimization) (Very High: 15 appearances)

**How to recognize:** "Identify linear vs binary recursion", "Is the recursive call a tail call?"

**Steps:**
1. **Linear recursion:** At most ONE recursive call per execution path (may have multiple branches, but each branch makes at most one call)
2. **Binary recursion:** TWO recursive calls in a single execution path (e.g., return f(n-1) + f(n-2))
3. **Tail call:** The recursive call is the LAST operation before returning. "return f(n-1)" is tail; "return 1 + f(n-1)" is NOT tail (addition happens after)
4. **Tail recursion optimization:** Compiler reuses the stack frame, reducing space from O(n) to O(1). Java does NOT perform this optimization automatically
5. **Making a method tail-recursive:** Move any work after the recursive call to before it (e.g., swap lines so recursive call is last)
6. **Recursive vs iterative:** Same time complexity, but iterative uses O(1) space vs O(n) for non-tail recursion

---

### P12 -- (2,4) Tree Operations (Insert / Delete / Overflow / Underflow) (High: 12 appearances)

**How to recognize:** "Count 3-nodes after deleting key X", "How many overflow splits on insertions"

**Steps:**
1. **Node types:** 2-node (1 key, 2 children), 3-node (2 keys, 3 children), 4-node (3 keys, 4 children)
2. **Insert:** Find the correct leaf, add key. If node becomes a 5-node (overflow): split into two 2-nodes and push middle key up to parent. This may cascade
3. **Delete:** If key is in internal node, replace with inorder successor (from leaf), then delete from leaf. If node becomes a 1-node (underflow): try transfer from sibling, else fusion with sibling (may cascade)
4. **Transfer (rotation):** Borrow a key from a sibling through the parent. Sibling must have >= 2 keys
5. **Fusion:** Merge underflow node with a sibling and pull down a key from parent. Parent may underflow too
6. **All leaves at same depth:** (2,4) trees are always perfectly balanced

**2025 exam tip:** (2,4) tree with root {20,25}, left child {14} with children {1,2} and {15,18}. Delete 21: it's in {22} (a 2-node), so underflow. Fusion with sibling {23}. Root becomes {20,25} with one fewer child. Count remaining 3-nodes after restructuring.

---

### P13 -- Red-Black Tree Operations & (2,4) Tree Correspondence (High: 12 appearances)

**How to recognize:** "Count red nodes after deleting X", "How many restructurings in RB tree corresponding to (2,4) operation"

**Steps:**
1. **Properties:** Root is black. Red nodes cannot have red children. Every path from root to null has the same number of black nodes
2. **(2,4) <-> Red-Black correspondence:** 2-node = single black node; 3-node = black node with one red child; 4-node = black node with two red children
3. **Insert:** New node is red. If parent is red (double-red): check uncle. Red uncle -> recolor (push black down). Black uncle -> restructure (rotate)
4. **Delete:** More complex. May require recoloring and/or restructuring to fix double-black
5. **Height:** A red-black tree with n nodes has height <= 2*log_2(n+1). Minimum leaf depth in RB tree of height h is ceil(h/2)
6. **Multiple RB trees from one (2,4) tree:** A 3-node can have the red child on left OR right, creating multiple valid RB trees

**2025 exam tip:** RB delete of 2 (red node) in tree: after removing 2 and replacing with inorder predecessor 4, may create double-black. Fix with trinode restructuring: 4 becomes red, 1 and 5 become black. Count red nodes after fix.

---

### P14 -- Dijkstra's Algorithm Execution (High: 12 appearances)

**How to recognize:** "How many distinct non-infinite labels for vertex V", "Count distance updates"

**Steps:**
1. **Algorithm:** Initialize all distances to infinity except source (0). Use a min-priority queue. Extract minimum, relax all outgoing edges
2. **Relaxation:** For edge (u,v) with weight w: if d[u] + w < d[v], update d[v] = d[u] + w
3. **Count distance updates:** A vertex's distance label changes each time a shorter path is found. Track each relaxation step
4. **Complexity:** O((n + m) log n) with binary heap PQ; O(n^2) with unsorted list PQ; O(n^2 + m) with sorted list PQ
5. **Requirement:** All edge weights must be non-negative. Does NOT work with negative edges
6. **Greedy property:** Once a vertex is extracted from PQ, its distance is final (correct)
7. **Worst-case PQ operations:** O(n) insertions, O(n) extractions, O(m) decrease-key operations

**2025 exam tip:** Dijkstra from A: dist(F) = infinity -> 51 (via A->D->F) -> 11 (via A->D->E->F). Total distinct non-infinite labels for F: 2.

---

### P15 -- Linked List Operations (SLL / DLL / CLL) (High: 11 appearances)

**How to recognize:** "CLL rotate", "removeFirst in CLL", "Which data structure for which operations"

**Steps:**
1. **addFirst (SLL):** new Node(e, head); head = newNode; O(1)
2. **removeLast (DLL):** Access tail.getPrevious(), set its next to null, update tail; O(1). For SLL: O(n) since must traverse to second-to-last
3. **CLL rotate:** tail = tail.getNext(). This makes the old head become the new tail's next. The implicit head shifts by one position
4. **CLL removeFirst:** head = tail.getNext().getNext(); tail.setNext(head). Removes the node after tail
5. **Method identification:** Check if new nodes are created (add) or elements are returned (remove). Check which end is affected (head/tail reference updates)
6. **DLL not suitable for CLL:** A circularly-linked list cannot use getPrevious (no backward links in SLL-based CLL)
7. **Inserting at head of CLL:** Need to update 2 next references (new node's next and tail's next)

---

### P16 -- AVL Tree Operations (Insert / Delete / Rotations) (High: 12 appearances)

**How to recognize:** "Count tri-node restructurings when deleting X", "Maximum height with n nodes"

**Steps:**
1. **AVL property:** For every node, |height(left) - height(right)| <= 1
2. **Insert:** Standard BST insert, then walk up to find first unbalanced node. Perform ONE tri-node restructuring (single or double rotation)
3. **Delete:** Standard BST delete, then walk up. May require MULTIPLE restructurings (up to O(log n))
4. **Single rotation:** When imbalance is on same side (left-left or right-right)
5. **Double rotation:** When imbalance is on opposite side (left-right or right-left)
6. **Max height with n nodes:** h <= 1.44 * log_2(n+2). With 7 nodes, max height = 3
7. **Min nodes for height h:** N(h) = N(h-1) + N(h-2) + 1 (Fibonacci-like). N(0)=1, N(1)=2, N(2)=4, N(3)=7, N(4)=12
8. **Max nodes at depth d:** 2^(d+1) - 1 (full tree)

**2025 exam tip:** Delete 35 from AVL (root 35, left=30, right=65). Replace 35 with inorder successor 31. Node 30 becomes unbalanced (left-height=1, right-height=-1): double rotation needed. Then 31's parent also unbalanced: another double rotation. Total: 2 tri-node restructurings.

---

### P17 -- Minimum Spanning Trees (Kruskal's / Prim's) (High: 12 appearances)

**How to recognize:** "How many distinct MSTs", "Kruskal's algorithm on graph"

**Steps:**
1. **Kruskal's:** Sort edges by weight. For each edge, if it connects two different components (clusters), add it. Use Union-Find
2. **Termination:** Stop when n-1 edges are added (n = number of vertices)
3. **Skip edge:** If both endpoints are in the same cluster (would create a cycle)
4. **Distinct edge weights:** If all edge weights are distinct, the MST is unique
5. **Multiple MSTs:** Occur when there are edges with equal weights that can be interchanged
6. **MST property:** In a forest (tree), m = n - 1 (edges = vertices - 1)
7. **Prim's:** Grow MST from a single vertex, always adding the cheapest edge connecting MST to non-MST vertex

**2025 exam tip:** Graph with distinct edge weights -> exactly 1 MST possible. If all weights distinct, answer is A (1).

---

### P18 -- Data Structure Choice for Application (High: 12 appearances)

**How to recognize:** "Hashmap vs AVL tree for k-th lowest-paid employee removal", "Which data structure for given operations"

**Steps:**
1. **List all required operations** and their frequencies (e.g., n inserts, n removes, k lookups)
2. **For each candidate data structure,** compute the time complexity of each operation:
   - Hash map: O(1) expected insert/delete/lookup, but NO ordering (no findMin, findNext)
   - AVL/BST: O(log n) for everything, supports ordering (findMin, findNext, range queries)
   - Heap: O(log n) insert/removeMin, but O(n) for arbitrary delete or search
   - Sorted array: O(log n) search (binary search), O(n) insert/delete
   - Unsorted list: O(1) insert, O(n) search/delete
3. **Multiply** each operation cost by its frequency, sum up for total time
4. **Key insight:** If you need ordering/range queries, use AVL tree. If you only need key lookup, use hash map. If you need repeated min/max extraction, use heap

**2025 exam tip:** Find k-th lowest-paid employee + remove. AVL: inorder traversal O(log n + k), remove O(log n) -> total O(log n + k). Hashmap: copy to array O(n), quickselect O(n) -> total O(n). AVL wins since k << n.

---

### P19 -- Priority Queue Implementations Comparison (High: 11 appearances)

**How to recognize:** "Merge sorted lists using heap", "Compare PQ implementations"

**Steps:**
1. **Unsorted list PQ:** Insert O(1), removeMin O(n), peek O(n) — corresponds to selection sort
2. **Sorted list PQ:** Insert O(n), removeMin O(1), peek O(1) — corresponds to insertion sort
3. **Heap PQ:** Insert O(log n), removeMin O(log n), peek O(1) — corresponds to heap sort
4. **n inserts + n removes:** Unsorted = O(n^2), Sorted = O(n^2), Heap = O(n log n). Heap wins
5. **For heapify + n removes:** O(n) + O(n log n) = O(n log n) with heap. Alternative: unsorted list to sorted list in O(n log n) + O(n) removes = O(n log n). Same asymptotically
6. **Merging two PQs:** Heap: create combined array + heapify = O(n). Sorted list: merge two sorted lists = O(n). Unsorted list: concatenate = O(1) with linked list

**2025 exam tip:** Merge log n sorted lists of size n/log n using heap: build heap of size log n in O(log n), then extract n elements each taking O(log log n). Total: O(n log log n).

---

### P20 -- Non-Comparison Sorting (Bucket / Radix / Counting Sort) (High: 11 appearances)

**How to recognize:** "Tightest bound on runtime for sorting integers with bounded range", "When to use non-comparison sorts"

**Steps:**
1. **Counting sort:** O(n + k) time and space, where k is the range of values. Best when k = O(n)
2. **Bucket sort:** Distribute into buckets, sort each bucket. O(n + k) expected time if elements are uniformly distributed
3. **Radix sort (LSD):** Sort by each digit from least significant to most significant using a stable sort (e.g., counting sort). O(d * (n + b)) where d = digits, b = base
4. **When to use:** When keys are integers in a bounded range, or strings of bounded length. NOT suitable for arbitrary comparison-based data
5. **Stability requirement:** Radix sort requires the per-digit sort to be stable (counting sort is stable)
6. **Not comparison-based:** These sorts break the Omega(n log n) lower bound for comparison sorts

---

### P21 -- Formal Big-O / Big-Omega Proof (High: 11 appearances)

**How to recognize:** "Prove that f(n) is O(g(n))" with formal mathematical notation

**Steps:**
1. **For O(g(n)):** Prove exists c > 0, n0 >= 1 such that f(n) <= c * g(n) for all n >= n0
2. **For Omega(g(n)):** Prove exists c > 0, n0 >= 1 such that f(n) >= c * g(n) for all n >= n0
3. **Step 1:** State the formal condition (the exists c, exists n0, forall n >= n0 inequality)
4. **Step 2:** Choose specific values of c and n0 (e.g., c = 1, n0 = 1)
5. **Step 3:** Show the inequality holds for all n >= n0. Use algebraic simplification
6. **Common trick for Omega:** Drop positive terms from the larger side; for O, bound each term above
7. **Be careful with O vs Omega:** The inequality direction flips! O uses <=, Omega uses >=

---

### P22 -- Identify Data Structure from Code (High: 11 appearances)

**How to recognize:** "Which data structure cannot be built with SimpleList interface in O(1)", "Identify ADT from method behavior"

**Steps:**
1. **Look at instance variables:** Array + size variable = stack/queue; Node with 3 references = binary tree with parent; Node with children array = general tree
2. **Look at method behavior:** LIFO (add/remove at same end) = stack; FIFO (add at one end, remove at other) = queue; add at arbitrary position = list
3. **Resizing strategy:** If growth factor is multiplicative (f*s+1), compatible with stack (amortized O(1)). Not suitable for queue (can't efficiently remove from front)
4. **Node references:** 1 reference (next) = SLL; 2 references (prev, next) = DLL; 3 references (left, right, parent) = binary tree with parent; element + children[] + parent = general tree

**2025 exam tip:** SimpleList has addFirst, addLast, removeFirst, removeLast, first, last, isEmpty, size in O(1). Queue = addLast+removeFirst. Stack = addFirst+removeFirst. CLL = addLast(removeFirst()). PQ requires min extraction in O(1) which is NOT possible -> cannot build PQ.

---

### P23 -- Stack / Queue Behavior Tracing (High: 11 appearances)

**How to recognize:** "Content of list after methodX completes", "Order of elements retrieved"

**Steps:**
1. **Stack (LIFO):** Last In, First Out. Push adds to top, Pop removes from top. Inserting 1,2,3 and popping gives 3,2,1
2. **Queue (FIFO):** First In, First Out. Enqueue adds to back, Dequeue removes from front. Inserting 1,2,3 and dequeuing gives 1,2,3
3. **Reversing with stack:** Moving all elements from a queue to a stack and back reverses the order
4. **Even/odd index split:** When inserting elements at even indices into a stack and odd indices into a queue, carefully track which elements go where
5. **Draw the state:** At each step, draw the current contents of the stack (top marked) and queue (front marked)

**2025 exam tip:** methodX iterates list, sums even elements (x%2==0), removes odd elements via iter.remove(). With [1,2,3,4,5,6]: even elements 2,4,6 -> sum=12. Odd elements 1,3,5 removed. List becomes [2,4,6].

---

### P24 -- Topological Ordering (High: 11 appearances)

**How to recognize:** "Which ordering is NOT valid", "Count valid topological orderings"

**Steps:**
1. **Definition:** A topological ordering places all vertices in a linear order such that for every directed edge (u,v), u appears before v
2. **Only for DAGs:** A topological ordering exists iff the graph has no directed cycles
3. **Algorithm:** Repeatedly remove a vertex with in-degree 0 (and its outgoing edges). The removal order is a valid topological ordering
4. **Counting orderings:** At each step, count how many vertices have in-degree 0 (those are interchangeable). Multiply the choices at each step
5. **Checking validity:** For each edge (u,v), verify u appears before v in the given sequence
6. **If a appears before b in a topological sort:** It does NOT necessarily mean there's an edge from a to b, only that there's no path from b to a

---

### P25 -- Graph Representation Comparison (High: 11 appearances)

**How to recognize:** "Which representation for which operations", "BFS shortest path property"

**Steps:**
1. **Edge list:** Space O(n+m). Check edge: O(m). Iterate neighbors of v: O(m). Good for nothing specific
2. **Adjacency list:** Space O(n+m). Check edge: O(deg(v)). Iterate neighbors: O(deg(v)). Best for sparse graphs
3. **Adjacency matrix:** Space O(n^2). Check edge: O(1). Iterate neighbors: O(n). Best for dense graphs with frequent edge queries
4. **Adjacency map:** Space O(n+m). Check edge: O(1) expected. Iterate neighbors: O(deg(v)). Best of both worlds for most operations
5. **Dense graph:** m ~ n^2. Adjacency matrix is efficient. **Sparse graph:** m ~ n. Adjacency list/map is efficient

---

### P26 -- Iterator Behavior (Snapshot vs Lazy) (High: 11 appearances)

**How to recognize:** "Output of code using iterator", "Snapshot vs lazy iterator behavior"

**Steps:**
1. **Snapshot iterator:** Makes a copy of the collection at creation. Subsequent modifications to the original collection do NOT affect iteration. Construction: O(n) time, O(n) space
2. **Lazy iterator:** References the live collection. Modifications to the collection ARE reflected during iteration. Construction: O(1) time, O(1) space
3. **Creating new iterator each loop:** elements.iterator() creates a NEW iterator starting from the beginning each time. The loop will always print the first element repeatedly
4. **Single iterator reused:** iterator.next() advances the SAME iterator. Successive calls return consecutive elements
5. **Java for-each:** Syntactic sugar for creating an iterator and calling hasNext()/next(). Uses a lazy iterator

---

### P27 -- Explain What Algorithm Does (High: 11 appearances)

**How to recognize:** "Describe what methodX computes", "For which inputs does it return true?"

**Steps:**
1. **Trace with small inputs:** Run the code mentally with arrays of size 3-5 to understand the pattern
2. **Identify the invariant:** What property is being checked/maintained? (e.g., "all elements are positive", "no duplicates", "sorted in strictly increasing order")
3. **Look at return conditions:** When does it return true vs false? This often reveals the purpose
4. **For "faster solution":** Think about sorting (O(n log n)), hash sets for duplicates (O(n)), or mathematical properties (min/max comparison)

---

### P28 -- Merge Sort Execution & Recursion Tree (High: 11 appearances)

**How to recognize:** "Array state after level k of merge sort", "Subsequences at each level"

**Steps:**
1. **Top-down:** Recursively split array in half until size 1, then merge. Level 0 = full array, level k = subarrays of size n/2^k
2. **Bottom-up:** Start with runs of size 1, merge adjacent pairs into runs of size 2, then 4, etc. After iteration k, runs have size 2^k
3. **Merging at level k:** At level k (from leaves), subarrays of size 2^(k-1) are merged into sorted subarrays of size 2^k
4. **Recurrence:** T(n) = 2T(n/2) + c1*n + c2. The c1*n comes from the merge step (linear scan). Closed form: O(n log n)
5. **Space:** O(n) for the auxiliary array used during merging. Cannot be done in-place with O(n log n) time

---

### P29 -- Quicksort / Quickselect (High: 11 appearances)

**How to recognize:** "Quicksort worst-case on sorted input", "Count swaps in partition"

**Steps:**
1. **Partition:** Choose pivot (often last element). Rearrange so elements <= pivot are left, > pivot are right. Pivot ends in final position
2. **In-place partition comparisons:** n-1 comparisons for array of size n (compare each element to pivot)
3. **Worst case:** Pivot is always min or max -> T(n) = T(n-1) + cn = O(n^2)
4. **Expected case:** Balanced partitions -> T(n) = 2T(n/2) + cn = O(n log n)
5. **Quickselect:** Like quicksort but only recurses into ONE partition (the one containing the k-th element) -> O(n) expected time
6. **Dual-pivot quicksort:** Two pivots, three partitions. Partition step: 2(n-2) comparisons worst case
7. **NOT stable:** Quicksort does not preserve relative order of equal elements

---

### P30 -- Positional List Operations (DLL with Sentinels) (High: 11 appearances)

**How to recognize:** "Count next/prev references used by removeFirst", "How many references accessed by addBefore"

**Steps:**
1. **Sentinel nodes:** Header and trailer are dummy nodes that simplify boundary conditions. Actual elements are between them
2. **addBefore(p, e):** (1) Get predecessor: p.prev, (2) Create new node, set new.prev = predecessor, (3) Set new.next = p, (4) Set predecessor.next = new, (5) Set p.prev = new. Total: 3 prev references
3. **removeFirst:** (1) first = header.next, (2) second = first.next, (3) header.next = second, (4) second.prev = header. Total: 3 next + 1 prev = 4 references
4. **replace(e, p):** Simply set p.element = e. 0 prev references needed (just access the node directly)
5. **Position abstraction:** Encapsulates the node, only exposes getElement(). Prevents unauthorized modifications

**2025 exam tip:** removeFirst in DLL with sentinels: header.next (1st next), first.next (2nd next), header.next = second (3rd next), second.prev = header (1st prev). Total: 4 references. Answer: C.

---

### P31 -- Time Complexity Polynomial for Iterative Method (Low: 4 appearances)

**How to recognize:** "Write the exact polynomial T(n) = c0 + c1*n + c2*n^2 for worst-case time"

**Steps:**
1. **c0 (constant term):** Method call overhead, variable initialization, return statement
2. **c1*n (linear term):** Single loop executing n times, with constant work per iteration
3. **c2*n^2 (quadratic term):** Nested loops (e.g., insertion sort), or a call to an O(n^2) subroutine
4. **Include subroutine costs:** If methodX calls inPlaceInsertionSort (O(n^2)), include that as c3 + c4*n + c5*n^2
5. **Justify each constant:** Name specific lines of code each ci accounts for
6. **Simplify to Big-O:** The highest-degree term dominates, so T(n) = c0 + c1*n + c2*n^2 is O(n^2)

---

### P32 -- BST Properties & Operations (Low: 4 appearances)

**How to recognize:** "Valid inorder traversal of BST", "Properties of BST"

**Steps:**
1. **BST property:** For every node, all keys in left subtree < node key < all keys in right subtree
2. **Inorder traversal of BST:** Always gives keys in sorted (non-decreasing) order
3. **Valid inorder check:** The sequence must be sorted. If not sorted, it cannot be a BST inorder traversal
4. **Preorder from BST:** First element is root, then all elements smaller than root (left subtree), then all larger (right subtree)
5. **From a set S:** Inorder traversal is fully determined (sorted order). Preorder is NOT determined (depends on tree shape)

---

### P33 -- Array-Based Tree Representation (Low: 4 appearances)

**How to recognize:** "Navigate array-based binary tree", "Which shape uses most space"

**Steps:**
1. **Standard formulas (0-indexed):** Left child = 2i+1, Right child = 2i+2, Parent = floor((i-1)/2)
2. **Alternative (with l = 2*p+1, r = 2*p+2):** Same as above, used in some exam questions
3. **Space usage:** Complete trees use minimal space (no gaps). Degenerate (line) trees waste exponential space: need 2^(h+1)-1 positions for h nodes
4. **Smallest tree that doesn't fit in array of size C:** A line tree (each node has only one child on the far side) maximizes the indices needed
5. **Not suitable for general trees:** Array-based representation assumes binary trees with specific index formulas

---

### P34 -- Deep Copy / Shallow Copy / Clone Behavior (Low: 4 appearances)

**How to recognize:** "Content of array after copy with clone1/clone2", "Number of new objects created"

**Steps:**
1. **Shallow copy:** Copies the array/structure but shares the same element references. Modifying an element in the original affects the copy
2. **Deep copy:** Copies the array AND creates new copies of each element. Modifications are independent
3. **Copy by reference:** Both variables point to the same object. No new objects created
4. **clone1() = new Score(this.value):** Creates a new independent object (deep copy of that element)
5. **clone2() = return this:** Returns the same object reference (shallow/alias)
6. **Count new objects:** Track how many times "new" is called during execution. clone1 at even indices creates ceil(n/2) new objects

---

## Confidence Assessment

### Strong — solved with minimal hints
- Asymptotic notation / Big-O relationships (P1) — growth rate hierarchy and dominant term
- Recurrence setup from code (P4) — can identify loops, recursion depth, and base cases
- Closed form derivation by unfolding (P3) — mechanical process of substitution and pattern recognition
- Data structure choice analysis (P18) — compare operation costs for hashmap vs AVL
- Heap operations and swap counting (P5) — bottom-up heapify is systematic

### Needs review — required multiple hints or conceptual confusion
- Hash table probing with DEFUNCT markers (P9) — need to carefully trace past deleted entries
- (2,4) tree deletion with fusion/transfer (P12) — cascade handling is tricky
- Red-black tree delete and recoloring (P13) — multiple cases depending on sibling/uncle color
- AVL tree delete and multiple restructurings (P16) — walk up after delete, count rotations
- Dijkstra's algorithm step-by-step execution (P14) — track all distance label changes
- Positional list sentinel reference counting (P30) — easy to miscount prev vs next

### Not attempted — review if time permits
- Time complexity polynomial for iterative methods (P31)
- BST properties and inorder validation (P32)
- Array-based tree representation and space (P33)
- Deep copy vs shallow copy tracing (P34)
- Iterator behavior (snapshot vs lazy) (P26)
- Explain what algorithm does from code (P27)
- Merge sort recursion tree tracing (P28)
- Quicksort partition analysis (P29)
- Formal Big-O/Omega proof construction (P21)
- Recursion tail-call identification (P11)

---

## Grasple Practice Guide

### Mapping Grasple Lectures to Endterm Question Patterns

| Grasple Topic | Endterm Patterns | Key Exercises |
|--------------|-----------------|---------------|
| Asymptotic Notation | P1, P21 | Analyze Exercises: Big-O proofs, growth comparisons |
| Recurrences & Complexity | P3, P4, P31 | Analyze Exercises: recurrence setup, closed form derivation |
| Arrays & Linked Lists | P6, P7, P15, P30 | Analysis Exercises: complexity comparison, amortized analysis |
| Heaps & Priority Queues | P5, P19 | Analysis Exercises: heapify, heap sort, PQ comparison |
| Trees | P8, P12, P13, P16, P32, P33 | Analysis Exercises: traversals, AVL rotations, (2,4)/RB trees |
| Hash Tables | P9, P34 | Analysis Exercises: linear probing, separate chaining, collisions |
| Graphs | P14, P17, P24, P25 | Analysis Exercises: Dijkstra, MST, topological sort, BFS/DFS |
| Sorting | P2, P20, P28, P29 | Analysis Exercises: sort comparison, stability, complexity |
| Iterators & ADTs | P22, P23, P26, P27 | Analysis Exercises: iterator behavior, ADT identification |

---

## Quick Reference — Frequency Summary

### Very High (10+ appearances, appear in ALL endterms)
| Pattern | Topic | Endterm Frequency |
|---------|-------|-------------------|
| P1 | Asymptotic Notation | 15/6 endterms |
| P2 | Sorting Algorithms | 15/6 endterms |
| P3 | Closed Form Unfolding | 15/6 endterms |
| P4 | Recurrence Setup | 15/6 endterms |
| P5 | Heap Operations | 15/6 endterms |
| P6 | Array vs Linked List | 15/6 endterms |
| P7 | Dynamic Array Resizing | 15/6 endterms |
| P8 | Tree Traversals | 15/6 endterms |
| P9 | Hash Tables | 15/6 endterms |
| P10 | Space Complexity | 14/6 endterms |
| P11 | Recursion Analysis | 14/6 endterms |

### High (5-9 appearances, appear in most endterms)
| Pattern | Topic | Endterm Frequency |
|---------|-------|-------------------|
| P12 | (2,4) Tree | 12/6 endterms |
| P13 | Red-Black Tree | 12/6 endterms |
| P14 | Dijkstra's | 12/6 endterms |
| P15 | Linked List Ops | 11/6 endterms |
| P16 | AVL Tree | 12/6 endterms |
| P17 | MST | 12/6 endterms |
| P18 | DS Choice | 12/6 endterms |
| P19 | PQ Comparison | 11/6 endterms |
| P20 | Non-Comparison Sort | 11/6 endterms |
| P21 | Formal Proof | 11/6 endterms |
| P22 | Identify DS | 11/6 endterms |
| P23 | Stack/Queue Tracing | 11/6 endterms |
| P24 | Topological Ordering | 11/6 endterms |
| P25 | Graph Representation | 12/6 endterms |
| P26 | Iterator Behavior | 11/6 endterms |
| P27 | Explain Algorithm | 11/6 endterms |
| P28 | Merge Sort | 11/6 endterms |
| P29 | Quicksort | 11/6 endterms |
| P30 | Positional List | 11/6 endterms |

### Low (1-4 appearances, rare on endterm)
| Pattern | Topic | Endterm Frequency |
|---------|-------|-------------------|
| P31 | Time Complexity Polynomial | 4/6 endterms |
| P32 | BST Properties | 4/6 endterms |
| P33 | Array-Based Tree | 4/6 endterms |
| P34 | Deep/Shallow Copy | 4/6 endterms |

---

## Open Question Templates

### O1: Recurrence Setup (5-6 pts)
**Structure:**
- Input size: n = list.size() / array.length
- Base case: T(0) = c0 or T(1) = c0
- Recurrence: T(n) = [constant work] + [loop work] + [recursive call] T(n-1)
- Justify: Reference specific line numbers for each term
- **Key terms to look for:**
  - Single loop -> c*n
  - Nested loops -> c*n^2
  - Collections.sort -> c*n*log(n) (on n^2 elements: c*n^2*log(n^2))
  - LinkedList.get -> O(n) per call
  - Recursive call -> T(n-1) or T(n/2)

### O2: Closed Form Derivation by Unfolding (5 pts)
**Structure:**
- Unfold 3-4 steps explicitly showing substitution
- Derive the general form for k steps (pattern recognition)
- Solve for k using base case condition
- Substitute k back into general form
- Simplify using 2^(log n) = n and geometric series identities
- **Key identity:** (2^k - 1) for geometric series sum

### O3: Data Structure Choice (4 pts)
**Structure:**
- State both data structures being compared
- Analyze each operation for both structures
- Give Big-O for total cost
- Make recommendation with justification
- **Key insight:** If ordering is needed (find k-th, range queries), AVL tree. If only key lookup, hash map.