Question

Consider the function FINDDUPLICATES(A[0. 1) that returns a list of all duplicate items in the unsorted integer array A of size n. For example, given the array |3, 2, 4, 3], the function should return the value 3. For the array 11 2,3 5,5,5,66,81, the function should return an array (or list) 5,6 In this task, you will develop two alternative solutions for the FINDDUPLICATES(Ao..n 1 func- tion. In your implementations, you may call any of the algorithms introduced in the lectures and/or generic' functions/operations/methods to help you develop your solution. That is, you do not have to write the 'standard' algorithms/functions just call them with an appropriate comment (a) 4 marksl Write a pre-sorting based algorithm for the FINDDUPLICATES(A[0.-1) function. Your algorithm should strictly run in O(n log n) time. (b) 4 marksl Write a hashing based algorithm for the FINDDUPLICATES(A[0.. 1 function. Your algorithm should run in O(n) time.

Answer 1

a)

Pre-Sorting based algorithm

• INPUT arr = array of elements
• arr = QuickSort(arr)
• int rep = INT_MAX
• rep_list = [ ]
• FOR i from 1 to length(arr)-1:
• if arr[ i ] == arr[ i+1 ] and arr[ i ] != rep:
• rep_list.append ( arr[i] )
• rep = arr[ i ]
• print rep_list

b)

Hashing based algorithm:

• INPUT arr = array of elements
• SET max_element = maximum ( arr )
• SET hash[ max_element ] = [0,0,....0]
• rep_list = [ ]
• FOR i from 1 to length( arr ) :
• if hash[ arr[ i ] ] == 1:
• rep_list.append( arr[ i ] )
• else:
• hash[ arr[ i ] ] = 1
• print rep_list