false

by
OneClass4706

Unlock Document

Computer Science

CSCC73H3

Vassos Hadzilacos

Fall

Description

University of Toronto
Scarborough Campus
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
Student Number
Problem Marks Marks
Rec’ved Worth
1. 20
2. 10
3. 20
4. 10
5. 20
6. 20
7. 20
8. 30
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.
ANSWER:
Symbol Frequency
A
D
B
C
C A B C D
D
A B
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.
E F
.25 .25
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
4:10 10:10
b d
10:10
a. (7 marks) Is the ﬂow shown a maximum ﬂow? Justify your answer.
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

More
Less
Related notes for CSCC73H3

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.