13 practice problems.
1. You are given a text T of n characters, and your goal is to find the length of a subsequence 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?
2. 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 recursion and then via dynamic programming. What space complexity can you achieve?
3. 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?
4. 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 correctness. (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?
5. 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.
6. 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?
7. For a connected graph G with distinct weights, initialize an edgeless forest, F, as V connected components; one per vertex of G. Here are two ideas for transforming F into a MST of G. Do they work? Why?
(a) arbitrarily choose two components C1, C2 of F that have at least one edge connecting them in G, and add the lightest edge between C1 and C2 to F. Merge C1,C2, and repeat until F is reduced to one component.
(b) simultaneously (in parallel) let every component select the lightest edge that connects it to the set of vertices not in that component. If an edge is selected twice, just count it once. After adding all such selected edges to F and merging components in the standard way, repeat until F is reduced to one component.
See CLRS 23-4 for other similar proposed MST ideas.
8. Let G be a directed 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.
9. (a) Given a connected graph G with distinct weights, explain how to construct a spanning tree T with maximum sum of weights. Mention the time complexity and briefly explain why the algorithm is correct. If you rely on concepts covered in class, you don’t need to prove their properties from scratch, instead just refer to them.
(b) Show that for every two vertices x, y in G the following holds:
Every path from x to y in G contains an edge with a weight that is no greater than the smallest weight in the path from x to y in T . In other words, T maximizes the “weakest connecting link”, for every pair of vertices.
10. Let G be a graph for which all edge weights are greater than 1. For two vertices x, y in G, we want to find a path from x to y that minimizes the product of edge-weights. Show how to do this.
11. An infectious disease starts at a node x in a weighted graph. The time it takes to move along an edge is equal to the weight of the edge. Whenever it gets to an unprotected node, that node gets infected and the disease keeps moving in parallel along all incident edges. In the beginning, all nodes are unprotected. However, at some node y in the graph, an antidote is released, at the same time as the disease. It moves along the graph just as the disease does, and if it reaches an uninfected node, it protects that node forever.
At any node that is reached simultaneously, the disease and the antidote neutralize (forever), and neither gets to keep traveling along incident edges. However, the node is left partially damaged.
Show how to determine whether more nodes will be (fully) infected or protected.
12. Prove or disprove that Dijkstra’s algorithm can be modified to work on a graph with negative edge weights, if we first scan all edges, find the minimum weight w, and add |w| to the weight of every edge.
13. Let G = {V,E} be a weighted directed graph with no negative cycles. However, G contains precisely one negative edge e, from vertex x to vertex y.
Given a source, s, show how to solve SSSP in O(E log V ) time.