Show the steps of deriving your answers. Points will be deducted for answers without adequate steps discussed. Submit your homework via Blackboard as one PDF or Word document.
(25) [Weighted Interval Scheduling: algorithm tracing] Consider the dynamic programming algorithm we discussed for the weighted interval scheduling problem. Run the bottom-up (i.e., iterative) implementation of the algorithm on the problem instance shown below. Show the algorithm trace in the same manner as in Figure 6.5(a) and (b) (page 260) of the textbook -- specifically, show (i) the plot of sorted intervals, (ii) the list of values of p(i) for each interval i, (iii) the memorization table with array entries filled in at the end of the algorithm, and (iv) the set of intervals selected as a result. Note that the interval numbers used by the algorithm are the numbers after the sorting.
(25) [Project hour division] Textbook Exercise 20 in Chapter 6. The problem is to divide up H hours into h1, h2, …, hn (Σi=1..nhi = H) for n projects so that the total grade from the n projects, i.e., Σi=1..n fi(hi), is maximized, where fi(hi) is the grade received for a project i as a result of putting in hi hours -- somehow UVM students know it . Assume that H is an integer and that time is allocated by the unit of an hour. Build an optimal substructure with explanation, write a memoized bottom-up (i.e., iterative) program (pseudo)code, and show the runtime complexity and the memory space complexity. It suffices for your code to calculate the maximum total grade without returning the actual hour allocations to the individual projects – this could be calculated easily through bookkeeping or post-processing.
Last modified: October 24, 2019
