CSCI 3110 Practice Midterm 2 Solutions 6.11.2019
Topics: algorithms with data structures, minimum spanning trees,
NP-completeness
1. (2 marks) Consider the problem longestValidParentheses:
Given a string containing just the characters ’(’ and ’)’,
find the length of the longest valid (well-formed) parentheses
substring.∗
There’s a short, fast stack-based solution — given on the penultimate
page of this document — but it turned out to be too tricky for me to ask
about on a midterm, alas. There’s a slightly longer, slightly slower but
theoretically nicer (and still linear-time) stack-based solution — given
on the ultimate page of this midterm, with -1 and -2 representing ’(’
and ’)’ — which is to push the characters of the string on the stack
one by one while following these three rules:
• whenever the top two elements on the stack are ’(’ and (on top)
’)’, do X;
• whenever the top three elements on the stack are ’(’, a number,
and (on top) ’)’, do Y;
• whenever the top two elements on the stack are two numbers, do Z.
After we’ve pushed the last character, we return the largest number in
the stack. What are X, Y and Z?
Solution:
• X is “pop ’)’ and ’(’ and push 2”;
• Y is “pop ’)’, the number and ’(’, and push the number plus 2”;
• Z is “pop the two numbers and push their sum”.
∗https://leetcode.com/problems/longest-valid-parentheses
a
b c d
e
fgh
i
4
8
1
11
7
2
8
6
4 14
7
2
10
9
Figure 1: An edge-weighted graph.
2. (2 marks) I told you in class that the amortized analysis of the union-
find data structure holds only when you don’t undo union operations.
If you don’t use path compression during the find operations, however,
then union and undo take O(1) time and find takes O(log n) time, where
n is the number of operations.†
Show how to modify Kruskal’s algorithm such that it still runs in O(m logm)
time, where m is the number of edges, but if the kth heaviest edge in
the graph is later deleted — say that road is washed away or something
— then you can fix the minimum spanning tree in O(k log n) time.
Solution: Keep the sorted list L of the edges and mark which ones are
in the minimum spanning tree. Also keep a stack S containing all the
pairs of vertices you union during the algorithm’s execution. If the kth
heaviest edge e is later deleted, walk backward through L until finding
e after k steps. If e is not a tree edge, simply delete it from L and stop.
If it is a tree edge, then pop pairs off S until you pop the pair whose
components are e’s endpoints; undo all those unions; and unmark all
the corresponding edges in L (again, working backwards). This has the
effect of reversing the algorithm’s execution to the point just before it
select e. Delete e and rerun the rest of the algorithm’s execution.
3. (2 marks) List the edges in a minimum spanning tree of the graph in
Figure 1, in the order Kruskal’s algorithm would select them.
Solution: Since there are equal-weight edges, there are several choices
of minimum spanning tree; you can list the edges in any of them. For
example, (g, h), (f, g), (c, i), (c, f), (a, b), (c, d), (b, c), (d, e).
†It’s actually possible to do them all in O(log log n) time:
https://link.springer.com/chapter/10.1007/3-540-16761-7 73 .
4. (2 marks) Recall that for Subset Sum we are given a set X = {x1, . . . , xn}
of numbers and a target t and asked if there is a subset {xi1, . . . , xik} of X
such that xi1 +xi2 + · · ·+xik = t. You saw in tutorial that Subset Sum
is NP-complete. Show it is only NP-hard in the weak sense by giving a
dynamic-programming algorithm for it that runs in time polynomial in
n and t. You can assume all the values are positive integers.
Solution: We create a two-dimensional Boolean matrix A[0..n][0..t]. We
will set A[i][j] to true if it is possible to select a subset of {x1, . . . , xi}
that sums to j. We start by setting A[0][0] to true and A[0][j] to false
for all j > 0. For i from 1 to n and j from 0 to t, we then set
A[i][j] = A[i− 1][j] ∨ A[i− 1][j − xi]
(considering A[i][j′] to be false for all j′ < 0). We return A[n][t]. 5. (2 marks) For the Hamiltonian-path problem, HamPath, we are given a graph G and asked if there is a path in G that visits each vertex exactly once. HamPath is NP-complete even when G is restricted to be a subgraph of the square grid graph‡; Figure 2 (left) shows an example. For the problem Wordz2, we are given a grid of characters, a dictionary of strings, and a number k, and asked it is possible to generate k distinct strings in the dictionary using the following rules for each string: (a) start on any unvisited character in the grid and output it; (b) repeatedly move one step up, down, left or right to an unvisited character and output it. Figure 2 (right) shows a grid with four strings highlighted with colours. Show that Wordz2 is NP-complete§ by (a) showing it is in NP; (b) showing that HamPath on subgraphs of the square grid graph re- duces to it in polynomial time. ‡The vertex set of the square grid graph is {(i, j) : i, j ∈ Z} and the edge set is {((i, j), (i′, j′)) : |i− i′|+ |j − j′| = 1}. §Apparently first proven by a student in my fourth-year String Algorithms class in 2014 as part of his course project; I was impressed. Figure 2: Left: A subgraph of the square grid graph. Right: An example of Wordz2. (Hint: your dictionary can be one binary string and your grid of char- acters can contain only two distinct characters, one for vertices in the graph and the other for edges.) Solution: To see that Wordz2 is in NP, consider that if someone gives us a list of k distinct strings in the dictionary and grid coordinates for each character in each of those strings, then we can check in polynomial time • whether each character occurs where it should, • whether consecutive characters in the strings are at adjacent grid positions, • whether any of the grid coordinates are duplicates. One possible reduction is as follows: given an n-vertex subgraph of the square grid graph, we build a grid of characters by replacing each vertex in the graph by v, each edge by e, and each missing vertex or edge by x, and we set the dictionary to be the single string (ve)n−1v . For example, the graph shown above becomes v e v e v x x x x e x e x x x x v x v e v x x e x e x e x x v e v e v x x x x e x x x x x x v x x with the dictionary {“vevevevevevevevevev”}.