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.