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

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

(a)  Clearly define 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.

(c)  State boundary conditions.

(d)  Analyze time.

(e)  Analyze space.

(f)  If you’re filling in a matrix, explain the order to fill in subproblems in English.

(g)  Give pseudocode.

(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 find 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.

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

(b)  (16 pts) Now assume that Bob’s claim is correct and Alice wants to compute distances to a different 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.

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

(a)  (5 points) Determine the probability that a fixed person i succeeds in accessing the computer during a specific 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 first 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 first 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 first upper bound the probability of the complementary event.