Course pages 2012–13
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.
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.
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.
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.
|(Vlad Tataranu, 3.5 h past the deadline)|
Here is the animation that I used in lectures (click for multi-page pdf).
Visualization of graphs and other linked data structures
Elementary graph algorithms
Minimum spanning trees
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.
Negative line numbers are counted from the bottom of the page. Top line (excluding headers) is 1. Bottom line (excluding footers) is -1.
|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||2012-11-06||author|
|37||9||2012-11-19||Miklós András Danka|
|37||11||2012-11-19||Miklós András Danka|
|38||1-10||whole listing||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.