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.