5. Consider the following problem: Given an array of n integers, are there any d

Question

5. Consider the following problem: Given an array of n integers, are there any duplicate integers in the array? (a) Write an algorithm (in pseudocode) which solves this problem USING A HASH TABLE. (Do NOT use sorting.) Your algorithm should use the hash table operations, Initialize, Insert, Retrieve and Member. Input to your algorithm is an array Al and the number of integers n in the array. The algorithm returns true if there are any duplicate numbers in the array and false otherwise. (b) Assume your hash table has size at least 2n. Analyze the EXPECTED asymptotic running time of your algorithm on an array with no duplicate numbers. Justify your running time analysis. (c) Assume your hash table has size at least 2n. Analyze the WORST CASE running time of your algorithm on an array with no duplicate numbers. Justify your running time analysis. (Note that the worst case time for insertion/find in a hash table is different than the expected case time. The difference between the worst case and expected times of insertion/find in the hash table will affect the worst case and expected times of your algorithm.)

Explanation / Answer

(A)

CountDistinctNumbers(a, n)
count = 0
hashtable hashT<key, value>;
for each i in array a : .....(1)
count = count + InsertAndFindMember( hashT, a[i])

return count

Procedure: InsertAndFindMember(hashT,X)

key = X % 10
current_element = findValue(hashT, key)
while (current_elemet.next != null) : ....(2)
if(current_element.value = X){
return 0;
}
current_element.next = new element(X, null)

return 1

----------------------------------------------------------------------------------------------------------------------------------------------

explanation :-

- Hashtable is used with chaining: each <key, value> pair has one key ( 0 ,1,2 ,..9) and one value(i.e address of first node of linked list) . each node in linked list has one element and one next pointer stored in it and next pointer points to the next element of the linked list. next pointer is null if the node is last element.

- modulo 10 hash function is used here.

- InsertAndFindMember(hashT, int X) : takes 2 inputs hashT and X. hashT is hashtable in which key has to be inserted and X is a key that has to be inserted.
It traverse through the linked list for a given key and finds out if element already exist in linked list or not. if element exist then returns 0 otherwise it will inser x at the end of linked list and returns 1.

- findValue(hashT, key) function returns the value(i.e address of first node of given key) in hashT hashtable.

here chaining with hashing is used.

(B) if Hash table size is 2n Expectedd time :-

Expected runtime : here in given algo we have used modulo 10 hash function. if the hash table size is 2n then we can use modulo 2n hash function.

so loop (1) will be executed n times and loop (2) will be executed in constant amount of time if all n numbers in array are evely distributed. so time taken will be O(n).

(C) worst case time :-

when hashtable of 2n size is used , then in worst case one key can have upto n elements in linked list. so we have to go through all n elements in loop (2).

hence in worst case running time will be O(n^{2})

-----------------------------------------------------Thank You------------------------------------------------

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

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