CS630 Homework 2 Solution

Instructions

• No extension will be provided, unless for serious documented reasons.
• Despite having two weeks, better start early than late!
• Unless specified differently, the points are distributed equally among the subquestions.
• Study the material taught in class, and feel free to do so in small groups, but the solutions should be a product of your own work.
• This is not a multiple choice homework; reasoning, and mathematical proofs are required before giving your final answer.
• Sub-optimal algorithms and lack of proof of correctness will lead to a major deduction in points.
• If you work with others or utilize any external tools and resources, please make sure to annotate your answers.
• Please submit your work through Gradescope. You can find the access code on
Piazza.
Exercise 1 [10 points]
Given an integer array A of length n, and two integers k and ℓ, find the number of pairs of indices i,j (where 1 ≤ i,j ≤ n) such that A[i] ≤ A[j] and there are exactly k elements in the range [A[i],A[j]] that are divisible by ℓ . Give an efficient algorithm and analyze its time and space complexity.
Exercise 2 [10 points]
The input comprises a real number x and a matrix A[1..n,1..m] containing nm real numbers. It is given that each row A[i,1..m] is sorted in ascending order from left (i.e., first column j = 1) to right (i.e., last column j = m), and each column A[1..n,j] is sorted in ascending order from top (i.e., first row i = 1) to bottom (i.e., last row j = n). The objective is to ascertain whether the value x is present within matrix A. Give an efficient algorithm and analyze its time and space complexity.
Exercise 3 [10 points]
Given a sequence of n distinct numbers A = ⟨a1,a2,...,an⟩, we define a pair (ai,aj) as an inversion if i < j but ai > aj. The total number of inversions in the sequence A, denoted as I(A), is the count of pairs (ai,aj) that are inversions. Design a divide and conquer algorithm to determine I(A) in Θ(nlogn) time.
Exercise 4 [10 points]
1. Give tight upper and lower bounds on the number of occupied seats. Prove the tightness of your bounds.
2. Write a probabilistic recurrence that expresses the expected number of occupied seats.
Exercise 5 [10 points]
Consider a Monte Carlo algorithm A for a problem Π whose expected running time is at most T(n) on any instance of size n and that produces a correct solution with probability γ(n). Suppose further that given a solution to n, we can verify its correctness in time t(n). Show how to obtain a Las Vegas algorithm that always gives a correct answer to Π. What is the expected run time of your procedure?
Exercise 6 [5 points]
Suppose you are given a coin for which the probability of HEADS, say p, is unknown. How can you use this coin to generate unbiased (i.e., P[HEADS] = P[TAILS] = 1/2) coin-flips? Give a scheme for which the expected number of flips of the biased coin for extracting one unbiased coin-flip is no more than p (11−p).
Exercise 7 [10 points]
Exercise 8 [10 points]
An alternative analysis of the running time of randomized quicksort focuses on the expected running time of each individual recursive call to RANDOMIZED-QUICKSORT, rather than on the number of comparisons performed.
1. Argue that, given an array of size n, the probability that any particular element is chosen as the pivot is n1. 2. Show that
2 n−1
E[T(n)] = XE[T(q)] + Θ(n). (8.1)
n
q=2
3. Show that
n−1
X2
k lgklgn −n . (8.2)
k=2
4. Using the bound from equation (8.2), show that the recurrence in equation (8.1) has the solution E[T(n)] = Θ(nlgn).
Exercise 9 [10 points]
Prove the lower bound of j32nk − 2 comparisons in the worst case to find both the maximum and minimum of n numbers.
Exercise 10 [15 points + 10 bonus points]
Theory part [15 points]
For n distinct elements x1,x2 ...xn with positive weights w1,w2 ...wn such that Pin=1 wi = 1, the weighted median is the element xk satisfying Pxi<xk wi < and Pxi>xk wi . For example, if the elements are 0.1,0.1,0.1,0.3,0.4 and each element equals its weight (so wi = xi for 1 ≤ i ≤ 5), then the median is 0.1, but the weighted median is 0.3.
(a) Argue that the median of x1,x2 ...xn is the weighted median of the xi with weights wi = 1/n for i = 1,2,...n.
(b) Show how to compute the weighted median of n elements in O(nlogn) worst-case time using sorting.
(c) Show how to compute the weighted median in Θ(n) worst-case time using a linear-time median algorithm.
Define the distance between two elements a,b as d(a,b) = |a − b|. Given points x1,x2 ...xn with positive weights w1,w2 ...wn as defined previously, we wish to find a point x (not necessarily one of the input points) that minimizes the sum Pni=1 wi · d(x,xi).
(d) Argue that the weighted median is a best solution.
(e) We generalize the problem into 2-dimensions. We are given a set of n points {(xi,yi)}i=1,...,n, and their corresponding positive weights w1,w2 ...,wn such that Pni=1 wi = 1. What is a best solution point (x,y) that minimizes its weighted distance sum to all the n points in the set? Here the weighted distance between points (x,y) and (xi,yi) is defined as wi·(|xi−x|+|yi−y|).
Coding part [10 bonus points]
Implement an algorithm that finds the best solution you described in the last question (e) of the theory part. Achieve this by completing the best_position function in the Python file available at the Git repo https://github.com/tsourolampis/bu-cs630-fall23.