Question

In this exercise we deal with the problem of string matching.

a) Explain how to use a brute-force algorithm to find the first occurrence of the given string m of characters, called the target, in a string nof characters, where $m\le n$, called the text. [Hint: Think in terms of finding a match for the first character of the target and checking successive characters for a match, and if they do not all match, moving the start location one character to the right.]

b) Express your algorithm in pseudo code.

c) Give a big-O estimate for the worst-case time complexity of the brute-force algorithm you described.

Short answer

a) The algorithms best-case performance is when the number of comparisons made is the least, which is n - 1 in this algorithm.

b) The number of comparisons made is only one.

c) The numbers of comparisons made are $\lceil lo{g}_{2}n\rceil$times

Subpart a)

The first term of the array is selected as max.

With the help of the loop every element is checked.

Any element that has a greater value than the selected one is taken as max.

In one iterated for loop only one comparison is made.

The loop is iterated for i = 1 to n.

Therefore the number of iterations and comparisons are n - 1.

Subpart b)

The algorithm is,

Input: x integer, $(a_1,a_2,a_3,....,a_n)$:list of distinct integers

Output: Index such that$x=a_i$ or 0

If is not in the list.

Algorithm:

If $i:=1$;

While$i\le n$ and$x\ne a_i$

Do $i:=i+1$;

If$i\le n$ then $result:=i;$;

Else $result:=0;$;

Return $result$;

Therefore the best-case scenario is when the element to be located is the first element so only one comparison is made.

Step-by-step solution

Subpart c)Step 1:

The algorithm will be,

if$i:=1$;

$f:=n;$

While i < j do

$m:=\left|\frac{(i+j)}{2}\right|$

If $x>a_i$then i: = m + 1 else j: = m;

If $x=a_i$then result: = i; else result: = 0;

Return result;

Step 2:

We divide the set in to half$|{\log }_{2}n|$number of times.

Therefore the numbers of comparisons made are$|{\log }_{2}n|$ times