Algorithms homework related to exam 3
Hw7
1. Recall from your data structures course that a queue supports two operations, enqueue and dequeue, and a stack supports two operations, push and pop.
(a) Show how to simulate a queue using two stacks.
(b) What is the worst-case time complexity for the two queue operations, in your simulated queue from part (a)?
(c) What is the amortized time complexity of your queue operations, assuming you start with an empty structure?
2. An extended queue supports the two standard queue operations, but has one extra operation, called Q-pop, through which we access and remove the item that has been enqueued most recently. Show how to simulate an extended queue, using three stacks, such that the amortized cost of each extended queue operation is constant.
You can only use stack operations, and you should not duplicate (copy) elements.
Hw8
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.
2. 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.
Hw9
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.