Design an algorithm that, given two lists of integers, creates a list consisting
ID: 3930065 • Letter: D
Question
Design an algorithm that, given two lists of integers, creates a list consisting of those integers that appear in both lists (each integer on the final list should appear only once). Describe your algorithm in terms of a high-level pseudocode focusing on main algorithmic tasks and not on low-level details. Analyze the running time of your algorithm. You will get full credit only if your algorithm achieves an asymptotically better worst-case performance than theta(n^2), where n is the sum of the lengths of the two input lists.Explanation / Answer
Algorithm 1:Using Hash
1)Create Empty List L to store Union of Lists
2)Create Empty Hash table H
3)Now take list L1 and travese it and put each element of it in Hash table H and List L.
4)Consider second List L2 do following:
For every element e in List 2 ...Search x in hash H .
If not in Hash put in Hash H and put it in List L.
5)Finally,print List L
Time complexity:(n+n) It is assumed that Hash table insert and search takes (1) time
Algorithm 2:Using Sorting
1)For this we need to sort both Lists.so use merge sort to sort them
2)Take two index variable for travesing two lists.Let it be i=0,j=0;
3)Let List L be final list.
4)if List1[i] <List2[j] then insert in List L.Increment i
5)if List1[i] >List2[j] then insert in List L.Increment j
6)2)if List1[i] ==List2[j] then insert any one of them in List L.Increment i as well as j.
7)Print the remaining elements of Larger List.
Time Complexity: O(nLogn + nLogn).= O(nLogn).
In this case we are using merge sort so that we need O(nLogn + nLogn) time to sort both lists.
Also we need O(n) to traverse List.Hence Overall time complexity is O(nLogn)
Algorithm 3:Using sorting and searching
1) Initialize List L as empty.
2) Find smaller of List L1 and List L2 and sort the smaller array.
3) Copy the smaller array to List L.
4) For every element e of larger array, do following
Binary Search e in smaller array. If e is not present, then copy it to L.
5) Print List L
Time complexity:O(nLogn).As we are using binary search on every element of List.Hence O(Logn) for Binary Search and O(n) for traversing each element of List
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.