Course pages 2013–14

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. Thanks to Nikolaus Blow for pointing out this needed updating.

2013-11-08 Fri (Amortized analysis)

CLRS3: (Revise 6.5), 17.1, 17.3. You may skip 17.2, 17.4.

Handout: pages 1-18.

2013-11-11 Mon (Fibonacci heaps)

CLRS3: 19.1, 19.2.

Handout: pages 17-25.

Microchallenge: CDLL

2013-11-13 Wed (Fibonacci heaps)

CLRS3: 19.2, 19.3, 19.4.

Handout: pages 25-28.

2013-11-15 Fri (vEB trees)

CLRS3: 20.1, 20.2.

Handout: pages 28-33.

Subsequent lectures

CLRS3: 20.2, 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.) 22.2, 22.3, 22.4. (You may skip 22.5.) 23.1, 23.2. 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.) 25.1, 25.3, 26.1, 26.2. (You may skip 25.2.) 26.3. (You may skip 26.4, 26.5, 27.2, 27.3.) 27.1, 33.1, 33.3. (You may skip 33.2, 33.4.)

Handout: pages 33-end.

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.

Lecture handouts

Distributed during the first lecture. It will be to your advantage to bring your course 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.

Information for supervisees

This course supports the experimental Otter system for supervisions.

Information for supervisors

I like to know who is supervising this course, so as to be able to broadcast additional information to the supervisors when appropriate. If you want to be a supervisor for this course, 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 information for supervisors. Note that from this year we'll be using the Otter system for this course.

Microchallenges

CDLL: expired 2013-11-10 Sun 23:59

Heroes:

CDLL visual unit test (for previous heroes only): expires 2013-11-20 Wed 23:59

Additional resources

Student feedback

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.

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.