Home
Syllabus
Classwork
printable version
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]
[10 pts]
Following is a poor implementation of merge sort in Java.
In terms of n, the number of elements in the parameter ArrayList,
how fast is it on a single processor? Provide the simplest and tightest
big-O bound that you can, and justify your answer.
public static void mergeSort(ArrayList<Integer> nums) {
if(nums.size() <= 1) return;
ArrayList<Integer> a = new ArrayList<Integer>();
ArrayList<Integer> b = new ArrayList<Integer>();
for(int i = 0; i < nums.size(); i++) {
if(i % 2 == 0) a.add(nums.get(i));
else b.add(nums.get(i));
}
mergeSort(a);
mergeSort(b);
nums.clear();
while(!a.isEmpty() && !b.isEmpty()) {
if(a.get(0).intValue() < b.get(0).intValue()) nums.add(a.remove(0));
else nums.add(b.remove(0));
}
nums.addAll(a);
nums.addAll(b);
}
The overall time taken by this poor merge sort implementation is O(n²).
While the first loop still takes O(n)
time, the second loop — which performs the merge —
now takes O(n²) time. This is because it
repeeatedly removes from the front of the ArrayList,
and each removal necessitates shifting all existing elements forward;
thus, each iteration of the loop takes O(n)
time, and there could be as many as n iterations of this
loop. As a result, we can build the following recurrence describing
the time for this method.
| T(n) = { | C | if n ≤ 1 |
| 2 T(n/2) + D n² | if n > 1 |
This recurrence matches the form for the Master Theorem, with a = 2, b = 2, and d = 2. Since logb a (which is log2 2 = 1) is less than d, the Master Theorem says that the solution to this recurrence is O(n²).
[10 pts] Suppose we perform a depth-first search on the below dag, recursing on adjacent nodes in alphabetical order, using the algorithm described in class. What is the pre and post number that is associated with each vertex?
 |
|
| pre | post | |
| a | 2 | 3 |
| b | 1 | 10 |
| c | 4 | 5 |
| d | 6 | 9 |
| e | 0 | 17 |
| f | 7 | 8 |
| g | 11 | 14 |
| h | 15 | 16 |
| i | 12 | 13 |
[10 pts]
Software for typesetting text must automatically decide where to
place the line breaks between words in a paragraph. One approach for
this, used in high-quality typesetting programs such as TEX, is to
define a cost function computing with the badness
of each line,
defined by a function c(i, j), which might be defined as ∞
if the line including words i through j simply is too long to
fit into the available space; but if the words fit, it yields a number
such as
(You don't have to worry about this formula for this problem.)
Assuming we have the badness
function already defined, we can
write a recurrence for computing the smallest overall badness for
each possible way to break lines in a paragraph of words.
| f(j) = { | c(1, j) | if c(1, j) ≠ ∞ |
| min1 ≤ k < j (f(k) + c(k + 1, j)) | if c(1, j) = ∞ |
Using dynamic programming, convert this recurrence into a Java
method that takes O(n²) time, assuming
that a method c has already been defined and takes
O(1) time for each invocation. The c method
returns Integer.MAX_VALUE to signify an infinite return
value.
public static int f(int n) {
int[] table = new int[n + 1];
for(int j = 1; j <= n; j++) {
if(c(1, j) == Integer.MAX_VALUE) {
int min = Integer.MAX_VALUE;
for(int k = 1; k < j; k++) {
int cv = c(k + 1, j);
if(cv != Integer.MAX_VALUE) {
if(table[k] + cv < min) min = table[k] + cv;
}
}
table[j] = min;
} else {
table[j] = c(1, j);
}
}
return table[n];
}
[14 pts] In the DOMINATING SET problem, we're given a directed graph G and an integer k, and we wish to find a set of k vertices in G so that every vertex is either in the selected set or has an edge coming from the selected set into it. For example, in the dag of Problem 2, the set of vertices {a, d, e, h} is a dominating set with four vertices, and there are many other four-vertex dominating sets; however, {b, e, g}. is the only three-vertex dominating set.
Using the fact that SET COVER is already known to be NP-hard, prove that DOMINATING SET is NP-hard. (If you cannot come up with a reduction that works perfectly, you can still receive partial credit (6 pts) for giving an outline of how one would prove this.)
Suppose we're given a SET COVER instance consisting of a collection {S0, S1, …, Sm − 1} of subsets of some universe V, along with some target number t of subsets to select in order to cover U. We will show how to convert this into a DOMINATING SET problem whose solution solves the original SET COVER problem.
Our corresponding DOMINATING SET graph will have a vertex for
each element of the universe U as well as a vertex
for each subset Si
and another grandparent
vertex. We will have a directed edge from
this grandparent vertex to each vertex corresponding to a subset
Si. For each subset
Si, we will also have
a directed edge from the subset's vertex to the vertex corresponding
to each element of the subset. Our target k for this DOMINATING SET problem will be t + 1 — i.e., one more than for the original SET COVER problem.
We need to show that there is a solution to the SET COVER problem
if and only if there is a solution to the constructed DOMINATING SET
problem. We first do the only if
: Suppose there were a SET
COVER consisting of t subsets. We could then select each
of the vertices in the DOMINATING SET graph corresponding to one of
the selected subsets; this would cover all vertices corresponding to
elements of U, since the subsets themselves cover all of
U. We will also select the grandparent vertex, which covers
itself and all the remaining vertices corresponding to subsets. This
covers all vertices in the graph, and so there is a solution to the
DOMINATING SET problem using t + 1 vertices.
Now we go in the other direction: Suppose there is a DOMINATING SET solution — does that imply a solution to the original SET COVER problem? First, observe that the DOMINATING SET solution need not include any vertices corresponding to elements from U: If such a vertex is selected, we can unselect it, and instead select a vertex corresponding to a subset containing that element. So we'll assume that no vertices corresponding to U elements are selected. Our solution to SET COVER is then simply to select all those subsets corresponding to vertices selected in the DOMINATING SET solution. The subsets so selected will end up covering all of U, because their corresponding vertices cover all of the vertices corresponding to elements of U. The number of such subsets cannot exceed t, since at most t + 1 vertices are selected, of which one will have to be the grandparent vertex (since there is no other way to cover that vertex), and as we've seen, we can ensure that none of the selected vertices correspond to elements of U. Thus the other t must correspond to subsets.
[8 pts] We manage a cargo plane with three compartments: front, center, and rear. The front compartment can hold at most 10 tons, the center compartment 16 tons, and the rear compartment 8 tons.
In order to balance the plane, each compartment must be filled to the same proportion by weight. Thus, if the front compartment holds 5 tons, then the center compartment must hold 8 tons, and the rear compartment must hold 4 tons.
We have four customers who have requested shipment. Each is perfectly happy if we choose to ship only a fraction of the request. We may split any shipment among the three compartments as we like, and we may mix multiple shipments' cargo into the same compartment.
| weight | profit | |
| (tons) | ($ per ton) | |
| A | 18 | 310 |
| B | 15 | 380 |
| C | 23 | 350 |
| D | 12 | 285 |
Write a linear program that determines how much of each customer's request to satisfy and how to apportion each shipment among the compartments. Be sure to explain what your variables mean; you need not justify your answer further.
We define variables fA, fB, fC, and fD representing the amount (measured in tons) of each customer's shipment placed in the front compartment; cA, cB, cC, and cD representing the amounts for the center compartment; and rA, rB, rC, and rD representing the amounts for the rear compartment.
| maximize | 310 (fA + cA + rA) + 380 (fB + cB + rB) + 350 (fC + cC + rC) + 285 (fD + cD + rD) | ||
| where | fA + fB + fC + fD | ≤ | 10 |
| cA + cB + cC + cD | ≤ | 16 | |
| rA + rB + rC + rD | ≤ | 8 | |
| (1/10) fA + (1/10) fB + (1/10) fC + (1/10) fD | = | (1/16) cA + (1/16) cB + (1/16) cC + (1/16) cD | |
| (1/10) fA + (1/10) fB + (1/10) fC + (1/10) fD | = | (1/8) rA + (1/8) rB + (1/8) rC + (1/8) rD | |
| fA + cA + rA | ≤ | 18 | |
| fB + cB + rB | ≤ | 15 | |
| fC + cC + rC | ≤ | 23 | |
| fD + cD + rD | ≤ | 12 | |
| fx | ≥ | 0 for x in {A, B, C, D} | |
| cx | ≥ | 0 for x in {A, B, C, D} | |
| rx | ≥ | 0 for x in {A, B, C, D} | |
[8 pts] Execute the Ford-Fulkerson algorithm for computing the maximum flow of the directed graph. With each step of the algorithm you should always choose the available path with fewest edges, breaking ties by choosing the maximum-capacity path. Identify each path selected, and draw a graph showing the final flow along each edge.
| edge capacities | paths taken (you need not use all blanks) | edge flows (final result) |
 |
1.
2. 3. 4. 5. |
 |
| paths taken | edge flows |
| 1. s-a-b-t
2. s-c-d-e-t 3. s-c-d-b-a-e-t |
 |
[6 pts] When studying edge coloring, we saw that χ′(G) ≥ Δ(G). Explain why this is true.
This inequality says that the number of colors required for a valid edge coloring must be at least the graph's maximum degree. Consider the vertex whose degree is maximum: Each edge incident on that vertex must be given a different color, since they all have that vertex in common. Thus we need at least as many colors as there are edges incident to the vertex — which is to say that we need at least as many colors as the degree of the vertex, which we selected so that its degree is Δ(G).
[6 pts] Describe Karger's O(n4) algorithm for finding the minimum cut in an unweighted graph.
Karger's algorithm is to randomly select an edge in the graph and
combine (contract
) its two endpoints into a single vertex,
merging the edges of the two endpoints together (keeping any duplicate
edges so created). We repeat this process until our graph has just
two vertices left; the remaining edges are the edges in our candidate
cut. This algorithm takes O(n²) time,
since each contraction takes O(n) time and
there will be n − 2 contractions.
However, this algorithm is not likely to find the minimum cut — the probability that it finds the minimum cut is about 1/n². Thus, Karger's algorithm repeats the process of the previous paragraph O(n²) times, so that it is likely to happen upon the true minimum cut. It outputs the smallest cut that it finds among all these attempts.
[10 pts]
Suppose we're using an n-processor shared-memory system allowing
concurrent reads. We have an n-integer array p
representing a tree, with one node for each array element, where
p[i] is the index of the node that is node i's
parent (or −1 if the node is the root). We have another n-integer
array d, initially all
0's, which we want to assign so that d[i] is the depth of
node i. The following illustration gives an example input
p, the tree that it describes, and the desired
output d.
 |
pp = p[pid];
d[pid] = pp >= 0 ? 1 : 0;
while(pp >= 0) {
dd = d[pid] + d[pp];
d[pid] = dd;
pp = p[pp];
p[pid] = pp;
}
|
To do this, each processor executes the algorithm given at right. (All processors execute this code in lockstep.) Remembering that we have a processor for each node of the tree, how much time does this algorithm take? Give the tightest and simplest big-O bound that you can, and justify your answer. Express your answer in terms of n, the number of nodes in the tree, and/or d, the tree's depth.
O(log d). The loop maintains three
invariants: First, pp matches
p[pid]. Second, d[i] is the distance
from i to p[i] in the
original tree.
And finally, if p[i] is not −1, then
d[i] is
2k, where k is
the number of iterations of the loop thus far.
It is easy to see that this holds entering the loop:
pp was initialized to p[pid],
d[i] was initialized to 1 for everything
but the root, and to 0 for the root; that is indeed
the distance from node i to the root.
And finally, for p[i] is not −1
for all non-root nodes, and for all of those i,
d[i] is 1, which matches
20 — and there have been 0
iterations at the beginning.
If the invariant holds at the loop's beginning, it will still
hold at the end. The first part about pp matching
p[pid] obviously
still holds, because the loop's final assignment assures this.
The second part holds because dd
is computed as the distance from node pid
to pp's parent — and by the end of the loop,
p[pid] has changed to be
the parent of what pp referenced at the iteration's
beginning. And finally, if it happens that pp's parent
is not −1 (and thus p[pid] is
not −1 at the iteration's end), then d[pp] must be
2k at the loop's beginning,
as must be d[pid], so the value of
d[pid] must end up being
2 ⋅ 2k
= 2k + 1.
Since k + 1 is the number of iterations
completed at the iteration's end, we still have that any entry
for which p is not −1, the corresponding
entry in d is 2# iters.
The consequence of this invariant is that each entry in
d continues to double until the final iteration.
Since no entry in d can exceed d, it
follows that the number of iterations must not exceed
⌈log2 d⌉.
[10 pts] Suppose we're given an n-element array of (θ, d) pairs, representing a sequence of commands to a turtle to turn counterclockwise θ degrees and then go forward d units. Below is an example array and the corresponding movement it represents, where the turtle's initial orientation is to the east — though the first command immediately turns the turtle to face northeast.
| array of commands | movement diagram |
| <(45, 40), (30, 50), (105, 40), (90, 20)> |  |
Suppose we have a p-processor system, and we want to compute the turtle's final location in O(n/p + log p) time. Define an algorithm, using the parallel scan and/or parallel prefix scan algorithms we saw in class. Argue briefly that your algorithm works correctly.
Note: You may not find this useful, but: If the first two commands are (θ0, d0) and (θ1, d1), then after executing the command the distance from the turtle's starting location to its current location is
I know of two very different approaches to this problem.
In the first, we define a new operator ⊗:
Essentially, this operator is saying that performing the two commands (θ, x) and (φ, y) is equivalent to turning an angle of θ + φ just once and going a distance of sqrt(x² + y² + 2 x y cos φ)) in that direction.
We can then perform a parallel scan of the array using this operator, ending up with a final result of (θtotal, dtotal). That is the final location in polar coordinates; if we want the location in Cartesian coordinates, we can compute those as (dtotal cos θtotal, dtotal sin θtotal)
The second approach is converts the computation into Cartesian coordinates earlier. We first apply a parallel prefix sum to the first entry of all the pairs, thus converting the turn angles to compass directions. In the example of the problem, our pairs would become: <(45, 40), (75, 50), (180, 40), (270, 20)>.
Then we convert each pair (φ, d) into (d cos φ, d sin φ), thus getting the change in x-coordinate and change in y-coordinate of each movement. And finally we perform two parallel sums, one for each of the coordinates. We would end up with the total change in x-coordinate and total change in y-coordinate.
[8 pts] Suppose we're working on a problem where n is the number of bits in the problem input and p is the number of processors. We develop an algorithm whose time requirement is
Can we conclude that this problem in the NC complexity class? Explain why or why not.
Yes, it is in NC. After all, if we were given n4 processors that is a number that is polynomial in n , then our algorithm takes just O(log² n4) = O((4 log n)²) = O(16 log² n) = O(log² n) time, which is polylogarithmic.