CSE 101 Assignment 1 PDF

Preview

Summary

First assignment of CSE 101 (Design and Analysis of Algorithms)....

Description

Question 1 a) FALSE 34n = 81 n , 43n = 64 n . 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 (n 6 + 2n + 1) 2/(3n 3 + 4n 2) 4 = [(n 6 + 2n + 1)/(9n 6 + 16n 4 + 24n 5)] 2 Since the highest term in both numerator and denominator match, the other terms are irrelevant as n → ∞ . If we divide both numerator and denominator by n6 , they will become 0. Therefore, lim (n6 + 2n + 1)2 /(3n3 + 4n 2) 4 = lim [(n6 + 2n + 1)/(9n6 + 16n4 + 24n5 )]2 = [1/9]2 = 1/81 n→∞

n→∞

Since 1/81 < ∞ , the limit definition is satisfied. c) TRUE log (n10)/log (n) = 10log (n)/log (n) = 10 , irrespective of n . Since 10 > 0 , the limit definition is satisfied. d) TRUE

n

n

∑ 2n > 0 , 2n > 0 , ∑ 2n > 2n . i=1

i=1 n

Therefore, ( ∑ 2n)/2 n > 0 for all n > 0, even as n → ∞. This satisfies the limit definition. i=1

e) FALSE nlog (n) = log (nn ) nn > n! for all n > 1 (Since the factors keep decreasing in n! 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 < 2x for all 0 < x < k . T k−1 < 2k−1 and 2T k−2 < 2 * 2k−2 T k−1 + 2T k−2 < 2 k−1 + 2 * 2k−2 T k < 2k−1 + 2k−1 T k < 2k

=> => => =>

Therefore, T k < 2k if T x < 2x for all 0 < x < k , and T k < 2k for k = 1, 2, 3, 4, 5 as shown, then T k < 2k for all k > 0 . This proves that T n ∈ O(2n ) . b) To prove T n ∈ Ω(2n ) , we must show that T k > c * 2k for all k > 0 for some constant c . Let c = 0.25 . 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 * (2k−1 + 2 k−1)

=>

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 that T n ∈ Ω(2n ) .

Question 3 a) Then y is in A[ x ]. So, during the for loops, x is added to the list AR [ y ]. b) Then x is in AR [ y ]. 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 AR[v ]i ”operation takes constant time. Therefore, the runtime would be T ∈ O(m).

Question 4 Proving return value TRUE: G’ contains a path from s to t ⇒ G contains a path from s to t in the form 0n 1m . We see that in the construction of G’ from G, all edges from a vertex with weight 1 to a vertex with weight 0 are removed. Let’s denote these as w(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 to t in the form 0n 1m , this path would consist of w(0, 0) edges, w(0, 1) edges and w(1, 1) edges only. This shows us that the required path would be intact in G’. Therefore, if G contains a path from s to t 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 weight 1 must be of the form 0n 1m . This proves that if a path from s to t is found in G’, then there must be a path in G from s to t in the form 0n 1m . Proving return value FALSE: G’ doesn’t contain a path from s to t ⇒ G doesn’t contain a path from s to t in the form 0n 1m . We see that in the construction of G’ from G, all edges from a vertex with weight 1 to a vertex with weight 0 are removed. Let’s denote these as w(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 to t , this means that there is no path in G from s to t that only consists of w(0, 0) edges, w(0, 1) edges and w(1, 1) edges. This means that either G doesn’t have any paths from s to t , or all paths from s to t contain at least one w(1, 0) edge. But a path from s to t in the form 0n 1m can’t contain any w(1, 0) edges. Therefore, such a path doesn’t exist in G. This proves that if there isn’t a path from s to t found in G’, then there cannot be a path in G from s to t in the form 0n 1m . Since both output values are proved correct, the algorithm is proved correct....