CSI503 – Algorithms and Data Structures – Spring 2021 Homework 1 – Page 1 of 1 Instructions • 4 questions (75 points) • Due date: Feb. 19, 2021. • Preparation: Your solutions must be typeset in Word or LaTeX. It is acceptable to insert hand-drawn figures in your Word/LaTeX document. Preparing your homework using LaTeX will earn you 5 bonus points that can help with missing points in this assignment. Note that your assignment grade will be no more than the total points allocated for this assignment. • Submission: Single PDF file on Blackboard. • Filename: [firstname]-[lastname]-hw[#].pdf. Replace [firstname], [lastname], and [#] with your first name, last name, and this homework number, respectively. Problems 1. First, determine the asymptotically tight bounds for each of the following running time func- tions. Then, arrange them in non-decreasing order of their asymptotic complexity. Explain your answer. [20pt.] • f1(n) = 2logn • f2(n) = 5n2 + n2.5 • f3(n) = n log n2 • f4(n) = √ 10n • f5(n) = n(log3 n+ 1010000) 2. Show that the following algorithm correctly reverses the input string by defining a loop in- variant and clearly justifying the correctness based on its initialization, maintenance, and termination. Here, S is an array of characters of length n. [10pt.] 1: function STRREV(S, n) 2: for i = 1 to bn/2c do 3: c = S[i] 4: S[i] = S[n− i+ 1] 5: S[n− i+ 1] = c 3. For the following recurrence, establish a guess about its asymptotically tight bound by drawing a recursion tree. (See Figure 2.5d in the textbook for an example.) Then, use the substitution method to justify both its lower and upper bounds. [15pt.] T (n) = 2T (n/4) + √ n 4. Derive asymptotic upper and lower bounds for T(n) in each of the following cases. Clearly justify your answer even when you use the master theorem. [30pt.] (a) T (n) = 4T (n/3) + n log n (b) T (n) = T (n/3) + T (n/6) + n (c) T (n) = 5T (n/2) + n3 (d) T (n) = T (n− 2) + n2 欢迎咨询51作业君
