Design and Analysis of Algorithms Assignment 1

Question 1 a) FALSE 34n = 81n , 43n = 64n . 81n > 64n , for all n > 0 which means as n → ∞ , 34n /43n → ∞ . This is the opposite of the definition, since we need the limit approach zero. b) TRUE (n6 + 2n + 1)2 /(3n3 + 4n2 )4 = [(n6 + 2n + 1)/(9n6 + 16n4 + 24n5 )]2 Since the highest term in both numerator and denominator match, the other terms are irrelevant n→ as∞ . If we divide both numerator and denominator byn6 , they will become 0. Therefore, lim (n6 + 2n + 1)2 /(3n3 + 4n2 )4 = lim [(n6 + 2n + 1)/(9n6 + 16n4 + 24n5 )]2 = [ 1/9]2 = 1/81 n→∞ n→∞ Since1/81 < ∞ , the limit definition is satisfied. c) TRUE log (n10 )/log (n) = 10log (n)/log (n) = 10 , irrespective of n . Since10 > 0 , the limit definition is satisfied. d) TRUE n n i=1 i=1 ∑ 2n > 0 , 2n > 0 , ∑ 2n > 2n . n Therefore, (∑ )/22n i=1 e) 0n > for all n > 0, even as n → .∞This satisfies the limit definition. FALSE nlog (n) = log (nn ) nn > n! for n all > 1 (Since the factors keep decreasing inn! but they don’t in nn ) Therefore log (n!) < nlog (n) for all n > 1 . This violates the definition of Ω itself. Question 2 a) Let’s use strong induction. T1 T2 T3 T4 = = = = 1 1 1 + 2 = 3 3 + 2 = 5 T 5 = 5 + 6 = 11 ( ( ( ( < < < < 21 22 23 24 = = = = 2) 4) 8) 16 ) ( < 25 = 32 ) We see that the first few values hold true. Let’s assume that for some k , all T x < 2 x for all 0 < x < k. T k−1 < 2 k−1 and 2T k−2 < 2 * 2k−2 T k−1 + 2T k−2 < 2 k−1 + 2 * 2k−2 T k < 2 k−1 + 2 k−1 T k < 2k => => => => Therefore, T k < 2k ifT x < 2 x for all0 < x < k , and T k < 2 k for k = 1, 2, 3, 4, 5 as shown, then T k < 2 k for all k > 0 . This proves thatT n ∈ O(2 n) . b) To prove T n ∈ Ω(2 n) Let c = 0.25 . , we must show that Tk > c * 2k for all k > 0 Let’s use strong induction. T1 T2 T3 T4 = = = = 1 1 1 + 2 = 3 3 + 2 = 5 T 5 = 5 + 6 = 11 ( ( ( ( > > > > 0.25 * 21 0.25 * 22 0.25 * 23 0.25 * 24 = = = = 0.5 ) 1) 2) 4) ( > 0.25 * 25 = 8 ) We see that the first few values hold true. Let’s assume that for some k , all T x > 0.25 * 2x for all 0 < x < k. => T k−1 > 0.25 * 2k−1 and 2T k−2 > 2 * (0.25 * 2k−2) => => T k−1 + 2T k−2 > 0.25 * (2 k−1 + 2 * 2k−2) T k > 0.25 * (2 k−1 + 2 k−1) for some constant c . => T k > 0.25 * 2k Therefore, T k > 0.25 * 2k if T x > 0.25 * 2x for all 0 < x < k , and T k > 0.25 * 2k for k = 1, 2, 3, 4, 5 as shown, then T k > 0.25 * 2k for all k > 0. This proves thatT n ∈ Ω(2 n) . Question 3 a) Theny is in A[x ]. So, during the for loops, xis added to the list A R [ y ]. b) Then x is in A yR [ ]. The only way this could have happened is if y was in A[ x ]. c) Since the two for loops essentially iterate through the adjacency list, they run the inner operation the same number of times as entries in the entire adjacency list (inside each A[v i] for i = 1... n ). If the input is an array of lists, then this would equal the number of edges. The “adding to R T ∈ O( A [v ] . m) i ”operation takes constant time. Therefore, the runtime would be Question 4 Proving return value TRUE : G’ contains a path from s t to ⇒ G contains a path froms tot in the form0n 1m . We see that in the construction of G’ from G, all edges from a vertex with weight1 to a vertex with weight 0 are removed. Let’s denote these asw(1, 0) edges. Since the other edges are intact in G’, we see that w(0, 0) edges,w(0, 1) edges and w(1, 1) edges would still be a part of G’. If G contains a path from s t to in the form 0n 1m , this path would consist ofw(0, 0) edges, w(0, 1) edges andw(1, 1) edges only. This shows us that the required path would be intact in G’. Therefore, if G contains a path from s t to in the form 0n 1m , then G’ should contain a path from s to t . Let’s reverse this to prove the TRUE case. Since all edges in G’ are a part of G, a path found in G’ would also exist in G. Since all paths in G’ do not contain w(1, 0) edges, a path starting from a vertex with weight 0 and ending at a vertex with weight1 must be of the form 0n 1m . This proves that if a path from s t to in the form 0n 1m . Proving return value FALSE : G’ doesn’t contain a path from s t to is found in G’, then there must be a path in G from s to t ⇒ G doesn’t contain a path froms tot in the form0n 1m . We see that in the construction of G’ from G, all edges from a vertex with weight1 to a vertex with weight 0 are removed. Let’s denote these asw(1, 0) edges. Since the other edges are intact in G’, we see that w(0, 0) edges,w(0, 1) edges and w(1, 1) edges would still be a part of G’. If G’ doesn’t contain a path from s t to , this means that there is no path in G froms tot that only consistswof (0, 0) edges, w(0, 1) edges and w(1, 1) edges. This means that either G doesn’t have any paths from s tto , or all paths froms tot contain at least one w(1, 0) edge. But a path from s t to in the form 0n 1m can’t contain anyw(1, 0) edges. Therefore, such a path doesn’t exist in G. This proves that if there isn’t a path from s t to froms tot in the form 0n 1m . found in G’, then there cannot be a path in G Since both output values are proved correct, the algorithm is proved correct.