Design an algorithm that, given two lists of integers, creates a list consisting

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 (n 2 ), where n is the sum of the lengths of the two input lists.

Explanation / Answer

Algorithm CommonValues(A[1..n1], B[1..n2], C[])

MergeSort(A[1..n1]) //It takes O(nlogn) time.

MergeSort(B[1..n2]) //It takes O(nlogn) time.

j := 1, k := 1

while(j <= n1 and k <= n2)

if A[j] < B[k]:

j += 1

else if A[j] > B[k]:

k += 1

else:

if l == 0:

C[l] = A[j]

j += 1, k += 1, l += 1;

else:

if A[j] ~= C[l-1]

C[l] = A[j]

l += 1

j += 1, k += 1;

return C;

This algorithm has a worst case efficiency of O(nlogn), as the maximum time is required to sort the lists. And the worst case efficiency of MergeSort is O(nlogn).

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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