Combining lists. For this problem, assume the list ADTs are implemented using doubly linked lists. a. Let L and L 0 be two list ADTs. Each one contains distinct numbers sorted in increasing order. We want to output another list ADT that combines L and L 0 . There are two natural choices for combining L and L 0 - (i) take their union or (ii) take their intersection. In the union of L and L 0 , the list should contain all the numbers that appear in L or L 0 . On the other hand, in the intersection of L and L 0 , the list should contain all the numbers that appear in L and L 0 . For both the union and intersection operations, we want the combined list's numbers to still be in sorted order. For example, let L = (3, 5, 6, 9) and L 0 = (2, 3, 8, 9, 10). Then the union of L and L 0 is (2, 3, 5, 6, 8, 9, 10) while the intersection of the two lists is (3, 9).

a1. (1 pt.) Assume the sizes of L and L 0 are n and m respectively. Design Union(L, L0 ), an algorithm that outputs the union of L and L 0 in O(n + m) time.

a2. (1 pt.) Similarly, design Intersect(L, L0 ) an algorithm that outputs the intersection of L and L 0 in O(n + m) time.

b. Suppose we now have k list ADTs L1, L2, . . . , Lk whose elements are distinct numbers in sorted order. This time we want to combine all of them into a single list ADT whose elements are again in sorted order. Let D be an ADT that contains references to Li for i = 1, . . . , k. Then we can combine the lists as follows:

lists as follows: function UNIONALL(D) while D.size > 2 do remove L and L' from D L" + Union(L, L') add L" to D end while return the only list L in D. end function Thus, UnionAll(D) outputs a list that contains all the numbers that appeared in at least one of the Li's.how you arrived at your answer. Next, consider the following way of combining the lists: function INTERSECTALL( D) while D.size > 2 do remove L and L' from D L" + Intersect(L, L') add L" to D end while return the only list _ in D. end function