Selection and Medians
based problems
Discussions of Last Lecture’s questions
• Q3: Find Kth smallest element in a min heap of n elements.
• Q4: Implement stack using min Heap/PQ
2
Discussions of Last Lecture’s questions
• Q5: Given a big file of billions of elements. Find max 10
numbers from the file.
•
3
Discussions of Last Lecture’s questions
• Q6: Merge K sorted lists each with n/K elements. Aim to
improve time as well as space complexity.
• Hint: merge logic of merge-sort can be one option. Use of PQ can
be thought
• Hint: merge logic of merge-sort can be one option. Use of PQ can
be thought
• Sol A: merge 2nd list with 1st, then 3rd list with 1+2, & so on
• Time: 2n/K+3n/k+…Kn/K = O (n.K)
• Sol B: Pairwise merge => O (n log K)
• Sol C: Use of min-heap
Make min-heap of K roots,
extract-min & add new element from the corresponding list
K+ n log K = O (n log K)
4
5
Selection Based
• Q1: Find 2nd largest in an array of unsorted distinct elements
• Can we do better that (n-1) + (n-2) steps?
• Hint: Tournament tree based search can be useful.
• Q2: Find all K smallest elements from an unsorted list of
elements.
• Explore all alternates: brute force, heap, BST
• Q3: Find Kth smallest element in worst case linear time.
• Hint: Concept of median of medians will be used 6
Selection: Medians
• Median of n elements:
If n is odd: middle element in the sorted list
If n is even: average of middle two elements of the sorted list
• Median of Medians Algorithm: sel_median(A,n) {
• Step1: Partition the list into sub-groups (SGs), each of 5 elements
count of SGs = ceil(n/5)
• Step 2: Sort each SG using insertion sort in constant time
• Step 3: A' [1] = median of first SG(m1), A' [2] = m2, …
A' [count] = mcount;… ; m1 is median of 1st SG, and so on.
• Step 4: Using median of medians algo recursively, Find median of
A'. m_o_m = sel_median(A', count of SGs)
• To find Kth smallest element in Ɵ(n):
Let q= no of elements of A smaller than m_o_m
Use K vs q to recursively call in sublist <= m_o_m OR sublist
>= m_o_m. 7
Median of Medians: How Ɵ(n) in Worst case
• Recursion to find Kth element/exact-median will call
sel_medians algo recursively.
• For worst case analysis, we should consider the max size
of the sublists being called recursively and use that in
recurrence relation (like we do in worst case analysis of
quicksort)
• To estimate size of each sublist: once m_o_m is found, it
is sure that atleast half of elements of A' <=m_o_m (A'
elements are medians of 5-element groups).
• Each such median of A' contributes at least 3 elements <=
m (except max two groups: last group & the group
having m, m can be from last group also)
8
Median of Medians: How Ɵ(n) in Worst case
• So no of elements in the left sublist of m_o_m will be
atleast
left_size >= 3*[(n/5)/2 - 2] = 3n/10 -6
• In that case no of elements in the right sublist :
right_size <= T(n/5) – [3n/10 – 6] = 7n/10 + 6
• Recurrence relation:
T(n) = T(n/5) * T(1) + Ɵ(n) + T (max (left_size, right_size)
<=T(n/5)+Ɵ(n)+T (7n/10 ) ; Use Master Theorem:- Ɵ(n)
9
Problem Solving using Selection/Medians
• Q4: Given two arrays each containing n sorted elements. Find
median of 2n elements in lesser time complexity?
• Point to remember: Merge both lists and use m_o_m will take how
much time?
• Can you improve that further?
• Point to note: Both lists are already sorted. Can we use that ?
Obvious aim is to try for O (log n) now. So size during recursive
call needs to reduce to say half.
10
