Course pages 2011–12
Algorithms II
2011–2012
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.
Taken by: Part IB
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.
2011-11-04 Fri
17.1, 17.3
You may skip 17.2, 17.4
From last year: revise 6.5 and binomial heaps (problem 19-2) if you forgot them.
2011-11-07 Mon
19.1, 19.2
2011-11-09 Wed
19.3, 19.4
2011-11-11 Fri
20.1, 20.2
2011-11-14 Mon
20.3
2011-11-16 Wed
21.1, 21.2, 21.3, 22.1, 22.2, 22.3
You may skip 21.4, 22.5
2011-11-18 Fri
22.4, 23.1, 23.2
2011-11-21 Mon
24.1, 24.3, 24.5
You may skip 24.2, 24.4
2011-11-23 Wed
25.1, 25.3
You may skip 25.2
2011-11-25 Fri
26.1, 26.2, 26.3
You may skip 26.4, 26.5
2011-11-28 Mon
27.1
You may skip 27.2, 27.3
2011-11-30 Wed
33.1, 33.2, 33.3
You may skip 33.4
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
This year the course has two new lectures. You want the new guide. Contact lecturer for access, stating your name, your CRSID and, if you are a student, your PhD supervisor.
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
2011-11-04 Fri
CDLL (expired)
2011-11-09 Wed
lg lg nanochallenge (expired)
2011-11-25 Fri
MST microchallenge (expired)
My heroes!
2011-11-04 microchallenge (circular doubly-linked list)
Timothy Goh |
James King |
David Brazdil |
Eduardo Munoz |
Lewis Brown |
Rory McCann |
Thomas Chetwin |
Dylan Ede (8 mins past the deadline :-)) |
2011-11-09 nanochallenge (lg lg x)
Tom Smith (7 mins after the lecture!!!) |
Thomas Chetwin |
Timothy Goh |
Rolandas Glotnis |
David Brazdil |
James Morley |
2011-11-16 (spontaneous initiative, not a microchallenge)
Szymon Sidor, for suggesting and implementing a non-recursive alternative (Kahn's algorithm) for topological sort. There is pseudocode on Wikipedia.
2011-11-25 microchallenge (MST)
Timothy Goh |
Lewis Brown |
Max Spencer (Prim only) |
"I know my submission is totally late and you might not even have read these emails, but I am so glad I figured it out I just wanted to send it anyway! This is the best feeling, this is why I love programming."
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.
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 |
---|---|---|---|---|---|
8 | pseudocode line 29 | Payload p; | Data payload; | 2011-12-03 | Heidi Howard |
15 | -4 | cost of Dijkstra is |V| times | cost of Dijkstra is dominated by |V| times | 2011-11-03 | author |
19 | -3 | void decreaseKey(FibNode n, int delta) | void decreaseKey(FibNode n, int newKey) | 2011-12-03 | Heidi Howard |
20 | 1 | Decrease the key of node n by delta | Decrease the key of node n to newKey | 2011-12-03 | Heidi Howard |
20 | 2 | and delta is non-negative | and newKey < n.key | 2011-12-03 | Heidi Howard |
20 | 5 | Decrease that key by the stated amount | Decrease n.key to the new value | 2011-12-03 | Heidi Howard |
20 | 21 | with the largest possible delta (conceptually decreasing the key to -infinity) | with a newKey of -infinity | 2011-12-03 | Heidi Howard |
21 | -16 | given heap in a given state | heap with n nodes | 2011-11-03 | author |
21 | -16, -14, -13, -13, -13 | d | d(n) | 2011-11-03 | author |
21 | -10 | O(d) = O(lg n) | d(n) = O(lg n) | 2011-11-03 | author |
21 | -3 | void decreaseKey(FibNode n, int delta) | void decreaseKey(FibNode n, int newKey) | 2011-12-03 | Heidi Howard |
22 | 13 | This is still a constant, | This is still a constant with respect to n, | 2011-11-03 | author |
22 | -14 | in a Fibonacci heap | in an n-node Fibonacci heap | 2011-11-03 | author |
24 | 8 | were the fastest | were the asymptotically fastest | 2011-11-01 | author |
24 | 20 | set: insert() | set (except that we disregard satellite data): member(), insert() | 2011-11-01 | author |
25 | -6 | the total cost is O(1) | the total cost is O(√ u) | 2011-11-11 | author |
30 | -26 to -24 | If it's not the base case, we set the appropriate summary bit (direct access, therefore constant time) and we recursively insert the key into the correct cluster. | If the node is empty, insert directly at constant cost. Otherwise, insert into both cluster and summary. However only one of these two calls is recursive: if the cluster was empty, insertion into cluster has constant cost and insertion into summary is recursive; otherwise, insertion into cluster is recursive and insertion into summary is not needed because it's already marked as non-empty. | 2011-11-14 | author |
32 | lines 10 and 11 of first pseudocode block | PRECONDITION: there exists a set containing x and a different one containing y. | PRECONDITION: x != y. | 2011-12-27 | Simon Blessenohl |
42 | lines 11 to 14 of Kruskal listing |
for edge in E: if D.findSet(edge.start) != D.findSet(edge.end): A.append(edge) D.union(edge.start, edge.end) | for edge in E: startSet = D.findSet(edge.start) endSet = D.findSet(edge.end) if startSet != endSet: A.append(edge) D.union(startSet, endSet) | 2011-12-27 | Simon Blessenohl |
45 | -15 to -14 | equal to the number of vertices in the graph | eqal to the maximum possible length of a shortest path, |V|-1 | 2011-12-16 | Tom Sparrow |
47 | -8 | cost of decreaseKey. | cost of decreaseKey(). | 2011-11-01 | author |
59 | 5 | computation on on | computation on | 2011-11-19 | author |
59 | 15 | >= | ≥ | 2011-11-19 | author |
61 | 13 | (and the next vertex may or may not be a source at that point) | (and the next vertex will be a source at that point) | 2011-11-28 | Ben Thorner |
63 | -4 | Extrapolating to 256 processors | Extrapolating to 512 processors | 2011-11-19 | author |
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. Recursive thanks also to Simon Iremonger for finding a further error, now corrected, in the Errata Corrige itself.