Instructions:
You are expected to solve the problems in the easier section on your own. For the harder section you are expected to
think about a problem alone for at least 24 hours before discussing it with others. Discussions are meant to help you
understand the problem better. You should not ask someone for solutions. If we nd evidence of cheating then you
will be reported to the university and could be subject to disciplinary action. Be prepared to come and explain your
solution to us in person if we feel the need. You can discuss the harder section in groups of 1, 2 or 3. In the end you
must write up your own solution and write names and RUIDs of students you collaborated with. For each problem,
justify your answer. Write formal proofs when asked for. Submit a single .pdf le on sakai containing your homework.
The name of the le should be your netid. Late homeworks will not be accepted.
In this homework whenever the problem mentions a string s of length n, you can assume that each of the n
characters is one of the 26 lowercase alphabets. If the problem mentions a bit string of length n, then each character is
either 0 or 1.
1
Easy Questions. 5 points each.
For each of the problems in the easy section it is enough to describe in English the idea of your algorithm, dene the
memo table, write the base case and the recursive step to ll the table, and analyze the run time. No need for pseudo
code.
Given a string s of length n, design an algorithm that outputs the smallest number k such that s = w1w2 . . . wk
where each wi is a palindrome. In other words, nd the smallest k such that s can be written as a concatenation
of k palindromes. For the denition of a palindrome see practice problems. For example if s = “add” then the
algorithm should output k = 2 since we can take w1 =“a” and w2 =“dd”. On the other hand, if s = “ada”, then
the algorithm should output k = 1.
Given two strings of length n and m, design an algorithm that outputs the length of the longest common substring
of the two strings. If A[1, . . . n] is the array representing a string, then any contiguous chunk A[i, . . . , j] is a
substring of A.
Given an array A[1, . . . , n] of integers, design a dynamic programming algorithm running in time O(n) to nd
indices i, j such that the subarray A[i, . . . , j] has the maximum sum.
You are given a set of n non-negative integers, and a target integer K. You need to nd out of there exists a
subset of the n integers that adds up to K. Design a dynamic programming algorithm for this problem that runs
in time O(nK).
Given a string of length n, a subsequence is any non empty subset of characters read from left to right. For
example, if A = atc then a, t, c, at, tc, ac, atc are all subsequnces of A. Given two strings of length n, m,
design an algorithm that outputs the length of the longest common subsequence (LCS) of the two strings.
Modify the algorithm for the longest common subsequence (LCS) problem that you designed above such that it
runs in time O(nm) but only uses O(min(n, m)) space.
2
Harder Questions
2.1
Weekend Planning (20 pts)
It’s Friday night and you have n parties to go to. Party i has a start time si, end time ti > si and a value vi ≥ 0. Think
of the value as an indicator of how excited you are about that party. You want to pick a subset of the parties to attend so
that you get maximum total value. The only constraint is that in order to get a value vi from party i you need to attend
the party from start to nish. Hence you cannot drop in midway and leave before the party ends. This means that if
two parties overlap, you can only attend one of them. For example, if party 1 has a start time of 7pm and ends at 9pm
and party 2 starts at 7:30pm and ends at 10pm, you can only attend one of them. On the other hand, if party 2 starts at
9pm or later then you can attend both. Given as input start times, end times and values of each of the n parties, design
an O(n log n) time algorithm to plan your night optimally. Describe in English the idea of your algorithm. If you use
dynamic programming dene the memo table, base case and recursive steps. You don’t need to write the pseudo code
or provide a proof of correctness.
2.2
Knapsack (20 pts)
In the knapsack problem we have n items, where each item i has an integer value vi and an integer price pi, and we
also have a budget of B. The goal is to nd the maximum total value of items that can be picked without exceeding the
budget. In particular, out of all sets of items whose total price is at most B, we want the set of highest total value. In
class, we gave a dynamic programming algorithm to solve this problem whose running time was O(nB). One issue,
though, is that if the prices are large, then O(nB) may not be so good. In this problem, we want you to come up with
an alternative algorithm whose running time is O(nV ), where V is the value of the optimal solution. So, this would be
a better algorithm if the prices are much larger than the values. Describe in English the idea of your algorithm. Dene
the memo table that you will use and write the base case and recursive step needed to ll the table. Finally write the
pseudo code. You don’t need to provide a proof of correctness.
[Note: Your algorithm should work even if V is not known in advance, but you may want to rst assume you are given
V up front and then afterwards gure out how to remove that requirement.]
2.3
How to make money via DP (30 pts)
An option (specically, an “American call option”) gives the holder the right to purchase some underlying asset (e.g.,
one share of IBM) at some specied exercise price (e.g., $200) within some specied time period (e.g., 1 year). For
instance, if the price of IBM went up to $212 in this period, you could exercise the option and then sell the stock,
making $12 (or you could keep the option, hoping the price will increase further before the option expires).
If you have a probabilistic model for how a stock will behave, then this gives you a well dened notion of the value
of a given option: the expected prot for having the option if you were to follow the optimal strategy for deciding
when to exercise it under that model.
For example, to take an easy case, suppose we have an option to buy one share of IBM at $200 that expires right
now. If IBM is currently going for $210, then the value of this option is $10. If IBM is currently going for $190, then
the value of this option is 0 (we wouldn’t want to exercise it). However, suppose the option expires tomorrow, and
suppose our model says that each day, with probability 1/4 the share price goes up by $20, and with probability 3/4
the share price goes down by $10 . In that case, if IBM is currently worth $190, then the value of this option is $2.50
because that is our expected gain if we use the optimal strategy “wait until tomorrow, and then exercise the option if
IBM went up” (our expected gain under this strategy would be
1
4 × 10 +
3
4 × 0). If IBM is currently worth $210, then
the value of the option is $10 (because if you work it out, our optimal strategy in this case is to exercise the option
right away).
Formally, the value of an option is the expected prot it will produce under the optimal strategy for using the
option, given our probabilistic model for the stock. Note that the optimal strategy need not commit in advance to what
day the option will be exercised: the date it gets exercised (if ever) may depend on how the stock has performed so
far1.