S6-P1,2

Question 1

158

Answer 1

4
A

Question 2

159

Answer 2

2
A
Note: To find Kth number among n numbers, we don’t use excess memory.

Question 3

160

Answer 3

1
A
Note: Counting sort is for when we know the range and the numbers are integers.

Question 4

Memorize the formula

161

Answer 4

1
A

Question 5

162

Answer 5

3
A

Note On Finding Kth. element: If we use the quick-select approach, then we do not need to sort the array before finding the kth minimum element. The time complexity of the quick-select approach is O(n), where n is the number of elements in the array. Fix that one note where kth element is explained

Question 5

Mind fuck

163

Answer 5

4
A
Note On Method 2: when median x > median y, then the upper half of x is bigger than its upper half + y’s lower half, so the xy median must be in the lower half of x or the upper half of y.

Question 6

164

Answer 6

2
A

Question 7

165

Answer 7

4
A
Sorting Algorithms

Note: When we partition the array using √n, we have at least √n smaller numbers since we found √nth element (the median) of the first 2√n+1.

Note: The question wants the worst case, worst case is when there’s exactly √n numbers behind the median of 2√n+1 first elements, because it creates the biggest unsorted part after √nth element.

The order of the final recursive formula: draw a tree, nodes on each level =n and since we are doing n-√n in each step, the height would be √n.

Question 8

End Of P1,2