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) = 3dlog2(n)e • 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 (bn/2c) + 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 < 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. [10 points] Question 5 (Extra credit, 1 point). Approximately how much time did you spend working on this homework? 2