41 Final Exam Review (CSS 343)
42 Final Exam Review (CSS 343)
Week 10, Session 1. CSS 343.
The 343 final covers chapters 21–38, with extra weight on 31–38 (post-midterm content). Same structure as the midterm review: rapid pass through likely question shapes.
42.1 Topics by likely weight
| Chapter | Topic | Likely on final |
|---|---|---|
| 22 | Tree traversals | Yes |
| 23 | BST delete | Yes |
| 25 | Heap operations | Yes |
| 26 | BFS / DFS | Yes |
| 27 | Dijkstra, MST, topo sort | Yes |
| 28 | Hash collisions | Likely |
| 29 | AVL rotation | Likely |
| 31 | Master Theorem | Yes |
| 32 | Greedy correctness | Likely |
| 33–34 | DP recurrence and table | Yes |
| 35 | Identify the pattern | Likely |
| 36 | Virtual functions / vtable | Possible |
| 37 | DFA construction | Yes |
| 38 | P/NP, halting, complexity classes | Yes |
42.2 D&C — apply Master Theorem
T(n) = 3T(n/2) + n². a=3, b=2. log_b a = log_2 3 ≈ 1.585. f(n) = n² = O(n^c) with c=2 > 1.585. Case 3 → T(n) = Θ(n²).
T(n) = 2T(n/4) + √n. a=2, b=4. log_b a = 0.5. f(n) = √n = Θ(n^0.5). Case 2 → T(n) = Θ(√n · log n).
42.3 DP recurrence — write it
For Longest Palindromic Subsequence of s:
Subproblem: dp[i][j] = LPS length in s[i..j].
Recurrence: - If i > j: 0. - If i == j: 1. - If s[i] == s[j]: dp[i+1][j-1] + 2. - Else: max(dp[i+1][j], dp[i][j-1]).
For Edit Distance of s1 (length m) and s2 (length n):
Subproblem: dp[i][j] = edit distance between s1[0..i-1] and s2[0..j-1].
Base: dp[0][j] = j, dp[i][0] = i.
Recurrence: if chars match, dp[i-1][j-1]; else 1 + min of three (replace, delete, insert).
42.4 Greedy proof sketch
Activity selection: prove the “earliest finish time” greedy is optimal.
Exchange argument. Suppose an optimal solution O* does not include the activity with earliest finish time, a₁. Consider O* sorted by finish time: a₁, a₂, … Replace a₁ with a₁. Since a₁’s finish ≤ a₁’s finish, a₁ does not conflict with a₂, …, aₖ. So the new schedule is valid and has the same count. ∎
42.5 OOP — identify the pattern
“We need exactly one instance of a config object accessible globally.” → Singleton.
“We need to support multiple sorting algorithms selected at runtime by a string.” → Strategy (concrete strategies + a factory).
“A subscriber should be notified when an event occurs.” → Observer.
“We have a legacy printer with a different interface than the rest of our codebase.” → Adapter.
42.6 Theory — DFA construction
“Strings over {0, 1} with an even number of 1s”:
Two states. q0 = even count (accept, start). q1 = odd count.
| State | 0 | 1 |
|---|---|---|
| q0 | q0 | q1 |
| q1 | q1 | q0 |
42.7 Theory — classify
| Problem | Class |
|---|---|
| Sort an array | P |
| Find a Hamiltonian path | NP-complete |
| Verify a vertex cover | P |
| Find minimum vertex cover | NP-complete |
| Halting problem | Undecidable |
aⁿbⁿ membership |
Decidable, not regular |
| Balanced parentheses | Decidable, context-free |
42.8 Integration — a class with a BST inside
A class IntDictionary stores word/count pairs in a BST keyed by word.
class IntDictionary {
public:
void put(const string& word, int count);
int get(const string& word) const;
// Rule of Three?
private:
TreeNode* root_;
};What does the destructor need? Walk the tree, delete every node (post-order).
What does the copy constructor need? Deep copy of the tree (recursive helper).
What does operator= need? Self-assignment guard, delete current tree, deep copy.
The same Rule of Three from 342 chapter 7, applied to a tree-shaped resource.
42.9 Common wrong answers
- “Greedy is optimal for 0/1 knapsack.” It is not. Use DP.
- “DP requires recursion.” It does not. Tabulation is iterative.
- “Master Theorem applies to any recurrence.” Only to T(n) = aT(n/b) + f(n) with a, b constants.
- “The halting problem is hard to solve.” It is impossible. Not hard.
- “Hash tables are always faster than BSTs.” Average yes, worst case no, and BSTs support range queries.
42.10 Top 5 to review tonight
- Master Theorem cases. Memorize.
- DP framework: subproblem in words → recurrence → base case → table.
- AVL rotation case identification: LL/LR/RL/RR.
- Halting problem proof (sketch).
- The pattern names: Singleton, Strategy, Factory, Observer, Adapter, Iterator — one-sentence each.
42.11 Try it
For each chapter 31–38, write down the one result you would put on a flashcard. Compare against this chapter’s “Topics by likely weight.” Anything you cannot summarize → re-read.
42.12 Where this fits
After the final, the closing chapter ties everything together and points where to go next.
| You are here | Coming up |
|---|---|
| Final review (343) | Chapter 40: wrap-up, what’s next |