CS 6363.004: Algorithms Spring 2019 Assignment 3 Wed, Feb 20, 2019 You can write or type your answers. Submit on elearning. Due: 11:59 PM, Sun, Mar 10 (on elearning). 1. Consider the activity selection problem discussed in class. Activity a_i occupies the interval [s_i,f_i) and yields revenue of p_i. Suppose, some activities are marked as special events. A boolean array S[1..n] is given, and S[i]=True whenever a_i is a special event. Consider the problem of finding a set of compatible activities to generate maximum total profit, with the restriction that two consecutive events that are selected cannot both be special. One or more non-special events must be scheduled between two special events. Non-special events do not have this restriction and any number of them can be scheduled back to back. Design a dynamic program for the problem. 2. Suppose that in the rod-cutting problem, we also had limit l_i on the maximum number of pieces of length i we are allowed to produce, for i=1,2,...,n. Give a dynamic program for this modified problem. 3. Given an array A[1..n] representing a sequence of n integers, a subsequence is a subset of elements of A, in the same order as they appear in A. A subsequence is monotonic if it is a sequence of strictly increasing numbers. Define LMS(i) to be the length of a longest monotonically increasing subsequence of A[1..i] that must have A[i] as its last element. Write a recurrence for LMS(i) and convert into a dynamic program that calculates LMS(i) for i=1..n. Optional problems (extra credit): 4. Ex. 8.2-4 (p. 197) [Describe an algorithm that, ... preprocessing time.] 5. Consider a modification of the rod-cutting problem in which, in addition to a price P_i for each rod, cutting a rod of length i into two pieces incurs a cost of C_i. The input consists of two arrays P[1..n] and C[1..n]. The revenue associated with a solution is now the sum of the pieces minus the costs of making the cuts. Give a dynamic program to solve this problem. 6. Modify the rod-cutting problem as follows: sizes that have value are given as a sorted array s[1..k], with s_1 < s_2 < ... < s_k. A rode of length s[i] generates a revenue of p[i]. Write a recursive solution based on DAC for this problem, where the objective is to maximize the revenue that can be generated from a given rod of length n. Prove that it is correct. Write a dynamic program based on this recurrence and analyze its RT. Your algorithm should run in O(nk) time. 7. An alternating monotonic sequence (AMS) is a monotonically increasing sequence which alternates between even and odd numbers. For example, {7,12,13,22} is an AMS, but {7,12,14,21} is not (though it is a monotonic sequence). Describe a dynamic program for finding a longest alternating monotonic subsequence of a given sequence. 8. Problem 15-2 (p. 405) [Longest palindromic subsequence]. Solve this problem from first principles, without converting to LCS.