Home
Syllabus
Classwork
[8 pts]
The below method takes an undirected graph as a parameter and
returns the vertex with the most neighbors-of-neighbors.
The UndirectedGraph class is the same as on Assignment 2;
all instance methods on it take O(1) time.
Using m to represent the number of edges in the graph and n to represent the number of vertices, what is the running time of the method? Use big-O notation, giving the tightest and simplest bound you can, and justify your answer.
public static <V> V countNeighborsOfNeighbors(UndirectedGraph<V> g) {
V bestVertex = null;
int bestCount = -1;
for(int i = 0; i < g.getVertexCount(); i++) {
V a = g.getVertex(i);
HashSet<V> neighbneighb = new HashSet<V>();
for(V b : g.getNeighbors(a)) {
for(V c : g.getNeighbors(b)) neighbneighb.add(c);
}
if(neighbneighb.size() > bestCount) {
bestVertex = a;
bestCount = neighbneighb.size();
}
}
return bestVertex;
}
[8 pts] Suppose we are playing a series of games against an opponent for which we have a probability p of winning, and we want to know the probability that we'll win k of the next n games against our opponent. Below is a recurrence for computing this.
Use dynamic programming to complete the below Java method to compute this value in O(n ⋅ k) time.
public static double computeProbabilityKofN(int k, int n, double p) {
[8 pts] You run a factory that manufactures only one item, which can be either a widget or a gizmo. Your team of analysts have predicted the demand for widgets and gizmos for each of the upcoming T weeks and determined that you will earn a profit of p0, t dollars in week t (where 1 ≤ t ≤ T) if you choose to make widgets that week and p1, t dollars if you choose to make gizmos. All profits are nonnegative.
However, switching your factory from widgets to gizmos isn't cheap: You have to fire all your old widget-makers and hire a new team of gizmo-makers, and you have to switch out all your equipment. Overall, the switching process takes two weeks during which no product is produced, and it costs s dollars, whether switching from widgets to gizmos or vice versa.
Using dynamic programming, describe an O(T) algorithm that determines the maximum profit. Feel free to express the main part of your algorithm as a recurrence.
[8 pts] Suppose we have a weighted, undirected graph where all weights are positive. Two sets of vertices have been identified: One is a collection of possible start points, and the other is a collection of possible end points. Each set has sqrt(n) vertices. We want to find the shortest path from any single vertex in the start set to any vertex in the end set.
Give an O(m log n)-time algorithm for solving this problem. (Recall that Dijkstra's algorithm takes O(m log n) time, but it works only from a single source to a single destination.)
[8 pts] Suppose we know how to reduce problem A to problem B. For which problem is it now easier to find a polynomial-time algorithm, and why?
[10 pts] For the COMPOSITE problem, our input consists of a single integer N (written using 2 ⌈log2 N⌉ bits) and asked to determine whether N is composite. (Recall that N is composite if it has an integer divisor other than 1 or N. In other words, each integer is either composite or prime.)
Describe an algorithm that shows that COMPOSITE is within NP, and explain why your algorithm satisfies the constraints for NP.
O(m ⋅ n).
There are n iterations of the outer loop,
and over all iterations of the outer loop, there are
2m iterations of the inner loop over b.
(There are 2m iterations because if I go through each
vertex and check each edge around it, then I'll end up checking
each edge once for each of its two endpoints.)
For each iteration of the loop over b, there are at most
n iterations of the loop over c, each
iteration taking O(1) time. Thus each iteration of
the b loop takes O(n) time.
Over all 2m iterations of the b loop
overall, the time spent is
O(m ⋅ n).
The outer loop over i takes just O(1)
time per iteration, if we neglect the time spent on the
b loop. Thus the outer loop takes
O(n) time over all iterations, neglecting
the time on the b loop. The code outside the outer
loop takes O(1) time.
Thus the total time is O(1 + n + m ⋅ n), which is O(m ⋅ n).
double[][] prob[k + 1][n + 1];
for(int ni = 0; ni <= n; ni++) {
for(int ki = 0; ki <= k; ki++) {
if(ki > ni) {
prob[ki][ni] = 0;
} else if(ki == 0) {
prob[ki][ni] = Math.pow(1 - p, ni)
} else {
prob[ki][ni] = p * prob[ki - 1][ni - 1]
+ (1 - p) * prob[ki][ni - 1];
}
}
}
return prob[k][n];
}
We define the recurrence P(i, t), which represents the most profit that can be made in the first t weeks if we need to be ready to produce product i in week t + 1.
With this recurrence defined, we use dynamic programming to compute both P(0, T) and P(1, T). The larger of these two values is the maximum profit obtainable within T weeks.
We add a new vertex labeled α, which is connected to each start vertex with a zero-length edge. And we add a new vertex labeled ω, which is connected to each end vertex with a zero-length edge. Then we run Dijkstra's algorithm to find the shortest path from α to ω. The second step along the shortest path found is guaranteed to be a vertex from the start set, and the next-to-last step is guaranteed to be a vertex from the end set. The path found between the second vertex and the next-to-last vertex is the shortest path from the start set to the end set.
A is easier, since we can find a polynomial-time algorithm for it, or we could find a polynomial-time algorithm for B, which according to our reduction would imply a polynomial-time algorithm for A. The reverse is not true, so the only way we have for solving B is to solve it directly.
Our algorithm is to select a random integer between 1 and N, confirm it is not 1 or N, and confirm that it is a divisor of N. If it is, we output that N is composite; and if it is not, we output that N is not composite.
This algorithm satisfies the NP constraints because the
amount of time is polynomial in the number of bits (selecting a random
integer is polynomial in log N, and dividing into
N is polynomial in log N), because it has a
chance of saying yes
when the true answer is yes
(since
if N is composite, then there must be a divisor, which
might be the integer randomly chosen by the algorithm), and because
it will always say no
when the true answer is no.
.