**Text: ***Algorithm Design, *J.
Kleinberg and E. Tardos,* Pearson 2006.*

*Additional
material, including power point slides for this text, available from WebCT *and a hidden website
(contact me or TAs)

Sep 1: Course overview, web pages etc. All meals for a dollar: linear programming and vertex enumeration. slides.

Sep 3: The stable marriage problem. Read: Section 1.1 and this fun article. (Extra for those interested: LP-bliss paper is on the hidden website.) Kazuo Iwama will give a colloquium on Friday Sep 18.

Sep 8: Greedy algorithms. Scheduling and shortest paths. Read: Sections 4.1, 4.2, 4.4

Sep 10: The sushi problem and other weighted selection problems. Characterization of weighted selection problems solvable by greedy selection. Read: handout on selection (pdf) (do the exercises!).

Sep 15: Dynamic Programming. Weighted interval selection, line fitting. Read: Beginning of Ch. 6.1-6.3

Sep 17: Maze problem. DP solution to Knapsack. Read sections 6.4 and 6.8.

Sep 22: Bellman-Ford algorithm. Detecting negative cycles in graphs. Application to routing. Read: 6.8,6.9,6.10

Sep 24: Network flows and Cuts. Formulations. Review the slides 07maxcut (first 12) and start reading Ch. 7.

Sep 29, Oct 1: Residual graphs and the augmenting path algorithm. Proof of the Max-flow min-cut theorem. Read: 7.1,7.2

Oct 6: Bipartite matchings, vertex covers, proof that maximum matching = minimum vertex cover. Scaling to give a fast implementation of Ford-Fulkerson algorithm. Read: 7.3,7.5

Oct 8: Circulations, lower bounds on capacities. Applications: disjoint paths, Image segmentation. Read: 7.6, 7.7, 7.10

Oct 13: More applications: project selection and baseball scheduling. Read: 7.11, 7.12

Midterm will be based on all material above.

Oct 15: Review and exercises.

Oct 20: Midterm in Trottier 0060 . Closed book, no notes.

Oct 22,27: Introduction to linear programming. Formulation of wine blending problem and dual. Three outcomes of linear programming. Geometric interpretation. Read: lp_handout.pdf in "hidden" folder, Sections 7.1 and 7.4 and Komei Fukuda's notes Chapter 1.

Oct 29: We worked through an example of the simplex method from scratch. Certificates for unbounded solution and infeasible solution.

Read: lp_handout.pdf section 7.6 (the description is a bit different from what we did in class, but it is equivalent). Also read and Komei Fukuda's notes sections 2.1-2.4.

Nov 3,5: Introduction to NP, NP-complete, NP-hard problems. Polynomial time reductions. Cook's Theorem. Integer programming is NP-hard,

3-SAT is NP-complete. Note that " A ≤

Nov 10,12: NP-completeness reductions. 3-SAT -> IND-SET -> VERTEX COVER -> SET COVER and

3-SAT -> SUBSET-SUM -> PARTITION -> 2-MACHINE SCHEDULING -> KNAPSACK (Decision version)

Read: Section 8.8. Slides 36-37 of 08reductions-poly contain the reduction we did in class from 3-SAT to SUBSET SUM. It is also in Cormen et al. (2nd edition) pp. 1014-6.

Nov 17: Travelling salesman problem case study

Nov 19: Approximation algorithms for Vertex Cover. Read: Text sections 11.4 and 11.6

Nov 24: Approximation algorithms for machine scheduling. We get tighter bounds than those given in the text. Approximation scheme for the Knapsack problem. Read: Text sections 11.1, 11.8.

Nov 26: Local search. Hopfield Networks. Max cut. Read: 12.1, 12.3, 12.4.

Nov 30: Problem session and review.

Dec 16, 2pm Final exam. Covers all above material except Nov. 17 lecture.