Problem 1. Construct the Huffman tree of the following phrase: ”data structure”

Problem 2. During the lecture we saw that the Fractional Knapsack algorithm’s cor- rectness depends on which greedy choice we make. We saw that there are instances where always picking the ”highest benefit” or always picking the ”smallest weight” doesn’t give the optimal solution.

For each of these two strategies, give an infinite class of instances where the algorithm gives the optimal solution, thus showing that you can’t show correctness of an algorithm by using a finite number of example instances.

Problem 3. Given vectors a, b ∈ Rn, consider the problem of finding a permutation a\ and b\ of a and b respectively minimizing their total difference

∑  |a − b |.

1≤i≤n

Prove or disprove the correctness (i.e., that it always returns the optimal solution) of the following algorithm that greedily tries to pair up similar coordinates.

Problem 4. Given vectors a, b ∈ Rn, consider the problem of finding a permutation a\ and b\ of a and b respectively that minimizes

∑  |a − b |.

1≤i≤n

Prove or disprove the correctness (i.e., that it always returns the optimal solution) of the following algorithm that greedily tries to pair up similar coordinates.