Algorithms I 2008–09
Principal lecturer: Dr Frank Stajano
Taken by: Part IA CST, Part IA NST, Part I PPS
Syllabus
Past exam questions
Past exam questions can be found
under Algorithms
but also, for historical reasons,
under Data
Structures and Algorithms (the parent course for both Algorithms I
and Algorithms II). Since these courses have been restructured several
times over the years, be sure to select questions dealing with topics
covered in this year's syllabus.
Assessed exercises (required)
The only way to really learn about algorithms and data structures
is to program them yourself. Every Friday, for three Fridays, a new
challenge will appear on this page. You will have to submit your
solution (via email) by the following Wednesday in order to receive
your tick.
 Tick 1 (issued 20090424, due 20090429)
 Tick 2 (issued 20090501, due 20090506)
 Tick 3 (issued 20090508, due 20090513)
Lecture handouts
A handout, covering the whole course, will be distributed during
the first lecture. Bringing your handout to every lecture, together
with a paper notebook with nondetachable pages and a few coloured
pens, will be to your advantage. Further printed copies of the handout
are available from the student administration
office. An electronic
copy is available (also
in large
print): please do not print it again yourself and please do not
circulate it outside cam.ac.uk. Note that you will also need a
textbook and that the handout is not a substitute for one.
Errata corrige
If you find any errors in the handout, please email me and I'll
credit you here and in the next edition.
Page  Line  Errata  Corrige  Found on  by 

12  9 of
insertsort  len(a)1  len(a)2  20090423  author, but also
during lecture 1 by an enterprising student in the front row before I
had actually published this correction; if you are him, tell me your
name and I'll credit you here!
 20  7  Θ(n lg n)  O(n lg n)  20090427  author
 22  22 of binaryInsertSort  for j from i to k1:  for j from k1 to i:  20090428  Rasmus Kyng
 23  12 of bubblesort  len(a)1  len(a)2  20090427  Chloë Brown
 23  13 of bubblesort  a[k1]  a[k+1]  20090427  Chloë Brown
 24  14 of mergesort  return a copy of a  return a  20090428  Rob Harle
 24  26 of mergesort  a3[i3]  a3[i3++]  20090428  Rob Harle
 28  big formula in the middle of the page  c()  f() (replace all three occurrences)  20090428  author
 32  29 to 35 of heapSort listing  k  i (replace all
five occurrences)  20090430  author
 n/a  n/a  I wrongly said in lecture 2 that you could stop
mergesort early and do a final pass over the quasisorted
array.  This trick won't work with mergesort because at each pass of
merge the worstcase distance between the entries and their ideal
destination might approximately double.  20090427  another smart
student (who?) during lecture 2

