Problem Set 3

Which of the following is true for our dynamic programming algorithm for computing a maximum-weight independent set of a path graph? (Assume there are no ties.)

As long as the input graph has at least two vertices, the algorithm never selects the minimum-weight vertex.

The algorithm always selects the maximum-weight vertex.

If a vertex is excluded from the optimal solution of two consecutive subproblems, then it is excluded from the optimal solutions of all bigger subproblems.

If a vertex is excluded from the optimal solution of a subproblem, then it is excluded from the optimal solutions of all bigger subproblems.

ANSWER: Consider the path $10 - 2 - 1 - 4$ . The vertices selected by the algorithm are $10, 1$ , where $1$ , the minimum, is selected. Thus, option 1 is incorrect.

Consider the path $1 - 3 - 10 - 9$ . The vertices selected by the algorithm are $3, 9$ , where the maximum $10$ isn’t selected. Thus, option 2 is incorrect.

Consider the path $1 - 9 - 7 - 1 - 5$ . The vertices selected by the algorithm are $1, 7, 5$ . However, $7$ was not included in the optional solution of the subproblem $1 - 9 - 7$ . Note that, $7$ was not included in the optional solution of the subproblem $1 - 9 - 7 - 1$ either, because the its previous vertex was “heavier”, and since all weights are positive, the sum of the next weight and the heavier vertex is certainly greater than $7$ . Thus, option 4 is incorrect.

Option 3 is correct. This follows from induction, since the optimal solution to a subproblem depends only on the solutions of the previous two subproblems.

Recall our dynamic programming algorithm for computing the maximum-weight independent set of a path graph. Consider the following proposed extension to more general graphs. Consider an undirected graph with positive vertex weights. For a vertex $𝑣$ , obtain the graph $𝐺' (𝑣)$ by deleting $𝑣$ and its incident edges from $𝐺$ , and obtain the graph $𝐺 ″ (𝑣)$ from $𝐺$ by deleting $𝑣$ , its neighbors, and all of the corresponding incident edges from $𝐺$ . Let $𝑂 𝑃 𝑇 (𝐻)$ denote the value of a maximum-weight independent set of a graph $𝐻$ . Consider the formula $𝑂 𝑃 𝑇 (𝐺) = m a x {𝑂 𝑃 𝑇 (𝐺' (𝑣)), 𝑤 𝑣 + 𝑂 𝑃 𝑇 (𝐺 ″ (𝑣))}$ , where $𝑣$ is an arbitrary vertex of $𝐺$ of weight $𝑤 𝑣$ . Which of the following statements is true?

The formula is always correct in trees, and it leads to an efficient dynamic programming algorithm.

The formula is always correct in trees, but does not lead to an efficient dynamic programming algorithm.

The formula is correct in path graphs but is not always correct in trees.

The formula is always correct in general graphs, and it leads to an efficient dynamic programming algorithm.

ANSWER: Clearly, both $𝐺'$ and $𝐺 ″$ are trees if $𝐺$ is a tree. If there was no cycle in $𝐺$ , there’re none in $𝐺'$ and $𝐺 ″$ either. Also, removing an edge and all its incident edges preserves connectivity among the remaining vertices. Thus, $𝐺'$ and $𝐺 ″$ exhibit optimal substructures, and hence the algorithm is correct for trees. However, we can’t prove optimal substructure property for arbitrary general graphs. Thus, option 1 is correct, and the rest are not. The time complexity is $𝑂 (| 𝑉 |)$ ; see MWIS in a Tree - Chen + Kuo + Sheu].

