You are given a sequence S of n purchases at a stock exchange, possibly containi

Question

You are given a sequence S of n purchases at a stock exchange, possibly containing some events multiple times. For example, S might be Buy Amazon, Buy Google, Buy eBay, Buy Google, Buy Google, Buy Oracle. You are also given another sequence S' of m purchases m < n. Show how to determine if S' is a subsequence of S in linear time. For example, if S' is Buy Amazon, Buy eBay, Buy Google then S’ is a subsequence of S, whereas if S' is Buy Amazon, Buy Google, Buy Google, Buy eBay then S' is not a subsequence of S. Prove that your algorithm is optimal via a ”Greedy Stays Ahead” argument

Explanation / Answer

/**
* S -> Original Sequence
* S_1 -> Another Sequence
* n -> Number of elements in Sequence S
* m -> Number of elements in Sequence S_1
*/
bool isSubsequnce(S,S_1,n,m){
   j = 0; // For index of subsequence

   // Traverse S and S_1, and compare current Stock
   // of Sequence S with the first unmatched Stock of Sequence
   // if matched then move ahead in S_1
   for i = 1:n
       if (S[i] == S_1[j])
           j += 1;
   end

   // If all stock of S_1 were found in S
   if (j == m) return true;
   return false;
}

Algorithm is optimal because we compare current Stock of Sequence S with the first unmatched Stock and move forward a=only and only if match is found

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.