1. Consider the following algorithm to find the distance between the two closest
ID: 3837266 • Letter: 1
Question
1. Consider the following algorithm to find the distance between the two closest elements in an array of numbers.
Algorithm MinDistance (A[0..n-1])
//Input: Array A[0..n-1] of numbers
//Output: Minimum distance between two of it’s elements
Dmin <-
For i <- 0 to n – 1 do
For j <- 0 to n-1 do
If i j and |A[i] – A[j]| < dmin
Dmin <- |A[i] – A[J]|
Return dmin
(a) Even though it’s small, make at least two improvements in the algorithm and present them clearly
(b) Rewrite the pseudocode to reflect your improvements.
Explanation / Answer
Sort array, and then look for distance in adjacent elements. This will run in O(nlogn) instead of logn
Algorithm MinDistance (A[0..n-1])
//Input: Array A[0..n-1] of numbers
//Output: Minimum distance between two of it’s elements
Dmin <-
sort array
For i <- 0 to n – 2 do
if A[i+1] – A[i] < dmin
Dmin <- A[i+1] – A[j]
Return dmin
if you do not want to sort, then change inner loop to iterate from i rather than 0 as those diff are already considered.
Algorithm MinDistance (A[0..n-1])
//Input: Array A[0..n-1] of numbers
//Output: Minimum distance between two of it’s elements
Dmin <-
For i <- 0 to n – 1 do
For j <- i to n-1 do
If |A[i] – A[j]| < dmin
Dmin <- |A[i] – A[J]|
Return dmin
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.