Consider a variation of the Knapsack problem where we have two knapsacks, with integer capacities $𝑊 1$ and $𝑊 2$ . As usual, we are given $𝑛$ items with positive values and positive integer weights. We want to pick subsets $𝑆 1, 𝑆 2$ with maximum total value (i.e., $\sum 𝑖 \in 𝑆 1 𝑣 𝑖 + \sum 𝑖 \in 𝑆 2 𝑣 𝑖$ ) such that the total weights of $𝑆 1$ and $𝑆 1$ are at most $𝑊 1$ and $𝑊 2$ , respectively. Assume that every item fits in either knapsack (i.e., $𝑤 𝑖 \leq m i n {𝑊 1, 𝑊 2}$ for every item $𝑖$ ). Consider the following two algorithmic approaches. (1) Use the algorithm from lecture to pick a max-value feasible solution $𝑆 1$ for the first knapsack, and then run it again on the remaining items to pick a max-value feasible solution $𝑆 2$ for the second knapsack. (2) Use the algorithm from lecture to pick a max-value feasible solution for a knapsack with capacity $𝑊 1 + 𝑊 2$ , and then split the chosen items into two sets $𝑆 1 + 𝑆 2$ that have size at most $𝑊 1$ and $𝑊 2$ , respectively.

Which of the following statements is true?

Algorithm (1) is guaranteed to produce an optimal feasible solution to the original problem provided $𝑊 1 = 𝑊 2$ .

Algorithm (1) is guaranteed to produce an optimal feasible solution to the original problem but algorithm (2) is not.

Algorithm (2) is guaranteed to produce an optimal feasible solution to the original problem but algorithm (1) is not.

Neither algorithm is guaranteed to produce an optimal feasible solution to the original problem.

ANSWER: Consider the set of items $𝑆 (𝑤 𝑖, 𝑣 𝑖) = (1, 2), (2, 1), (3, 10), (4, 7)$ and two sacks of equal capacities $5$ . Algorithm 1 picks $𝑠 1$ and $𝑠 3$ in the first iteration, and $𝑠 4$ in the second ( $𝑠 2$ is not picked). Total value of both sacks $12 + 7 = 19$ . However, the optimal solution would put $𝑠 1$ and $𝑠 4$ in one sack, and $𝑠 2$ and $𝑠 3$ in the other, bringing the total value of both sacks to $9 + 11 = 20$ . Thus, option 1 is incorrect.

Consider the set of items $𝑆 (𝑤 𝑖, 𝑣 𝑖) = (3, 10), (3, 10), (4, 2)$ and two sacks of capacities $7$ and $3$ , respectively. Algorithm 1 picks $𝑠 1$ and $𝑠 2$ in the first iteration, and nothing in the second iteration. Total value of both sacks $20$ . However, the optimal solution would put $𝑠 1$ and $𝑠 3$ in one sack, and $𝑠 2$ in the other, bringing the total value of both sacks to $12 + 10 = 22$ . Thus, option 2 is incorrect.

Consider the set of items $𝑆 (𝑤 𝑖, 𝑣 𝑖) = (4, 10), (4, 10), (4, 10), (2, 1)$ and two sacks of equal capacities $6$ . Algorithm 2 picks $𝑠 1, 𝑠 2, 𝑠 3$ , but this set cannot fit into two sacks, so one is dropped when redistributing. Total value of both sacks $10 + 10 = 20$ . However, the optimal solution would put $𝑠 1$ and $𝑠 4$ in one sack, and $𝑠 2$ in the other ( $𝑠 3$ is not picked), bringing the total value of both sacks to $11 + 10 = 21$ . Thus, option 3 is incorrect.

Option 4 is correct based on the above counterexamples.

A correct algorithm would consider both sacks, and the following three cases:

Item is put into sack 1.
Item is put into sack 2.
Item is not put into any sack.

The recurrence, therefore, is:

𝑎 [𝑖] [𝑗] [𝑘] = m a x {𝑎 [𝑖 - 1] [𝑗] [𝑘], 𝑎 [𝑖 - 1] [𝑗 - 𝑤 𝑖] [𝑘] + 𝑐 𝑖, 𝑎 [𝑖 - 1] [𝑗] [𝑘 - 𝑤 𝑖] + 𝑐 𝑖}

