Question

Suppose that we have two unsorted lists of integers A and B. The lists are the same size, n.

a) Write an algorithm that outputs how many integers occur in both lists.

An integer occurs at most once in each given list.

For example: if A = [1,2,5,7,13,19] and B = [2,9,13,14,19,22], then we can see that elements {2, 13, 19} occur in both lists, so the output will be 3.

b) If the lists were sorted, say how we could improve the efficiency of the algorithm.

Answer 1

a) Algorithm to find common elements in two lists:

Step 1: Get the size of lists, n

Step 2: Get the two integer lists of size, n

Step 3: Initialize two temporary variables i and j to 0

Step 4: Initialize count to 0 for maintaining count of numbers that occur in both lists

Step 5: The variable 'i' is used to iterate over first list and variable 'j' is used to iterate over second list

Step 6: The first element of first list is compared with all the elements in the second list until it is matched. If the element is matched in the second list, increment the count variable by 1 and break the second loop because the element is found.

Step 7: If the searching element is not found after iterating all over the second list, then it means that the element is not there in the second list and count should not be incremented.

Step 8: Loop all over the two lists.

Step 9: Output the count variable which indicates the number of matching elements in both lists.

b) If the elements are sorted, instead of searching for the element all over the second list, we continue searching for the element until the element in the second list is not greater than the searching element. In this way, we can optimize the number of comparisons compared with the above algorithm when the lists are not sorted.