CS计算机代考程序代写 algorithm CSE 101 Homework 0

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