5.1: Introduction to Algorithm

We have frequently used the word algorithm in our programming class to mean the idea, or the method of solving a programming problem. More precisely, an algorithm is a step-by-step method of solving some problem. In computer science, algorithm typically refers to a solution that can be executed by a computer.

Algorithms typically have the following characteristics:

• An algorithm normally requires some input data, which means an algorithm should specify what kind of data it works on
• An algorithm normally produces an output. Such output can be multiple data values, multiple data types. It can also be a display
• The steps in an algorithm are precisely stated
• The intermediate results of each step of execution are unique and are determined only by the inputs and results of the preceding steps. It means, if an algorithm receives the same set of inputs, it should produce the same set of outputs.
• The output produced by an algorithm should be correct
• The algorithm should be applied to a set of inputs. In other words, an algorithm should not just work for a specific input.

But, what exactly an algorithm is? Let's take a look at an example.

Example

Suppose we are given a program task: "Write a user-defined function that receives three numbers and returns the maximum of those three numbers the function receives."

Before we proceed, we need to note:

1. We don't have to write an algorithm for each programming task before the coding. It is just like we don't have to have speech notes before we give a speech. But, preparing notes for a speech will definitely help us to give a better speech.
2. We may have different ways of solving a programming problem. Thus, there may be different algorithms for a single programming task.

The programming task given in this example can be accomplished in many different ways, therefore, we can write different algorithms for this programming task. Here we only provide one of them which is considered as the best.

Algorithm of Finding the Maximum of Three Numbers

Input: three numbers a, b, and c

Output: The largest of a, b, and c

1. 1. large = a
   2. if b > large, then large = b;
   3. if c > large, then large = c;

return large

Of course, we don't really need to write such algorithm to code the function. But, by studying the algorithm of this simple programming task which we already know how to code, we will understand what an algorithm is and how it should be written.

Writing an algorithm is like writing a program in normal language. But, not exactly. It is more like to write a plan for a task.

Writing an algorithm is providing a solution to a programming problem. One of important benefits of writing an algorithm as the solution is the algorithm we provide is not programming language specific. It can be used to implement the programming solution with different programming languages. For example, if we provide the solution of this task with C++ code directly, then the people who are using python may not understand what we are talking about.

The idea of above algorithm is to inspect the numbers one by one and copy the largest value seen into a variable large. At the conclusion of the algorithm, the value of the variable large will then be equal to the largest of the three numbers.

It is easy to understand this algorithm because we already know how to solve this problem before we see the algorithm. For some unfamiliar programming tasks, even someone provides the solution in the form of an algorithm, it may still be difficult to understand what the algorithm is talking about. To be a good programmer, following two abilities are essential:

1. Understand an algorithm written by someone else
2. To be able to write an algorithm for the solution of a programming problem.

One of the common way to study an algorithm is to execute the algorithm for some specific values of the variables in the algorithm. Such simulation is called a trace. In the process of the tracing, we record the values of each variable at each step.

Here, we show how to trace the algorithm presented in this example.

First suppose that

a = 1, b=5, c = 3

At line 1: we set the variable large to a, so the value of the variable large now is 1

At line 2; we compare the value of the next number, b, with the value of the variable large. If b > large, then change the value of large to b, otherwise, do nothing. Since b = 5, large =1, we change the value of large to 5

At line 3: we compare the value of the third number, c, with the value of the variable large. If b > large, then change the value of large to c, otherwise, do nothing. Since c = 3, large =5, we don't do anything.

At this point, we can see the algorithm ensures the value of the variable large holds the largest numbers of a, b, and c.

For an unfamiliar algorithm or a more complicated algorithm, we often need to trace the algorithm several times with different sets of input data.

Although ordinary language is sometimes adequate to specify an algorithm, most programmers and computer scientists prefer a so called pseudocode because of its precision, structure, and universality. Pseudocode is so named because it resembles the actual code of computer languages such as C++, Java.

Here we provide the pseudocode version of the algorithm we presented in this example:

Algorithm of Finding the Maximum of Three Numbers (written in pseudocode)

This algorithm finds the largest of the numbers a, b, and c

Input: three numbers a, b, and c

Output: large (the largest of a, b, and c)

1. maxThree(a, b, c){
2. large = a;
3. if(b>large) //if b is greater than large, update large
4. large=b
5. if(c>large) //if c is greater than large, update large
6. large=c;
7. return large
8. }

As the pseudocode of the algorithm, here we

• Given a title to the algorithm
• Provide a brief description of the algorithm
• List the input and outputs of the algorithm
• Provide a function that contains step by step instructions
• for convenience, label each line of the pseudocode.

Example

Programming Task: "Find the largest number in a given sequence" Now, let's write an algorithm for this task.

Algorithm Title: Finding the Maximum Value in a Sequence

Algorithm Description: This algorithm finds the largest of the numbers s₁, s₂, ..., s_n

List of Inputs and output: The sequence s, which represents s₁, s₂, ..., s_n and size or the length of the sequence, n

Function:

getMax(s, n)
{
large=s₁
for k=2 to n
if (s_k>large)
large=s_k
return large
}

If we eliminate those labels and descriptions, the algorithm can be trimmed down to

Finding the Maximum Value in a Sequence

This algorithm finds the largest of the numbers s₁, s₂, ..., s_n

Input: s, n

Output: large

getMax(s, n)
{
large=s₁
for k=2 to n
if (s_k>large)
large=s_k
return large
}

This algorithm is using the same logic as the one we used in the previous example. But this algorithm can be used for solving more general problem: "Find the largest value from any sequence of data"