CSE 101 Homework 0
Winter 2021
This homework is due on gradescope Friday January 8th at 11:59pm pacific time. Remember to justify your work even if the problem does not explicitly say so. Writing your solutions in LATEXis recommend though not required.
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 Θ(−).
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) = 3⌈log2(n)⌉
• c(n) = n2(2 + cos(n)) • d(n) = n1002n/2
• e(n) = 2n
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.
Question 4 (Recurrence Relations, 30 points). Consider the recurrence relation T(1) = 1, T(n) = 2T(⌊n/2⌋) + n.
(a) What is the exact value of T(2n)? [10 points]
(b) Give a Θ expression for T(n). Hint: compare its value to that at nearby powers of 2. [10 points]
1
(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