算法设计代写 | CSOR W4231：Homework 3

这是一篇美国的关于算法设计编程代写

Homework Instructions.

Forall algorithms that you are asked to “give” or “design”, you should

Describeyour algorithm clearly in English.
Givepseudocode.
Arguecorrectness; you may provide a formal proof or a convincing argument.
Provide,with an explanation,the best (smallest) upper bound that you can for the running time. All bounds should be worst-case bounds, unless explicitly stated otherwise. You are also encouraged to analyze the space required by your algorithm. We will not remove marks if you don’t, unless the problem explicitly asks you to analyze space complexity.

Ifyou give a Dynamic Programming algorithm, the above requirements are modiﬁed as follows:

(a) Clearly deﬁne the subproblems in English.

(b) Explain the recurrence in English. (This counts as a proof of correctness; feel free to give an inductive proof of correctness too for practice but points will not be deducted if you don’t.) Then give the recurrence in symbols.

(d) Analyze time.

(e) Analyze space.

(f) If you’re ﬁlling in a matrix, explain the order to ﬁll in subproblems in English.

(g) Give pseudocode.

Full credit will be given to the fastest correct solution. For example, an algorithm that solves the problem but runs in time O (n2 ) will not receive full marks if there is another algorithm that solves the problem and runs in O (n) (possibly at the expense of some additional space).
Youshould submit this assignment as a pdf ﬁle to Gradescope. Other ﬁle formats will not be graded, and will automatically receive a score of 0.
Irecommend you type your solutions using LaTeX. For every assignment, you will earn 5 extra credit points if you type your solutions using LaTeX or other software that prints equations and algorithms neatly. If you do not type your solutions, make sure that your handwriting is very clear and that your scan is high quality.
Youshould write up the solutions entirely on your own. Collaboration is limited to discussion of ideas only. You should adhere to the department’s academic honesty policy (see the course syllabus). Similarity between your solutions and solutions of your classmates or solutions posted online will result in receiving a 0 in this assignment, and possibly further disciplinary actions. There will be no exception to this policy and it may be applied retro-actively if we have reasons to re-evaluate this homework.

Homework Problems.

(55points)

(a) (30 points) Given an unlimited supply of coins of denominations c1 , c2 , . . . , cn , you wish to make change for a value v; that is, you wish to ﬁnd a set of coins whose total value is v. This might not be possible: for instance, if the denominations are 5 and 10, then we can make change for 15 = 10 + 5 but not for 11. Design an O(nv) algorithm to determine whether it is possible to make change for v using coins of denominations c1 , c2 , . . . , cn. If the answer is yes, also output a way to make change for v .

(b) (25 points) Consider the following variation of the above problem. You are only allowed to use each denomination at most once. For example, if the denominations are 1, 5 and 10, then you can make change for 6 = 1 + 5 but not for 20 since you cannot use 10 twice.

Design an O(nv) algorithm to determine whether it is possible to make change for v using each denomination c1 , c2 , . . . , cn at most once.

(20points) Problem 24-3, part a. only, from your textbook (p. 679).

(30points) Alice has a directed graph G = (V, E) with possibly negative weights on the edges we for e e E, a destination node t and a set of ﬁnite values dv for every v e V . Bob claims that value dv equals the weight of the shortest path from v to the destination t .

(a) (14 pts) Give an algorithm that runs in O(n + m) time and veriﬁes or disproves Bob’s claim.

(b) (16 pts) Now assume that Bob’s claim is correct and Alice wants to compute distances to a diﬀerent destination t/. Suggest an algorithm to Alice that runs in time O(m log n) for computing weights d/ (v) of shortest paths for all nodes v e V to the destination t / . If needed, check the hint provided at the end of the recommended exercises.

(20points) Let S and T be two disjoint subsets of size n of a ﬁnite universe U. Suppose we select a random subset R c U by independently including each element of U with probability p. We say that the sample is good if it contains an element of T but no element of S.Show that when p = 1/n, the probability our sample is good is larger than some positive constant (independent of n).

Remark 1 You may use the fact that, for all x , n e R such that n > 1 and lx l s n,

(45points) Suppose that time is divided in discrete steps. There are n people and a single shared computer than can only be accessed by one person in a single step: if two or more people attempt to access the computer at the same step, then everybody is “locked out” during that step. At every step, each of the n people attempts to access the computer with probability p.

(a) (5 points) Determine the probability that a ﬁxed person i succeeds in accessing the computer during a speciﬁc step.

(b) (5 points) How would you set p to maximize the above probability?

(c) (10 points) For the choice of p in part (b), upper bound the probability that person i did not succeed to access the computer in any of the ﬁrst t = en steps.

Hint: Use inequality 1 in Remark 1.

(d) (10 points) What is the number of steps t required so that the probability that person i did not succeed to access the computer in any of the ﬁrst t steps is upper bounded by an inverse polynomial in n?

(e) (15 points) How many steps are required to guarantee that all people succeeded to access the computer with probability at least 1 – 1/n (that is, with high probability)?

Hint: You may want to ﬁrst upper bound the probability of the complementary event.