CS 344 Problem Set 1 Fall 2020 Due: Sep 28, 2020, 11:59 p.m. Name: (Replace me with your name) NetID: (Replace me with your NetID) Honor Code: Students may discuss and work on homework problems in groups, which is encouraged. However, each student must write down their solutions independently to show they understand the solution well enough to reconstruct it by themselves. Students should clearly mention the names of the other students who offered discussions. We check all submissions for plagiarism. We take the honor code seriously and expect students to do the same. Instruction for Submission: This homework has a total of 100 points, it will be rescaled to 10 points as the eventual score. We have provided the homework1.tex file for you, please write your answer to each question in this latex file directly after the corresponding question, and submit the complied PDF file only. You should name your PDF file as “Firstname-Lastname- NetID.pdf’’. Discussion Group (People with whom you discussed ideas used in your answers if any): I acknowledge and accept the Honor Code. Please type your initials below: Signed: (Replace me with your initials) 1. Big-O notation. We have learnt big-O notation to compare the growth rates of func- tions, 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) = 2 n. Intuitively, the growth rate of the functions sat- isfy 1 < log n < n < n log n < n2 < 2n. 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(n2), 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(n2+n log n+n) = O(n2).] 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 A′ = [a′1, . . . , a ′ 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) + n2 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(nlog6(6)) = O(n). (a) (5 points) T (n) = 3T (n/4) + √ n Answer: (b) (5 points) T (n) = 7T (n/2) + Θ(n3) Answer: (c) (5 points) T (n) = 2T (n/3) + nc, 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 re- cursion tree method, the iteration method, and the Master method. The Master Theorem states that, suppose T (n) = a · T (n/b) + O(nd), we have: T (n) = O(nd log n), if a = bd O(nd), if a < bd O(nlogb 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 Then, the number of distinct pairs of users who are on the site at the same time is three: these pairs are (1, 2), (4, 5), (3, 5). (Drawing the intervals on a number line may make this easier to see). (a) (10 points) Given input (a1, b1), (a2, b2), . . . , (an, bn) as above in no particular order (i.e., not sorted in any way), describe a straightforward algorithm that takes Θ(n2)- time to compute the number of pairs of users who are ever on the site at the same time, and explain why it takes Θ(n2)-time. [We are expecting pseudocode and a brief justification for its runtime.] Answer: (b) (10 points) Give an Θ(n log(n))-time algorithm to do the same task and analyze its running time. (Hint: consider sorting relevant events by time). [We are expecting pseudocode and a brief justification for its runtime.] Answer: 4
