0. How To Study For This Exam (Seriously)

This is not a memorization exam.

You must be able to:

Look at unfamiliar code and reason about it.
Distinguish asymptotic growth from constant factors.
Recognize algorithm patterns (D&C, DP, greedy, backtracking).
Explain trade-offs clearly in plain language.
Modify working programs correctly.
Justify why something works — not just that it works.

If you cannot explain something in 3–5 precise sentences, you don’t understand it well enough yet.

1. Big-O Analysis (Time and Space)

You Must Be Able To:

Analyze nested loops.
Recognize triangular sums.
Analyze recursion depth.
Separate time complexity from space complexity.
Distinguish input size from auxiliary space.
Recognize amortized vs worst-case.

1.1 Nested Loop Patterns

Pattern A: Independent loops

for (int i=0; i<n; i++)
  for (int j=0; j<n; j++)

Time: O(n²)

Pattern B: Triangular loop

for (int i=0; i<n; i++)
  for (int j=i; j<n; j++)

Time:
n + (n-1) + … + 1 = n(n+1)/2 = O(n²)

Pattern C: Shrinking inner loop

for (int i=0; i<n; i++)
  for (int j=0; j<i; j++)

Also triangular → O(n²)

1.2 Recursion Patterns

Binary split

T(n) = 2T(n/2) + O(n)

Example: merge sort
Time: O(n log n)

Single recursion

T(n) = T(n-1) + O(1)

Time: O(n)

Exponential recursion

T(n) = 2T(n-1)

Time: O(2ⁿ)

1.3 Space Complexity

Always ask:

Are we allocating new arrays?
What is recursion depth?
Is memory reused?

Examples:

Algorithm	Time	Extra Space
Selection sort	O(n²)	O(1)
Merge sort	O(n log n)	O(n)
DFS (recursive)	O(n+m)	O(n) stack
Fibonacci naive	O(2ⁿ)	O(n) stack

1.4 Amortized Analysis (Practical View)

Union-Find:

Single operation not constant
But amortized ~ constant (inverse Ackermann)

Vector push_back:

Occasional resize O(n)
Amortized O(1)

Understand what amortized means:

Average cost per operation over a long sequence.

2. Benchmarking vs Theoretical Analysis

2.1 Why Benchmarking Alone Misleads

CPU frequency scaling
Cache behavior
Compiler optimization
Background processes
Input distribution
Small-n constant factors hiding asymptotics

Example:
O(n²) beats O(n log n) for small n.

2.2 Good Benchmarking Practice

Multiple trials
Warm-up runs
Fix compiler flags
Report hardware
Vary input size exponentially (1k, 10k, 100k…)
Plot results

2.3 When Theory Is Stronger

Worst-case guarantees
Very large n
Adversarial input
Security-sensitive systems
Proving optimality

3. Divide and Conquer

Pattern

Divide problem
Solve subproblems
Combine results

3.1 Merge Sort Structure

sort left half
sort right half
merge sorted halves

Common student mistakes:

Forget copying remainder
Off-by-one errors
Not copying back to original array

3.2 Advantages

Often parallelizable
Clean structure
Good asymptotic performance
Cache-friendly (sometimes)

3.3 Issues

Stack depth
Extra memory (merge sort)
Overhead for small n

4. Backtracking

What It Is

Systematic search of decision tree.

Core idea:

Choose
Recurse
Undo (backtrack)

Structure

choose option
if (valid)
    recurse
undo choice

Complexity

Often exponential:

Subset sum: O(2ⁿ)
N-Queens: exponential

Pruning

Cut off branches early if:

Constraint violated
Partial solution impossible

Pruning is the difference between:

Feasible
Impossible

5. Greedy Algorithms

Two Required Properties

1. Greedy Choice Property

Local optimal choice leads to global optimal solution.

2. Optimal Substructure

Optimal solution contains optimal solutions to subproblems.

Examples

Works:

MST (Kruskal, Prim)
Dijkstra (non-negative edges)
Activity selection

Fails:

0/1 knapsack
Some scheduling variants

6. Hybrid Greedy + Backtracking

Strategy:

Use greedy to choose promising branch first.
Use backtracking for correctness.

Benefits:

Finds good solution early.
Improves pruning.
Often drastically reduces runtime.

Example:
Subset sum:

Sort descending
Try large numbers first
Hit target earlier
Prune sooner

7. Minimum Spanning Trees (Kruskal + Union-Find)

Kruskal Algorithm

Sort edges by weight
Add smallest edge that does not create cycle
Use Union-Find to detect cycles

Time:
O(m log m)

Union-Find

Operations:

find(x)
union(x,y)

Optimizations:

Path compression
Union by rank/size

Amortized: ~ constant

8. Dynamic Programming

When To Use DP

Two required properties:

Overlapping subproblems
Optimal substructure

8.1 Memoization vs Tabulation

Memoization:

Top-down
Recursive
Cache as needed

Tabulation:

Bottom-up
Iterative
Fill table systematically

8.2 Subset Sum DP

State:
dp[i][s] = can we make sum s using first i items?

Transition:

dp[i][s] = dp[i-1][s] 
        OR (s>=a[i] AND dp[i-1][s-a[i]])

Time:
O(n * target)

8.3 DP vs D&C

Divide & Conquer	Dynamic Programming
Recomputes	Reuses
Independent subproblems	Overlapping subproblems
Often recursive	Often table-based

9. Hashing

Expected Load

n keys, m buckets:
Expected load = n/m

Collisions

Unavoidable when n > m.

But good hashing:

Spreads keys evenly
Keeps chains short
Expected O(1)

Pitfalls

Poor hash function
Clustering
Adversarial input
Hash flooding attacks

10. Zobrist Hashing

Used in:

Game trees
State caching
Transposition tables

Idea:

Pre-generate random bitstrings for (piece, position)
XOR them together
To update: XOR out old piece, XOR in new piece

Why fast?

O(1) incremental update

Limitation:

Collisions still possible

11. Disjoint Sets

Maintains:
Partition of elements into non-overlapping sets.

Operations:

find
union

Used in:

MST
Connectivity
Clustering

Path compression:

During find, flatten tree
Makes future finds faster

12. Simulated Annealing

Metaheuristic for optimization.

Core idea:

Allow worse moves early
Gradually reduce randomness

Acceptance probability:

P = exp(-ΔE / T)

High T:

Explore

Low T:

Exploit

Cooling schedule:

How T decreases over time

Pitfalls:

Cooling too fast → stuck
Cooling too slow → too slow

13. Common Comparison Questions

You should be able to compare:

Backtracking vs DP
Greedy vs DP
Greedy vs Backtracking
Annealing vs Greedy
Hashing vs Trees
Union-Find vs DFS for connectivity

14. Big Patterns to Recognize

If you see:

Binary split recursion → D&C
Choice tree → Backtracking
“Best local choice” → Greedy
Reuse subresults → DP
Repeated state search → Hashing
Connectivity merging → Disjoint sets
Optimization with randomness → Annealing

15. Typical Exam Mistakes

Confusing O(n²) with O(n log n)
Forgetting space complexity
Thinking greedy “seems to work” means “provably works”
Not copying merge remainder
Confusing memoization and tabulation
Thinking path compression alone guarantees constant time (it’s amortized)

16. If You Want To Be Fully Prepared

You should be able to:

Implement merge sort from memory.
Implement union-find with rank + compression.
Write subset-sum DP table.
Explain why knapsack greedy fails.
Explain why Dijkstra fails with negative edges.
Compare backtracking vs DP for subset sum.
Explain how Zobrist hashing updates in O(1).
Explain why annealing escapes local minima.