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 (200708) 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 V1 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  doublylinked list. The  doublylinked list,
updating the pointertosmallest 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.
