The Australian National University Research School of Computer Science
COMP3600/6466 – Algorithms
This tutorial is compiled by:
Semester 2, 2020 Tutorial 8
Hanna Kurniawati
Exercise 1 Exercise 2 Exercise 3
Questions on A3
Questions on Final Project – Final Deliverables Dynamic Programming Cont.
1. Recall Merge-sort. Would it be beneficial if we use top-down dynamic programming with memo- ization in merge-sort? Please explain why or why not.
2. Mr T would like to typeset n words neatly. Suppose each word consists of li (i ∈ [1, · · · , n]) characters and suppose monospaced font (all characters having the same width) is used. Each line can hold at most C characters, the text is left-aligned, and the words cannot be split between lines. Mr T knows that the nicest looking paragraph would be one with the minimum extra white space at the end of each line. When a line consists of word-i to word-j (i, j ∈ [1, n]), the number of extra white space in that line can be computed as E = C−(jk=i lk)−(j−i). Mr T’s goal is to find the typeset that will minimize the sum of cubes of extra white spaces over all lines. Please:
(a) Design a dynamic programming algorithm for Mr T. Please specify each of the four steps of the dynamic programming development steps.
(b) Derive the time complexity of the algorithm you described in (a).
3. With states border opening up, Mr T plans to travel to the Mountain Region for a holiday. To keep things simple, he wants to travel light in this holiday —that is, he plans to bring only a small luggage with a total weight of at most w kg. Since Mr T is a frequent traveller and a highly organised person, he already has a list of objects he usually brings when he is travelling. This list contains n objects, with each object-i annotated by its weight wi and value vi (i ∈ [1,n]). Please find the objects Mr T should bring in his backpack, so that its weight does not exceed w kg, but the total values of the objects Mr T carries is maximised. In this problem, you can assume that the weight of the empty backpack is negligible, and that you can only bring or not bring a particular object as a whole (i.e., you cannot bring a fraction of an object nor multiple instances of an object), Please:
(a) Show that the above problem is suitable to be solved using a dynamic programming approach. (b) Specify the four steps of the dynamic programming development steps of this problem.
(c) Derive the time complexity of the algorithm you developed in (b).
4. Related to the above problem, please answer the following questions
(a) If for each object in the list, Mr T can bring multiple copies of the object as many as he likes, would dynamic programming remains a suitable solution to the problem? Please explain why or why not. If dynamic programming remains a suitable solution, please provide the dynamic programming algorithm for solving this problem (if different from 3(b)).
(b) If for each object in the list, Mr T can bring a fraction of the object, would dynamic program- ming remains a suitable solution to the problem? Please explain why or why not. If dynamic programming remains a suitable solution, please provide the dynamic programming algorithm for solving this problem (if different from 3(b)).