Advanced Algorithms -- Fall 2011

• 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, scheduling, finance, etc.
• Recommended reading
• Administrivia
• Please form groups of 3 people as soon as possible; announce your groups to Prof. Moret and the TAs using the lcbb dot epfl at gmail dot com gmail address.
• The tests will be 36h take-home, with the PDF file put on this server at noon on Thursday and the solutions due to the gmail address by Friday midnight. The tests will be given on Thursdays October 20, November 17, and December 15. If any of you has a known scheduling conflict, please let Prof. Moret know about it as soon as possible.
• Known absences:
  Oct. 5-8 (Cambridge U.); senior PhD students Vaibhav Rajan and Yu Lin will lecture on Thursday Oct. 6.
  Nov. 12-16 (BIBM, Atlanta); postdoctoral fellow Xiuwei Zhang will lecture on Monday Nov. 14.
• Notetaking schedule
• LaTeX template: please use this template for all homeworks (a separate version will be put on this web site for each of Tests 2 and 3); available are the LaTeX template and the resulting PDF file.

Weekly Schedule

• Week 2:
  The solution sheet for the entrance test is available as a PDF file.
  Homework assignment 1, due next Monday (Oct. 3) by midnight, is available as a PDF file.
  The solutions for Homework assignment 1 are available as a PDF file.
  Notes for Thursday, September 29 (average-case analysis and leftist heaps), are available as a PDF file.
• Week 3:
  Homework assignment 2, due next Monday (Oct. 10) by midnight, is available as a PDF file.
  The solutions for Homework assignment 2 are available as a PDF file.
  Notes for Monday, October 3 (amortized analysis, skew heaps), are available as a PDF file.
  For the amortized analysis of skew heaps themselves, consult this note.
  Notes for Thursday, October 6 (competitive analysis, MTF and paging), are available as a PDF file.
