Question

Q2) (1 point) Given two lists, L1 of length n and L2 of length m. We say that L2 is a subsequence of L1 if we can remove elements from L1 to produce L2. This means that there exists indices i1 < ... < im such that L1[ij] = L2[j] for each j. Design an algorithm that detects if L2 is a subsequence of L1 and outputs the indices i1,....,im if L2 is a subsequence of L1.

a.Provide the pseudo-code of that algorithm.

b.Implement the algorithm in a language of your choice and provide a sample run with meaningful input.

Answer 1

a.

The algorithm is a greedy algorithm that makes one pass over both lists. It starts with pointers at the first element of each list, repeatedly incrementing the pointer on L1 until it finds an element i such that L1[i] =L2[1]. This valueiis the outputi1, and at this point thealgorithm increments the pointer onL2to point to the second element, while also incrementing thepointer on the first list, to point to thei+ 1st element. The process repeats until both lists have been traversed.

Here is the pseudocode.
j = 1,
k=1
for k= 1,...,m do
   while L1[j]/=L2[k] do
       j←j+ 1
   end while
   ik=j(in the solution)
   j←j+ 1,k←k+ 1
end for

------------------------------------------------Please Upvote---------------------------------------------------------------------------