CS218, Spring 2022, Assignment #1 1 Name:
Due: 11:59pm, Sun 04/10, 2022 Basic Programming Due: 11:59pm, Sun 04/03, 2022
Student ID:
Deadline. The homework is due 11:59pm, Sun 04/10, 2022. You must submit your solutions (in pdf format generated by LaTeX) via GradeScope. The training programming assignment is due earlier, see more details below.
Copyright By PowCoder代写 加微信 powcoder
Late Policy. You have up to two grace days (calendar day) for the entire quarter. You don’t lose any point by using grace days. If you decide to use grace days, please specify how many grace days you would like to use and the reason at the beginning of your submission.
Collaboration Policy. You can discuss the homework solutions with your classmates. You can get help from the instructor, but only after you have thought about the problems on your own. It is OK to get inspiration (but not solutions) from books or online resources, again after you have carefully thought about the problems on your own. However, you cannot copy anything from other source. You cannot share your solution/code with anyone else. You cannot read other’s solution/code. If you use any reference or webpage, or discussed with anyone, you must cite it fully and completely (e.g., I used case 2 in the examples in the Wikipedia page https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms) about Master theorem for Problem 3, or I discussed problem 2 with Alice and Bob.). Otherwise it will be considered cheating. We reserve the right to deduct points for using such material beyond reason. You must write up your solution independently: close the book and all of your notes when you are writing your final answers.
Write-up. Please use LaTeX to prepare your solutions. For all problems, please explain how you get the answer instead of directly giving the final answer, except for some special cases (will be specified in the problem).
Programming Problems. You will need to submit your code on CodeForces (a readme file about submitting code is available on the course webpage). You also need to submit a short report through GradeScope (there will be a separate entry for it) along with your solutions of the written assignments. In the report, you need to specify your submission id, describe the algorithm you designed, and show cost analysis if necessary. Note that your code will be automatically saved by CodeForces, so you do not need to submit the code again. For each problem, there will be 10 test cases. For the training programming problems, you need to finish before 11:59pm, Sun 04/03, 2022. With reasonable implementation, using C++ or Java is guaranteed to be able to pass all tests. You can use other languages, but it’s not guaranteed that the implementations can be within the time limit.
1Some of the problems are adapted from existing problems from online sources. Thanks to the original authors. 1
Required Written Homework (60pts)
1 A Complex Complexity Problem (16pts)
Yihan recently learned the asymptotical analysis. The key idea is to evaluate the growth of a function. For example, she now knows that n2 grows faster than n, but for more complicated functions, she feels confused. Can you help Yihan compare the functions below? We use log n to denote log2 n. Explain each of your answer briefly.
For the following questions, use o, Θ or ω to fill in the blanks. Questions:
(√2)log n = (√3 n) Explain briefly:
loglogn= (lnlnn) Explain briefly:
Solve Recurrences (16pts)
3. 22n+1 = (22n+1) Explain briefly:
4. (n+1)!= (n!) Explainbriefly:
For all of them, you can assume the base case is when n < 2, T (n) is also a constant. Use Θ(·) to present your answer. Show your steps.
Questions:
(1) T(n)=T(n/2)+Θ(n2) √
(2) T(n)=2T(n/4)+Θ( nlogn) (3) T(n)=4T(n/4)+Θ(loglogn)
(4) T(n)=T( n)+1
3 Test the candies (28pts)
You got job at a candy factory. It’s not always the case that all the candies produced are perfect. There will be some bad ones. Your task is to identify these bad candies from n candies and discard them. However, you can not tell which ones are bad directly: they look exactly the same. The only thing you know is that, a bad candy has lighter weight than standard (good) candies. More precisely, all the good (standard) candies have the same weight wg, and all the bad candies have the same weight wb < wg.
The only device you have is a balance scale, and you don’t have any weights (so you cannot really know the weight of each candy). As a result, the only thing you can do is to put some candies on the left and some on the right, and the balance will tell you if the left one is heavier, the right one is heavier, or they balance.
Every time you use the balance, you have to pay 1 dollar. All the other cost is free. Your task is to find all bad candies using the lowest cost.
Questions:
For all questions below, please describe your algorithm and briefly explain the cost. 2
1. (3pts) Your boss told you that there is only one bad candy. In that case, can you show an algorithm that uses ⌈log2 n⌉ (note: this is not in big-O!) dollars to find this bad candy?
2. (5pts) Your boss told you that there is only one bad candy. Now let’s improve the previous cost by a little bit. Can you show an algorithm that uses ⌈log3 n⌉ (again, not in big-O!) dollars to find this bad candy?
3. (5pts) Prove that ⌈log3 n⌉ dollars is the lower-bound of the candy-testing problem in 3.2. In other words, you cannot use fewer than ⌈log3 n⌉ dollars to guarantee to find the bad candy.
4. (5pts) Your boss told you that there are only two bad candies. Can you show an algorithm that uses O(log n) dollars to find the two bad candies?
5. (5pts) If you already know that there are only k bad candies, where k is a known constant, can you show an algorithm that uses O(log n) dollars to find the k bad candies? You could assume that k is a known value and it could appear in your algorithm.
6. (5pts) In all above questions, we assume you know the bad candy is lighter than standard. A more difficult cases is where you only know that the bad candy is of a different weight, but you do not know if it is lighter or heavier. Again assume there is only one bad candy. Prove that, in this case, you need at least ⌈log3 2n⌉ dollars to find the bad candy, and also tell whether it is lighter or heavier.
7. (bonus, 4pts and 1 candy) Now let’s consider the challenging setting where there is only one bad candy, but you don’t know if the bad candy is lighter or heavier. Luckily, your boss also gave you one good candy as a reference (you’ll find this useful). Now you have n = 13 candies, and one of them is bad (either lighter or heavier). Plugging this into the lower bound above gives ⌈log3(2 × 13)⌉ = 3 dollars. Now, show a solution for n = 13 for this case using 3 dollars.
Maybe divide-and-conquer is a good idea.
Basic Programming Problems (20pts)
See all problems at https://codeforces.com/group/VVz3kLaLS7/contest/373905.
Challenge Problems (30pts)
4 Sort the Train
The programming problem can be found at: https://codeforces.com/group/VVz3kLaLS7/contest/373905/problem/B.
You will find out that, if you run a bubble sort (where you are only allowed to do “adjacent swaps”), and record the number of swaps, that is always the optimal answer (lowest number of swaps).
However, simulating bubble sort takes O(n2) time. Can you come up with a better algorithm for that? In particular, if you have an algorithm with complexity O(n log n), you can pass all the test cases.
5 Sort the Train - Let’s prove it!
Well, now, let’s prove that your algorithm for the previous question is correct and efficient.
Questions:
1. (5pts) Show that, the number of swaps in the bubble sort algorithm will give you the optimal solution.
2. (5pts) Design an algorithm with O(nlogn) running time to compute the number of fewest adjacent swaps you need. You need to prove the complexity of your algorithm.
6 Upper Bound Meets Lower Bound (20pts)
In this question, we’ll see an interesting proof for upper/lower bound.
To find the maximum element of an array of size n, it is clear that we need to do at least n−1 comparisons.
It is the same if you just want the minimum element. Then what happens if we want to find both? Consider the problem of finding both the maximum element and the minimum element of an arbitrary
set of n distinct numbers, where n is even.
It turns out that 32 n − 2 comparisons are required in the worst case to do this. That is, 23 n − 2 is a lower
bound on the number of comparisions needed (if you use fewer than this number of comparisons, you cannot guarantee to find the correct answer).
There’s also an algorithm that achieves exactly this bound. That is, 32 n − 2 is an upper bound on the number of comparisons needed.
Since these bounds are equal, they are optimal.
(a) (7pts) Your task is to prove the following theorem:
Theorem: Consider a deterministic comparison based-algorithm A which does the following: given a set S of n numbers as input, A returns the largest and the smallest element of S. Prove that there is an input on which A must perform at least 23 n − 2 comparisons (i.e., this is a lower bound for a comparison-based algorithm).
(b) (3pts) The proof above may directly leads to an optimal deterministic algorithm (in terms of the number of comparisons). Describe one such algorithm.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com