University of Toronto
December 16, 2009
CSC C73 Final Examination
Instructor: Vassos Hadzilacos
Aids allowed: One 8.5 × 11 handwritten, non-photocopied ‘cheat sheet’
Duration: Three hours
• There should be 10 pages in this exam booklet, including this cover page.
• Answer all questions.
• Put all answers in this booklet, in the spaces provided.
• For rough work, use the backs of the pages; these will not be marked.
• Good luck!
Family Name Given Name
Problem Marks Marks
TOTAL 150 CSC C73 Final Exam, Fall 2009 Page 2 out of 10
QUESTION 1. (20 marks)
a. (10 marks)Fill the frequency table below with a frequency for each of the symbols A, B, C,
and D so that, for these frequencies, diﬀerent executions of Huﬀman’s algorithm (corresponding
to diﬀerent ways of resolving ties) could produce both of the following two trees.
C A B C D
b. (10 marks) Below is a full binary tree that represents an encoding of the symbols A, B,
C, D, E, and F (shown as leaves of the tree), where each symbol appears with the frequency
indicated below the leaf that corresponds to the symbol.
Is the encoding represented by this tree optimal? That is, does it minimise the number of
bits required to encode a text over the six symbols A-F, where the symbols appear with the
indicated frequencies? Justify your answer.
A B C D
.10 .10 .15 .15
ANSWER: CSC C73 Final Exam, Fall 2009 Page 3 out of 10
QUESTION 2. (10 marks)
Shown below if a ﬂow graph, and a ﬂow through its edges. The label “f : c” on an edge indicates
that the capacity of the edge is c and the ﬂow through the edge is f.
a 4:8 c
10:10 0:5 4:5
s 6:8 t
a. (7 marks) Is the ﬂow shown a maximum ﬂow? Justify your answer.
b. (3 marks) Find a minimum cut of the above ﬂow graph.
ANSWER: CSC C73 Final Exam, Fall 2009 Page 4 out of 10
QUESTION 3. (20 marks)
Dijkstra’s algorithm does not always work correctly if edges can have negative weights. To rectify
this problem Professor N. O’Bright suggests the following: Let w be the minimum (negative)
weight of any edge; add |w| to every edge’s weight, thereby ensuring that each edge has a non-
negative weight; then use Dijkstra’s algorithm to ﬁnd a shortest path from the start node s to
each vertex in this modiﬁed graph.
Does N. O’Bright’s idea work? That is, is a shortest path from s to each vertex v in the
modiﬁed graph also a shortest path from s to v in the original grap