1.a) Write a pseudo-code for the “closest-pair” problem. In this problem, you wi
ID: 3736704 • Letter: 1
Question
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?
Explanation / Answer
1.a) The pseudo code for the closest pair problem is as illustrated below:
clospair(A,i,j)
input: Array A is indexed from i to j. clospair returns the indices of the closest pairs.
diff = A[2] - A[1] // This is the initial difference between the first two numbers. We will iterate through the array and get the indices based on this difference. Assumption: A[2] > A[1] else vice versa
loop from i to j
loop from i to j
//work only when i <> j i.e. i is not equal to j
if A[i] < A[j] and diff > A[j] - A[i]
// Here, A[j] is greater than A[i] and is greater than the current value in diff
then diff = A[j] - A[i]
index1 = i
index2 = j
elseif A[j] < A[i] and diff > A[i] - A[j]
// Here, A[i] is greater than A[j] and is greater than the current value in diff
then diff = A[i] - A[j]
index1 = i
index2 = j
else
// Here, the values in A[i] and A[j] are same
then diff = 0
index1 = i
index2 = j
return index1, index2
1.b) On examining the algorithm, the following points can be inferred
• The nested loop renders a complexity of O(n^2). Nested loops easily yield a Big-Oh notation, the value of which depends on the index.
• The algorithm has only one input: n. It's time complexity is O(n^2), regardless of n, so there's no particular “best case” and "average case". Note that we can produce the same result in constant time.
2.a) The pseudo code for the binary search problem is as illustrated below:
binsrch(A, i, j, v)
input: array A indexed from i to j with items sorted from smallest to largest and item v. output: binsrch returns a location of item v in array A; if v is not found, -1 is returned.
if (i > j) then return (-1); m = (i + j)/2;
if (A[m] == v) then return(m);
if (A[m] < v)
then return(binsrch(A, m+1, j, v));
else return(binsrch(A, i, m-1, v));
2.b) On examining the algorithm, the following points can be inferred:
• The non-recursive work takes constant time C.
• The single recursive call has input half the size of the original.
• The algorithm terminates when the array has size no larger than one.
Therefore, we have the following recurrence: T (n) = T (n/2) + C, and we conclude that T (n) = k · (C + 1), where k is the number of recursive calls. Also, we note that, if the size of array A is n, then (n/2k ) = 1, so k = lg n, and T (n) = (C + 1) · lg n.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.