Scribd
Upload
62 views

CSE 101 Homework 0 Solutions: Winter 2021

This document contains solutions to four questions about algorithm analysis. Question 1 analyzes the runtime of two algorithms and determines they are Θ(n^2) and Θ(n log n), respectively. Question 2 sorts five functions by asymptotic growth rate and determines which are polynomial. Question 3 proves that if there is a walk between two vertices in a graph, there is also a walk where all vertices are distinct. Question 4 analyzes a recurrence relation, determining an exact solution, Θ expression, and identifying a flaw in an attempted inductive proof.

Uploaded by

Hoang Nguyen
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
62 views

CSE 101 Homework 0 Solutions: Winter 2021

This document contains solutions to four questions about algorithm analysis. Question 1 analyzes the runtime of two algorithms and determines they are Θ(n^2) and Θ(n log n), respectively. Question 2 sorts five functions by asymptotic growth rate and determines which are polynomial. Question 3 proves that if there is a walk between two vertices in a graph, there is also a walk where all vertices are distinct. Question 4 analyzes a recurrence relation, determining an exact solution, Θ expression, and identifying a flaw in an attempted inductive proof.

Uploaded by

Hoang Nguyen
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

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 ) .
n
Alg2: In each iteration of the for loop, Pnj is incremented
Pn Θ( i )1 times. i iterates from 1 to n, th
so our total
n n n
runtime is Θ(n) + Θ( 2 ) + Θ( 3 ) + · · · = i=1 Θ( i ) = n · i=1 Θ( i ). The summation is just the n 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) = n100 2n/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) = n100 2n/2

1
• Ω(n100 2n/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)2blog2 nc ≤ T (n) ≤ (blog2 nc + 2)2blog2 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.

You might also like