Old test Final

10 Pages
Unlock Document

Computer Science
Vassos Hadzilacos

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, different executions of Huffman’s algorithm (corresponding to different 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 flow graph, and a flow through its edges. The label “f : c” on an edge indicates that the capacity of the edge is c and the flow 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 flow shown a maximum flow? Justify your answer. ANSWER: b. (3 marks) Find a minimum cut of the above flow 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 find a shortest path from the start node s to each vertex in this modified graph. Does N. O’Bright’s idea work? That is, is a shortest path from s to each vertex v in the modified graph also a shortest path from s to v in the original grap
More Less

Related notes for CSCC73H3

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
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.

Add your courses

Get notes from the top students in your class.