1. For the dynamic array problem (see class notes), consider handling insertions and dele- tions. Assume that deletion always involves the rightmost element in the array.
At any moment, the array storing your data must have a size that is Θ(k), where k is the number of elements currently stored. In other words, you don’t want to be occupying too much empty space. This means that at some point you might have to downsize, i.e., copy all the data into a smaller array.
(a) When should you double and when should you downsize, to get low amortized cost? (b) Explain (informally, if you wish) why the amortized cost is low for your strategy.
2. You must support the following two operations on a set of numbers: (i) insertion, and (ii) “large-delete” which is to delete the largest half of the values in the set. In other words if there are k elements you delete the elements with the ⌈k/2⌉ largest values. Both operations should take constant time, amortized. Assume that you start with an empty set.
(a) What data structure will you use, and how will you handle the operations? What is the worst-case time complexity for one operation?
(b) Show why each operation costs O(1) amortized. You should try both accounting and the potential method.
3. You are given k cards, arranged in k columns, each containing one card. A “move” is defined as choosing a column and redistributing all of its cards into other columns, but when doing this each of the columns can receive at most one card. Also, during the move, you are allowed to make new columns (in fact this is unavoidable if you don’t have enough existing columns in which to place all the cards), but again only one card can go in each new column.
The reward of one move is precisely the number of cards in the column that you choose to redistribute. Suppose that you get to make some huge number of moves (say, n, far greater than k).
(a) Develop a strategy to maximize your average reward per move (equivalent to max- imizing total reward over n moves). Express this as a function of k, using Θ-notation. In other words your maximization doesn’t have to be entirely precise; you may assume that k is any convenient number that will make the math easier for your strategy, but you cannot assume that k = O(1). Notice that any strategy that you come up with provides a lower bound on reward optimality. The better the strategy, the better (higher) the lower bound. It’s trivial to get Ω(1) per move, so you must get ω(1).
(b) Now it’s time to figure out how good your strategy actually is. We will get an upper bound on the optimal reward for this game: Use amortization (specifically, the potential method) to obtain an upper bound on the best possible average reward. Ideally this upper bound should match what you get in part (a), using Θ-notation. If it doesn’t, then either your algorithm isn’t optimal, or your analysis in part (b) isn’t tight enough. If it helps to think in terms of cost instead of reward, pretend that your friend is playing this game and it will cost you because you must pay their reward. In this context, you want to find an upper bound on the total cost of your friend’s n moves, without having the slightest idea of what their strategy is. In other words you will get an upper bound on what you will pay your friend, before your friend even
starts to think about their strategy.
For amortization, as usual, you want to take advantage of the fact that “expensive” moves do not happen that often. Your Φ should create a ∆Φ that offsets expensive moves, making their amortized cost relatively smaller. So, first think about defining what an expensive move is, and what a non-expensive move is. It will help to have a good strategy in part (a) to determine what the cutoff should be. Then think about something that changes a lot in the configuration of columns whenever you have an expensive move, and use that as your ∆Φ, then reverse-engineer Φ. Always remember that when you evaluate Φi at any given time, you are taking a snapshot of the current state of the world. Φ cannot be a function of “what changed” between two iterations. That is the job of ∆Φ.
(c) Instead of the potential method, use the accounting method.
4. You are given a text T of n characters, and your goal is to find the length of a sub- sequence in T that is as long as possible and has the property that it reads the same forward and backward. For example, in XABCBBACXA, we can find XAB…BBA…X… to form the subsequence XABBBAX of length 7.
(a) Write a recursive formula to solve this, without getting LCS involved.
(b) Describe your dynamic programming table, and how it gets filled bottom-up. (where are the base cases, where is the answer, how do you calculate each item in the table?)
(c) What is the time and space complexity?
5. You and your friend are presented with a row of n buckets, each containing some amount of gold. Suppose that each amount is represented by some real number. You both decide to play a game, taking turns as follows. First you will keep either the first or the last bucket. Then your friend will keep the first or last of what remains, and so on. This will continue until you have partitioned the buckets.
(a) Provide a recursive formulation that returns the maximum amount of gold that you can acquire. This assumes that both sides are playing as best as possible, each to maximize their own yield.
(b) Analyze the time complexity of finding the maximum in part (a), via plain recur- sion and then via dynamic programming. What space complexity can you achieve?
6. You have an integer amount, n, of liquid to transport. You’re able to manufacture k different container types. Each type has a unique integer volume. In other words, for 1 ≤ i ≤ k, container type i fits bi units of liquid, where bi is an integer. You also know that one of the container types has unit volume (e.g., b1 = 1).
For each type you can produce as many containers as you like. Every container that you produce costs one dollar, regardless of volume. Every container that you use for transportation must be entirely full.
Show how we can determine the minimum cost (in dollars) to transport all the liquid. What is the time and space complexity of finding the minimum cost?
7. Suppose that you have two strings, S1,S2, each consisting of characters from some small alphabet. The lengths of the strings are k and n respectively. You can assume that n ≥ k but not that k is necessarily some small value.
If we alternate reading characters from one string and then the other, we create a “blend” of the two strings. For example if
S1 = DY NOGRASOAMA and S2 = AMICPRMMINGISZING we can create this blend: DYNAMICPROGRAMMINGISSOAMAZING
Note that the length of a blend is n+k, and there can be many blends.
Now for the problem:
Given three strings S1, S2 and C, determine if C is a blend of S1 and S2. If S1 and S2 have size k and n respectively, the time complexity should be O(kn).
You should address the following in your answer:
Formulate the problem recursively, including an informal justification for its correct- ness. (How can you categorize subproblems that will be helpful to solve first?) How many distinct subproblems are there? Mention what you consider to be a base case. What is the size of the dynamic programming table that you will use, how do you fill it in, and where are the base cases and final answer located?
8. Show how to determine whether a directed graph G contains a vertex with in-degree V −1 and out-degree 0, in time O(V ), given an adjacency matrix for G.
9. You’ve invited n friends to a party. Your palace has two floors, each of which can fit everyone invited. The problem is, some of your friends don’t like each other, and refuse to be on the same floor. Each person gives you a list of who they like and a list of who they don’t like. How do you set this up as a graph problem and figure out if everyone can come to your party?
10. Let G be a graph with red, blue and white vertices. Show how to identify all red vertices that have a path to at least one blue vertex without going through other red vertices. Argue correctness and provide a time complexity for your algorithm.