TOPIC 3 : DIVIDE AND CONQUER

1. Write a Program to find both the maximum and minimum values in the array. Implement using any
programming language of your choice. Execute your code and provide the maximum and
minimum values found.
Input : N= 8, a[] = {5,7,3,4,9,12,6,2}
Output : Min = 2, Max = 12
Test Cases :
Input : N= 9, a[] = {1,3,5,7,9,11,13,15,17}
Output : Min = 1, Max = 17
Test Cases :
Input : N= 10, a[] = {22,34,35,36,43,67, 12,13,15,17}
Output : Min 12, Max 67

2. Consider an array of integers sorted in ascending order: 2,4,6,8,10,12,14,18. Write a Program to

3. You are given an unsorted array 31,23,35,27,11,21,15,28. Write a program for Merge Sort and
implement using any programming language of your choice.
Test Cases :
Input : N= 8, a[] = {31,23,35,27,11,21,15,28}
Output : 11,15,21,23,27,28,31,35
Test Cases :
Input : N= 10, a[] = {22,34,25,36,43,67, 52,13,65,17}
Output : 13,17,22,25,34,36,43,52,65,67

4. Implement the Merge Sort algorithm in a programming language of your choice and test it on the
array 12,4,78,23,45,67,89,1. Modify your implementation to count the number of comparisons
made during the sorting process. Print this count along with the sorted array.
Test Cases :
Input : N= 8, a[] = {12,4,78,23,45,67,89,1}
Output : 1,4,12,23,45,67,78,89
Test Cases :
Input : N= 7, a[] = {38,27,43,3,9,82,10}
Output : 3,9,10,27,38,43,82,

5. Given an unsorted array 10,16,8,12,15,6,3,9,5 Write a program to perform Quick Sort. Choose the
first element as the pivot and partition the array accordingly. Show the array after this partition.
 Recursively apply Quick Sort on the sub-arrays formed. Display the array after each recursive call
until the entire array is sorted.
Input : N= 9, a[]= {10,16,8,12,15,6,3,9,5}
Output : 3,5,6,8,9,10,12,15,16
Test Cases :
Input : N= 8, a[] = {12,4,78,23,45,67,89,1}
Output : 1,4,12,23,45,67,78,89
Test Cases :
Input : N= 7, a[] = {38,27,43,3,9,82,10}
Output : 3,9,10,27,38,43,82,

6. Implement the Quick Sort algorithm in a programming language of your choice and test it on the
array 19,72,35,46,58,91,22,31. Choose the middle element as the pivot and partition the array
accordingly. Show the array after this partition. Recursively apply Quick Sort on the sub-arrays
formed. Display the array after each recursive call until the entire array is sorted. Execute your code
and show the sorted array.
Input : N= 8, a[] = {19,72,35,46,58,91,22,31}
Output : 19,22,31,35,46,58,72,91
Test Cases :
Input : N= 8, a[] = {31,23,35,27,11,21,15,28}
Output : 11,15,21,23,27,28,31,35
Test Cases :
Input : N= 10, a[] = {22,34,25,36,43,67, 52,13,65,17}
Output : 13,17,22,25,34,36,43,52,65,67

7. Implement the Binary Search algorithm in a programming language of your choice and test it on the
array 5,10,15,20,25,30,35,40,45 to find the position of the element 20. Execute your code and
provide the index of the element 20. Modify your implementation to count the number of
comparisons made during the search process. Print this count along with the result.
Input : N= 9, a[] = {5,10,15,20,25,30,35,40,45}, search key = 20
Output : 4
Test cases
Input : N= 6, a[] = {10,20,30,40,50,60}, search key = 50
Output : 5
Input : N= 7, a[] = {21,32,40,54,65,76,87}, search key = 32
Output : 2

8. You are given a sorted array 3,9,14,19,25,31,42,47,53 and asked to find the position of the element
31 using Binary Search. Show the mid-point calculations and the steps involved in finding the
element. Display, what would happen if the array was not sorted, how would this impact the
performance and correctness of the Binary Search algorithm?
Input : N= 9, a[] = {3,9,14,19,25,31,42,47,53}, search key = 31
Output : 6
Test cases
Input : N= 7, a[] = {13,19,24,29,35,41,42}, search key = 42
Output : 7
Test cases
Input : N= 6, a[] = {20,40,60,80,100,120}, search key = 60
Output : 3
 9. Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and
an integer k, return the k closest points to the origin (0, 0).
(i) Input : points = [[1,3],[-2,2],[5,8],[0,1]],k=2
Output:[[-2, 2], [0, 1]]
(ii) Input: points = [[1, 3], [-2, 2]], k = 1
Output: [[-2, 2]]
(iii) Input: points = [[3, 3], [5, -1], [-2, 4]], k = 2
Output: [[3, 3], [-2, 4]]

10. Given four lists A, B, C, D of integer values,Write a program to compute how many tuples
n(i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
(i) Input: A = [1, 2], B = [-2, -1], C = [-1, 2], D = [0, 2]
Output: 2
(ii) Input: A = [0], B = [0], C = [0], D = [0]
Output: 1

11. To Implement the Median of Medians algorithm ensures that you handle the worst-case
time complexity efficiently while finding the k-th smallest element in an unsorted array.
arr = [12, 3, 5, 7, 19] k = 2 Expected Output:5
arr = [12, 3, 5, 7, 4, 19, 26] k = 3 Expected Output:5
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] k = 6 Expected Output:6

12. To Implement a function median_of_medians(arr, k) that takes an unsorted array arr and an
integer k, and returns the k-th smallest element in the array.
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] k = 6
arr = [23, 17, 31, 44, 55, 21, 20, 18, 19, 27] k = 5
Output: An integer representing the k-th smallest element in the array.

13. Write a program to implement Meet in the Middle Technique. Given an array of integers
and a target sum, find the subset whose sum is closest to the target. You will use the Meet
in the Middle technique to efficiently find this subset.
a) Set[] = {45, 34, 4, 12, 5, 2} Target Sum : 42

b) Set[]= {1, 3, 2, 7, 4, 6} Target sum = 10:

14. Write a program to implement Meet in the Middle Technique. Given a large array of
integers and an exact sum E, determine if there is any subset that sums exactly to E. Utilize
the Meet in the Middle technique to handle the potentially large size of the array. Return
true if there is a subset that sums exactly to E, otherwise return false.
a) E = {1, 3, 9, 2, 7, 12} exact Sum = 15
b) E = {3, 34, 4, 12, 5, 2} exact Sum = 15

15 Given two 2×2 Matrices A and B

3 5) 7 5)

Use Strassen's matrix multiplication algorithm to compute the product matrix C such that
C=A×B.

Test Cases:

Consider the following matrices for testing your implementation:

Test Case 1:

A=(1 7 B=( 6 8
3 5), 4 2)

Expected Output:
C=(18 14
62 66)

16 Given two integers X=1234 and Y=5678: Use the Karatsuba algorithm to compute the
product Z=X x Y

Test Case 1:

Input: x=1234,y=5678

Expected Output: z=1234×5678=7016652