# Help With 59PM Assignment 4Help With C/C++,C/C++ ProgrammingGhostwriter

CSC373, Winter/Spring 2020 Assignment 4
Due: Thursday, April 16, 2020 4:59PM on MarkUs
You will receive 20% of the points for any (sub)problem for which you write “I do
not know how to answer this question.” You will receive 10% if you leave a question
You may receive partial credit for the work that is clearly “on the right track.”
You may choose to spend your time looking for solutions on the internet and may
likely succeed in doing so but you probably won’t understand the concepts. So at the
very least try to do the assignment initially without searching the internet. If you
obtain a solution directly from the internet, you must cite the link and explain the
solution in your own words to avoid plagarizing.
Note: As we had to change the grading scheme, it is especially important that
you work individually. In particular you should not take a solution from someone else.
However, it is permissable to discuss a problem with other students so as you are
learning together. But then you should wait at least one hour before writing down
your solution and you should not use any written notes from conversations with other
students. Just keep in mind that the goal is to understand the concepts. It is always
important not to plagarize but if we are going to increase the weight of assignments,
we clearly have to have some confidence that your work is your work.
1. (20 points) Consider again the weighted set packing problemi as in Assignment A3. The
input is a collection C = {S1, S2, . . . , Sm} of sets where |Si| ≤ k for some fixed integer k and
wi is the weight of Si. The objective is to select a subcollection C ′ of disjoint sets so as to
maximize

Si∈C′ wi.
Consider the oblivious local search algorithm LOCAL that for any current solution C ′,
tries to add a set Si ∈ C \ C ′, removing any Sj ∈ C ′ that intersects Si. The algorithm
stops when there is no such Ci ∈ C \ C ′. Initially, we can set C ′ = ∅ or Si for any single
set Si. Show that LOCAL achieves a k approximation ratio. That is, for every input C,
LOCAL(C) ≥ 1
k
OPT (C). Use a charging argument to show that your algorithm obtains the
stated approximation.
2. (20 points) Consider the Exact Max-2-SAT problem and the oblivious local search algorithm
with Hamming distance neighbourhood N1(τ) as defined in the slides for week 10. This al-
gorithm achieves approximation (totality) ratio 2
3
. Suppose we extend the neighbourhood of
any truth assignment to N ′1(τ) = N1(τ) ∪ {τ} where τ is the complement truth assignment;
that is, τ = true iff τ = false.
Prove that the same oblivious local search algorithm using neighbourhood N ′1 acheives an
approximation (totality) ratio of 3
4
.
Note: You can just consider the unweighted problem as the proof for the weikghted problem
would be the same. You will receive reasonable credit if you can argue why this extended
neighbourhood will help improve the totality ratio knowing what you know about the analysis
for the N1 neighbourhood.
1 of 2
CSC373, Winter/Spring 2020 Assignment 4
3. (20 points) Consider the following weighted Max-Sat problem:
We are given a weighted CNF formula F = C1 ∧ C2 ∧ . . . ∧ Cm where each clause Ci has a
positive integer weight wi. Furthermore, all the clauses in F have either 3 or 4 literals and
that

i:Ci has 3 literalswi =

i:Ci has 4 literalswi.
The goal is to find a truth assignment so as to maximize the weight of satisfied clauses.
Provide a polynomial time randomized algorithm whose objective is to maximize in expecta-
tion the weight of satisfied clauses. What guarantee can you provide on the expected weight
4. (20 points) Consider two polynomial size (i.e., number of aritmetic operations) arithmetic
circuits C1 and C2 each having operations +,−,× and inputs x1, x2, . . . , xn, c1, . . . cm where
the ci ≤ n are constants in N. Furthermore, the circuits have depth O(log n). The output
of these circuits are polynomials P1(x1, . . . xn) and P2(x1, . . . , xn).
We say that two such circuits are equivalent (denoted C1 ≡ C2) if P1 and P2 are identical
multivariate polynomials. For example, (x1 − x2) · (x1 + x2) ≡ x21 − x22. Describe a 1-sided
error randomized polynomial (in n) time algorithm ALG that will determine if C1 ≡ C2
with high probability. Namely, ALG must satisfy the following:
• If C1 ≡ C2, then ALG will say YES
• If C1 6≡ C2, then ALG will say NO with probability at least 1− 2−n.
5. (20 points) We have posted on the 373 web page, lecture notes by Dan Spielman (Yale
University) on Schoning’s algorithm for 3SAT. Those notes start with a slighlty different al-
gorithm and somewhat simpler analysis resulting in a 1-sided error randomized O˜(2
3
2 ) time
bound (say with constant error probability) where O˜ hides logarithmic factors.
The slides then show how to obtain Schoning’s algorithms obtaining time O˜(2
4
3 ).
In this exercise you are to adapt the simpler analysis for the 4-SAT problem. What is your
time bound?
2 of 2