COT 5405 Analysis of Algorithms, Spring 2010. Midterm 3
April 8, 2010
Notes
• If the problem necessitates writing an algorithm, you must first informally describe the algorithm, in brief, in a paragraph. You can choose to follow this up with pseudocode that formally describes the algorithm. We will peruse your pseudocode only if your English description is not clear.
• Write your name on the top right hand corner of your exam. Be sure to write your last name as the last word in your name.
• If you are designing an algorithm, you must write a formal proof of correctness.
• Please write legibly.
Name:
UFID: –
• This is a closed-book exam. No calculator.
• You have 100 minutes for the exam.
https://www.coursehero.com/file/62260962817187/5M/Miditdetremrm3s3oslo/l/
1
This study resource was shared via CourseHero.com
1. [1 page][33points] The following graph with weights on edges is given. Apply Floyd-Warshall algo- rithm to compute shortest path between all pairs of vertices (only the distance of the path, not the path itself). Provide a weight matrix at each iteration. Floyd-Warshall recurrence relation is as below.
Let D(k) = (d(k)) be the weight matrix after kth iteration, i,j
d(k) = min(d(k−1), d(k−1) + d(k−1)), k ≥ 1
i,j
d(0) = i,j
i,j i,k k,j 0
weight of edge(i, j) ∞
if i = j if i ̸= j otherwise
1
1
-1 335
1
25 -2
4
02100
3 0 3 −2 2 D = 4 1 0 − 1 − 1
96504 12 9 8 3 0
3
Solution:
This study resource was shared via CourseHero.com
https://www.coursehero.com/file/26629026817187/5M/Miditdetremrm3s3oslo/l/
2
2. [1 page][33points] You need to go over a river by canoe and there are n trading posts along the river. We use fi,j to denote the fee from post i to post j. These fees are arbitrary. For example it is possible that f1,3 = 10 and f1,4 = 5. You begin at trading post 1 and must end at trading post n (using rented canoes). Your goal is to minimize the rental cost. Design an efficient algorithm for this problem. Be sure to prove that your algorithm yields an optimal solution and analyze the time complexity.
Solution:
Letm[i]betherentalcostforthebestsolutiontogofrompostitopostnfor1≤i≤n. Thefinal answer is in m[1]. We can recursively, define m[i] as follows:
m[i] = 0 if i = n
m[i] = mini≤j≤n(fi,j + m[j]) otherwise
We now prove this is correct. The canoe must be rented starting at post i (the starting location) and then returned next at a station among i + 1, . . . , n. In the recurrence we try all possibilities (with j being the station where the canoe is next returned). Furthermore, since fi,j is independent from how the subproblem of going from post j, . . . , n is solved, we have the optimal substructure property. For the time complexity there are n subproblems to be solved each of which takes O(n) time. These subproblems can be computed in the order m[n],m[n-1], . . . ,m[1]. Hence the overall time complexity is O(n2).
https://www.coursehero.com/file/26620926811778/5M/Miditdetremrm3s3oslo/l/
3
This study resource was shared via CourseHero.com
Powered by TCPDF (www.tcpdf.org)
3. [2page][(8+3)+(8+3)+(8+3)+1=34points][(8+3)+(8+3)+(8+3)+1=34 points] You are given coins of n different integer denominations x1 < x2 < ... < xn. Suppose you are asked to determine whether coins of these denominations can be used to make change for an amount of exactly V (where V is an integer). Consider the following different conditions: (A) You are allowed to use at most one coin for each denomination, (B) You are allowed to use as many coins as required for each denomination, (C) You are allowed to use as many coins as required for each denomination but you are allowed to use at the most K coins in total.
Note: When we say ‘as many coins as required’, we include cases where no coins of some denominations are used.
For each condition, you must (1) write a recurrence relation for a dynamic programming algorithm, explain the recurrence clearly and specify the base case, and (2) analyze the time complexity of the algorithm. Which of your algorithms (if any) qualifies as being a polynomial time algorithm? Why or why not?
Examples: Let x1 = 9, x2 = 11 be the two denominations available to you. (Part A) You can create change for V = 20 but not for V = 29 as the latter requires two coins of value 9. (Part B) You can create change for V = 29 but not for V = 12 as the latter amount cannot be broken down as an integer combination of 9 and 11 even if you had an unlimited supply of coins of both values. (Part C) You can create change for V = 29 using K = 3 coins, but not for V = 38 as the latter requires 4 coins.
Solution:
Part (A): You are allowed to use at most one coin for each denomination.
Recurrence: M(n,V)=M(n−1,V −xn)|M(n−1,V)where|referstoalogicalORoperator.
Let M(i,v) = 1 if you can make change for an amount of v using denominations x1,x2,...,xi else it is 0. The logic for this recurrence is this: either you can use a coin of value xn for making the change, or you don’t. In the former case, our algorithm should output 1 if you could make change for an amountv−xn usingthefirstn−1denominations(henceM(n,V)=M(n−1,V −xn)). Inthelatter case, our algorithm should output 1 if you could make change for an amount v using the first n − 1 denominations (hence M (n, V ) = M (n − 1, V )). If either of these possibilities is true, our algorithm outputs 1 and hence the logical OR operator in the recurrence. Complexity: O(nV ) as you have to build a table of n rows and V columns.
Part (B): You are allowed to use as many coins of a given denomination as required.
Recurrence: M(V ) = max{i:xi≤V }M(V − xi)
(another way of writing: M(V ) = δ(x1 ≤ V )M(V −x1)|δ(x2 ≤ V )M(V −x2)|...|δ(xn ≤ V )M(V −xn)). whereδ(xi ≤V)=1ifxi ≤V elseδ(xi ≤V)=0. HereM(V)=1ifyoucanusecoinsofthesevalues to make change for V , else it is 0. Complexity: O(nV ) as you have to build a 1D array of V entries but the initial recurrence requires you to examine n possibilities.
Part (C): You are allowed to use as many coins of a given denomination as required but you can use at the most K coins.
Recurrence: If k > 1, M(k,V) = max{i:xi≤V}M(k−1,V −xi) else M(k,V) = (x1 == V)|(x2 == V )|…|(xn == V )
where M(k,v) = 1 if you can make change of value v using k coins at the most. Complexity: O(nV K) as you have to build a table of K rows and V columns, but the initial recurrence requires you to examine n possibilities.
All three algorithms are pseudo-polynomial (not polynomial) because their running time is directly proportional to the value V which requires O(log2V ) bits of storage. The value is always exponential in the number of bits for storage. Hence, all three algorithms are exponential time.
4
https://www.coursehero.com/file/62269062817187/5M/Miditdetremrm3s3oslo/l/
This study resource was shared via CourseHero.com