Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS 344

Problem Set 1

        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 encourage you to use LaTex to write your answer, because it’s particularly suitable to type equations and it’s frequently used for writing academic papers. We have provided the homework1.tex file for you, you can write your answer to each question in this .tex file directly after the corresponding question, and then compile the .tex file into a PDF file for submission. As a quick introduction to LaTex, please see this Learn LaTeX in 30 minutes. Compiling a .tex file into a PDF file needs installing the LaTex software on your laptop. It’s free and open source. But if you don’t want to install the software, you can just use this website https://www.overleaf.com/, which is also free of charge. You can just create an empty project in this website and upload the homework1.zip, and then the website will compile the PDF for you. You can also directly edit your answers on the website and instantly compile your file.

        You can also use Microsoft Word or other software if you don’t want to use LaTex. If so, please clearly number your answers so that we know which answer corresponds to which question. You also need to save your answers as a PDF file for submission.

        Finally, please submit your PDF file only. You should name your PDF file as “Firstname-Lastname-NetID.pdf’’.

        Late Policy: The homework is due on 10/5 (Tuesday) at 11:59pm. We will release the solutions of the homework on Canvas on 10/9 (Saturday) 11:59pm. If your homework is sub-mitted to Canvas before 10/5 11:59pm, there will no late penalty. If you submit to Canvas after 10/5 11:59pm and before 10/9 11:59pm (i.e., before we release the solution), your score will be penalized by 0.9k , where k is the number of days of late submission. For example, if you submitted on 10/8, and your original score is 80, then your final score will be 80 ∗ 0.93 = 58.32 for 8 − 5 = 3 days of late submission. If you submit to Canvas after 10/9 11:59pm (i.e., after we release the solution), then you will earn no score for the homework.

        Make best use of picture in Latex: If you think some part of your answer is too difficult to type using Latex, you may write that part on paper and scan it as a picture, and then insert that part into Latex as a picture, and finally Latex will compile the picture into the final PDF output. This will make things easier. Regarding how to insert pictures in Latex, you may refer to the Figure 1 in the following, which is an example of inserting pictures in Latex.

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.

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.]

3. Practice the recursion tree. (10 points) We have already had a recurrence relation of an algorithm, which is T(n) = 3T(n/2) + 2n. 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.]

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.

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.]

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:

Prove that the Master Theorem is true by using either the recursion tree method or the iteration method.

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:

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).