2023年11月25日

算法分析代写 | CSE 347 Analysis of Algorithms Homework 2: Divide and Conquer

本次美国代写是算法分析的一个Homework

1. Wash U. Health Services has measured the weights of all students in two classes, BMI 326 and BMI
517. The students in each of the two classes have been sorted by weight and stored in arrays X and
Y , respectively. Nurse Chapel wants to determine the median weight of a student across both classes
combined.

Assume that arrays X and Y each have exactly n students, that no student is in both classes, and
that no two students have exactly the same weight. Then, the goal is to report the weight w such that
n students (across both classes combined) have weights < w.

To preserve students’ privacy, the nurse does not have full access to the arrays. All she can do is ask,
for either single array, what is the weight of rank k in that array (that is, w such that k students have
weights < w). Call this query a probe.

Give an algorithm to determine the median weight for both arrays combined that performs O(log n)
probes. You may assume for simplicity that n is a power of 2.

2. Professor John Snow (who knows nothing) wants to estimate how many of his students, from a class of
n, will be quarantined for COVID during next week’s in-class exam. He has scraped the social media
feeds of each of his students and, based on how many parties they have been attending, has estimated
for each student i a probability qi that the student will be quarantined on exam day.

Each student is assumed to quarantine or not independently of all others. Hence, in two disjoint
groups of students A and B, the numbers Q(A) and Q(B) quarantining in each group are independent
variables, and so Pr(Q(A) = a ^ Q(B) = b) = Pr(Q(A) = a)Pr(Q(B) = b).

Give an efficient algorithm to compute, for every 0 <= j <= n, the probability that exactly j students
will be quarantined. You may assume for simplicity that n is a power of 2.