Quiz 2

[1] [2] [3] [4] [5] [6]

Problem Q2.1.

[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;
}

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).




Problem Q2.2.
[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) {









    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];
}






Problem Q2.3.
[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
p_0, t dollars in week
t (where
1 ≤ t ≤ T) if you choose to make
widgets that week and
p_1, 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.








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.






Problem Q2.4.
[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.)








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.






Problem Q2.5.
[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?








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.






Problem Q2.6.
[10 pts]
For the COMPOSITE problem, our input consists of a single
integer N
(written using
2 ⌈log₂ 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.








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..