Question 1
How many different minimum cuts are there in a tree with n nodes (ie. n−1 edges) ?
n
n2
n−1
2n−2
Question 2
Let "output" denote the cut output by Karger's min cut algorithm on a given connected graph with n vertices, and let p=1n2. Which of the following statements are true?
For hints on this question, you might want to watch the short optional video on "Counting Minimum Cuts".
For every graph G with n nodes, there exists a min cut (A,B) of G such that
Pr[out=(A,B)]≥p.
For every graph G with n nodes, there exists a min cut (A,B) such that
Pr[out=(A,B)]≤p.
There exists a graph G with n nodes and a min cut (A,B) of G such that
Pr[out=(A,B)]≤p.
For every graph G with n nodes and every min cut (A,B) of G,
Pr[out=(A,B)]≥p.
For every graph G with n nodes and every min cut (A,B),
Pr[out=(A,B)]≤p.
Question 3
Let .5<α<1be some constant. Suppose you are looking for the median element in an
array using RANDOMIZED SELECT (as explained in lectures). What is the
probability that after the first iteration the size of the subarray in
which the element you are looking for lies is ≤α times the size of the original array?
1−α2
α−12
2*α - 1
1−α
Question 4
Let 0<α<1 be a constant, independent of n. Consider an execution of RSelect in which you always manage to throw out at least a 1−αfraction of the remaining elements before you recurse. What is the
maximum number of recursive calls you'll make before terminating?
−log(n)log(α)
−log(n)log(1−α)
−log(n)α
−log(n)log(12+α)
Question 5
The minimum s-t cut problem isthe following. The input is an undirected graph, and two distinct
vertices of the graph are labelled "s" and "t". The goal is to compute
the minimum cut (i.e., fewest number of crossing edges) that satisfies
the property that s and t are on different sides of the cut.
Suppose someone gives you a subroutine for this s-t minimum cut problem
via an API. Your job is to solve the original minimum cut problem (the
one discussed in the lectures), when all you can do is invoke the given
min s-t cut subroutine. (That is, the goal is to reduce the min cut
problem to the min s-t cut problem.)
Now suppose you are given an instance of the minimum cut problem -- that
is, you are given an undirected graph (with no specially labelled
vertices) and need to compute the minimum cut. What is the minimum
number of times that you need to call the given min s-t cut subroutine
to guarantee that you'll find a min cut of the given graph?
n2
n
n−1
2n
