CS 3330 Assignment 1 (Due: at 11:59PM on 3/25/2018) 1.a) Write a pseudo-code for
ID: 3737411 • Letter: C
Question
CS 3330 Assignment 1 (Due: at 11:59PM on 3/25/2018) 1.a) Write a pseudo-code for the "closest-pair" problem. In this problem, you will determine the closest number pair in a given randomly order number array. For example assume your array A is as follows: A [2, 20, 35, 28, 45, 23, 67, 21, 95, 15] Your program (or pseudo-code) will find the indices of closest numbers in the array. In the above array A, 20 and 21 are the closest pairs. 1.b) Perform a complexity analysis of your algorithm as I did in the video tutorial What is the best-case, average-case, and the worst-case scenarios? 2.a) Write a pseudo-code for "binary search" problem. In this problem, you will search an element in a sorted array. For example: A 1, 4, 7,9, 12, 24, 56, 61, 62, 65, 89] If the search element is 12, your algorithm must find its index. 2.b) Perform a complexity analysis for your algorithm as I did in the video tutorial. What is the best, average, and worst case? No code submission over Canvas is necessary. Please submit your solutions to the Canvas on due date as Word or Pdf file. On the top of your paper, please add your name and number, Course ID, Assignment number and the date.Explanation / Answer
1.a)
sort(arr,n)//sort the array
int closest=INT_MAX,int i,int j,int k=0
while(till the end of array)
if(abs(arr[k]-arr[k+1]<closest)
closest=abs(arr[k]-arr[k+1]
i=k,j=k+1
k++
print(arr[i] and arr[j])
1.b)
Acoording to above psudo code best case time coplexity =time complexity of sort + time complexity of find closest . we can see that after the sorting find closest will be O(n).In the best case time complexity for sort will be O(n). so totall time complexity in best case will ne O(n) + O(n) = O(n) In average and worst case of sorting is O(nlog(n)) so time complexity of for worst and average case will be O(nlog(n)) + O(n) = O(nlog(n))
2.a)
2.b)
in the binary search first of all we search the middle element if it is target then we return . it will be best case so best case time complexity will O(1) If middle is greter then target then we ignore the right part of array and search in the left part of the middle of the array If middle is less then target then we ignore the left part of array and search in the right part of the middle of the array . so we can say every time we ignore the half of the array . so at the xth iteration n/2^x=1 if target found or end of the array so n=2^x . x = nlog(n) in both average and worst case