Question

Problem 1:

You have two sorted lists of integers, L1 and L2. You know the lengths of each list, L1 has length N1 and L2 has length N2.

Design a linear running time complexity algorithm (ONLY PSEUDOCODE) to output a sorted list L1 ∧ L2 (the intersection of L1 and L2).

Important Notes:

For this problem, you don’t need to submit any implementation in Java. Only the pseudocode of your algorithm is required.

Pseudocode is a simple way of writing programming code in English. It uses short phrases to write code for programs before you actually create it in a specific language.

• Example of pseudocode:

Set total to zero
Set grade counter to one
While grade counter is less than or equal to ten

Input the next grade

Add the grade into the total
Set the class average to the total divided by ten

Print the class average.

Please make sure answer is given in pseudocode

Answer 1

Pseudocode

Set ordered list L2 with L2 elements                //List2 L2
set i=0                                             //Set variables for looping
set j=0
set k=0
Declare a list L3                                   //List for output
while i<N1 and j<N2                                 //Loop until end of lists
   if L1[i]<L2[j]                                   //Check greater
      i=i+1
   Else If L1[i]>L2[j]                              //Check lesser
       j=j+1
   Else                                             //Check equal
      L3[k]=L2[j]                                   //Add element into output list
      i=i+1
      j=j+1
      k=k+1
   End If
End while