## Introduction

See the general rules about assignments in this course.

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

## Questions

### 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.