CSE 101 Homework 0 Solutions
Winter 2021
Question 1 (Program Runtimes, 20 points). Consider the following programs:
Alg1(n):
For i = 1 to n
j = 1
while j < n j = j+1 Alg2(n): For i = 1 to n j = 1 while j < n j = j+i For each of these algorithms, compute the asymptotic runtime in the form Θ(−). Solution 1. Alg1: Each iteration of the for loop involves Θ(n) operations, as j is always incremented n−1 times. There are n iterations of the for loop, so our total runtime is n ∗Θ(n) = Θ(n2) . Alg2: In each iteration of the for loop, j is incremented Θ(n i ) times. i iterates from 1 to n, so our total runtime is Θ(n)+Θ(n 2 )+Θ(n 3 )+ · · · = ∑n i=1 Θ( n i ) = n · ∑n i=1 Θ( 1 i ). The summation is just the nth harmonic number Hn, and Hn = Θ(log n), so our total runtime is Θ(n log n) . Question 2 (Big-O Computations, 20 points). Sort the functions below in terms of their asymptotic growth rates. Which of these functions have polynomial growth rates? Remember to justify your answers. • a(n) = n+ n1/2 + n1/3 + . . .+ n1/n • b(n) = 3dlog2(n)e • c(n) = n2(2 + cos(n)) • d(n) = n1002n/2 • e(n) = 2n Solution 2. • n ≤ a(n) ≤ n+ log(n)n1/2 + n× n1/ log(n) = O(n) since log(n) ∈ O(n1/2). Notice that l = n1/ log(n) is a constant since log(l) = 1/ log(n) ∗ log(n) = 1 =⇒ l = e. So a(n) ∈ θ(n). • b(n) = 3dlog2(n)e ≤ 3 × 3log2(n) = 3 × 2log2(3) log2(n) = 3nlog2(3) and b(n) = 3dlog2(n)e ≥ 3log2(n)/3 = 2log2(3) log2(n)/3 = nlog2(3)/3. So b(n) = θ(nlog2(3)). • Ω(n2) ≤ c(n) = n2(2 + cos(n)) ≤ O(n2) since 1 ≤ 2 + cos(n) ≤ 3. • Ω(n2) ≤ d(n) = n1002n/2 1 • Ω(n1002n/2) ≤ e(n) = 2n since n100 ∈ O(2n/2) So the order is clearly a, b, c, d, e by reasons above. The functions a, b, c are polynomial growth rates. The functions d, e are not polynomial growth since they are greater than 2n/2 which is not polynomial growth. Question 3 (Walks and Paths, 30 points). In a graph G we say that there is a walk from vertex u to another vertex w if there is a sequence of vertices u = v0, v1, . . . , vn = w so that (vi, vi+1) is an edge of G for each 0 ≤ i < n. Prove that if there is a walk from u to w there is a walk where all of the vertices vi are distinct. Hint: if two are the same show how you can use this to construct a shorter walk. Solution 3. Suppose we have a walk from vertex u to vertex w, the walk is denoted as (u, v0, v1, ..., vn, w) = p where there are duplicated vertices in p. Assume that we cannot find a walk p̂ such that p̂ ⊂ p and ele- ments in p̂ are distinct. Suppose vi, vj ∈ p, vi = vj , i < j. Then (vi, vj+1) is also an edge of G. So p̂ = (u, v0, ..., vi, vj+1, ..., vn, w) is a valid walk. We can apply this procedure until all the elements are distinct. This contradicts with the assumption we have. So there exists a walk from v to w where all the vertices vi are distinct. Question 4 (Recurrence Relations, 30 points). Consider the recurrence relation T (1) = 1, T (n) = 2T (bn/2c) + n. (a) What is the exact value of T (2n)? (b) Give a Θ expression for T (n). Hint: compare its value to that at nearby powers of 2. (c) Consider the following purported proof that T (n) = O(n) by induction: If n = 1, then T (1) = 1 = O(1). If T (m) = O(m) for m < n, then T (n) = 2T (bn/2c) + n = O(n) +O(n) = O(n). Thus, T (n) = O(n). What is wrong with this proof? Hint: consider the implied constants in the big-Os. Solution 4. (a) We show by induction that ∀n ≥ 0, T (2n) = (n + 1) · 2n. For n = 1, clearly T (20) = 1 = (0 + 1) · 1. Suppose the relationship holds for all n ≤ t. Then, T (2n+1) = 2T (2n) + 2n+1 = 2(n+ 1) · 2n + 2n+1 = (n+ 2) · 2n+1 . (b) Let k = blog2 nc Observe that T (2k) ≤ T (n) ≤ T (2k+1) or (blog2 nc+ 1)2 blog2 nc ≤ T (n) ≤ (blog2 nc+ 2)2 blog2 nc+1 implying log2 n · n/2 ≤ T (n) ≤ 2(log2 n+ 2)n. Thus T (n) = Θ(n log2 n) . (c) In order for the induction step to be correct, we require that the same constant as that of T (m) for m < n is also obtained for T (n). Under the assumption that ∀m < n, T (m) = O(m), let c be a constant such that for a sufficiently large m, T (m) ≤ c·m. This only implies that T (n) = 2T (bn/2c)+n ≤ (c+1)n and the induction step fails. 2