8. Huffman Coding and Set Cover

Huffman Coding

Goal: minimize symbols used

Using binary trees to binary encode symbols

Greedy

Choosing with greedy paradigm, but taking the lowest frequency symbols first into the bottom of the tree instead of taking the highest frequency symbols into the top

$O(n^2)$

Set Cover

Given a set B and a collection of sets that collectively cover B, find a subcollection with the smallest size that encompasses B

Greedy

Choose set that covers most uncovered elements Inoptimal