COMP 582 GRADUATE DESIGN AND ANALYSIS OF ALGORITHMS Spring 2023 Homework #2
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Homework #2
COMP 582
GRADUATE DESIGN AND ANALYSIS OF ALGORITHMS
Spring 2023
Problem 1 (1.5 points)
You are given two unsorted arrays of size n, A and B, where A has no repeated elements and B has no repeated elements. Provide an algorithm that finds the k-th smallest entry of their intersection A ∩ B and prove that your algorithm is correct. For full credit, your algorithm must run in O(nlog n) time.
Problem 2 (1.5 points)
Let A and B be two sorted arrays of n elements each. We can easily find the median element in A – it is just the element in the middle – and similarly we can easily find the median element in B . (Let us define the median of 2k elements as the element that is greater than k −1 elements and less than k elements.) However, suppose we want to find the median element overall – i.e., the nth smallest in the union of A and B .
Give an O(log n) time algorithm to compute the median of A ∪ B . You may assume there are no duplicate elements.
As usual, prove correctness and the runtime of your algorithm.
Hint: use divide and conquer approach
2023-02-16