首页 » 算法辅导 » 算法代写 | CSC373, Winter/Spring 2020 Assignment 4

算法代写 | CSC373, Winter/Spring 2020 Assignment 4

这个算法代写是解决加权装箱问题和加权卫星问题
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
blank. If instead you submit irrelevant or erroneous answers you will receive 0 points.
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 problem 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
0 of disjoint sets so as to
maximize P
Si∈C0 wi
.
Consider the oblivious local search algorithm LOCAL that for any current solution C
0
,
tries to add a set Si ∈ C \ C0
, removing any Sj ∈ C0
that intersects Si
. The algorithm
stops when there is no such Ci ∈ C \ C0
. Initially, we can set C
0 = ∅ or Si
for any single
set Si
. Show that LOCAL achieves a k approximation ratio. That is, for every input C,
LOCAL(C) ≥
1
kOP T(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 algorithm achieves approximation (totality) ratio 2
3
. Suppose we extend the neighbourhood of
any truth assignment to N0
1
(τ ) = N1(τ ) ∪ {τ} where τ is the complement truth assignment;
that is, τ = true iff τ = f alse.
Prove that the same oblivious local search algorithm using neighbourhood N0
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 P
i:Ci has 3 literals wi =
P
i:Ci has 4 literals wi
.
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 expectation the weight of satisfied clauses. What guarantee can you provide on the expected weight
of satisfied clauses. Explain your answer.
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) ≡ x
2
1 − x
2
2
. 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
algorithm and somewhat simpler analysis resulting in a 1-sided error randomized O˜(
3
2
)
n
)
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˜(
4
3
)
n
).
In this exercise you are to adapt the simpler analysis for the 4-SAT problem. What is your
time bound?
2 of 2


程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


本网站支持 Alipay WeChatPay PayPal等支付方式

E-mail: vipdue@outlook.com  微信号:vipnxx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论

您的电子邮箱地址不会被公开。