Solutions to Homework 2 Practice Problem
[DPV] Problem 6.17 – Making change I (unlimited supply) [DPV] Problem 6.18 – Making change II
See solutions in HW1 practice solutions.pdf
[DPV] 4.11 (length of shortest cycle on a graph)
Copyright By PowCoder代写 加微信 powcoder
Solution: As presented, we are given a directed graph with positive edge weights. These conditions assure that there is no negative-weight cycle within the graph. How do we find the length of the shortest cycle? Note that the shortest cycle visiting vertices u and v has length d(u, v) + d(v, u), hence the answer we are looking for is
min(d(u, v) + d(v, u)) u,v
Notice that if the quantity above is equal to infinity it means the graph is acyclic, and we report that.
Our approach: run Floyd-Warshall on the given graph to get an array {d(u,v)}u,v∈V of the distances between any pair of points. It is assumed that at the beginning any (u,v) pair which is not represented by an edge [(u,v) ∈/ E] is set d(u,v) = ∞. Now, inspect the diagonal in the array and our shortest path is the min(d(v, v)) across all vertex v ∈ V
To see why this algorithm is correct: note first that every cycle visiting vertices u and v can be broke into two directed paths: from u to v and from v back to u. Each such path achieves its minimum length at d(u, v) and d(v, u) respectively, hence the cycle of minimal length is given by this sum.
Floyd-Warshall takes O(|V |3) and the minimum can be found in O(|V |), leading to an O(|V |3) runtime.
[DPV] 4.21 (Currency trading)
Solution: We are presented with a directed graph problem, so hopefully we can use a known algorithm as the basis for our solution. The key is to recognize two things: (a) the currency calculation is a product (b) we want to maximize that product. We solve for the former by converting the ex- change rates to logs (recalling that log(a) + log(b) = log(a × b)) , and solve for the latter by using the negative of the log for our edge weight (flipping maximization to minimization).
So, for part (a), we create a graph where the vertices represent coun- tries, and the edges between them have a weight wi,j = −logri,j. We then run Bellman-Ford from vertex s to vertex t, and the minimal weight path represents the most advantageous sequence of currency trades. This takes O(|V ||E|) time.
For part (b), we run one more iteration of Bellman-Ford, and if any of the distances (weights) change, we have detected a negative cycle – such a cycle represents the trading anomaly which allows for infinite profit.
[DPV] Problem 2.1 – Practice Multiplication
The product is 28,830. See 2.1 Practice Multiplication.pdf for the value calculated at each level of the recursive stack.
[DPV] Problem 2.5 – Recurrence Solution:
(a) (b) (c) (d) (e) (f)
T (n) = 2T (n/3) + 1 = O(nlog3 2) by the Master theorem T (n) = 5T (n/4) + n = O(nlog4 5) by the Master theorem
T (n) = 7T (n/7) + n = O(n log7 n) = O(n log n) by the Master theorem T (n) = 9T (n/3)+n2 = O(n2 log3 n) = O(n2 log n) by the Master theorem T (n) = 8T (n/2)+n3 = O(n3 log2 n) = O(n3 log n) by the Master theorem
T (n) = 49T (n/25) + n3/2 log n = O(n3/2 log n)
Hint: the contribution of level i of the recursion is ( 49 )iO(n3/2 log n).
T (n) = T (n − 1) + 2 = O(n)
n T(n)=T(n−1)+nc =ic +T(0)=O(nc+1)
n T(n)=T(n−1)+cn =ci +T(0)=O(cn)
n−1 T(n)=2T(n−1)+1=2i +2nT(0)=O(2n)
√ k T(n)=T( n)+1=
where k is an integer such that n 2k is a small constant b (the size of the
base case). This implies that k = O(log log n) and T (n) = O(log log n).
[DPV] Problem 2.7 – Roots of unity Solution:
For the sum, use the geometric series equality to get 1+ω+ω2 +···+ωn−1 = ωn −1 =0.
ω−1 Fortheproduct,since1+2+···+(n−1)=(n−1)n weget
2 1ωω2 …ωn−1 = ω(n−1)n
2n whichequals1ifnisoddandωn =−1forneven(rememberthatω=e2πi).
[DPV] Problem 2.14 – Erase Duplicates Solution:
This is a straight forward application of the MergeSort algorithm.
STEP1: Sort the given list. The running time of this step is O(n log (n)).
STEP2: For i = 1 to n−1: if ai = ai+1, delete ai from the list. Output the final list. This list has no repeated terms. The running time of this step is O(n).
Why the algorithm is correct: the list after step 1 is sorted, so if there are repeated terms of aj for some j, they are all consecutive. STEP2 guarantees a comparison of all elements with both of its neighbors and elimination of one of the copies every time we found one. Hence no copies survived after STEP2 is completed.
The running time is O(n log (n) + n) = O(n log (n)).
(Alternatively, you can modify the Merge subroutine to eliminate copies at the same time that the merging is done. As this change adds constant work at each level to test for and remove duplicates, this additional step does not impact the overall run time.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com