6 Greedy

Continuous problem

You are given $n$ activities with their start and finish times. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time

Solution: Select the least end time suitable remaining activities each time

Proof:

• Let $A$ be the greedy choice (starting with 1st activity in the sorted array).
• Let there be another choice $B$ starting with some activity $k$ ($k \neq 1$, so finishTime($k$) >= finishTime(1)) which alone gives the optimal solution.

So, $B$ does not have the 1st activity and we can make $B$ more likes $A$ without changing the number of activities by:

$A \leftarrow \{B − \{k\}\} \cup \{1\}$

Repeat until B turning into A.

We conclude that $|A| = |B|$, therefore activity $A$ also gives the optimal solution.

Huffman Tree

Introduction

• Fixed-length coding: Information Entropy(en- tropicalturn混乱)
• Variable-length coding: Prefix-Free code (no codeword is a prefix of a codework of another symbol)

Proof

Theorem

• T: a tree for some prefix encoding A and some probability distribution p over the symbols.
• x and y: two leaves
• T': the tree obtained by swapping x and y in T.

Then

$E_p(T')-E_p(T)=(p(x)-p(y))(depth(y,T)-depth(x,T))$

Lemma

something received or taken (di-:both side)

An optimal tree two symbols with least probabilities are sibling leaves in the lowest level. Easy

Correctness proof

• n=2 obvious
• n>2

Consider an alphabet A of n-1 letters.(except the two least probabilities leaves which parent is z)

Let T be an optimum tree for A

Let A'=A+{x,y}-z,T':adding x,y as children of z.

$H'$:optimum tree for A'

$H$:removing x,y from H;

Then $E_p(T)<=E_p(H)$

$E_p(T')=E_p(T)+p(x)+p(y)<=E_p(H')$

$E_p(T')>=E_p(H')$

so $E_p(T')=E_p(H')$