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 takehome, 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. 58 (Cambridge U.); senior PhD students Vaibhav Rajan
and Yu Lin will lecture on Thursday Oct. 6.
Nov. 1216 (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 (averagecase 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 (UnionFind, 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.5}E
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 pushrelabel
algorithm in broad outline) are available as a
PDF file.
Notes for Thursday, November 3 (analysis and proofs for the
pushrelabel 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; nearestneighbor 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 inclass 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 takehome 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 PhD students:
6.0: 4 students
5.5: 4 students
5.0: 13 students
4.5: 5 students
4.0: 2 students
3.5: 3 students
3.0: 2 students
Thus 22 students meet their respective programs' requirements, while 11
do not  a pass rate of 67%.
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%.