Course pages 2012–13
Algorithms II
Principal
lecturer: Dr Frank
Stajano
Email to the address frank.stajano--algs2 at cl cam
ac uk (a special address containing two consecutive hyphens) will be
given priority over that sent to other addresses.
Syllabus
The official syllabus has its own page. More accurately, here is what we actually did in lectures and is considered examinable, with reference to CLRS3 and mentioning any book sections you may skip from the relevant chapters.
2012-11-02 Fri (Amortized analysis)
CLRS3: (Revise 6.5), 17.1, 17.3. You may skip 17.2, 17.4.
Handout: pages 1-17.
2012-11-05 Mon (Fibonacci heaps)
CLRS3: 19.1, 19.2.
Handout: pages 17-22.
Microchallenge: CDLL
2012-11-07 Wed (Fibonacci heaps)
CLRS3: 19.2, 19.3, 19.4.
Handout: pages 22-27.
2012-11-09 Fri (vEB trees)
CLRS3: 20.1, 20.2.
Handout: pages 27-31.
2012-11-12 Mon (vEB trees)
CLRS3: 20.2, 20.3.
Handout: pages 31-35.
2012-11-14 Wed (vEB trees, disjoint sets, graphs)
CLRS3: 20.3, 21.1, 21.2, 21.3, 22.1. You may skip 21.4 and the proof of theorem 21.1 in section 21.2.
Handout: pages 35-43.
Microchallenge: proto-vEB delete
2012-11-16 Fri (Elementary graph algorithms)
CLRS3: 22.2, 22.3, 22.4. You may skip 22.5.
Handout: pages 43-47.
2012-11-19 Mon (Minimum Spanning Trees)
CLRS3: 23.1, 23.2
Handout: pages 47-51.
2012-11-21 Wed (Single source shortest paths)
CLRS3: 24.0 (i.e. don't skip all that longer-than-usual intro stuff), 24.1, 24.3. You may skip 24.2, 24.4, 24.5.
Handout: pages 52-56.
2012-11-23 Fri (All pairs shortest paths; flow networks)
CLRS3: 25.1, 25.3, 26.1, 26.2. You may skip 25.2.
Handout: pages 57-63.
Microchallenge: determinacy race
2012-11-26 Mon (Bipartite graph matchings; parallel algorithms)
CLRS3: 26.3, 27.1. You may skip 26.4, 26.5, 27.2, 27.3.
Handout: pages 63-69.
2012-11-28 Wed (Parallel algorithms; geometric algorithms)
CLRS3: 27.1, 33.1, 33.3. You may skip 33.2, 33.4.
Handout: pages 69-80.
Past exam questions
Questions can be found under Algorithms II but also, for historical reasons, under Data Structures and Algorithms (the parent course for both Algorithms I and Algorithms II); if you pick from the latter set, be sure to select questions dealing with topics covered in this year's syllabus.
Information for supervisors
I like to know who is supervising this course. If you are, first of all thank you. Second, please drop me an email, stating your name, your CRSID and, if you are a student, your PhD supervisor. I will then give you access to the supervisor's guide.
Lecture handouts
Distributed during the first lecture. It will be to your advantage to bring your handout to every lecture, together with a notebook with non-detachable pages and a few coloured pens. Further printed copies of the handout are available from the student administration office. An electronic copy is also available: please do not print it again yourself and please do not circulate it outside cam.ac.uk.
Microchallenges
CDLL: expired 2012-11-11 Sun 23:59
Heroes:
| Leonhard Markert |
| Munraj Vadera |
| Matthew Ireland |
| (Vlad Tataranu, 3.5 h past the deadline) |
proto-vEB delete: expired 2012-11-18 Sun 23:59
Hero:
| Leonhard Markert |
determinacy race: expired 2012-11-25 Sun 23:59
Hero:
| Alex Chadwick |
Additional resources
Fibonacci heaps
The original paper on Fibonacci heaps is available from the ACM digital library (or cached).
Here is the animation that I used in lectures (click for multi-page pdf).
Visualization of graphs and other linked data structures
Worth becoming familiar with DOT and Graphviz; then, when you write programs to practice what you study in this course, with modest additional effort you can neatly display what goes on inside.
Elementary graph algorithms
My little animations of breadth-first search, depth-first search and DAG linearization (and I guess there are a few smart people among you who will write much prettier ones).
Minimum spanning trees
My little animations of Kruskal and Prim's algorithms (same comment as above).
Student feedback
In order to understand whether the lectures matched the expectations of the audience, I collected anonymous student feedback halfway through the course using this form, which 34 students were kind enough to fill in. I find it more useful to collect feedback while the course is still running, rather than just at the end, so as to give current students a chance to benefit from any improvements that might result from their comments. My aim is obviously to learn how to make the bright green bar the longest in all the histograms!
At the end of the course I collected student feedback again using this form. Although with fewer respondents, we can see small improvements in the ratings of my presentation; I am grateful for all the constructive feedback and I am happy that a fair proportion of the students appreciated and enjoyed the course as much as I did, as indicated by their comments and particularly the final histogram, where three quarters of the class (20 out of 27) gave the highest score to the happiness question.
The department also collects student feedback using an online system but the return rate is usually lower and, with the current system, I am not aware of a URL showing the results.
Errata corrige
Negative line numbers are counted from the bottom of the page. Top line (excluding headers) is 1. Bottom line (excluding footers) is -1.
| Page | Line | Errata | Corrige | Found on | by |
|---|---|---|---|---|---|
| 29 | -3 | footnote 21 | delete the footnote: it's wrong (cfr the previous one) | 2012-11-06 | author |
| 30 | 16-17 | but whose values are the summary bits of the children of n. | but whose values are the indices of the children of n that are not empty. | 2012-11-19 | Miklós András Danka and his supervision students |
| 32 | line 7 of listing | self.summary.min(
) | self.summary.min()
| 2012-11-06 | author |
| 37 | 9 | void union | Handle
union | 2012-11-19 | Miklós András Danka |
| 37 | 11 | merge those sets into
one. | merge those sets into one and return the
handle of the new set. | 2012-11-19 | Miklós András Danka |
| 38 | 1-10 | whole listing | d =
DisjointSet() | 2012-11-19 | Miklós András Danka |
If you find any more errors, please mail them to me and I'll credit you here and in the next version of the handout.