Change problem: to compute the number of ways that one could make change for n c
ID: 640390 • Letter: C
Question
Change problem: to compute the number of ways that one could make change for n cents assuming that one can use six types of coins: $1 coins, half dollars, quarters, dimes, nickels, and pennies. For example, when is 25 cents, there are 13 ways to make change. Assume that the maximum allowable input it $100.
a.
Consider the algorithm with the pseudocode given below. Given the fact that the execution of each pass of the most inner loop (i.e., the if-statement) takes 10^(-9) sec (suppose this is considered to be exceedingly fast for curent technology). Estimate the running time of A.
A(n)
Count <- 0
for s <- 0 to 100
do for h <- 0 to 200
do for q <- 0 to 400
do for d <- 0 to 1000
do for ni <- 0 to 2000
do for p <- 0 to 10000
do if (100*s + 50*h + 25*q + 10*d + 5*ni + p = n)
then count <- count +1
b.
Let the problem size for the change problem be n (the input in cents as defined earlier.) What is the worst case running time of the algorithm A in O-notation?
c.
Consider a pseudocode of an alternative algorithm B to solve the change problem below. Analyze its worst case running time for a prblem of size n and compare performance of algorithms A and B in O-notation.
B(n)
count <- 0
s <- 0
while s <= n/100
do srem <- n -100*s
s <- s + 1
h <- 0
while h <= srem/50
do hrem <- srem - 50*h
h <- h + 1
q <- 0
while q <= hrem/25
do qrem <- hrem - 25*q
q <- q+1
d <- 0
while d <= qrem/10
do drem <- qrem - 10*d
d <- d + 1
ni <- 0
while ni <= drem/5
do ni <- ni + 1
count <- count + 1
return count
d.
Explain if you would use algorithm A or B to solve the problem if you know that the input is at most $10. Justify your answer.
THIS IS WHAT I GOT (I am not sure if they are right )
a. 16^7
b. Big theta(n^6)
c. Big theta(n)
d. I think I would use B, but I'm not to sure why besides the better worst case scenario
Explanation / Answer
my answer is d )C
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.