Pennsylvania State University — CMPSC 497 : Advanced Algorithms Midterm Exam
Lecturer: Antonio Blanca March 17, 2023
Midterm Exam
Name:
Penn State ID:
Student ID number:
Instructions: Answer all questions. Read them carefully first. Be precise and concise. Handwriting needs
to be neat (if we can’t understand what you write, we can’t grade it). Box numerical final answers. Write
only on the provided space; if you need extra space for a question, put a note in the question and use the
extra pages provided at the end.
Please clearly write your name and your PSU Access User ID (i.e., xyz1234) in the box on top of every page.
Good luck!
1
Name: PSU Access ID (xyz1234):
1 True/False (20 points)
True or false? Mark the right answer with an “x” (not a check mark or a circle). No justification is needed.
No points will be subtracted for wrong answers.
T F
□ □ In the coupon collecting problem (i.e., every day we receive one of n coupons uniformly at random),
the expected number of days required to collect every coupon is Θ(n2).
False. The expected number of days is Θ(n log n).
□ □ If we throw 4√n balls into n bins, by each ball selecting a bin independently and uniformly at random,
the expected number of collisions is at least 5.
True. The expected number of collisions is
(
m
2
)
1
n , where m = 4
√
n in this case. This is 4
√
n(4
√
n−1)
2n
which is bigger than 5 if n ≥ 1.
□ □ If we throw n balls into n bins, by each ball selecting a bin independently and uniformly at random,
the expected maximum load is Θ(log n).
False. The max load is Θ( lognlog logn ).
□ □ The sum of two binomial random variables is always a binomial random variable.
False. If the probability parameters are different, i.e., X ∼ Bin(n, p) and Y ∼ Bin(m, q), then X +Y
is not binomial. Do note that if p = q, then X + Y ∼ Bin(n+m, p).
□ □ If X is a Binomial(n, 1/2) random variable with n ≥ 1, then the probability that X is odd is 1/2.
True. Homework problem.
□ □ There is an improved version of Karger’s min-cut algorithm that runs in O(n2 log n) time and succeeds
with probability at least 0.99.
False. The success probability is Ω( 1logn ).
□ □ If X is a non-negative random variable such that E[X] = 12, then the probability that X ≥ 30 is at
most 2/5.
True. This follows from Markov’s inequality: Pr[X ≥ 30] ≤ E[X]/30 = 12/30 = 2/5.
□ □ In the setting of the Multiplicative Weight Update algorithm, if we knew all losses of all experts on all
days in advance (before the first day), we may be able to incur less total loss (over T days) than the
total loss incurred by the best expert.
True. Because we could switch experts and use the best expert each day.
□ □ In the setting of the Multiplicative Weight Update algorithm, there always exists a strategy that
chooses the same expert on every day (and no other experts) that achieves regret equal to 0.
True. The definition of regret is the difference between the expected loss of the strategy we choose
and that of following the best overall expert. So, if the latter is the strategy we use, the regret is 0.
2
□ □ Given a set of n points in Rd, we can use Johnson-Lindenstrauss dimensionality reduction lemma to
project the points in X to a lower-dimensional Y ⊂ Rk, where k = Θ(log d), such that the L2-distance
between the new set points is preserved within a %1 error.
False. k should be Θ(log n), independent of the dimension d.
3
Name: PSU Access ID:
2 Random matrices (20 points)
Consider an n × n random matrix A where each entry is either −1 with probability 1/2 or 1 otherwise,
independently of all other entries. Consider an n-dimensional column vector b with each entry bi of b
satisfying: 0 ≤ bi ≤ n1/4. Show that for any such b, ∥Ab∥∞ = O(n3/4
√
lnn) with probability 1−O(n−1).
Hint: Recall the version of the Chernoff bound where if X1, . . . , Xn are independent random variables such
that Xi ∈ [xi, yi] and Sn =
∑n
i=iXi, then for any δ > 0 Pr[|Sn − E[Sn]| ≥ δ] ≤ 2 exp
(
− 2δ2∑n
i=1(yi−xi)2
)
.
Soln: This problem is a minor modification of one from the second problem set. The solution is essentially
the same
Let ci =
∑
j Aijbi. Then E[ci] = 0 since E[Aij ] = 0 (by linearity of expectations). Also, −n1/4 ≤ Aijbi ≤
n1/4. Using the given bound, taking yi = n
1/4 and xi = −n1/4, we get
Pr[∥ci∥∞ ≥ 2n3/4
√
ln(n)] ≤ 2 exp
( −8n3/2 lnn∑n
i=1(n
1/4 − (−n1/4))2
)
= 2 exp
(−8n3/2 lnn
4n3/2
)
=
2
n2
.
A union bound then implies that
Pr[∥Ab∥∞ ≥ 2n3/4
√
ln(n)] = Pr[∃i : ∥ci∥∞ ≥ 2n3/4
√
ln(n)] ≤ n · 2
n2
= O(n−1),
as desired.
Note: This is a hard problem to solve on exam time if it is the first time you are seeing it, but since it is
nearly identical to a homework problem, I assumed that most folks would get it quickly. (I will continue to
prepare exam problems under this type of assumption.)
4
Name: PSU Access ID:
3 Randomized grading (20 points)
Professor AB only assigns A and B grades in his class. He does so at random as follows: if a student attends
75% or more of the lectures in the semester, then Professor AB assigns A with probability 0.9 and B with
probability 0.1 (independently of any other student). If, on the other hand, a student attends less than 75%
of the lectures, then Professor AB assigns A to the student with probability 0.5 and B otherwise.
Suppose there are n students in the class (with n even) and that exactly half of the students attended 75%
or more of the lectures in the semester. Let X be the random variable corresponding to number of students
that receive an A in the class.
1. Compute the expectation of X.
The expected value of X is the number of students with greater than 75% attendance (n/2) who get
an A (with probability 0.9) and the number of students with less than 75% attendance (n/2) who get
an A (with probability 0.5). i.e.
E[X] = n/2(0.9) + n/2(0.5)
E[X] = 0.45n+ 0.25n = 0.7n
2. Compute the variance of X.
The variance can be calculated using V ar(X) = E[X2]− (E[X])2 where we calculate the variance for
both cases wrt attendance. i.e. For greater than 75% attendance : V ar = 0.9 − 0.81 = 0.09 and for
less than 75% attendance : V ar = 0.5− 0.25 = 0.25. Since there are n/2 students in both cases :
V ar(X) =
n
2
(0.09 + 0.25) = 0.17n
3. Show that the probability that 80% or more of the students get A (i.e., that X ≥ 0.8n) is at most
20/n.
5
Using Chebyshev’s, we know that Pr[|X − E[X]| ≥ kσ] ≤ 1k2 .
P [X ≥ 0.7n+ k
√
0.17n] ≤ 1/(k2)
For P [X ≥ 0.8n], k√0.17n = 0.1n i.e. k = 0.1
√
n√
0.17
. This gives us :
P [X ≥ 0.8n] ≤ 1/(0.1√n/
√
0.17)2 ≤ 20/n
6
Name: PSU Access ID:
4 Randomized majority (20 points)
In the majority element problem you want to determine whether there are strictly more than n/2 elements
in an array of n elements with the same value, subject to the constraint that you can only check whether two
elements are equal or different. Design a randomized algorithm that when there is a majority element, the
algorithm returns “1” with probability at least 1− 10−9, and if there is no majority element, the algorithm
always returns “no majority.” The running time of your algorithm should be O(n). (Note that you are
required to design a randomized algorithm; deterministic algorithms will receive no credit.)
Hints: Note that checking if a given element (say chosen uniformly at random) is the majority element takes
O(n) times.
Soln:
Algorithm :
• Initialize count to 0.
• While count is less than k :
– Pick an element e uniformly at random from the array of n elements.
– Iterate through the array to check if e occurs more than n/2 time.
– Return 1 if it does. Else update count = count +1.
• Return 0.
Analysis:
Clearly, the runtime is O(nk). The probability of e being the majority element, if one exists is at least 1/2.
The probability of returning in one iteration of the while loop is then ≥ 1/2. However, since we try k times,
the probability of the above algorithm not returning the majority element is at most (1/2)k. We want this
probability to be ≤ 10−9. This is achieved by taking k to be a sufficiently large constant; i.e. k ≥ 30 suffices.
Thus the runtime is O(n) and we can guarantee success with probability ≥ 1− 10−9.
7
Name: PSU Access ID:
Extra space.
8
Name: PSU Access ID:
Extra space.
9
Name: PSU Access ID:
Extra space.
10