For all (and only) dynamic programming problems in this class, we would like you to follow...

 

Transcribed Image Text:

For all (and only) dynamic programming problems in this class, we would like you to follow a 4-part solution format: 1. Algorithm Description: since dynamic programming algorithms can be difficult to explain, you should follow the template below to optimize clarity. (a) Define your subproblem. In words, define a function f so that the evaluation of f on a certain input gives the answer to the stated problem. You should clearly state how many parameters f has, what those parameters represent, what f evaluated on those parameters represents, and what inputs you should feed into f to get the answer to the stated problem. (b) Provide your recurrence relation. More precisely, give a recurrence relation show- ing how to compute f recursively, and make sure to provide base cases. If you need to use certain data structures to make computation of f faster, you should say so. (c) Subproblem Ordering: describe the order in which you should solve the subprob- lems to obtain the final answer. 2. Proof of Correctness: provide some inductive proof that shows why your DP algo- rithm computes the correct result. 3. Runtime Analysis: analyze the runtime of your algorithm. 4. Space Analysis: analyze the space/memory complexity of your algorithm. Ac Go As we have learned in lecture, the Huffman code satisfies the Prefix Property, which states that the bit string representing each symbol is not a prefix of the bit string representing any other symbol. One nice property of such codes is that, given a bit string, there is at most one way to decode it back to a sequence of symbols. However, this is not true anymore once we are working with codes that do not satisfy the Prefix Property. For example, consider the code that maps A to 1, B to 01 and C to 101. A bit string 101 can be interpreted in two ways: as C or as AB. Your task is to, given a bit string s, determine whether it is possible to interpret s as a sequence of symbols. The mapping from symbols to bit strings of the code will be given to you as a dictionary d (e.g., in the example, d {A 1, B 01, C: 101}); you may assume = : that you can access each symbol in the dictionary in constant time. (a) Describe an algorithm that solves this problem in at most O(nkl) where n is the length of the input bit string s, k is the number of symbols, and l is an upper bound on the length of the bit strings representing symbols. Please provide a 4-part solution. (b) (Optional) How can you modify the algorithm from part (a) to speed up the runtime to O((n + k)l)? For all (and only) dynamic programming problems in this class, we would like you to follow a 4-part solution format: 1. Algorithm Description: since dynamic programming algorithms can be difficult to explain, you should follow the template below to optimize clarity. (a) Define your subproblem. In words, define a function f so that the evaluation of f on a certain input gives the answer to the stated problem. You should clearly state how many parameters f has, what those parameters represent, what f evaluated on those parameters represents, and what inputs you should feed into f to get the answer to the stated problem. (b) Provide your recurrence relation. More precisely, give a recurrence relation show- ing how to compute f recursively, and make sure to provide base cases. If you need to use certain data structures to make computation of f faster, you should say so. (c) Subproblem Ordering: describe the order in which you should solve the subprob- lems to obtain the final answer. 2. Proof of Correctness: provide some inductive proof that shows why your DP algo- rithm computes the correct result. 3. Runtime Analysis: analyze the runtime of your algorithm. 4. Space Analysis: analyze the space/memory complexity of your algorithm. Ac Go As we have learned in lecture, the Huffman code satisfies the Prefix Property, which states that the bit string representing each symbol is not a prefix of the bit string representing any other symbol. One nice property of such codes is that, given a bit string, there is at most one way to decode it back to a sequence of symbols. However, this is not true anymore once we are working with codes that do not satisfy the Prefix Property. For example, consider the code that maps A to 1, B to 01 and C to 101. A bit string 101 can be interpreted in two ways: as C or as AB. Your task is to, given a bit string s, determine whether it is possible to interpret s as a sequence of symbols. The mapping from symbols to bit strings of the code will be given to you as a dictionary d (e.g., in the example, d {A 1, B 01, C: 101}); you may assume = : that you can access each symbol in the dictionary in constant time. (a) Describe an algorithm that solves this problem in at most O(nkl) where n is the length of the input bit string s, k is the number of symbols, and l is an upper bound on the length of the bit strings representing symbols. Please provide a 4-part solution. (b) (Optional) How can you modify the algorithm from part (a) to speed up the runtime to O((n + k)l)?

Answer rating: 100% (QA)

1 Algorithm Description a Define your subproblem In this part you are defining the smaller more manageable problems that make up the larger problem Its crucial to clearly specify the function f its pa... View the full answer