Computer Laboratory > Teaching > Course material 2007–08 > Algorithms II

Algorithms II
2007–08

Principal lecturer: Dr Frank Stajano
Taken by: Part IB, Part II (General), Diploma
Syllabus
Past exam questions can be found under Algorithms II but also, for historical reasons, under Data Structures and Algorithms; in the latter case, be sure to select questions on topics covered in this year's syllabus: the various algorithms courses have evolved and changed quite a bit over the years.

Feedback

If you were a student for this course, please comment (anonymously) on my lectures, noting explicitly what you liked and what you didn't.

Handout

Here are the errors I found so far in the new (2007-08) edition of the course handout. My apologies. If you find any more yourselves, please let me know. (Negative lines are counted from the bottom of the page. As traditional in typography, I count from 1 rather than 0.)

Page	Line	Errata	Corrige
10	-12	nodes into two sets.	nodes.
12	-18	distance to the root along the	distance to the
15	1	`for v in G.vertices(): # v not used: just counting`	`repeat \|V\|-1 times:`
16	23	`Q.decreaseKey(item=v, newKey=G.weightOfEdge(u,v))`	`Q.decreaseKey(item=v, newKey=u.d+G.weightOfEdge(u,v))`
23	-3	”The smallest	“The smallest
31	5	doubly-linked list. The	doubly-linked list, updating the pointer-to-smallest if necessary. The
31	-14	prevent `deleteKey()` from	prevent `decreaseKey()` from
32	1+2	heap, which could be pretty expensive (O(n)) if they were all single node trees. So we choose	heap. But we choose
32	7	tree order,	tree rank,
32	11	tree per order.	tree per rank.
32	-2	those of `deleteKey()`	those of `decreaseKey()`

If you are a member of the Computer Laboratory or a supervisor for this course and need a copy of the handout, please ask Fiona nicely.

Algorithms II2007–08

Feedback

Handout

Algorithms II
2007–08