CS218, Spring 2025
Assignment #1
Due: 11:59pm, Friday, 4/11
Deadline. The homework is due 11:59pm, Friday, 4/11. You must submit your solutions (in pdf format generated by LaTeX) via GradeScope. The training programming assignment is due earlier, see more details below.
Late Policy. You have up to four 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.). If you use ChatGPT or similar AI tools, you have to attach the full conversation to make it clear what help you obtained from them. 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, and type your answers word by word on your own: close the book/notes/online resources 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). For all algorithm design problems, please describe using natural language. You could present pseudocode if you think that helps to illustrate your idea. Please do not only give some code without explanation. In grading, we will reward not only correctness but also clarity and simplicity. To avoid losing points for hard-to-understand solutions, you should make sure your solutions are either self-explanatory or contains good explanations. See some more details here https: //www.cs.ucr.edu/~ygu/teaching/218/S25//assignments/index.html
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 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-20 test cases. For the training programming problems, you need to finish before 11:59pm, Friday, 4/04. 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.
1 A Complex Complexity Problem (1.6pts)
Yihan recently learned asymptotical analysis. The key idea is to evaluate the growth of a function. For example, she now knows that n
2 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. n! = 1 × 2 × · · · × n. Explain each of your answers briefly.
For the following questions, use o, Θ or ω to fill in the blanks.
Questions:
2 Solve Recurrences (0.9pts)
For all of them, you can assume the base case is when n is a constant, T(n) is also a constant. Use Θ(·) to present your answer.
Questions:
3 Test the candies (2.5 pts + 1 bonus pt)
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.
1. (0.2pts) 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. (0.2pts) 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. (0.7pts) 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. (Note: you are asked to show that any possible solution needs ⌈log3 n⌉ dollars, instead of a specific strategy.)
4. (0.3pts) 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. (0.3pts) 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. (0.8pts) 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. (Hint: again, a common incorrect answer is that you design an algorithm that uses ⌈log3 2n⌉ dollars (and say this is optimal). This is not what the question asks. It asks you to show that any possible solution needs ⌈log3 2n⌉ dollars.)
7. (bonus, 1pt) 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.
Hint
Maybe divide-and-conquer is a good idea.
Bonus Problems
4 Finding the Minimum Value (1pt)
This programming problem can be found on codeforces.
5 Multiple Medians in Linear Time (1pt)
In order to get the 1 point from this problem, you need to design and implement the algorithm that can pass all test cases on codeforces. Then, you must explain your algorithm and prove the O(n) cost (deterministic worst-case or randomized expected).
6 Share candies (1pt)
This programming problem can be found on codeforces.
7 Being Unique (2 pts)
You are given an array A of n numbers from the set {1, 2, . . . , n}. The array has the “unique-in-range” property if for every range [i, j] there exists an element A[k] (where i ≤ k ≤ j) such that the number A[k] occurs just once in that range.
For example, the sequence: 1 2 1 3 1 2 1 4 1 2 1 3 1 has the unique-in-range property. As does 1 2 3 4 5 6. But the sequence 1 2 3 1 2 3 does not (it fails on the whole range: every number appears twice).
Give an algorithm to determine if a given array has the property. It should have runtime O(n log n) or better. You must prove your answer.