home search a-z help
University of Cambridge Computer Laboratory
Data Structures and Algorithms
Computer Laboratory > Course material 2005-06 > Data Structures and Algorithms

Data Structures and Algorithms
2005-06

Principal lecturer: Dr Frank Stajano
Taken by: Part IB, Part II (General), Diploma
Syllabus
Past exam questions (not always relevant as the syllabus changed over the years)

Hall of fame

My smartest students for this course

DateNameClaim to fame
Microchallenge 1 (insertion sort)
2005-11-09Robin Message Overall winner of microchallenge 1.
2005-11-09Andrew Lewis, Christian Richardt, David Emett, Hugh Warrington, Justin Salamon, James Bridge, Michael Dodson, Philip Bielby, Teanlorg Chan, Tung Jin ChewSubmitted entries that passed microchallenge 1.
2005-11-09jts, kb, mtw, pjt, prm, sbw, sr, sxpz, twk, wctAlso took up microchallenge 1. Even if their entries technically didn't pass the challenge, it was still a smart move for them to write a working insertion sort program, and they are a step ahead of those who didn't.
Microchallenge 2 (merge sort)
2005-11-16David EmettOverall winner of microchallenge 2.
2005-11-16Andrew Lewis, Christian Richardt, Hugh Warrington, Justin Salamon, James Bridge, Philip Bielby, Robin Message, Teanlorg Chan, Tung Jin ChewSubmitted entries that passed microchallenge 2.
2005-11-09djs, jts, kb, lec, md, prm, sbwAlso took up microchallenge 2, which makes them smarter than those who didn't.
Microchallenge 3 (Professor Bunyan)
2005-11-16David EmettOverall winner of microchallenge 3.
2005-11-16Philip Bielby, Stephen Williams, Matthew Wightman, James Bridge, Colin Howe, Kay Henning Brodersen, Jonathan Senior, Andrew LewisSubmitted entries that passed (or almost passed) microchallenge 3.
2005-11-16md, jjsAlso took up microchallenge 3, which makes them smarter than those who didn't.
Microchallenge 4 (heap sort)
2005-11-18Rowan HillOverall winner of microchallenge 4.
2005-11-18Andrew Lewis, David Emett, Tung Jin ChewSubmitted entries that almost passed microchallenge 4.
Microchallenge 5 (BST insert and prettyprint)
2005-11-21Andrew Lewis and David EmettEx-aequo winners of microchallenge 5.
2005-11-21Tung Jin ChewAlmost won microchallenge 5.
2005-11-21twkAlso took up microchallenge 5.

Helpful typo spotters

DateNamePageLineErrataCorrige
2005-10-05author9-1perhapsperhaps.
2005-10-07Alastair Beresford923Sometimes is notSometimes it is not
2005-10-07Alastair Beresford1119On chipOn-chip
2005-10-12author5-1copy of the firstcopy of the first.
2005-10-16author261is already order.is already ordered.
2005-10-25author2614generalisegeneralize
2005-10-25author27-14not be the amountnot by the amount
2005-10-25author27-13initialiseinitialize
2005-10-26author2592k and 2k+12k+1 and 2k+2 [This was not a mistake in itself, for a 1-based array, but I prefer zero-based indexing for consistency with footnote 3 on page 23.]
2005-10-26author2512item at location 1item at location 0 [See related entry about 0-based vs 1-based indexing.]
2005-11-06author4716graph2graph2.
2005-11-15author526boundbounded
2005-11-15author527boundbounded
2005-11-15author528the whole algorithmthe number of such steps
2005-11-16Alastair Beresford499stilstill
2005-11-16Alastair Beresford56-9section 7section 4.6, footnote 7
2005-11-16Alastair Beresford58-3eforteffort

Negative lines are counted from the bottom of the page.


Additional material

Example traces of the execution of several algorithms were presented in the lectures. You are warmly encouraged to replicate those outputs with your own programs, but please don't email me the results; for fame and glory, submit your code via the microchallenge server.

In Lecture 5 (2005-10-26) I showed two extracts from Bob Cringely's "Triumph of the nerds" (originally a 3-part TV documentary). Full transcripts are available free of charge and the video, in DVD or VHS, can be bought online (more expensive than a Hollywood blockbuster, but longer and well worth the money). The full video was shown on 2005-11-23 in Lecture Theatre 2, from 1730 onwards.