printable version
Quiz 3
[1]
[2]
[3]
[4]
[5]
[6]
Problem Q3.1.
[8 pts]
Graham's scan is an algorithm for finding the top half of a
convex hull of two-dimensional points. It proceeds as follows.
def grahamScan(points): # assume points are sorted by x-coordinate
hull = [points[0], points[1]]
for i in range(2, len(points)):
p = points[i]
while len(hull) >= 2 and isLeftTurn(hull[-2], hull[-1], p):
hull.pop()
hull.append(p)
return hull
Using big-O notation in terms of n, the length of the
points parameter, how much time does this algorithm take?
Use big-O notation, giving the tightest and simplest
bound you can, and justify your answer.
You should assume that pop, append, and
isLeftTurn
take O(1) time.
O(n). There are a total of n
points added into hull, since the outer loop
iterates only n times. Each iteration of the inner
loop removes an element from hull, so it can occur
only n times total over all iterations of the outer
loop. Each iteration of the inner loop takes O(1)
time, so the total time spent on the inner loop, across all
iterations of the outer loop, is O(n).
Ignoring the time spent on the inner loop, each iteration of
the outer loop takes O(1) time, and there are
O(n) iterations of it. Thus the total time
on the outer loop, ignoring the inner loop, is
O(n). Adding in the
O(n) total time on the inner loop,
we arrive at
O(2 n)
= O(n) time.
Problem Q3.2.
[8 pts]
In the MAX-3SAT problem, we're given a list of 3-term
disjunctions and an integer target g, and we're asked to
determine whether there is an assignment of truth values to
variables that satisfies at least g of the
disjunctions. For
example, our list of disjunctions might be the following 14
choices.
x1 ∨ x2 ∨ x3
x1 ∨ x2 ∨ x3
x1 ∨ x2 ∨ x4
x1 ∨ x2 ∨ x3
x1 ∨ x2 ∨ x3
x1 ∨ x2 ∨ x4
x1 ∨ x2 ∨ x4
| |
x1 ∨ x2 ∨ x3
x1 ∨ x2 ∨ x3
x1 ∨ x2 ∨ x4
x1 ∨ x2 ∨ x4
x1 ∨ x2 ∨ x3
x1 ∨ x2 ∨ x4
x1 ∨ x2 ∨ x4
|
If g were 13, then the answer would be yes; one assignment
that satisfies 13 of the clauses is when all variables are true.
However, if g were 14, the answer would be no, because there
is no single set of assignments that satisfies all 14
disjunctions.
Using a reduction with 3SAT, which is known to be
NP-hard,
show that MAX-3SAT is also NP-hard.
Suppose we're given a 3SAT problem, which is a
conjunction of disjunctions. We count the number of
disjunctions, then pass this number as g to MAX-3SAT
along with a list of all the disjunctions in original 3SAT
problem.
This transformation takes polynomial time, since it is simply
a matter of counting the disjunctions and then listing each
disjunction separately; each step takes time that is linear in
the length of the 3SAT expression.
The solution to the 3SAT problem is yes
if and only if
the solution to the corresponding MAX-3SAT problem is yes. Going
in the forward direction: If there is a solution to the 3SAT,
then there is an assignment that satisfies all clauses of the
3SAT expression, and so it satisfies all g clauses
listed in the MAX-3SAT problem. And in the other direction: If
a MAX-3SAT algorithm concludes that there is a variable
assignment satisfying all clauses in its list of disjunctions, then
this same variable assignment will satisfy the conjunction of
all this disjunctions, which is the original 3SAT problem.
Problem Q3.3.
[10 pts]
Argue that the following is a 2-approximation algorithm for MAX-3SAT.
We consider two possible assignments: In one, all variables are true;
and in the other, all variables are false. We then determine how many
disjunctions are satisfied by each assignment, and we output the
assignment that satisfies more of the disjunctions.
Imagine each disjunction voting for which of the two
assignments satisfies it (or voting randomly if both
assignments satisfy it). We know each disjunction will cast a
vote, because each disjunction is satisfied by at least one of the two
possible assignments. After all, we can just look at the first
variable appearing in each disjunction: If the variable appears
without negation, then the all-true assignment will match the
variable and thus the disjunction; and if the first variable
appears negated, then the all-false assignment will match the
negated variable and thus the disjunction.
Since each disjunction casts a vote, one of the two possible
assignments must receive at least half of the votes. Thus, if
there are m disjunctions, one of the two assignments
(maybe both) will satisfy at least m / 2 of
the disjunctions. On the other hand, no assignment can possibly
satisfy more than m of the disjunctions, since there
are only m. Thus, the better of the two assignments
will satisfy at least half as many disjunctions as the best
possible assignment. Thus, this is a 2-approximation
algorithm.
Problem Q3.4.
[8 pts]
To rank each page in a Web of n pages, we first
determine an n × n matrix
M based on the links beween pages.
Then we find a vector v of length n where
M × v = v; this
vector v will then hold the PageRank of each page.
Describe the algorithm from class for computing v once we have
M.
We choose an initial vector
v0
where all the entries sum to 1; one possibility is
1 / n
in every vector entry. Then we compute
v1
to be
M × v0.
And we compute
v2 to be
M × vi.
This process will converge to a point where
vi is very close to
vi − 1,
and at that point we have found an approximate value for v.
Problem Q3.5.
[8 pts]
Describe the experts problem inspiring the Halving and Weighted
Majority algorithms. Also, when would Halving be
preferred, and when would Weighted Majority be preferred?
Why?
We imagine a series of events where there are many
experts,
each making a prediction for the event. With
each event, we collate these experts' predictions somehow into
our own prediction, and then we learn what the correct answer
was — an answer that we can use to adapt how much we trust
each expert in the future. Our goal is to find a way to combine
expert predictions and update our trust in each expert so that
we don't make many more mistakes than the best expert.
The halving algorithm adapts quite quickly to the best expert,
but it only works well when the best expert predicts perfectly.
Weighted Majority makes more mistakes (at least when it's not
in the degenerate case where it behaves exactly as the Halving
algorithm) but can deal with the case where the best expert
occassionally errs.
Problem Q3.6.
[8 pts]
Give an example of an undirected, weighted graph for which there is a pair
of vertices s and t where the shortest
path from s to t does
not lie within the graph's minimum spanning tree. Justify your
answer.
In the above graph, there is just one minimum spanning tree,
which includes the edges labeled 2 and 3. However, the shortest
path from s to t is to take
the edge of length 4, which is not included
in the minimum spanning tree.
Home
Syllabus
Classwork