Course pages 2011–12
lecturer: Dr Frank
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
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.
You may skip 17.2, 17.4
From last year: revise 6.5 and binomial heaps (problem 19-2) if you forgot them.
21.1, 21.2, 21.3, 22.1, 22.2, 22.3
You may skip 21.4, 22.5
22.4, 23.1, 23.2
24.1, 24.3, 24.5
You may skip 24.2, 24.4
You may skip 25.2
26.1, 26.2, 26.3
You may skip 26.4, 26.5
You may skip 27.2, 27.3
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.
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.
lg lg nanochallenge (expired)
MST microchallenge (expired)
2011-11-04 microchallenge (circular doubly-linked list)
|Dylan Ede (8 mins past the deadline :-))|
2011-11-09 nanochallenge (lg lg x)
|Tom Smith (7 mins after the lecture!!!)|
2011-11-16 (spontaneous initiative, not a microchallenge)
2011-11-25 microchallenge (MST)
|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."
Here is the animation that I used in lectures (click for multi-page pdf).
Visualization of graphs and other linked data structures
Negative line numbers are counted from the bottom of the page. Top line (excluding headers) is 1. Bottom line (excluding footers) is -1.
|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)
|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|
|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.