CompSci 161 Design and Analysis of Algorithms Problem Set 1
Due date: Wednesday, January 18 at 10:30 AM. You will need to submit this via GradeScope. Late problem sets are not accepted.
In CompSci161, your response to each numbered question must be contained within a single piece of paper. Each numbered question must be responded to on a separate page. When you submit to GradeScope, you will need to inform the system which page of your scanned PDF contains the response you want graded. On occasion, we might request you to tag two (or more) parts, even though we know the two parts will be on the same page; when that happens, it usually means we are going to grade the parts separately. Failure to follow these directions will be treated as non-submission for the question(s) affected.
Please review the syllabus and course reference for the expectations of assignments in this class. Remember that problem sets are not online treasure hunts. You are welcome to discuss matters with classmates, but remember the Kenny Loggins rule. Remember that you may not seek help from any source where not all respondents are subject to UC Irvine’s academic honesty policy.
1. In the lecture, we discussed the “famous problem.” We saw an algorithm that uses exactly 3n − 3 questions to identify a celebrity.
(a) Is it true or false that any correct algorithm to identify a celebrity in a group of size n must ask Ω(n) questions? Justify your response in a few sentences. You may assume I am only asking about deterministic algorithms if you would prefer.
(b) Give an algorithm to identify a celebrity with at most 3n − 3 − log n questions asked, or correctly determines that no celebrity exists in the input group given. Note that this is strictly fewer than the algorithm given in class, but is not asymptotically better. You may assume that n is a power of two for purposes of this problem. Explain how your algorithm uses the desired number of questions.
2. For this problem, leave your answer in terms of “n choose k” (often written as n k , although other clear notations are fine too) and other mathematical expressions such as summations. A numeric on its own will be worth zero credit, even if it is correct. Suppose a donut shop has 15 kinds of donuts. Two orders of donuts are considered the same if they have the same total number of donuts purchased and the quantity of each type is the same. For example, there is only one way to purchase an order that is 10 Lemon Jelly donuts and 8 Boston Creme donuts.
(a) How many ways are there to sample 5 donuts, if each donut sampled must be a different type and the order in which I sample them does not matter?
(b) How many ways are there to purchase 20 donuts?
(c) How many ways are there to purchase 20 donuts, if we are required to get at least two Lemon Jelly donuts?
(d) How many ways are there to purchase 20 donuts, if we are required to get at least one of each type of donut?
(e) How many ways are there to purchase at most 20 donuts (with no restrictions within each count)? There is one remaining question on the next (digital) page →
3. For this problem, leave your answer in terms of “n choose k” (often written as n k , although other clear notations are fine too) and other mathematical expressions such as summations. A numeric on its own for parts (b) or (c) will be worth zero credit, even if it is correct. Suppose I have a fair die that has twenty (20) sides. That is, if we roll it, each of the first twenty positive integers are equally likely to be the result of the roll.
(a) If we roll the die, what is the probability the result is a composite number? The composite numbers that are possible results are {4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20}, for a total of 11 possible.
(b) Suppose we roll this die 1500 times. What is the probability we get a composite number exactly 500 times?
(c) Suppose we roll this die 1500 times. What is the probability we get a composite number at least 500 times?
(d) What is the expected value of a single roll of this die? It might interest you to know that 1 + 2 + . . . + 20 = 210. Feel free to leave this answer as a fraction, even one that is improper or not reduced.
4. I claim that for all positive integers n, if n is odd, then (n − 1)/2 is odd. Give a counterexample to prove that this claim is incorrect. © CompSci 161 Winter 2023– Michael Shindler– University of California, Irvine This Problem Set may not be reposted without the express written permission of the professor teaching this course