UNB/ CS/ David Bremner/ teaching/ cs3383/ assignments/ CS3383 Assignment 5


See the general rules about assignments in this course.

DUE: 2016-10-27, 16:30 in the assignment box.


1 Huffman coding

From an exercise in DPV.

Consider a discrete probability distribution on symbols 1 to n with probabilities p₁ … pₙ where each pᵢ is an integer power of 1/2. Suppose a long sequence S of samples is drawn from the distribution such that symbol i occurs pᵢ|S| times. Prove that if a Huffman code based on the probabilities pᵢ is used, the total number of bits to encode S is

|S|∑ { pᵢ log (1/pᵢ) | 1 ≤ i ≤ n }

Hint Show that the two smallest probabilities must be the same; or for part marks assume this holds.

2 Greedy Scheduling

Consider the problem of scheduling n jobs on a 3D printer. The turnaround time for a job is the total time from when it arrives to when it finishes printing. Suppose that all jobs arrive at the same time, and that we know the time that job i will take time tᵢ to print once started on the printer. Prove that scheduling the jobs in greedy order (i.e. shortest job first) minimizes the average turnaround time.