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
Date | Name | Claim to fame
|
---|
Microchallenge 1 (insertion sort)
| 2005-11-09 | Robin Message | Overall winner of
microchallenge 1.
| 2005-11-09 | Andrew Lewis, Christian Richardt, David Emett,
Hugh Warrington, Justin Salamon, James Bridge, Michael Dodson, Philip
Bielby, Teanlorg Chan, Tung Jin Chew | Submitted entries that passed
microchallenge 1.
| 2005-11-09 | jts, kb, mtw, pjt, prm, sbw, sr, sxpz, twk,
wct | Also 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-16 | David Emett | Overall winner of
microchallenge 2.
| 2005-11-16 | Andrew Lewis, Christian Richardt, Hugh
Warrington, Justin Salamon, James Bridge, Philip Bielby, Robin
Message, Teanlorg Chan, Tung Jin Chew | Submitted entries that passed
microchallenge 2.
| 2005-11-09 | djs, jts, kb, lec, md, prm, sbw | Also took up
microchallenge 2, which makes them smarter than those who didn't.
| Microchallenge 3 (Professor Bunyan)
| 2005-11-16 | David Emett | Overall winner of
microchallenge 3.
| 2005-11-16 | Philip Bielby, Stephen Williams, Matthew
Wightman, James Bridge, Colin Howe, Kay Henning Brodersen, Jonathan
Senior, Andrew Lewis | Submitted entries that passed (or almost
passed) microchallenge 3.
| 2005-11-16 | md, jjs | Also took up microchallenge 3, which
makes them smarter than those who didn't.
| Microchallenge 4 (heap sort)
| 2005-11-18 | Rowan Hill | Overall winner of
microchallenge 4.
| 2005-11-18 | Andrew Lewis, David Emett, Tung Jin
Chew | Submitted entries that almost passed microchallenge 4.
| Microchallenge 5 (BST insert and prettyprint)
| 2005-11-21 | Andrew Lewis and David
Emett | Ex-aequo winners of microchallenge 5.
| 2005-11-21 | Tung Jin Chew | Almost won
microchallenge 5.
| 2005-11-21 | twk | Also took up microchallenge 5.
|
Helpful typo spotters
Date | Name | Page | Line | Errata | Corrige
|
---|
2005-10-05 | author | 9 | -1 | perhaps | perhaps.
| 2005-10-07 | Alastair Beresford | 9 | 23 | Sometimes is
not | Sometimes it is not
| 2005-10-07 | Alastair Beresford | 11 | 19 | On
chip | On-chip
| 2005-10-12 | author | 5 | -1 | copy of the first | copy
of the first.
| 2005-10-16 | author | 26 | 1 | is already order. | is already ordered.
| 2005-10-25 | author | 26 | 14 | generalise | generalize
| 2005-10-25 | author | 27 | -14 | not be the amount | not by the amount
| 2005-10-25 | author | 27 | -13 | initialise | initialize
| 2005-10-26 | author | 25 | 9 | 2k and 2k+1 | 2k+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-26 | author | 25 | 12 | item at location 1 | item
at location 0 [See related entry about 0-based vs 1-based
indexing.]
2005-11-06 | author | 47 | 16 | graph2 | graph2.
| 2005-11-15 | author | 52 | 6 | bound | bounded
| 2005-11-15 | author | 52 | 7 | bound | bounded
| 2005-11-15 | author | 52 | 8 | the whole algorithm | the
number of such steps
| 2005-11-16 | Alastair Beresford | 49 | 9 | stil | still
| 2005-11-16 | Alastair Beresford | 56 | -9 | section 7 | section 4.6, footnote 7
| 2005-11-16 | Alastair Beresford | 58 | -3 | efort | effort
|
| |
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.
|