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
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.
Page | Line | Errata | Corrige | Found by | on |
---|---|---|---|---|---|
11 | 8 | Cormen et al.: | Cormen et al. 3rd ed: | author | 2011-04-26 |
12 | -5 | i - 1 | i | author | 2011-04-29 |
16 | 15 and 16 | sin(n) | |sin(n)| | Daniel Bates | 2011-05-16 |
20 | -15 | at least O(n lg n) | at least Ω(n lg n) | author | 2011-05-01 |
22 | line 9 of listing | for k from 0 included | for k from 1 included | Wing Yung Chan | 2011-05-25 |
23 | -3 | == false | ==
False | author | 2011-05-01 |
27 | 12 to 14 | Note that [...] few elements. | [Delete this paragraph.] | author | 2011-05-01 |
29 | 11 | A[iRight] ≤ Pivot | A[iRight - 1] ≤ Pivot | Wing Yung Chan | 2011-05-26 |
29 | 12 | by iLeft and iRight | by iLeft and iRight - 1 | Wing Yung Chan | 2011-05-26 |
38 | 7 | Cormen et al.: | Cormen et al. 3rd ed: | author | 2011-04-26 |
45 | 7 | Cormen et al.: 10, 11, 12, 13, 18, 19,20, 21. | Cormen et al. 3rd ed: 6, 10, 11, 12, 13, 18, 21. | author | 2011-04-26 |
47 | -16 to -19 | [4-line listing starting with "struct"] | [add line numbers in the margin] | author | 2011-05-13 |
49 | 24 | it can be represented by an | it can be represented by an nxn | author | 2011-05-13 |
55 | line number 8 of the listing | get(k) ==
value | get(k) ==
v | author | 2011-05-13 |
56 | 6 | If duplicate | Since in this second case duplicate | author | 2011-05-13 |
56 | 13 | The other version has | The other version keeps that cost down but has | author | 2011-05-13 |
58 | line number 3 of the second listing | 3 } | [Delete that line] | author | 2011-05-13 |
59 | 15 | before having gone up-and-left | before having gone up-and-right | Tom Sparrow | 2011-05-16 |
59 | -7 to -3 | One 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 Sparrow | 2011-05-16 |
69 | lines 12 to 16 of the listing | Key old | Item 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 Farkas | 2011-05-25 |
71 | last line of the table: row "merge()", column "binary heap" | O(n lg n) | O(n) | author | 2011-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 $