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作业君