Computer Laboratory

Course material 2010–11

Algorithms I
2010–2011

Principal lecturer: Dr Frank Stajano
(email to frank.stajano--algs1 at cl cam ac uk will be given priority over that sent to other addresses)

Taken by: Part IA CST, Part IA NST, Part I PPS

Syllabus

Past exam questions can be found under Algorithms I but also, for historical reasons, under Data Structures and Algorithms (the parent course for both Algorithms I and Algorithms II); be sure to select questions dealing with topics covered in this year's syllabus.

Further information for supervisors is available (contact lecturer for access, stating your name, CRSID and PhD supervisor).

Lecture handouts

Distributed during the first lecture on 2011-04-29. It will be to your advantage to come to every lecture with all of the following resources:

  • your handout
  • a notebook with non-detachable pages
  • a pen you like writing with
  • a few more coloured pens or pencils.

Further printed copies of the handout are available from the student administration office. An electronic copy is also available: please do not print it again yourself and please do not circulate it outside cam.ac.uk.

You are strongly encouraged to study on one of the recommended textbooks rather than relying only on the handout. And, especially if you are a Computer Lab undergraduate rather than a guest from another department, it would be a sound investment to buy your textbook now and use it throughout as a long term reference (good also for Algorithms II, for your upcoming job interviews and for your actual professional life).

Errata corrige

If you find any errors in the handout, please email me (at the --algs1 address mentioned above in order to get higher priority) and I'll credit you here and in the next edition.

PageLineErrata CorrigeFound byon
118Cormen et al.:Cormen et al. 3rd ed:author2011-04-26
12-5i - 1iauthor2011-04-29
1615 and 16sin(n)|sin(n)|Daniel Bates2011-05-16
20-15at least O(n lg n)at least Ω(n lg n)author2011-05-01
22line 9 of listingfor k from 0 includedfor k from 1 includedWing Yung Chan2011-05-25
23-3== false== Falseauthor2011-05-01
2712 to 14Note that [...] few elements.[Delete this paragraph.]author2011-05-01
2911A[iRight] ≤ PivotA[iRight - 1] ≤ PivotWing Yung Chan2011-05-26
2912by iLeft and iRightby iLeft and iRight - 1Wing Yung Chan2011-05-26
387Cormen et al.:Cormen et al. 3rd ed:author2011-04-26
457Cormen et al.: 10, 11, 12, 13, 18, 19,20, 21.Cormen et al. 3rd ed: 6, 10, 11, 12, 13, 18, 21.author2011-04-26
47-16 to -19[4-line listing starting with "struct"][add line numbers in the margin]author2011-05-13
4924it can be represented by anit can be represented by an nxnauthor2011-05-13
55line number 8 of the listingget(k) == valueget(k) == vauthor2011-05-13
566If duplicateSince in this second case duplicateauthor2011-05-13
5613The other version hasThe other version keeps that cost down but hasauthor2011-05-13
58line number 3 of the second listing3 }[Delete that line]author2011-05-13
5915before having gone up-and-leftbefore having gone up-and-rightTom Sparrow2011-05-16
59-7 to -3One will be to exchange the contents of the non-leaf cell with either the predecessor or the successor (whichever one is a descendant rather than an ancestor---from the result of the previous exercise you can prove that at least one of the two is). Then the item for deletion is in a leaf position and can be disposed of without further trouble;A non-leaf with only one child can be simply replaced by its child. For a non-leaf with two children, an option is to replace it with its successor (or predecessor---either will work). Then the item for deletion can't have two children (cfr. exercise above) and can thus be deleted in one of the ways already seen; Tom Sparrow2011-05-16
69lines 12 to 16 of the listingKey oldItem x [The item whose key is to be decreased must be identified by a pointer to the item itself within the priority queue, not by its key, because the priority queue does not efficiently support retrieval of elements by key. The comments should also be edited to refer to the item rather than the key.]Marton Farkas2011-05-25
71last line of the table: row "merge()", column "binary heap"O(n lg n)O(n)author2011-05-25

Timetable

Every Monday, Wednesday, Friday at 1000 in New Museums Site, Arts School A, starting Fri 2011-04-29 included and ending Wed 2011-05-25 included (12 lectures).


$Id: index-b.html 46 2011-05-26 18:32:46Z fms27 $

Valid XHTML 1.0 Strict