where $𝑖$ is the index corresponding to the items, $𝑗$ corresponding to sack 1, and $𝑘$ corresponding to sack 2.

Recall the dynamic programming algorithms from lecture for the Knapsack and sequence alignment problems. Both fill in a two-dimensional table using a double-for loop. Suppose we reverse the order of the two for loops. (I.e., cut and paste the second for loop in front of the first for loop, without otherwise changing the text in any way.)

Are the resulting algorithms still well defined and correct?

Neither algorithm remains well defined and correct after reversing the order of the for loops.

The Knapsack algorithm remains well defined and correct after reversing the order of the for loops, but the sequence alignment algorithm does not.

The sequence alignment algorithm remains well defined and correct after reversing the order of the for loops, but the Knapsack algorithm does not.

Both algorithms remain well defined and correct after reversing the order of the for loops.

ANSWER: The recurrence for the knapsack problem is $𝑎 [𝑖] [𝑥] = m a x {𝑎 [𝑖 - 1] [𝑥], 𝑎 [𝑖 - 1] [𝑥 - 𝑤 𝑖]}$ . What we care about is that the array entries on the R.H.S. have already been populated by the time we attempt to populate $𝑎 [𝑖] [𝑥]$ . Clearly, the order of the for loops doesn’t matter; the lecture has $𝑥$ in the inner loop, but if we have it in the outer, the $(𝑖 - 1)$ -th entries for some $𝑥$ are still populated before $𝑖$ -th entry. Thus, option 4 is correct.

Consider an instance of the optimal binary search tree problem with 7 keys (say 1,2,3,4,5,6,7 in sorted order) and frequencies $𝑤 1 = . 05, 𝑤 2 = . 4, 𝑤 3 = . 08, 𝑤 4 = . 04, 𝑤 5 = . 1, 𝑤 6 = . 1, 𝑤 7 = . 23$ .

What is the minimum-possible average search time of a binary search tree with these keys?

2.08

2.42

2.9

2.18

ANSWER: Option 4 is correct. See the code on GitHub.

The following problems all take as input two strings $𝑋$ and $𝑌$ , of length $𝑚$ and $𝑛$ , over some alphabet $Σ$ . Which of them can be solved in $𝑂 (𝑚 𝑛)$ time? [Check all that apply.]

Compute the length of a longest common substring of $𝑋$ and $𝑌$ . (A substring is a consecutive subsequence of a string. So “bcd” is a substring of “abcdef”, whereas “bdf” is not.)

Compute the length of a longest common subsequence of $𝑋$ and $𝑌$ . (Recall a subsequence need not be consecutive. For example, the longest common subsequence of “abcdef” and “afebcd” is “abcd”.)

Assume that $𝑋$ and $𝑌$ have the same length $𝑛$ . Does there exist a permutation $𝑓$ , mapping each $𝑖 \in {1, 2, \dots, 𝑛}$ to a distinct $𝑓 (𝑖) \in {1, 2, \dots, 𝑛}$ , such that $𝑋 𝑖 = 𝑌 𝑓 (𝑖)$ for every $𝑖 = 1, 2, \dots, 𝑛$ ?

Consider the following variation of sequence alignment. Instead of a single gap penalty $𝛼 𝑔 𝑎 𝑝$ , you’re given two numbers $𝑎$ and $𝑏$ . The penalty of inserting $𝑘$ gaps in a row is now defined as $𝑎 𝑘 + 𝑏$ , rather than $𝑘 𝛼 𝑔 𝑎 𝑝$ . Other penalties (for matching two non-gaps) are defined as before. The goal is to compute the minimum-possible penalty of an alignment under this new cost model.

