Computer Science Homework Help

1. Write a program that takes two strings S and T and outputs an optimal alignment in
O(|S||T|) time, displayed as in the lecture notes. For example, if S = AGATACATCA and
T = GATTAGATACAT, then an optimal alignment is
AGAT-ACAT-CA-
-GATTAGATACAT
(I think). You need not analyze your algorithm nor prove it correct.

2. Write a linear-time dynamic-programming algorithm for https://leetcode.com/problems/
maximum-subarray and EXPLAIN IT.
(It’s not hard to find code online, but most of the explanations are terrible. Remember, if
you can’t explain your answer, there’s a problem!)

3. Suppose your professor has assigned a “profit” to each of several indivisible food items,
expressing how much he likes each item. He’s now filling his knapsack and trying to select
items to maximize the total profit. The food items are light but bulky, so the key constraint
now is the volume the knapsack can hold, rather than the weight. Even though the food items
cannot be cut, they can be squashed, which reduces their volume by a factor of 2 — but also
reduces their profit by a factor of 2 (since squashed food is not as appetizing).
Write a dynamic-programming algorithm that runs in time polynomial in the number of items
and the capacity of the knapsack (in litres) and tells your professor which food items to select
and, of the selected ones, which ones to squash. You can assume the knapsack’s capacity and
the original volume in litres of each item are integers. Explain why your algorithm is correct.

4. Write pseudo-code — you don’t have to code this — for an O(n log n) time algorithm that
takes a sequence of n integers and finds the longest slowly increasing subsequence (LSIS),
where an LSIS is a sequence in which each number after the first is larger than it’s predecessor
but not by more than 10. Explain why your algorithm is correct.

5. Modify the code in the lecture notes (to be posted by June 21st) for building an optimal
binary search tree such that it runs in O(n
2
) time instead of O(n
3
) time. You need not
analyze your algorithm nor prove it correct.