Description
1. We say that a sequence of Roman letters A occurs as a subsequence of a sequence of Roman
letters B if we can obtain A by deleting some of the symbols of B. Design an algorithm which
for every two sequences A and B gives the number of different occurrences of A in B, i.e., the
number of ways one can delete some of the symbols of B to get A. For example, the sequence
ba has three occurrences in the sequence baba: baba, baba, baba .
2. Some people think that the bigger an elephant is, the smarter it is. To disprove this you want
to analyze a collection of elephants and place as large a subset of elephants as possible into a
sequence whose weights are increasing but their IQ’s are decreasing. Design an algorithm
which given the weights and IQ’s of n elephants, will find a longest sequence of elephants
such that their weights are increasing but IQ’s are decreasing.
3. A company is organizing a party for its employees. The organizers of the party want it to be a
fun party, and so have assigned a ‘fun’ rating to every employee. The employees are
organized into a strict hierarchy, i.e. a tree rooted at the president. There is one restriction,
though, on the guest list to the party: an employee and their immediate supervisor (parent in
the tree) cannot both attend the party (because that would be no fun at all). Give an
algorithm that makes a guest list for the party that maximizes the sum of the ‘fun’ ratings of
the guests.
4. You have to cut a wood stick into several pieces. The most affordable company, Analog
Cutting Machinery (ACM), charges money according to the length of the stick being cut. Their
cutting saw allows them to make only one cut at a time. It is easy to see that different cutting
orders can lead to different prices.
For example, consider a stick of length 10 m that has to
be cut at 2, 4, and 7 m from one end. There are several choices. One can cut first at 2, then at
4, then at 7. This leads to a price of 10 + 8 + 6 = 24 because the first stick was of 10 m, the
resulting stick of 8 m, and the last one of 6 m. Another choice could cut at 4, then at 2, then
at This would lead to a price of 10 + 4 + 6 = 20, which is better for us.
Your boss demands
that you design an algorithm to find the minimum possible cutting cost for any given stick.
5. For bit strings X=x1 …xm ,Y=y1 …yn and Z=z1 …zm+n we say hat Z is an interleaving of X and
Y if it can be obtained by interleaving the bits in X and Y in a way that maintains the left-toright order of the bits in X and Y. For example if X = 101 and Y = 01 then x1x2y1x3y2 = 10011
is an interleaving of X and Y, whereas 11010 is not. Give an efficient algorithm to determine
if Z is an interleaving of X and Y.
6. You are given n turtles, and for each turtle you are given its weight and its strength. The
strength of a turtle is the maximal weight you can put on it without cracking its shell.
Find
the largest possible number of turtles which you can stack one on top of the other without
cracking any turtle. (Hint: for each turtle consider the sum of its weight and its strength).
