Assistance with a simple algorithm

Question

I'm currently learning algorithms from a book I have bought from Amazon but it is the worst book in the world, it shows examples but crucially doesn't show how to work the answers out.

so the first question I have is,

Prefix-Match(T[1..n], P[1..m]) {
i := 1 // point to current position in T[]
while(i <= n) {
// find a match for first character of P
while( i <= n && T[i] != P[1]) i++
if (i > n) return; // quit
len := 1
// match as much as possible
while(len < m && i+len <= n && T[i+len] == P[1+len]) len++
output i, len
i++
}

what would the output of this program be if T = [a,b,a,b,c,a,b] and P = [a,b,a]???

and secondly how do I work out time complexity of the algorithm, in terms of m and n?

Answer 1

what would the output of this program be is T = [a,b,a,b,c,a,b] and P = [a,b,a]???

The beginner way to do this is to take a pen and a paper and make a slot for each variable. Then go through each statement, just as a computer would and change the written variable values as result of the statement execution.

For example, if you start with T and P as above, you would first set values for T, n, P and m go through i := 1 write 1 in the slot for i, then you would pass through while(i <= n) { because (1 is < n) and so on...

When you do this a few times you will be be able to do it much faster.

I'm currently learning algorithms from a book I have bought from Amazon but it is the worst book in the world, it shows examples but crucially doesn't show how to work the answers out.

so the first question I have is,

 Prefix-Match(T[1..n], P[1..m]) {
  i := 1 // point to current position in T[]
  while(i <= n) {
     // find a match for first character of P
     while( i <= n && T[i] != P[1]) i++
     if (i > n) return; // quit
     len := 1
     // match as much as possible
     while(len < m && i+len <= n && T[i+len] == P[1+len]) len++
     output i, len
     i++
 }

what would the output of this program be is T = [a,b,a,b,c,a,b] and P = [a,b,a]???

and secondly how do I work out time complexity of the algorithm, in terms of m and n?

I am not convinced you are ready to workout time complexity, but think about how m and n affect the maximum time taken by the algorithm (or how long it will take you to do by hand):

• Does it depend on m?
• Does it depend on n?
• If it depends on both is it a function on m+n or more like m*n? That is, for the same sizt of T and double the size of P does it take twice as long?

Answer 2

Well first of all a question: what book you are talking about? If this is exactly a code sample from it, then it has to be terrible...

And now for the answer:

• this function runs through every element of T (this is the first while loop),
• then it finds the first occurrence of the the first element of P in the range from "i" to the end of the table T. In this case i = 1, because T[1] == P[1] (if T does not contain the first element of P then the function simply returns),
• then it looks at how many elements in T starting from i match subsequent elements in P (meaning that it will take element T[i+1] and check if it matches P[2] and same with T[i+2] and P[3]),
• it then prints the i it found and how many matches it found.

Basically this function finds all the subsets of T that match P. And the exact output should look like this:

1, 3
3, 2
6, 2

Tldr: the first number is the index at which the element P[1] is in the table T and the second number is the number of elements following it equal to its counterparts in table P.

But I do not know what was the author's intention - from what I understand the found subset doesn't have to completely match the P set, i.e. if we took: T = [a,c,a] and P = [a,b,a] we would still get the output 1,3. There is no element that breaks the loop if the subsequent element of the found subset in T is different from its counterpart in P.

About time complexity there's plenty of articles on the web. If you want a book then CLRS Introduction to Algorithms or Algorithm Design Manual are my favorits.