5.2: More Examples of Algorithms

Example

Write an algorithm that returns the index of the first occurrence of a specific character in a string (a sequence of characters): s₁, s₂, ..., s_n

Here is the word "index" is referring to the position of a character in a sequence. For example, the index of '&' in the sequence "abcd&dcba" is 5

Algorithm: Character Search

This algorithm is used for finding the index of the first occurrence of a specific character in a string

Input: a string of character s = s₁, s₂, ..., s_n and a character ch

Output: k (an integer that is the index of the first occurrence of ch in the string s) If the character ch is not in the string s, then the output is 0;

getIndex(s, ch)
{
for k=1 to n
if(s_k==ch)
return k;
return 0;
}

Example

Write an algorithm that returns the index of the last occurrence of a specific character in a string (a sequence of characters): s₁, s₂, ..., s_n

Algorithm: Find the index of the last occurrence of a specific character in a string

This algorithm is used for finding the index of the last occurrence of a specific character in a string

Input: a string of character s = s₁, s₂, ..., s_n and a character ch

Output: index (an integer that is the index of the last occurrence of ch in the string s) If the character ch is not in the string s, then index=0;

getIndex(s, ch)
{
int index
for k=1 to n
if(s_k==ch){
index=k;
}
return index;
}

Examples presented above are algorithms of simple programming tasks. It seems trivial if we need to write those algorithms for the tasks. Unfortunately, it is not always the case. Let's study an algorithm that is slightly more difficult then the previous two examples.

Searching Algorithm

One of major computer programming task is searching. Examples are searching a student record from a school data file, searching a website from the internet, searching a book from a library and so on. All of those tasks can be stated as a searching problem. Here we will discuss an algorithm to solve a tex-searching problem.

Example

Suppose we are given a text document and look for the first occurrent of a specific word. Instead of coding a program directly, we write an algorithm that provides a solution to this searching problem.

Algorithm: Word Search

This algorithm searches for an occurrence of a word W in a text document D. It returns the smallest index i such that W occurs in D starting at index i. If the word W does not occur in D, it returns 0.

Input: W (indexed from 1 to m), m, D (indexed from 1 to n), n

Output: i

1 word_search(W, m, D, n)
2 {
3 for i=1 to n-m+1 {
4 j=1
5 while(D_i+j-1==W_j){
6 j++;
7 if(j>m)
8 return i
9 }
10 }
11 return 0
12 }

If we are in the real world and facing such programming task. That is all we will get as a guideline for coding the program. It will leave us to figure out the logic of the algorithm. Since we are now in the classroom situation and we are learning it, we will provide further assistance to explain the logic of this algorithm.

1. All the characters in the document D are indexed as D_i , with i=1, 2, 3, ..., n and all the characters in the word W are indexed as W_j , with j=1, 2, 3, ..., m
2. Inputs of the function are: the text document. It may be an array with n elements or a Linked list with n nodes or some other types of data structures; the length of the array, which is n; the word that we are looking for. It may also be an array with m elements or a linked list with m nodes or some other types of data structures; the length of the array, which is m. So the inputs are D, n, W, m
3. Output: i, which is the index of the first character of the word when it first occurs in the document.
4. Line 1 specify the name of the function as well as its inputs. The function has total of four inputs: The word that we are search for, the length of the word, the document that we will be searching, the length of the document, which is the total number of characters in the document.
5. From line 3 to line 9, it is a nested looping statement with an outer for loop and an inner while loop with outer looping variable i and an inner looping variable j
6. The outer loop varies the value of i from 1 to n-m+1 because the number of characters in the word is m, if the word is in the document, then the index of the first character in the word can not be greater than n-m+1. For example, if the document has 100 characters, then n=100. If the word that we are searching for has 5 characters, them m=5. So, the largest possible value of i can not be greater than 100-5+1, which is 96. Since i is the index of the first character in the word, and word has 5 characters, if i=97, then we won't have the full word occurs in the document.
7. The nested looping statement begins with D₁ , which is the first character in the document. The inner while loop compare this character with each character in the word W_j with j=1, 2,...,m. If there is a match, then compare with the next character in the word (j=j+1). If there is a mismatch, inner loop stop, increase the value i (which means moving to the next character in the document) and then repeat the inner loop (which is comparing the next character in the document with each character in the word as we did in the previous step)
8. If one of the character and onward four consecutive characters all match, we would have j>m, then the function returns i, which will be the index of the first character of the word when it first occurs in the document.
9. If the algorithm never return i, then it means the document does not contain the word, so the function returns 0

Hope those explanations help you better understand the logic of the algorithm. You can also use some sample inputs to trace the algorithm.