Algorithm Design

What it covers

• Greedy algorithms: interval scheduling, Dijkstra's, MST (Prim's/Kruskal's), "greedy stays ahead" and exchange-argument proofs
• Divide and conquer: recurrences, the Master Method, mergesort, closest pair of points, integer multiplication
• Dynamic programming: memoization vs. tabulation, knapsack, sequence alignment, Bellman-Ford
• Network flow: max-flow min-cut, Ford-Fulkerson, bipartite matching, circulations with demands

Assessment

Two-part written exam (W1 mid-quarter + W2 end-of-quarter, weighted 0.4/0.6) plus a 3-hour computer exam (P) on WebLab in Java. A final grade is only computed if both W and P independently score ≥5.0 — otherwise your grade is capped at the lower of the two. Written exam is closed-book; the WebLab exam permits only the Java API docs.

Worth knowing

• The computer exam explicitly demands the asymptotically optimal solution — a correct brute-force answer still loses points.
• Network-flow questions are graded mainly on correct problem modelling; a max-flow library is usually provided, so the challenge is turning the scenario into a graph.
• Assumes CSE13C (data structures, graph traversal, Big-O) and CSE11A (induction, proof by contradiction) are solid going in.