Math 182: General Course Outline
Catalog Description
182. Algorithms. (4) Lecture, three hours; discussion, one hour. Requisite: course 3C or 32A and 61. Lecture, three hours; discussion, one hour. Requisite: course 3C or 32A, and 61. Not open for credit to students with credit for Computer Science 180. 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.
Textbook
Kleinberg, Tardos: Algorithm Design, Addison Wesley
Schedule of Lectures
Lecture  Section  Topics 

Week 1 
Introduction, Stable Marriage Problem, GaleShapley 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. 