Computer Laboratory > Teaching > Course material 2008–09 > Algorithms I

 

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.

PageLineErrataCorrigeFound onby
129 of insertsortlen(a)-1len(a)-22009-04-23author, 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!
207Θ(n lg n)O(n lg n)2009-04-27author
2222 of binaryInsertSortfor j from i to k-1:for j from k-1 to i:2009-04-28Rasmus Kyng
2312 of bubblesortlen(a)-1len(a)-22009-04-27Chloë Brown
2313 of bubblesorta[k-1]a[k+1]2009-04-27Chloë Brown
2414 of mergesortreturn a copy of areturn a2009-04-28Rob Harle
2426 of mergesorta3[i3]a3[i3++]2009-04-28Rob Harle
28big formula in the middle of the pagec()f() (replace all three occurrences)2009-04-28author
3229 to 35 of heapSort listingki (replace all five occurrences)2009-04-30author
n/an/aI 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-27another smart student (who?) during lecture 2

Valid XHTML 1.0 Transitional