Is my proof of my greedy algorithm to find subsequence correct?

Question

Credit to KleinBerg and Taros Book

Some of your friends have gotten into the burgeoning field of time-series data mining, in which one looks for patterns in sequences of events that occur over time. Purchases at stock exchanges—what’s being bought— are one source of data with a natural ordering in time. Given a long sequence $S$ of such events, your friends want an efficient way to detect certain “patterns” in them—for example, they may want to know if the four events:

{buy Yahoo, buy eBay, buy Yahoo, buy Oracle}

occur in this sequence $S$, in order but not necessarily consecutively. They begin with a collection of possible events (e.g., the possible transactions) and a sequence $S$ of $n$ of these events. A given event may occur multiple times in $S$ (e.g., Yahoo stock may be bought many times in a single sequence S). We will say that a sequence $S'$ is a subsequence of $S$ if there is a way to delete certain of the events from S so that the remaining events, in order, are equal to the sequence $S'$. So, for example, the sequence of four events above is a subsequence of the sequence

{buy Amazon, buy Yahoo, buy eBay, buy Yahoo, buy Yahoo, buy Oracle}

Their goal is to be able to dream up short sequences and quickly detect whether they are subsequences of $S$. So this is the problem they pose to you: Give an algorithm that takes two sequences of events—$S'$ of length $m$ and $S$ of length $n$, each possibly containing an event more than once—and decides in time $O(m+n)$ whether $S'$ is a subsequence of $S$.

Here is my pseudocode to this solutions:

set i and j to 1
when i <= S.length & j <= S'.length{
    if S(i) is the same as S'(j)
    then increment i and j by 1
    else just increment i
}
if ( j > S'.length) {
    return true
else
    false

My proof of correctness of optimality:

Let $A = (j_1,\cdots,j_m)$ be the sequence found by our greedy solution and hence return true, and let $B = (l_1,\cdots,l_n)$, be the sequence found by an optimal solution and also returns true.

We prove by induction that the greedy algorithm will succeed in returning true if a match was found and will ensure that $j_m \ge l_n$, showing that the greedy is as optimal as the optimal solution.

Base: Consider the case where $m = 1$ and $n = 1$, then the algorithm let $j_1$ of $A$ and $l_1$ of $B$ be the first events found and hence $j_1 >= l_1$.

IH: Now the case where $m > 1$ and $n > 1$, and assume $m-1 < A.\text{length}$ and $n-1 < B.\text{length}$, and by the IH, we have found events matching the subsequence and hence also $j_{m-1}$ and $l_{n-1}$, has a match, giving use $m-1 \ge n-1$. Knowing that the next for either solutions would be at $j_m$ and $l_n$ and hence $A=B$, and hence $j_m \ge ln$. Hence the greedy is as good as the optimal. ///

Would this be a way to prove the optimality as I cannot find another optimal that takes more than $O(n+m)$, hence just showing that the optimal and greedy would give the same result.?? Very confused.

Thanks in advance.

Answer 1

A post that requests us to check if a solution to a problem is correct is off-topic in general, especially when the solution is correct. However, in the current case, there are a couple of minor conceptual misunderstandings in this question, which I would like to address.

---

Would this be a way to prove the optimality as I cannot find another optimal that takes more than $O(n+m)$, hence just showing that the optimal and greedy would give the same result?

What is "the optimality"? In the original problem, there is no requirement of any kind of optimality. The requirements are

• the algorithm should decide whether $𝑆'$ is a subsequence of $𝑆$.
• the algorithm should run in time $𝑂(m+n)$.

Although your algorithm looks like a greedy algorithm, the quantity or the objective function that should be optimized is never defined. So, it makes little sense to "prove the optimality" of your algorithm. It does not, in fact, make much sense to say that your algorithm is a greedy algorithm without specifying the objective function! That is probably the source of your confusion. That is why your proof seems unclear and dangling at a few places, since your proof is only a proof of correctness.

---

On the other hand, we can list three objective functions. For one of them, your algorithm is the optimal algorithm. For the other two, your algorithm becomes a greedy and correct algorithm.

I will state the objective functions in the form of three easy exercises. Hopefully you will not be confused any more.

Exercise 1. Show that your algorithm run in $O(m)$ time. Show that any algorithm that finds $S'$ will run at least in $\Theta(m)$ time in worst cases. (Note that $O(m+n)$ cannot be used here unless we assume $m\ge n$, in which case $O(m)=O(m+n)$.)

Exercise 3. For each subsequence $sub=(S_{i_1}, S_{i_2}, \cdots, S_{i_k})$ of $S$, define its finishing index $FI(sub)=i_k$. Show that your algorithm is a greedy algorithm that finds a subsequence of S that is the same as $S'$ with the minimum finishing index if there is a subsequence that is the same as $S'$.

Exercise 3. For each subsequence $sub=(S_{i_1}, S_{i_2}, \cdots, S_{i_k})$ of $S$, define its total index $TI(sub)=i_1+i_2+\cdots+i_k$. Show that your algorithm is a greedy algorithm that finds a subsequence of S that is the same as $S'$ with the minimum total index if there is a subsequence that is the same as $S'$.