(a) Describe an algorithm to find all the common elements in two sorted lists of
ID: 639031 • Letter: #
Question
(a) Describe an algorithm to find all the common elements in two sorted lists of numbers. You can describe the algorithm in English or in a pseudocode. For example, for the lists 2, 5, 5, 5 and 2, 2, 3, 5, 5, 7, the output should be 2, 5, 5.
(b) What is the minimum number of comparisons your algorithm makes if the lengths of the two given lists are 5 and 7? Present sample lists of the minimum number of comparisons.
(c) What is the maximum number of comparisons your algorithm makes if the lengths of the two given lists are 5 and 7? Present sample lists of the maximum number of comparisons.
(d) What is the maximum number of comparisons your algorithm makes if the lengths of the two given lists are m and n?
Explanation / Answer
ok . Lets have a simpler version.
First instinct would be to keep track of 2 indices, one for each list and a total of course.
Starting with the first value in each list, do the following
Check if all 2 values are equal, if so increment the total and all indices by 1.
Otherwise, increment the index of lowest value by 1.
Repeat until you reach the end of one list (at this point you are done)
This would use a single loop and at first glance seems reasonably efficient since each iteration guarantees that you advance in one of the lists. This means you have at most 2*n iterations of your loop.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.