Description
A. [10] Design an algorithm that can identify cycles in a directed graph.
B. Coin denomination problem
You have large amount of coins of each denominations: 1 cent, 5-cent, 10-cent, 25-cent, and 1
dollar. The optimal denomination problem is defined as:
PROBLEM: a total amount x cents to be made up in coins.
SOLUTION: Generate N1
, N5
, N10
, N25
, N100 such that
1. We minimize N1+N5+N10 + N25+N100
2. while subject to the constraint N1 + 5*N2 + 10*N10 + 25*N25 + 100*N100 = x.
Devise an algorithm that solves the optimal denomination problem using dynamic programming
by following the these steps.
1. [10] How do you generate sub-problems?
2. [10] How do you synthesize the solution of a larger problem based on the solutions of the
subproblems.
3. [10] Write down the recursive solution.
4. [10] What is the runtime of the recursive solution?
5. [20] Formulate the bottom-up computation so that it runs in polynomial time complexity.
6. [10] Formulate the memoization version of the recursive solution so that it runs in polynomial
time complexity.
C. Solve the optimal denomination problem using a greedy algorithm.
1. [10] What is the complexity of the greedy algorithm.
2. [10] For the following values of x, compute the optimal number of coins used by both
dynamic programming and the greedy algorithm.
x by dynamic programming by greedy
104
122
141
156
157
167
188
189
200
Submission:
● Report.pdf