Problem Set #7 - Due 04/02/03 Total 100 The purpose of this problem set is to: • Help you become familiar with material covered in week 7 of class. • There is no programming in this pset. Please turn in each problem on a separate page. Each page should have your Name, email id, and the problem number clearly printed/written on it. Keep track of how long time it takes to complete each problem. The time taken for each problem should be printed on the first page. If you use more than one page for one problem, please STAPLE the pages together. You will lose points if you do not document the time taken for each problem, which at the same time means that you will get points for documenting “time taken”. Problem 1 (30 points) Define the following terms in a few lines. Provide a diagram for each graph illustrating your definition. Simple Graph Multi Graph Directed Graph Tree Binary Tree Ordered Binary Tree Problem 2 (40 points) For the graph below find a minimum weight spanning tree using A) The Prim-Dijkstra algorithm (starting with node 1). B) Kruskal’s algorithm 1232543361321212453867Problem 3 (30 points) A source generates letters from the alphabet {a1, a2, a3, a4} with corresponding probabilities {1/2, 1/4, 3/16, 1/16}. Letters are generated independently at a rate of one letter per second. A) What is the binary entropy of the source? B) What is the minimum required average codeword length to represent the source for error free reconstruction? C) Design a Huffman code for the source. What is the average codeword length of your
View Full Document
Unlocking...