ALGORITHMS HOMEWORK (Part 3), SUMMER 2020
Due June 17
1. You are given two strings that each have length n. You must find their LCS; not only its length. You are allowed polynomial time to do this but you must only use linear space. Describe how to do this.
Due June 19
1. Let S be a string with n characters, indexed 1 to n. Let X be a sorted array with m integers within range 1 to n−1, inclusive. The integers in X correspond to indices in S after which we must insert a space. For example, if S = ALGOISSOCOOL is to be split into 4 words of length 4,2,2,4 respectively, then X = [4, 6, 8].
Given S and X, the spaces must be inserted one at a time, in any order. The order matters because it costs k to insert a space anywhere on a substring of size k. When a space is inserted, we get two substrings that we eventually process disjointly. In the example above if you first split at position 6, the cost will be 12. Then on each side the cost of the next split will be 6. On the other hand if you were to first split at position 4, the cost would be 12 but then you would pay 8 for the next split, etc.
(a) Derive a recursive formula that returns the minimum cost of splitting a string as defined above. Briefly explain why the formula is correct.
(b) How many distinct subproblems might you need to solve during recursion?
(c) How fast can you determine what the minimum cost of splitting a given string is? Your time complexity should be polynomial.
Due June 21
1. Let G be an n × n grid. You start at a particular position, with zero velocity. At every time step you can modify your horizontal velocity by 1, or keep it the same. The same holds independently for vertical velocity. So if at a particular time you are at position x,y and already have velocity vx,vy, then at the next time step you will jump and land at position x + vx, y + vy, and you then have the option of modifying each component of your velocity by ±1.
At several (known) grid positions there are pits full of dragons that you want to avoid landing on. It is ok to jump over a dragon pit. You also shouldn’t jump off the grid. The goal is to arrive at a specified target position, with zero velocity, in as little time as possible. Show how fast you can compute an optimal trajectory or decide that there is no way to reach the target. Hint: To warm up, try this out in 1D instead of 2D.
Due June 23
1. You are given a graph G = {V,E} and its minimum spanning tree, MST(G), both in ad- jacency list representation. Suppose that we wish to add a vertex v to G, along with some weighted edges from v to other vertices in G. In other words we create a new graph, G′. Let MST(G′) be the minimum spanning tree of G′. You may assume that all edge weights are distinct.
(a) Can any edge of G that is not in MST(G) end up in MST(G′)? Provide a clear proof.
(b) Your job is to produce MST(G′), given that G and MST(G) are already available. Outline an algorithm, in English. Justify the time-complexity of your algorithm.
Due June 24
1. Consider a one-dimensional intergalactic highway (let’s just model it as a horizontal line, on which you can travel left or right). On the highway are n space stations. You’re currently at some particular station, s, and want to get to another station, t, that is somewhere to the right of s. To get from station to station, you must use privately owned teleportation services. Each owner of a teleportation device is able to transport you between precisely one specific pair of stations (in either direction), but nowhere else. There are m pairs of stations that are directly connected in this way.
For each pair of stations, a, b, the owner of the teleport connector between a and b charges whatever they like for a transfer. The amount is fixed, it doesn’t change over time. The amount charged is not correlated to distance covered. You have full knowledge of all tele- portation options and prices.
As everyone knows, because of the effect of teleportation on the human body, you can’t keep switching directions when you teleport, unless you rest for a long time. In fact you can switch directions at most once. You have no time to rest though, so you must get from s to t following this constraint.
Algorithmically, how will you determine which path to take, so that the total price paid is minimized? How fast can you compute / construct the best path?