Full Drill Session for FAC1004

Full Drill Session for FAC1004

Overview

• FAC1004 full drill session for exam preparation focusing on key problem types and derivations.

Core Topics

• Data structures: Heaps, Binary Search Trees, Hashing
• Algorithms: Sorting (Quick, Merge), Graph Traversal (BFS, DFS), Dynamic Programming
• Complexity Analysis: Big-O, recurrence relations, amortized analysis

Essential Formulas

• Master Theorem: $$T(n) = aT(n/b) + f(n)$$
  • If $f(n) = O(n^{\log_b a - \epsilon})$, then $T(n) = \Theta(n^{\log_b a})$
  • If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$
  • If $f(n) = \Omega(n^{\log_b a + \epsilon})$, then $T(n) = \Theta(f(n))$

Practice Problems

• Analyze worst-case runtime:
  • QuickSort: $O(n^2)$ with bad pivot, expected $O(n \log n)$
  • Mergesort: Always $O(n \log n)$
• Graph traversal: BFS/DFS complexity $O(V + E)$

Common Exam Traps

• $\uparrow$ Missing base cases in recurrences
• Confusing average vs worst-case time complexities
• Neglecting memory usage in space complexity analysis