Advanced Algorithms -- Fall 2009

• Administrative details
• Goals: To learn the main techniques for analyzing and for designing algorithms, while also building a repertory of basic algorithmic solutions to problems in graph theory, linear algebra, geometry, biology, finance, etc.
• Prerequisites: Basic data structures (arrays, lists, stacks, queues, trees) and algorithms (binary search; sorting, including mergesort; graph connectivity); basic discrete mathematics (proof methods, induction, enumeration and counting, basic graph theory); data abstraction (as in OO design).
• Topics: Algorithm analysis techniques: worst-case and amortized, average-case, randomized, competitive. Basic algorithm design techniques: greedy, iterative, incremental, divide-and-conquer, dynamic programming, and randomization. Specific problems from graph theory, numerical algebra, scheduling, computational geometry, computational biology, computational finance, etc. For details, see the weekly schedule below.
• Recommended Reading

Weekly Schedule

• Week 1 (Sept. 17 -- see note in administrative details): Introduction to the course; algorithm analysis: a.e. and i.o. asymptotics, notation, recurrence relations and their solution.
  The entrance examination and its solution are posted.
• Week 2 (Sept. 24): Review of some asymptotics and recurrence work; introduction to amortized analysis with potential functions.
  Solutions for Homework 1 are posted. Lecture notes are posted.
• Week 3 (Sept. 28 and Oct. 1): Amortized analysis; meldable heaps, splay trees, and union-find; if time allows, lazy data structuring.
  Solutions for Homework 2 are posted. Lecture notes for both days are posted.
• Week 4 (Oct. 5 and Oct. 8): Competitive analysis, average-case analysis and randomization; review of analysis techniques and implications for design.
  Solutions for Homework 3 are posted. Lecture notes for both days are posted.
• Week 5 (Oct. 12 and Oct. 15): Example of competitive analysis: the move-to-front heuristic. Introduction to design techniques for algorithms: greedy, iterative, divide-and-conquer, dynamic programming, and randomized strategies, exhaustive search and bounding. Greedy algorithms in general.
  Lecture notes for both days are posted.
  Test 1 and solutions are posted.
  We received 66 tests in all; grades (on a scale of 100) varied from a low of 3 to a high of 95, with an average of 70; 21 students received a grade of 80 or better and 38 students received a score of 70 or better.
• Week 6 (Oct. 19 and Oct. 22): Convex hulls. Iterative improvement algorithms, including 2-opt for the TSP problem; matching in bipartite graphs (marriage and assignment problems, augmenting paths, and algorithms; also the stable marriage problem).
  Solutions for Homework 4 are posted. Lecture notes for both days are posted.
  
• Week 7 (Oct. 26 and Oct. 29): Matching: the Koenig-Hall theorem and duality between matching and vertex cover; blossoms in general matching. Network flow: augmenting flows, the min-cut max-flow theorem, blocking flows, and preflows; the push-relabel algorithm.
  Solutions for Homework 5 are posted. Lecture notes for both days are posted.
  
• Week 8 (Nov. 2 and Nov. 5): Analysis and proofs for the push-relabel algorithm. Divide-and-conquer algorithms: convex hulls revisited, the nearest-neighbor pair in 2D, maxima in high dimensions.
  Solutions for Homework 6 are posted. Lecture notes for both days are posted.
  
• Week 9 (Nov. 9 and Nov. 12): Divide-and-conquer and sweep methods in computational geometry: Voronoi diagrams, trapezoidal decompositions of the plane.
  Lecture notes for both days are posted.
  Test 2 and solutions are posted.
  We received 67 tests in all; grades (on a scale of 100) varied from a low of 36 to a high of 98, with an average of 74 (30 PhD students averaged 77.5, 37 MS students averaged 68); 63 students scored at least 50, 56 students scored at least 60, 42 scored at least 70, 25 scored at least 80, and 10 scored at least 90.
• Week 10 (Nov. 16 and Nov. 19): Randomized incremental algorithm for trapezoidal decomposition. Introduction to dynamic programming; dynamic programming in computational biology: pairwise string alignment.
  Solutions to Homework 7 are posted. Lecture notes for both days are posted.
  
• Week 11 (Nov. 23 and Nov. 26): Dynamic programming for pairwise string alignment (global and local), reduction to linear space and to banded matrices; on trees (the small parsimony problem); and for HMMs (Viterbi's algorithm). Randomized algorithms: generalities, fingerprinting for matrix multiplication.
  Lecture notes for both days are posted.
  
• Week 12 (Nov. 30 and Dec. 3): Randomized algorithms: more fingerprinting, one- and two-sided tests (RPP and ZPP), amplification (BPP vs. PP). Randomization in sampling and counting: the stable marriage problem revisited, min-cut revisited. The probabilistic method: MaxSAT, expander graphs.
  Lecture notes for both days are posted.
• Week 13 (Dec. 7 and Dec. 10): Interactive proofs and zero knowledge.
  Lecture notes for both days are posted.
• Week 14 (Dec. 14 and Dec. 17): The PCP (probabilistically checkable proofs) theorem, gap amplification, and inapproximability results.
  Lecture notes for Dec. 14 are available.
  Test 3 and solutions are posted.
  We received 66 tests in all; grades (on a scale of 100) varied from a low of 23 to a high of 95, with an average of 76 (30 PhD students scored from 55 to 95 and averaged 82, 36 MS students scored from 23 to 95 and averaged 71.2); 64 students scored at least 50, 60 students scored at least 60, 47 scored at least 70, 32 scored at least 80, and 8 scored at least 90.

Semester Grades: Summary