Computer Laboratory

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).

Fibonacci heap execution trace

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.

PageLineErrataCorrigeFound onby
8pseudocode line 29Payload p;Data payload;2011-12-03Heidi Howard
15-4cost of Dijkstra is |V| timescost of Dijkstra is dominated by |V| times2011-11-03author
19-3void decreaseKey(FibNode n, int delta)void decreaseKey(FibNode n, int newKey)2011-12-03Heidi Howard
201Decrease the key of node n by deltaDecrease the key of node n to newKey2011-12-03Heidi Howard
202and delta is non-negativeand newKey < n.key2011-12-03Heidi Howard
205Decrease that key by the stated amountDecrease n.key to the new value2011-12-03Heidi Howard
2021with the largest possible delta (conceptually decreasing the key to -infinity)with a newKey of -infinity2011-12-03Heidi Howard
21-16given heap in a given stateheap with n nodes2011-11-03author
21-16, -14, -13, -13, -13dd(n)2011-11-03author
21-10O(d) = O(lg n)d(n) = O(lg n)2011-11-03author
21-3void decreaseKey(FibNode n, int delta)void decreaseKey(FibNode n, int newKey)2011-12-03Heidi Howard
2213This is still a constant,This is still a constant with respect to n,2011-11-03author
22-14in a Fibonacci heapin an n-node Fibonacci heap2011-11-03author
248were the fastestwere the asymptotically fastest2011-11-01author
2420set: insert()set (except that we disregard satellite data): member(), insert()2011-11-01author
25-6the total cost is O(1)the total cost is O(√ u)2011-11-11author
30-26 to -24If 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-14author
32lines 10 and 11 of first pseudocode blockPRECONDITION: there exists a set containing x and a different one containing y.PRECONDITION: x != y.2011-12-27Simon Blessenohl
42lines 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-27Simon Blessenohl
45-15 to -14equal to the number of vertices in the grapheqal to the maximum possible length of a shortest path, |V|-12011-12-16Tom Sparrow
47-8cost of decreaseKey.cost of decreaseKey().2011-11-01author
595computation on oncomputation on2011-11-19author
5915>=2011-11-19author
6113(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-28Ben Thorner
63-4Extrapolating to 256 processorsExtrapolating to 512 processors2011-11-19author

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.

Valid XHTML 1.0 Transitional