Write an algorithm in pseudocode for each of following two problems below The al

Question

Write 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 x and y in A that minimize r - 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 contain the numbers 1,4,7,5,3 in any order

Explanation / Answer

Part 1 Answer:

We can solve this problems with in n (log n) time.

step 1:Take Array A with n distinct elements

step 2: Find minDiff -> |A[1] - A[0]|

step 3: Run a for loop each element from 2 to length of array

          step4 :Find minDiff using Math min method between minDiff and |A[i+1] - A[i]| ->min(minDiff, abs(A[i+1] - A[1]))

              step 5: Print least minDiff value

              step 6: Print pair of x, y = A[i+1], A[i] respectively whichever is giving that minDiff.

Part 2 Answer:

This problem we can solve using C, C++ or Java containers such List, Map, Vector or Hash table in n (log n) time.

           step 1: Take Array A with n elements

step 2: Define a hash table ->H : = new Hash table

step 3: Take a count variable->count = 0

step 4: Now run a for loop for each element in A

step 5: Add A elements into Hash table H

step 6: If element is not present in H then move element count number of positions Left

step 7: If it is present increment count

                         step 8: Push back H to A

             step 9: Print the array A

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.