首页 >
> 详细

Final version DSafonte 4/20

Updated M.Trinh 4/21

CS 325 - Spring 2020

Homework #4

Problem 1. (6pts)

a) Assume the following symbols a, b, c, d, e occur with frequencies 1/2, 1/4, 1/8, 1/16, 1/16 respectively.

What is the Huffman encoding of the alphabet? (3 pts)

b) If the encoding is applied to a file consisting of 1 million characters with the same given frequencies,

what is the length of the encoded file in bits? (3 pts)

Problem 2. (5pts)

Complete problem 16.2-2 on page 427 in the book:

Give a dynamic-programming solution to the 0-1 knapsack problem that runs in Ο(n W) time, where n is the

number of items and W is the maximum weight of items that a thief can put in their knapsack.

Problem 3. (8 pts)

Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin's

value is an integer.

Problem 3.a. (4 points)

a) Suppose that the available coins are in the denominations that are powers of c, i.e., the denominations

for some integers c > 1 and k _ 1. Show that the greedy algorithm of picking the largest

denomination first always yields an optimal solution. You are expected to reason about why this

approach gives an optimal solution. (Hint: Show that for each denomination ci, the optimal solution

must have less than c coins.)

Problem 3.b. (4 points)

b) Design an Ο(nk) time algorithm that makes change for any set of k different coin denominations,

assuming that one of the coins is 3 cents in value.

Problem 4. (6 pts)

Implementation:

Implement the make change algorithm you designed in the previous problem. Your program should read a

text file “data.txt" where each line in “data.txt" contains three values c, k and n. Please make sure you take

your input in the specified order c, k and n. For example, a line in “data.txt" may look like the following:

4 3 73

Final version DSafonte 4/20

Updated M.Trinh 4/21

where c = 4; k = 3; n = 73. That is, the set of denominations is {40

; 41

; 42

; 43

} = {1; 4; 16; 64}, and we would like

to make change for n = 73. The file “data.txt” may include multiple lines like above.

The output will be written to a file called “change.txt”, where the output corresponding to each input line

contains a few lines. Each line has two numbers, where the first number denotes a denomination and the

second number represents the cardinality of that denomination in the solution. For example, for the above

input line ‘4 3 73’, the optimal solution is the multiset {64; 4; 4; 1}, and the output in the file “change.txt” is as

follows:

Data input: c = 4, k = 3, n = 73

Denomination: 64 Quantity: 1

Denomination: 16 Quantity: none

Denomination: 4 Quantity: 2

Denomination: 1 Quantity: 1

which means the solution contains one coin of denomination 64, none of 16, two coins of 4, and one coin of 1.

You can use a delimiter line to separate the outputs generated for different input lines.

Problem 5 – Extra Credit (4 pts)

a) Using Huffman encoding of n symbols with the frequencies f1, f2, f3… fn, what is the longest a codeword

could possibly be? (2pts)

b) Give at least one example set of frequencies that would produce the case above. (2pts)

Submit a copy of all your code files and a README file that explains how to compile and run your code

in a ZIP file to TEACH. We will only test execution with an input file named data.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Comp 250 Assignment 3 2020-05-24
- Macm 316 – Computing Assignment 7 2020-05-24
- Sta457 Assignment 2020-05-24
- Homework 10 2020-05-24
- Lab 2 Msc: Time Series Prediction With... 2020-05-24
- Comp2011作业代做、Data Analysis作业代写、C++编程语言 2020-05-24
- 代做compsys201作业、Python，Java，C/C++编程语言作业 2020-05-24
- Program留学生作业代做、Python编程设计作业调试、Data作业代写 2020-05-24
- 代写 Practical 3 Covid-19程序作业，代写... 2020-05-23
- 代写comp3059作业、代做programming作业、Java语言作业代 2020-05-23
- Coit12206作业代写、Program课程作业代做、Java、Pytho 2020-05-23
- Data2001作业代做、Data Science作业代做、Sql语言作业代 2020-05-23
- 代写comp2017作业、代写c/C++语言作业、代写data作业、C/C+ 2020-05-23
- Data留学生作业代做、Python编程设计作业调试、代写program课程 2020-05-22
- Mkan1-Uc 5103作业代写、代做analytics作业、Java，P 2020-05-22
- Pols 512作业代写、R编程设计作业调试、Data留学生作业代做、代写r 2020-05-21
- Econ 6070作业代做、Data课程作业代写、代做java，Python 2020-05-21
- Pstat 170 2020-05-20
- Comp 250 Assignment 3 2020-05-20
- Data留学生作业代做、代写r程序语言作业、代做r实验作业、代写progra 2020-05-20