Divide and Conquer, Median Finding,

Median Finding
Median of n items is the item with rank n=2. The rank of an item is its position in the list if the
items were sorted in ascending order.
Rank i item also called ith statistic.
Example: f16; 5; 30; 8; 55g.
Popular statistics are quantiles: items of rank
n=4; n=2; 3n=4.
SAT/GRE: which score value forms 95th
percentile? Item of rank 0:95n.

Subhash Suri UC Santa Barbara
Median Finding
After spending O(n log n) time on sorting, any
rank can be found in O(n) time.
Can we find a rank without sorting?
Subhash Suri UC Santa Barbara
Min and Max Finding
We can find items of rank 1 or n in O(n) time.
minimum (A)
min A[0]
for i = 1 to n ¡ 1 do
if min A[i] then min à A[i];
return min
The algorithm minimum finds the smallest
(rank 1) item in O(n) time.
A similar algorithm finds maximum item.
Subhash Suri UC Santa Barbara
Both Min and Max
Find both min and max using 3n=2 comparisons.
MIN-MAX (A)
if jAj = 1, then return min = max = A[0]
Divide A into two equal subsets A1;A2
(min1; max1) := MIN-MAX (A1)
(min2; max2) := MIN-MAX (A2)
if min1 · min2 then return min = min1
else return min = min2
if max1 ¸ max2 then return max = max1
else return max = max2

Must prepare exam questions and topics for Algorithms

Leture notes for Algorithms, Design Analysis and Algorithms, Analysis Design and Algorithms.

Please subsrcibe to our channel for more PPTs and Free material for BTech Computer Science and Engineering.

For Free consultancy and counseling, please drop an email to me.

Description
Hi Students, here I will share my lecture videos in advanced concepts in Computer Science and Engineering. Please subscribe to my channel, share my videos, and like them. You can ask me to my email ID if you want any kind of support related to concepts, tutorials, learning in CSE. I help students with:
1. Providing handwritten notes for CSE Subjects (AI, ML, DL, Graph Theory Applications, Discrete Maths, Cryptography, Operating Systems, Data Structures using C, Algorithms, DCN, Theory of Computation, Digital Logic, and Databases )
2. Providing Counseling for GATE CSE.
3. IIT Ph.D. and MTech Interview preparation
4. SOP and SOR preparation.
5. Abroad Collabs for universities.
6. Handwritten notes, Slides and PPTs, course design, Academic consultancy
7. Btech & Mtech projects in machine learning, computer vision, and Deep Learning using google colab
and many other related problems in academia.
Feel free to email me.

NO AUTHORSHIP WAS CLAIMED FOR THE MATERIAL. PPTs are downloaded from various sources.

Description
Hi Students, here I will share my lecture videos in advanced concepts in Computer Science and Engineering. Please subscribe to my channel, share my videos, and like them. You can ask me to my email ID if you want any kind of support related to concepts, tutorials, learning in CSE. I help students with:
1. Providing handwritten notes for CSE Subjects (AI, ML, DL, Graph Theory Applications, Discrete Maths, Cryptography, Operating Systems, Data Structures using C, Algorithms, DCN, Theory of Computation, Digital Logic, and Databases )
2. Providing Counseling for GATE CSE.
3. IIT Ph.D. and MTech Interview preparation
4. SOP and SOR preparation.
5. Abroad Collabs for universities.
6. Handwritten notes, Slides and PPTs, course design, Academic consultancy
7. Btech & Mtech projects in machine learning, computer vision, and Deep Learning using google colab
and many other related problems in academia.
Feel free to email me.