Preliminaries and Lecture 1 CS6033 Homework Assignment∗1
Due Sunday, September 17th at 11:00 p.m. No late assignments accepted
Turn in this assignment as a PDF file on Gradescope. All answers must be typed onto Gradescope in the designated text box. If any question requires supplementary material as part of the answer, you will be given the option to upload a file. The course assistants may provide additional information on how to turn in this assignment.
All homework questions must be tagged when submitted to Gradescope. 1. Have you read the syllabus?
2. Have you read the NYU policy on academic integrity (https://www.nyu.edu/about/ policies-guidelines-compliance/policies-and-guidelines/academic-integrity-for-students html)?
3. Have you read the policy on collaboration in the syllabus?
4. You have five algorithms, A1 took O(n2) steps, A2 took Θ(n2) steps, and A3 took Ω(n2) steps, A4 took Ω(n) steps, A5 took o(n2) steps. You had been given the exact number of steps the algorithm took, but unfortunately, you lost the paper you wrote it down on. In your messy office, you found the following formulas (you are sure the exact formula for each algorithm is one of them):
(a) 7n·log2 n+12log2 log2 n (b) 7·(22log2 n)+n/2+7
(c) (2log4 n)/3 + 120n + 7 (d) (log2 n)2 + 75
(f) 22log2n
(g) 2log4 n
∗Many of these questions came from outside sources.
程序代写 CS代考 加QQ: 749389476
For each algorithm, write down all the possible formulas that could be associated with it.
5. Find two functions f(n) and g(n) such that f(n) ̸∈ o(g(n)) and f(n) ∈ Ω(g(n)). If no such functions exist, write “No such functions exist”.
6. In your book,1 complete homework problem 1-1 pg 15, excluding determining the answer for n! and n log(n). Simplifying assumptions: assume 1 month has 31 days; assume a year has 365 days.
7. Does the following algorithm correctly print out all the items that appear more than once in the array (and print no other values)?
• If the code is correct, prove it using a loop invariant!
• If not, prove that it does not work by providing an example on which it fails and show how this example is a counterexample. Then fix the code and prove your code works using a loop invariant.
print duplicates(A)
1) for i = 1 to A.length
2) for j = i to A.length 3) if A[i] == A[j]
4) print(A[i])
8. What is the run time2 of the following questions? Expressing your answer using big-Oh, little-oh, Theta, and Omega.
gausses summation series 1(n) 1) s = 0
2)for i=1ton
3) for j = i to n 4) s=s+1 5) return s
gausses summation series 2(n) 1) s = 0
2)for i=1ton
4) return s
1Make sure you have the third edition.
2You do not need to prove our answers. The big-Oh and big-Omega bounds must be tight.
Code Help, Add WeChat: cstutorcs
9. Professor T. Ortis thought the insertion sort presented in class seemed rather inef- ficient.3 He thought he could improve the run time, so it runs asymptotically faster if in the while loop (lines 5-7) instead of using a backward scan through the already sorted items to find where the jth item belongs, he instead used binary search to find where the jth item belongs. Is he right?
10. Your aunt Mary is having a party! She asked everyone to write down the names of who should be invited. Your mother, Of course, wrote your name down; your father wrote your name down. Oddly your aunt Jane didn’t write your name down.4 Your name wasn’t the only one to appear multiple times on aunt Mary’s list of people to invite. Write the pseudocode for finding all the people aunt Mary should invite so each person’s name appears only one time in the list. Your algorithm must run in time o(n2). You may call any algorithm as a subroutine that was presented in lecture 1. State what the running time is of your algorithm in big-Oh, Theta, and Omega notation. Justify the running time of your algorithm.
11. You have acquired a job, and while highly paid, your boss is a control freak with strange opinions on algorithmic design. Normally this isn’t too much of an is- sue. However, recently your boss has decided to mandate a strange algorithm in a performance-critical part of the code (“a hot loop”). In order to prove to him that his algorithm is less efficient than your approach and thus saves the company money on cloud computing costs, you try to come up with a better solution.
Occasionally two numbers in a large array of objects get swapped5, and the array needs to get resorted in order to continue to allow your binary search algorithm to function.
Your boss’s algorithm is as follows: He chooses a pair of indexes i, j where 1 ≤ i < j ≤ n and swaps the item in position i with the item in position j and then uses n − 1 comparisons to determine if the items are now sorted. If the items are sorted, the algorithm stops. If the items are not sorted, then the items are returned to their original position, and the procedure is repeated with an untested pair of indexes, and so on until the array is sorted.
3We saw that Mergesort take O(n log n) time.
4 She couldn’t still be mad about you drinking all her favorite ”non-alcoholic” beverage last time you visited her, or could she?
5Due to other portions of the system architecture, it is impractical to update the numbers at the time you swapped to the numbers
Computer Science Tutoring
Turn in the following:
• Determine the Big Oh worst-case running time of your boss’s algorithm. Justify the running time of the algorithm
• Design an efficient algorithm. We want both a high-level description of your algorithm and the pseudocode.
• Determine the Big Oh worst-case running time of your algorithm. Justify the running time of your algorithm.
12. (3 bonus points) Think of a good6 exam question for the material covered in Lecture 1
6Only well-thought-out questions will receive the bonus points. 4