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


Algorithms II

Principal lecturer: Dr Frank Stajano
Taken by: Part IB, Part II (General), Diploma
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.


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


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.)

10-12nodes into two sets.nodes.
12-18distance to the root along thedistance to the
151for v in G.vertices(): # v not used: just countingrepeat |V|-1 times:
1623Q.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
315doubly-linked list. Thedoubly-linked list, updating the pointer-to-smallest if necessary. The
31-14prevent deleteKey() fromprevent decreaseKey() from
321+2heap, which could be pretty expensive (O(n)) if they were all single node trees. So we chooseheap. But we choose
327tree order,tree rank,
3211tree per order.tree per rank.
32-2those 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.