联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp2

您当前位置:首页 >> Java编程Java编程

日期:2020-06-14 09:10

CMPT307

Summer 2020

Assignment 2

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


版权所有:编程辅导网 2018 All Rights Reserved 联系方式:QQ:99515681 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。