1. [15 points] Consider a DAG which has already been topologically sorted, so edges go from left to right. In the lecture notes, we have seen a Dynamic Programming algorithm that finds the shortest path in a DAG where edges have weights associated with them. Now consider the following greedy strategies. Show that all of them fail to find the shortest path from node 1 to node n by giving appropriate small examples. You should also explain what is the value of the optimal solution compared to the greedy one.

Greedy strategy 1 Set i=1

While in,

Pick the edge (i, j) with the largest j Set i=j and repeat

Return the weight of the path constructed from node 1 to node n.

Greedy strategy 2

Set i=1 While in,

Pick the edge (i, j) with the smallest weight

Set i=j and repeat

Return the weight of the path constructed from node 1 to node n.

Greedy strategy 3 Set i=1

While in,

Pick the edge (i, j) with the smallest ratio weight/(j-i) Set i=j and repeat

Return the weight of the path constructed from node 1 to node n. Design and Analysis of Algorithms Homework 5 Page 1 of 2

Design and Analysis of Algorithms Prof. Tassos Dimitriou Homework 5

January 16, 2022

2. [5 points] Construct the Huffman tree and show the encoding of each letter based on the frequencies below:

Letter abcdefghi Frequency 25 10 13 6 20 14 5 3 4

If you have to encode a file consisting of 106 characters, how much space would the Huffman encoding require? What about the fixed size encoding?

Problem 2 (20 points) 1. [15 points] Consider a DAG which has already been topologically sorted, so edges go from left to right. In the lecture notes, we have seen a Dynamic Programming algorithm that finds the shortest path in a DAG where edges have weights associated with them. Now consider the following greedy strategies. Show that all of them fail to find the shortest path from node 1 to node ni by giving appropriate small examples. You should also explain what is the value of the optimal solution compared to the greedy one. Greedy strategy Set 1-1 While ien, Pick the edge (1, ) with the largest Set in and repeat Return the weight of the path constructed from node 1 to node n. Greedy strategy 2 Set 1-1 While iwn Pick the edge (1, 1) with the smallest weight Set in and repeat Return the weight of the path constructed from node 1 to node n. Greedy strategy 3 Set 1-1 While in Pick the edge (1, ) with the smallest ratio weight/(-i) Set in and repeat Return the weight of the path constructed from node 1 to node n. 2. [5 points) Construct the Huffman tree and show the encoding of each letter based on the frequencies below: Letter Frequency 25 10 13 6 20 14 5 3 4 If you have to encode a file consisting of 10 characters, how much space would the Huffman encoding require? What about the fixed size encoding