首页 » 算法代写 » 算法代写 | CMPT307 Summer 2020 Assignment 2

算法代写 | CMPT307 Summer 2020 Assignment 2

这个作业是完成LCS算法和贪婪算法
CMPT307 Summer 2020 Assignment 2
Due Wed June 24 at 23:59
3 problems, 40 points.
1. Improve the Longest Common Subsequence (LCS) algorithm (10 points):
(a) Show how to compute the length of an LCS using only 2 min(m, n)
entries in the c table plus O(1) additional space. Express in pseudocode. Then analyze the memory space usage of your algorithm.
(b) Then show how to do the same thing, but using min(m, n) entries plus
O(1) additional space. Again, express in pseudocode, and analyze the
memory space usage of your algorithm.
2. Refer to the power of 2 problem (Lecture 12, slides p21) (10 points).
(a) Redo the problem using the accounting method.
(b) Redo the problem using the potential method.
3. Coin changing (20 points):
Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin’s value is an integer.
(a) Describe a greedy algorithm to make change consisting of quarters,
dimes, nickels, and pennies. Prove that your algorithm yields an
optimal solution.
(b) Suppose that the available coins are in the denominations that are
powers of c, i.e., the denominations are c
0
, c1
, . . . , ck
for some integers
c > 1 and k ≥ 1. Show that the greedy algorithm always yields an
optimal solution.
(c) Give a set of coin denominations for which the greedy algorithm does
not yield an optimal solution. Your set should include a penny so
that there is a solution for every value of n.
(d) Give an O(nk)-time algorithm that makes change for any set of k
different coin denominations, assuming that one of the coins is a
penny.
1


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


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

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


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

标签:

发表评论

电子邮件地址不会被公开。 必填项已用*标注