Homework
Assignment 1 Coin Change – Minimum Coins
Given coins of different denominations and a total amount, find the minimum number of coins
needed.
Total amount = 6 and coin set = {4,3,1}
Assignment 2 (0-1 Knapsack problem)
As project manager, choose those projects which can be completed in the required amount of
time = 9 weeks which maximizes revenue
Completion Time Expected Revenue
Product ID
(wks) (1000 $)
F 7 110
G 5 90
H 4 40
J 3 60
K 1 10
Assignment 3 (The longest common subsequence problem)
Suppose we have a sequence of letters ACCGGTC. Then a subsequence of this sequence would
be like ACCG or ACTC or CCC. To get ACCG, we pick the first four letters. To get ACTC, we pick
letters 1, 2, 6, and 7. To get CCC, we pick letters 2, 3, and 7, etc.
Formally, given a sequence X = x1, x2,…, xm, another sequence Z = z1,…, zk is a subsequence of
X if there exists a strictly increasing sequence i1, i2,…, ik of indices of X such that for all j = 1, 2,
…, k, we have xij = zj.
In the longest-common-subsequence problem, we are given two sequences X and Y, and
want to find the longest possible sequence that is a subsequence of both X and Y. For example,
if X = ABCBDAB and Y = BDCABA, the sequence BCA is a common sequence of both X and Y .
However, it is not a longest common subsequence, because BCBA is a longer sequence that is
also common to both X and Y. Both BCBA and BDAB are longest common subsequences, since
there are no common sequences of length 5 or greater.
Please use dynamic algorithm to design an algorithm for this problem
Solution of all questions: If you can’t design an algorithm after studying very hard, just search
on google for solution. These problems are very famous.
