算法代写 | CS 344 Problem Set 1 Fall 2020

这个作业是分析算法的时间复杂度，完成递归算法等
CS 344 Problem Set 1 Fall 2020

1. Big-O notation. We have learnt big-O notation to compare the growth rates of functions, this exercise helps you to better understand its definition and properties.
(a) (10 points) Suppose n is the input size, we have the following commonly seen
functions in complexity analysis: f1(n) = 1, f2(n) = log n, f3(n) = n, f4(n) =
n log n, f5(n) = n
2
, f6(n) = 2n
. Intuitively, the growth rate of the functions satisfy 1 < log n < n < n log n < n2 < 2
n
. Prove this is true.
[Hint: You are expected to prove the following asymptotics by using the definition
of big-O notation: 1 = O(log n), log n = O(n), n = O(n log n), n log n = O(n
2
), n2 =
O(2n
). Note: Chap 3.2 of our textbook provides some math facts in case you need.]
Answer:
(b) (10 points) Let f, g : N → R+, prove that O(f(n) + g(n)) = O(max{f(n), g(n)}).
[Hint: The key is max{f(n), g(n)} ≤ f(n) + g(n) ≤ 2 · max{f(n), g(n)}. Note:
Proving this will help you to understand why we can leave out the insignificant parts
in big-O notation and only keep the dominate part, e.g., O(n
2+n log n+n) = O(n
2
).]
Answer:
2. Proof of correctness. (10 points) We have the following algorithm that sorts a list of
integers to ascending order. Prove that this algorithm is correct. [Hint: You are expected
to use mathematical induction to provide a rigorous proof.]
Answer:
1
Algorithm 1: Sort a list
Input: Unsorted list A = [a1, . . . , an] of n items
Output: Sorted list A0 = [a
0
1
, . . . , a0
n
] of n items in ascending order
for i = 0, i < n − 1, i++ do
// Find the minimum element
min index = i
for j = i + 1, j < n, j++ do
if A[j] < A[min index] then min index = j // Swap the minimum element with the first element swap(A, i, min index) return A 3. Practice the recursion tree. (10 points) We have already had a recurrence relation of an algorithm, which is T(n) = 2T(n/2) + 3n. Solve this recurrence relation, i.e. express it as T(n) = O(f(n)), by using the recursion tree method. [Note: If you find it difficult to draw a picture using Latex directly, you can draw it using Microsoft PowerPoint and then save it as a picture file (.png or .jpg), or you can draw on a piece of paper by hand, and take a picture of it using your phone. Then, you can insert the picture into your latex code and compile it into the final PDF submission. The following code shows an example of how to insert figures in latex code, as shown in Figure 1.] Figure 1: An example showing how to insert figures in latex code. Answer: 4. Practice with the iteration method. We have already had a recurrence relation of an algorithm, which is T(n) = 4T(n/2) + n 2 log n. (a) (5 points) Solve this recurrence relation, i.e., express it as T(n) = O(f(n)), by using the iteration method. Answer: (b) (5 points) Prove, by using mathematical induction, that the iteration rule you have observed in 4(a) is correct and you have solved the recurrence relation correctly. [Hint: You can write out the general form of T(n) at the iteration step t, and prove 2 that this form is correct for any iteration step t by using mathematical induction. Then by finding out the eventual number of t and substituting it into your general form of T(n), you get the O(·) notation of T(n).] Answer: 5. Practice with the Master Theorem. Solve the following recurrence relations; i.e. express each one as T(n) = O(f(n)) for the tightest possible function f(n) using the Master Theorem, and give a short justification. Unless otherwise stated, assume T(1) = 1. [To see the level of detail expected, we have worked out the first one for you.] (z) T(n) = 6T(n/6) + 1. We apply the master theorem with a = b = 6 and with d = 0. We have a > bd
, and so the running time is O(n
log6
(6)) = O(n).
(a) (5 points) T(n) = 3T(n/4) + √
n
Answer:
(b) (5 points) T(n) = 7T(n/2) + Θ(n
3
)
Answer:
(c) (5 points) T(n) = 2T(n/3) + n
c
, where c ≥ 1 is a constant that doesn’t depend on n.
Answer:
6. Proof of the Master Theorem. (15 points) Now that we have practiced with the recursion tree method, the iteration method, and the Master method. The Master Theorem
states that, suppose T(n) = a · T(n/b) + O(n
d
), we have:
T(n) =



O(n
d
log n), if a = b
d
O(n
d
), if a < bd O(n logb a ), if a > bd
Prove that the Master Theorem is true by using either the recursion tree method or the
iteration method.
Answer:
7. Algorithm design. Each of n users spends some time on a social media site. For each
i = 1, . . . , n, user i enters the site at time ai and leaves at time bi ≥ ai
. You are interested
in the question: how many distinct pairs of users are ever on the site at the same time?
(Here, the pair (i, j) is the same as the pair (j, i)).
Example: Suppose there are 5 users with the following entering and leaving times:
User Enter time Leave time
1 1 4
2 2 5
3 7 8
4 9 10
5 6 10
3