提供高质量的essay代写,Paper代写,留学作业代写-天才代写

首頁 > > 詳細

代做59PM-Assignment 4代做C/C++、C/C++編程代寫

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 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
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) ≡ 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

聯系我們
  • QQ:1067665373
  • 郵箱:1067665373@qq.com
  • 工作時間:8:00-23:00
  • 微信:Essay_Cheery
熱點文章
程序代寫更多圖片

聯系我們 - QQ: 1067665373 微信:Essay_Cheery
? 2021 uk-essays.net
程序代寫網!

在線客服

售前咨詢
售后咨詢
微信號
Essay_Cheery
微信
全优代写 - 北美Essay代写,Report代写,留学生论文代写作业代写 北美顶级代写|加拿大美国论文作业代写服务-最靠谱价格低-CoursePass 论文代写等留学生作业代做服务,北美网课代修领导者AssignmentBack 北美最专业的线上写作专家:网课代修,网课代做,CS代写,程序代写 代码代写,CS编程代写,java代写北美最好的一站式学术代写服务机构 美国essay代写,作业代写,✔美国网课代上-最靠谱最低价 美国代写服务,作业代写,CS编程代写,java代写,python代写,c++/c代写 代写essay,作业代写,金融代写,business代写-留学生代写平台 北美代写,美国作业代写,网课代修,Assignment代写-100%原创 北美作业代写,【essay代写】,作业【assignment代写】,网课代上代考