## 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).