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 asorted 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?

Cs3330

Assignment 1

January 13, 2019

1.a) The pseudo code for the closest pair problem is as illustrated below:

Closest pair (K, i, j)

input: Array K is indexed from i to j. closest pair returns the indices of the closest pairs.

diff = K[2] - K[1] // This is the initial difference between the first two numbers. This is shown through the array and these differences. example: K[2] > K[1] else vice versa

loop from i to j

loop from i to j

//works only when I j

if K[i] < K[j] and diff > K[j] - K[i]

// Here, K[j] is greater than K[i] and is greater than the current value in diff

then diff = K[j] - K[i]

index1 = i

index2 = j

elseif K[j] < K[i] and diff > K[i] - K[j]

// Here, K[i] is greater than K[j] and is greater than the current value in diff

then diff = K[i] - K[j]

index1 = i

index2 = j

else

// Here, the values in K[i] and K[j] are same

then diff = 0

index1 = i

index2 = j

return index1, index2

1.b) On examining the algorithm, the following points can be determined

The nested loop showa a complexity of O(n^2). Nested loops will show the 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 same result can be in constant time.

2.a) The pseudo code for the binary search problem is as illustrated below:

binsrch(K, i, j, v)

input: array K 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 K; if v is not found, -1 is returned.

if (i > j) then return (-1); m = (i + j)/2;

if (K[m] == v) then return(m);

if (K[m] < v)

then return(binsrch(K, m+1, j, v));

else return(binsrch(K, i, m-1, v));

2.b) On examining the algorithm, the following points can be deduced:

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.

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 asorted 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?

Cs3330

Assignment 1

January 13, 2019

1.a) The pseudo code for the closest pair problem is as illustrated below:

Closest pair (K, i, j)

input: Array K is indexed from i to j. closest pair returns the indices of the closest pairs.

diff = K[2] - K[1] // This is the initial difference between the first two numbers. This is shown through the array and these differences. example: K[2] > K[1] else vice versa

loop from i to j

loop from i to j

//works only when I j

if K[i] < K[j] and diff > K[j] - K[i]

// Here, K[j] is greater than K[i] and is greater than the current value in diff

then diff = K[j] - K[i]

index1 = i

index2 = j

elseif K[j] < K[i] and diff > K[i] - K[j]

// Here, K[i] is greater than K[j] and is greater than the current value in diff

then diff = K[i] - K[j]

index1 = i

index2 = j

else

// Here, the values in K[i] and K[j] are same

then diff = 0

index1 = i

index2 = j

return index1, index2

1.b) On examining the algorithm, the following points can be determined

The nested loop showa a complexity of O(n^2). Nested loops will show the 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 same result can be in constant time.

2.a) The pseudo code for the binary search problem is as illustrated below:

binsrch(K, i, j, v)

input: array K 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 K; if v is not found, -1 is returned.

if (i > j) then return (-1); m = (i + j)/2;

if (K[m] == v) then return(m);

if (K[m] < v)

then return(binsrch(K, m+1, j, v));

else return(binsrch(K, i, m-1, v));

2.b) On examining the algorithm, the following points can be deduced:

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.

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.