Computer Laboratory

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

Heroes:

proto-vEB delete: expired 2012-11-18 Sun 23:59

Hero:

 Leonhard Markert

Hero:

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.

PageLineErrataCorrigeFound onby
29-3footnote 21delete the footnote: it's wrong (cfr the previous one) 2012-11-06author
3016-17but 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-19Miklós András Danka and his supervision students
32line 7 of listing```self.summary.min( )````self.summary.min()` 2012-11-06author
379`void union````Handle union```2012-11-19Miklós András Danka
3711```merge those sets into one.``````merge those sets into one and return the handle of the new set.```2012-11-19Miklós András Danka
381-10whole listing```d = DisjointSet()h0 = d.makeSet(x0)h1 = d.makeSet(x1)h0 = d.union(h0, h1)h2 = d.makeSet(x2)h0 = d.union(h0, h2)h3 = d.makeSet(x3)h0 = d.union(h0, h3)h4 = d.makeSet(x4)h0 = d.union(h0, h4)```2012-11-19Mikló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.

• © 2012 Computer Laboratory, University of Cambridge
Information provided by Dr Frank Stajano