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 2009-04-24, due 2009-04-29)
- Tick 2 (issued 2009-05-01, due 2009-05-06)
- Tick 3 (issued 2009-05-08, due 2009-05-13)
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 non-detachable 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 | 2009-04-23 | 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) | 2009-04-27 | author
| 22 | 22 of binaryInsertSort | for j from i to k-1: | for j from k-1 to i: | 2009-04-28 | Rasmus Kyng
| 23 | 12 of bubblesort | len(a)-1 | len(a)-2 | 2009-04-27 | Chloë Brown
| 23 | 13 of bubblesort | a[k-1] | a[k+1] | 2009-04-27 | Chloë Brown
| 24 | 14 of mergesort | return a copy of a | return a | 2009-04-28 | Rob Harle
| 24 | 26 of mergesort | a3[i3] | a3[i3++] | 2009-04-28 | Rob Harle
| 28 | big formula in the middle of the page | c() | f() (replace all three occurrences) | 2009-04-28 | author
| 32 | 29 to 35 of heapSort listing | k | i (replace all
five occurrences) | 2009-04-30 | author
| n/a | n/a | I wrongly said in lecture 2 that you could stop
mergesort early and do a final pass over the quasi-sorted
array. | This trick won't work with mergesort because at each pass of
merge the worst-case distance between the entries and their ideal
destination might approximately double. | 2009-04-27 | another smart
student (who?) during lecture 2
|
|