3 Problem 3: rite an algorithm in pseudocode for each of following two problems
ID: 3751802 • Letter: 3
Question
3 Problem 3: rite an algorithm in pseudocode for each of following two problems below. The algorithm should be simple in both cases! Both algorithms should have running time significantly better than n2 Part 1: Closest Pair (5 points) » Input: An array A with n distinct (non-equal) elements . Output: numbers r and y in A that minimize |x - y, where -y denotes absolute-value(x-y) Part 2: Remove Duplicates (5 points) . Input: An array A of size n, with some elements possibly repeated many times Output: a list L that contains the elements of A (in any order), but without duplicates For example, if A -1,3,7, 5,3,5,3,1,4 then the output set L can contairn the numbers 1,4,7,5,3 in any order.Explanation / Answer
1. PSEUDOCODE
============================
Function Quicksort(A as array, low as int, high as int){
if (low < high){
pivot_location = Partition(A,low,high)
Quicksort(A,low, pivot_location)
Quicksort(A, pivot_location + 1, high)
}
}
Function Partition(A as array, low as int, high as int){
pivot = A[low]
leftwall = low
for i = low + 1 to high{
if (A[i] < pivot) then{
swap(A[i], A[leftwall + 1])
leftwall = leftwall + 1
}
}
swap(pivot,A[leftwall])
return (leftwall)
}
Function ClosestPair(A as array) {
// sort the array using Quick sort in O(nlogn)
Quicksort(A, 0, length(A) - 1)
minDiff = Infinity
x = 0
y = 0
for i = 1 to (length(A) - 1) {
if ((A[i] - A[i-1]) < minDiff) {
minDiff = A[i] - A[i-1]
x = A[i-1]
y = A[i]
}
}
print x, y
}
Time-complexity: O(n*logn)
2. PSEUDOCODE
============================
Function RemoveDuplicates(A as array) {
//A[]-- Initial Array to Sort : Complexity: O(k)
c as array // create a new array to store the frequencies
for i = 0 to k {
c[i] = 0
}
//Storing Count of each element : Complexity: O(n)
for j = 0 to n {
c[A[j]] = c[A[j]] + 1
}
// create a new result array
result as array
for j = 0 to n {
if (c[A[j]] != 0) {
// push A[j] to result array and make its count 0 to avoid another push to result
result.append(A[j])
c[A[j]] = 0
}
}
return result
}
Time-complexity: O(n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.