182. Algorithms. (4) Lecture, three hours; discussion, one hour. Requisite: course 3C or 32A. Graphs, greedy algorithms, divide and conquer algorithms, dynamic programming, network flow. Emphasis on designing efficient algorithms useful in diverse areas such as bioinformatics and allocation of resources. P/NP or letter grading.

Kleinberg, Tardos: Algorithm Design, Addison Wesley

Week 1: Introduction, Stable Marriage Problem, Gale-Shapley algorithm.

Week 2: Orders of magnitude (Big O notation). Estimating the running time for simple algorithms looking up an entry in a sorted list, mergesort.

Week 3: Basic graph definitions. Directed graphs, trees, paths. Data structures as graphs: stacks, heaps. Breadth first search, Depth First search, test of bipartitness, DAG's.

Week 4: Introduction to the four main classes of algorithms: Greedy, Divide and Conquer, Dynamic programming, Network flow. Application of greedy algorithms to interval scheduling and shortest path problems, minimum spanning trees.

Week 5: Divide and conquer algorithms. Mergesort, counting inversions, closest pairs of points. Recurrences.

Week 6: Dynamic programming, weighted interval scheduling, Knapsack problems.

Week 7: Dynamic programming continued, RNA secondary structures, sequence alignment.

Week 8: Network flow: Maximum flow problem. Min cuts. Circulations.

Week 9: Network flow: Airline scheduling, Image segmentation, Project selection.

Week 10: Introduction to P and NP.