• Week 4:
  Homework assignment 3, due next Monday (Oct. 17) by midnight, is available as a PDF file.
  The solutions for Homework assignment 3 are available as a PDF file.
  A recap of the amortized analysis of splay trees is available as a PDF file.
  Notes for Monday, October 10 (splay trees), are available as a PDF file.
  Notes for Thursday, October 13 (Union-Find, Ackermann's function), are available as a PDF file.
• Week 5:
  Notes for Monday, October 17 (greedy algorithms, MST) are available as a PDF file.
  Notes for Thursday, October 20 (greedy algorithms cont'd) are available as a PDF file.
  No homework this week, because of the test.
  Test 1 is available as a PDF file. The solution sheet for Test 1 is available as a PDF file.
  We received 95 tests. Grades on the tests varied from a low of 5 to a high of 97, with an average of 67 and a median of 74. For MS students only, the grades varied from a low of 5 to a high of 93, with an average of 61 and a median of 63; for PhD students only, the grades varied from a low of 49 to a high of 97, with an average of 79 and a median of 81.
  For MS students, who need a 4 to pass, a passing score is around 60 (a bit below); for PhD students, who need a 5 to pass, a passing score is around 75 (a bit above).
• Week 6:
  Homework assignment 4, due next Monday (Oct. 31) by midnight, is available as a PDF file.
  The solutions for Homework assignment 4 are available as a PDF file.
  Notes for Monday, October 24 (bipartite matching, stable matching, blossoms) are available as a PDF file.
  Notes for Thursday, October 27 (augmenting paths, the V^0.5E algorithm, and intro to network flow) are available as a PDF file.
• Week 7:
  Homework assignment 5, due next Monday (Nov. 7) by midnight, is available as a PDF file.
  The solutions for Homework assignment 5 are available as a PDF file.
  Notes for Monday, October 31 (network flow, the push-relabel algorithm in broad outline) are available as a PDF file.
  Notes for Thursday, November 3 (analysis and proofs for the push-relabel algorithm) are available as a PDF file.
• Week 8:
  Homework assignment 6, due next Monday (Nov. 13) by midnight, is available as a PDF file.
  The solutions for Homework assignment 6 are available as a PDF file.
  Notes for Monday, November 7 (TSP twice around the tree; nearest-neighbor pair in the plane; convex hulls in 2D) are available as a PDF file.
  Notes for Thursday, November 10 (convex hulls: string wrapping, D&C, Graham scan) are available as a PDF file.
• Week 9:
  Notes for Monday, November 14 (randomized algs and their analysis) are available as a PDF file.
  Notes for Thursday, November 17 (Markov chains; the randomized incremental alg. for 3D convex hulls) are available as a PDF file.
  Test 2 is available as a PDF file. The solution sheet for Test 2 is available as a PDF file.
  We received 93 tests. Grades on the tests varied from a low of 43.5 to a high of 100, with an average of 84 and a median of 86. For MS students only, the grades varied from a low of 43.5 to a high of 96, with an average of 79 and a median of 82; for PhD students only, the grades varied from a low of 55 to a high of 100, with an average of 87 and a median of 88.
• Week 10:
  Homework assignment 7, due next Monday (Nov. 28) by midnight, is available as a PDF file.
  The solutions for Homework assignment 7 are available as a PDF file.
  A set of notes on the analysis of the randomized incremental algorithm for 3D convex hulls is available as a PDF file.
  Notes for Monday, November 21 (3D hulls continued, 2D Voronoi polygons, 2D Delaunay triangulations by iterative flipping) are available as a PDF file.
  Notes for Thursday, November 24 (DCEL data structure, correctness and analysis of the 3D incremental convex hull algorithm) are available as a PDF file.
  
• Week 11:
  Homework assignment 8, due next Monday (Dec. 5) by midnight, is available as a PDF file.
  The solutions for Homework assignment 8 are available as a PDF file.
  Notes for Monday, November 28 (smallest enclosing disk, moving from D&C to DP) are available as a PDF file.
  Notes for Thursday, December 1 (DP: Fibonacci numbers, Floyd's algorithm, pairwise sequence alignment, beginning of Hidden Markov Models) are available as a PDF file.
• Week 12:
  Homework assignment 9, due next Monday (Dec. 12) by midnight, is available as a PDF file.
  The solutions for Homework assignment 9 are available as a PDF file.
  Proofs for the correctness of the various HMM algorithms discussed in class (Viterbi, forward, and backward algorithms) can be found in this note.
  Notes for Monday, December 5 (HMMs, Viterbi, forward, and backward algorithms, D&C to reduce space in DP) are available as a PDF file.
  Notes for Thursday, December 8 (DP on trees; randomized fingerprints for equality testing) are available as a PDF file.
• Week 13:
  No homework, as this is a test week.
  The solution sheet for the third test (given in-class and available here) is available as a PDF file.
  We received 90 tests. Grades on the tests varied from a low of 0 to a high of 85.5, with an average of 38 and a median of 41. For MS students only, the grades varied from a low of 12.5 to a high of 75.5, with an average of 36 and a median of 33; for PhD students only, the grades varied from a low of 0 to a high of 85.5, with an average of 41 and a median of 39. We curved these grades to put them on a scale comparable to that of the take-home exams: scores of 70 or better (for PhD students) or 65 or better (for MS students) became 6.0, scores below these but above 55 became 5.5, scores between 46 and 55 became 5.0, scores between 37 and 45 became 4.5, scores between 31 and 36 became 4.0, those betweeen 27 and 30 became 3.5, those between 21 and 26 became 3.0, those between 16 and 20 became 2.5, those between 10 and 15 became 2.0, and those below 10 became 1.0.
• Week 14:
  No exercise session on Friday.

Final grade distribution for MS students:
6.0: 4 students
5.5: 5 students
5.0: 11 students
4.5: 15 students
4.0: 12 students
3.5: 4 students
3.0: 5 students
2.5: 4 students
2.0: 1 student
NA: 1 student
Thus 47 of 62 students pass the course -- a pass rate of 76%.