282 Design & Analysis of Efficient Algorithms - Fall 2013
Instructor: Henry Kautz
Assignment 3
Due: Friday Oct 25 by 2:00pm, turn-in box in CSB 708
Be sure to follow Homework Rules at http://www.cs.rochester.edu/u/www/courses/282/fall2013/
Goals for this assignment:
- Understand principles of greedy algorithms and dynamic programming
- Understand the algorithms for:
- Minimum spanning trees
- Huffman coding
- Edit distrance
- Knapsack
1. [minimum spanning trees] DVP 5.5.
2. [Huffman coding] DVP 5.18. For parts (a)-(b), you may do your choice of the following:
- Work the problem by hand as stated.
- Work the problem by hand, but only using the letters in the first column (blank through "h"). Create a new symbol "other" whose frequency is the sum of the frequencies of letters "r" through "z".
- Write and run a program to compute the Huffman encoding and the expected number of bits. Translating the pseudocode from the textbook to a language such as Python is straighforward; the hardest part would be determining how to print the code for each symbol once you've built the tree.
In thinking about parts (c) and (d), consider the following: Shannon's Coding Theorem, the central theorem in information theory, says that the entropy of a probabilistic data source is an absolute lower bound on the average number of bits per symbol needed to encode a message from that source.
3. [greedy algorithms] DVP 5.33 in hardcopy textbook. (This is probelm 5.32 in the online draft of the textbook.) Read DVP 5.33 on your own. Workshops will go over this section and the principles of propositional logic.
4. [dynamic programming] DVP 6.3.
5. [edit distance] The solution to problem DVP 6.26 will be covered in workshop. Your job on the homework is to solve DVP 6.28. For extra credit, also solve 6.29.
6. [knapsack] DVP 6.17, 6.18, and 6.19. (Each problems involves a simple reduction to a problem with a solution given in the textbook.)