ANSWER: Let $𝑋 𝑖$ denote the prefix of $𝑋$ including the character at the i-th position, and $𝑌 𝑗$ denote the prefix of $𝑌$ including the character at the j-th position. The characters at the last positions of $𝑋 𝑖$ and $𝑌 𝑗$ either match or don’t; a match increases the length of the longest common substring found so far by one. Thus, if $𝐿 𝑖$ denotes the length of the longest common substring of $𝑋 𝑖$ and $𝑌 𝑗$ , the recurrence can be written as:

𝐿 𝑖, 𝑗 = {𝐿 𝑖 - 1, 𝑗 - 1 + 1 i f 𝑋 [𝑖] = 𝑌 [𝑗] 0 o t h e r w i s e

To find the longest common substring, we can either keep track of the maximum positive value while populating the array, or find it later by scanning each element (yikes!). Once found, follow the usual reconstruction procedure as explained in the lectures.

Clearly, this can be solved in $𝑂 (𝑚 𝑛)$ time. Thus, option 1 is correct.

The longest subsequence problem is similar to the longest substring, except for a no match, we pick up the match value so far. The recurrence can be written as:

𝐿 𝑖, 𝑗 = {𝐿 𝑖 - 1, 𝑗 - 1 + 1 i f 𝑋 [𝑖] = 𝑌 [𝑗] m a x {𝐿 𝑖 - 1, 𝑗, 𝐿 𝑖, 𝑗 - 1} o t h e r w i s e

Clearly, this can be solved in $𝑂 (𝑚 𝑛)$ time. Thus, option 2 is correct. Alternatively, this reduces to sequence alignment by setting the gap penalty to 1 and making the penalty of matching two different characters to be very large.

Problem in option 3 can be solved in $𝑂 (𝑛)$ time, without dynamic programming. We simply count the frequency of each symbol in each string. The permutation $𝑓$ exists if and only if every symbol occurs exactly the same number of times in each string.

Problem in option 4 is a variation of the original sequence alignment dynamic program. With each subproblem, we need to keep track of what gaps we insert, since the costs incurred at the current position depend on whether or not the previous subproblems inserted gaps. Blows up the number of subproblems and running time by a constant factor, but still can be solved in $𝑂 (𝑛)$ time. Thus, option 4 is correct.

Recall our dynamic programming algorithms for maximum-weight independent set, sequence alignment, and optimal binary search trees. The space requirements of these algorithms are proportional to the number of subproblems that get solved: $Θ (𝑛)$ (where $𝑛$ is the number of vertices), $Θ (𝑚 𝑛)$ (where $𝑚, 𝑛$ are the lengths of the two strings), and $Θ (𝑛 2)$ (where $𝑛$ is the number of keys), respectively.

Suppose we only want to compute the value of an optimal solution (the final answer of the first, forward pass) and don’t care about actually reconstructing an optimal solution (i.e., we skip the second, reverse pass over the table). How much space do you then really need to run each of three algorithms?

$Θ (1), Θ (𝑛) a n d Θ (𝑛 2)$
$Θ (𝑛), Θ (𝑚 𝑛) a n d Θ (𝑛 2)$
$Θ (1), Θ (𝑛) a n d Θ (𝑛)$
$Θ (1), Θ (1) a n d Θ (𝑛)$

ANSWER: The MWIS problem only ever looks at the last two columns ( $𝑖 - 1$ and $𝑖 - 2$ ), thus, we can get away with storing just those two values.

The sequence alignment problem may need to look at the previous row ( $𝑃 𝑖 - 1, 𝑗$ or $𝑃 𝑖 - 1, 𝑗 - 1$ ), or the previous column in the current row ( $𝑃 𝑖, 𝑗 - 1$ ). Thus, we can only store two rows, which takes linear space.

Unfortunately, the optional BST problems needs to keep track of $𝑛 2$ subproblems, and can’t be solved in reduced space.

Thus, option 1 is correct.

Share on

Twitter Facebook LinkedIn

Problem Set 3

Share on

Leave a comment

You may also enjoy

Scala Curated

Python Curated

System Design Curated

Online Algorithm Courses