CS2092D-ASSIGNMENT 3 Solved

QUESTIONS

 

1.    Write a program that reads n distinct integers of an array A, given in ascending order and checks whether a given integer k is present in the array using recursive binary search. If k is present in the array, print its index in A. Otherwise, print -1. Also print the number of calls made to the recursive binary search function over the course of the program (You are permitted to use a global variable to maintain this count).

Assume that the array index starts from 0.

Input Format:

•    The first line contains an integer, n ∈ [0,105], the size of the array A.

•    The second line lists the n distinct elements in A, as space-separated integers in the range [−106,106].

•    Third line is an integer k ∈ [−106,106] to be searched in the array.

Output Format:

•    The first line contains the index of k, if it is present in the array A. Otherwise print -1.

•    The second line contains the number of calls to the recursive function made over the course of the program.

Sample Input 1:

7

12  35 50 59 60 73 90

73

Sample Output 1:

5

2

Sample Input 2:

7

12 35 50 59 60 73 90

100

Sample Output 2:

-1

3

2.    Modify your program for Question 1 such that it reads n integers (not necessarily distinct) of an array A, given in ascending order and checks whether a given integer k is present in the array using recursive binary search. If k is present in the array, print the index of its first occurrence in A. Otherwise, print -1. Also print the number of calls to recursive function made over the course of the program.

Note: You should find the first occurrence of k using recursive calls only, and should not linearly traverse the array for any purpose.

Assume that the array index starts from 0.

Input Format:

•    The first line contains an integer, n ∈ [0,106], the size of the array A.

•    The second line lists the n elements in A, as space-separated integers in the range [−1000,1000].

•    Third line is an integer k ∈ [−1000,1000] to be searched in the array.

Output Format:

•    The first line contains the index of the first occurrence of k, if k is present in the array A. Otherwise print -1.

•    The second line contains the number of calls made to the recursive function over the course of the program.

Sample Input 1:

7

12  35 50 59 60 73 90

73

Sample Output 1:

5

2

Sample Input 2:

15

1 1 2 2 2 2 2 2 2 3 3 3 3 3 3

3

Sample Output 2:

9

3

3.    Given an unsorted array A containing m distinct integers and a sorted array B containing n integers, write a program to find their intersection using recursive binary search. Intersection of two arrays is the list containing common elements from both the arrays. If an element is repeated, then only one occurrence of that element should be present in the intersection. Assume that the array index starts from 0.

Input Format:

•    The first line contains two space-separated integers m and n ∈ [0,106], the size of the arrays A and B, respectively.

•    The second line lists the m distinct elements in A, as space-separated integers in the range [−103,103].

•    The third line lists the n elements in B, sorted in descending order, as space-separated integers in the range [−103,103].

Output Format:

•    The output contains the intersection of arrays A and B as space-separated integers in their order of occurrence in A.

Sample Input 1:

7 5

12  35 23 59 15 73 9095 73 67 59 3

Sample Output 1: 59 73

Sample Input 2: 4 6

33 25 56 19 77 67 6 5 4 3 2 1

Sample Output 2:

-1

4.    Write a program that uses the Merge-Sort algorithm for sorting a given input sequence of integers present in an array A and prints the number of comparisons performed during sorting. Your program must contain the following functions. (In what follows, the notation A[p..r] denotes the sub-array of A, contained within the pth and rth indices, both inclusive.)

•    A recursive function Merge-Sort(A, p, r) that takes as input an array A and sorts the elements in the sub-array A[p..r].

•    A function Merge(A, p, q, r) that takes as input an array A in which the sub-arrays A[p..q] and A[q+1..r] are sorted. It then merges these sub-arrays such that the the sub-array A[p..r] is sorted.

•    A function Print(A,n) that takes as input an array A of size n, and prints its contents in order, with a single space separating the elements. This function should only be called from the main() function.

Input Format:

•    The first line contains an integer n ∈ [0,105], the size of the array A.

•    The second line lists the n elements in A, as space-separated integers in the range [−103,103].

Output Format:

•    The first line contains the elements of A in sorted order, separated by space.

•    The second line contains the number of comparisons performed during sorting.

Notes:

•    The number of comparisons made can vary a little depending on the way Merge Sort is implemented. As such, we will be considering the number of comparisons as per the Merge Sort algorithm given in CLRS.

•    In particular, to split an array A[p..r] into two sub-arrays, the Merge-Sort() function should compute an index q ∈ [p,r] such that A[p..q] contains dn/2e elements, and A[q+1..r] contains bn/2c elements).

Sample Input 1:

10

23 76 89 3 8 0 789 123 889 25

Samle Output 1:

0 3 8 23 25 76 89 123 789 889

34

Sample Input 2:

10

90 89 78 67 56 45 34 23 12 11

Sample Output 2:

11 12 23 34 45 56 67 78 89 90

34

5.    Write a program to count the number of inversions in an array A containing n distinct integers by modifying the Merge-Sort algorithm. The inversion count of an array indicates how far (or close) the array is from being sorted; if the array is already sorted, then the inversion count is 0, whereas the count will be maximum if the array is sorted in the reverse order. Two elements A[i] and A[j] form an inversion if A[i] > A[j] and i < j.

Input Format:

•    The first line contains an integer n ∈ [0,105], the size of the array A.

•    The second line lists the n distinct elements in A, as space-separated integers in the range [−106,106].

Output Format:

•    The first line should contain the number of inversions in the array A.

•    The second line should contain the number of comparisons performed over the course of the program (Refer the note given in Question 4).

Sample Input 1:

10

23 76 89 3 8 0 789 123 889 25

Samle Output 1:

17

34

Sample Input 2:

10

90 89 78 67 56 45 34 23 12 11

Sample Output 2:

45

34