CSCI 3110 Assignment 5 posted: 18.06.2021
Instructor: Travis Gagie due: midnight 02.07.2021
You can work in groups of up to three people. One group member should submit a copy of the solu-
tions on Brightspace, with all members’ names and banner numbers on it; the other group members
should submit text files with all members’ names and banner numbers (otherwise Brightspace won’t
let us assign them marks!). You may consult with other people but each group should understand
the solutions: after discussions with people outside the groups, discard any notes and do something
unrelated for an hour before writing up your solutions; it’s a problem if no one in a group can ex-
plain one of their answers. For programming questions you should submit your code, which should
compile and run correctly to receive full marks.
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(n2) time instead of O(n3) time. You need not
analyze your algorithm nor prove it correct.
1
https://leetcode.com/problems/maximum-subarray
https://leetcode.com/problems/maximum-subarray