Home
Syllabus
Classwork
[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.
[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.
[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.
[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.
[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?
[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.
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.
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.
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.
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.
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.
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.