21 Final Exam Review (CSS 342)

22 Final Exam Review (CSS 342)

Week 10, Session 1. CSS 342.

The final covers chapters 1–18, with heavier emphasis on chapters 11–18 (everything after the midterm). This chapter is a fast pass through the highest-yield topics with worked examples.

22.1 Algorithm analysis — derive O for snippets

Snippet 1:

for (int i = 1; i < n; i *= 2)
  for (int j = 0; j < n; ++j)
    /* O(1) */;

Outer loop: O(log n). Inner: O(n). Total: O(n log n).

Snippet 2:

for (int i = 0; i < n; ++i)
  for (int j = i; j < n; ++j)
    for (int k = 0; k < j; ++k)
      /* O(1) */;

Inner two loops sum to O(n²). Outer loop runs n times but the inner work depends on i. Detailed analysis: O(n³).

Snippet 3:

int f(int n) {
  if (n <= 1) return 1;
  return f(n - 1) + f(n - 1);
}

Two recursive calls, each at n-1. T(n) = 2T(n-1) + O(1). O(2ⁿ).

22.2 Sorting — trace merge sort on `{4,7,2,1,9,3}`

[4,7,2,1,9,3]
├── [4,7,2]
│   ├── [4]
│   └── [7,2]
│       ├── [7]
│       └── [2]
│       merged: [2,7]
│   merged: [2,4,7]
└── [1,9,3]
    ├── [1]
    └── [9,3]
        ├── [9]
        └── [3]
        merged: [3,9]
    merged: [1,3,9]
merged: [1,2,3,4,7,9]

Complexity: O(n log n). Three levels (log₂ 6 ≈ 2.6, so 3), n work per level.

22.3 Induction — prove ∑i² = n(n+1)(2n+1)/6

Base (n=1): LHS = 1. RHS = 1·2·3/6 = 1. ✓

IH: Assume 1² + 2² + … + k² = k(k+1)(2k+1)/6.

Step: Show with k+1.

\[ \sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \]

Factor (k+1)/6:

\[ = \frac{(k+1)}{6} \left[ k(2k+1) + 6(k+1) \right] = \frac{(k+1)}{6} \left[ 2k^2 + 7k + 6 \right] \]

Factor the quadratic: 2k² + 7k + 6 = (k+2)(2k+3) = (k+2)(2(k+1)+1).

\[ = \frac{(k+1)(k+2)(2(k+1)+1)}{6} \]

which is the formula with n=k+1. ∎

22.4 Linked list — `deleteAll`

void deleteAll(Node*& head, int val) {
  // Peel head matches
  while (head != nullptr && head->data == val) {
    Node* tmp = head;
    head = head->next;
    delete tmp;
  }
  // Process the rest
  Node* curr = head;
  while (curr != nullptr && curr->next != nullptr) {
    if (curr->next->data == val) {
      Node* tmp = curr->next;
      curr->next = tmp->next;
      delete tmp;
    } else {
      curr = curr->next;
    }
  }
}

Edge cases: empty list (handled), all matching (handled by the peel loop), consecutive matches in the middle (handled by not advancing curr when we delete).

22.5 BST — delete a two-child node

Given a BST with root 50, delete 30 (which has two children 20 and 40):

        50                 50
       /  \      →        /  \
      30   70            40   70
     /  \                 /
    20  40              20

The in-order successor of 30 is 40 (smallest in the right subtree, which is just 40). Copy 40’s value into the node, then delete the node with value 40 (which is a leaf — trivial deletion).

22.6 Integration problem — class with a BST

A class that owns a TreeNode* root_. What does its destructor need?

class IntBST {
 public:
  IntBST() : root_(nullptr) {}
  ~IntBST() { deleteAll(root_); }
  // ... insert, search, etc.
 private:
  TreeNode* root_;
  void deleteAll(TreeNode* node) {
    if (node == nullptr) return;
    deleteAll(node->left);
    deleteAll(node->right);
    delete node;
  }
};

Post-order deletion: free children first, then yourself. Same recursive shape as everything else in this course.

And per Rule of Three: it needs a copy constructor (deep copy the whole tree) and copy assignment.

22.7 Common wrong answers from past exams

Using (lo + hi) / 2 instead of lo + (hi - lo) / 2 for midpoint. -2.
Forgetting the [] in delete[] data_;. -2.
Returning Box by value from operator= instead of Box&. Chained assignment breaks.
Forgetting *this return from operator=. Compile error or break of chaining.
Drawing in-order traversal in reverse order (right-then-left).

22.8 Top 5 things to review tonight

Pointers: & vs *, declaration vs expression, Node*& for “modify the caller’s pointer.”
Rule of Three: deep copy, self-assignment guard, return *this.
Templates: implementations in headers, deduction with single T.
Big-O: identify dominant term, drop constants, drop lower order.
Recursion on trees: base case is nullptr, two recursive calls, combine.

22.9 Try it

Pick one chapter you feel weakest on. Re-solve its three challenges without looking at your previous solutions. Time yourself. That is your gauge.

22.10 Where this fits

After the final, the course wraps with a synthesis lecture connecting all 18 content chapters and looking ahead to 343.

You are here	Coming up
Final review of 342	Chapter 20: wrap-up and 343 preview