CHAPTER 1: INTRODUCTION TO ALGORITHMS
Objectives of this Chapter
At the end of this chapter, you should be able to
Correctly define an algorithm
List at least five qualities of a good algorithm
Explain the relationship between algorithm and programming
List the three building blocks (construct) of an algorithm
1. Definition
When telling the computer what to do, we also get to choose how it’s going to do it. That’s where computer
algorithms come in. Algorithm is the basic technique used to get the job done. So, one can define an
algorithm as;
An algorithm is a step – by – step set of finite instructions performing a particular task to solve a problem.
1.1. Qualities of a Good Algorithm
Everyone can write algorithms but not everyone writes “good algorithms”.
For an algorithm to be qualified as a good algorithm, it should possess the following characteristics:
1. Precision: The steps of an algorithm should be precisely or clearly stated.
2. Non-ambiguity: Each instruction should be clear, there should not be any doubt on what is done at each
step.
3. Finiteness: The algorithm stops after a finite number of instructions are executed.
4. Effectiveness: The Algorithm should be able to give out the desired solution
5. Efficiency: The algorithm should be able to produce its solution within a reasonable amount of time.
6. Uniqueness: Results of each step should be well defined and only depend on the input and the result of
the preceding steps.
7. Input and Output: The algorithm may not receive any input and it may receive more than one.
However, it must produce at least one output.
8. Robustness: A robust algorithm should be able to handle erroneous input and/or handle errors during its
execution.
TO-DO
Use the internet to go to “Google maps” ([Link] and get driving or walking directions
from your home to Douala International Airport (DIA). Explain how the algorithm for driving or walking
directions meets each algorithmic criterion listed above.
The art of writing good algorithms rest on two main criteria:
1. Intuition
You need to have some intuition, because no recipe allows you to know beforehand which
instructions will achieve the desired results. But, there are people who have more intuition at
first than others, though reflexes can be acquired.
2. Methodical and Rigorous
Every time we write a series of instructions that we believe to be right, we must
systematically put ourselves at the place of the machine that will execute it, armed with a
paper and pencil in order to check if the result obtained is the desired one. This operation
does not require a little ounce of intelligence. But it remains essential, if we do not want to
write blindly.
1.2. The relationship between Algorithms and Programming
An algorithm describes the steps needed to solve a problem independent of the programming
language. Computers don’t understand instructions written in human languages (which are so
numerous) so, the algorithms must be written in a language the computers understand and that is
binary code. Programming languages were design to make this process easier. They use special
keywords and syntax which are equivalent of vocabulary and grammar in a human language. The
programming language then converts these keywords and syntax into binary code which the
computer can execute. So, with a written algorithm, one can use any programming language of
his/her choice to implement the program.
1.3. Representation of an Algorithm
There are three main methods used in representing algorithms
Flowcharts
Pseudo Code
Structured English
1.3.1. Flowcharts
A flowchart is a type of diagram that represents an algorithm showing the steps as boxes of
various kinds, and their order by connecting them with arrows. OR a flow chart is a step – by –
step diagrammatic representation of the logic paths to solve a given problem.
This diagrammatic representation illustrates a solution model to a given problem. A flowchart helps
to clarify how things are currently working and how they could be improved. It also assists in finding
the key elements of a process by drawing clear lines between where one process ends and the next
one starts. Flowcharts help in revealing redundant or misplaced steps. In addition, they help in
establishing important areas for monitoring or data collection and to identify areas for improvement
or increase in efficiency.
[Link]. Flowchart Symbols and their description
Start/Stop OR Begin/End: The terminator symbol marks the starting or ending
point of the system. It usually contains the word "Start" or "Stop."
Action or Process: A box can represent a single step ("add two cups of flour"),
or an entire sub-process ("make bread") within a larger process.
Document: A printed document or report.
Decision: A decision or branching point. Lines representing different decisions
emerge from different points of the diamond.
Input/output: Represents material or information entering or leaving the
system, such as customer order (input) or a product (output).
Connector: Indicates that the flow continues where a matching symbol
(containing the same letter) has been placed.
Flow Line: Lines indicate the sequence of steps and the direction of flow.
Delay: Indicates a delay in the process.
Merge: Indicates a step where two or more sub-lists or sub-processes become
one.
Collate: Indicates a step that orders information into a standard format.
Sort: Indicates a step that organizes a list of items into a sequence or sets based
on some pre-determined criteria.
Subroutine: Indicates a sequence of actions that perform a specific task
embedded within a larger process. This sequence of actions could be described
in more detail on a separate flowchart.
Manual Loop: Indicates a sequence of commands that will continue to repeat
until stopped manually.
Loop Limit: Indicates the point at which a loop should stop.
Data storage: Indicates a step where data gets stored.
Database: Indicates a list of information with a standard structure that allows for
searching and sorting.
Display: Indicates a step that displays information.
Off Page: Indicates that the process continues off page.
Example of a flowchart algorithm
[Link]. Advantages of flowchart
- Communication: Flowcharts are helpful in explaining the program to other people.
- Effective analysis: With the help of flowchart, the problem can be analyzed more effectively
- Proper documentation: Program flowchart serves as a good program documentation, which is
needed for various purposes
- Efficient coding: Once the flowchart is drawn, it becomes easy to write the program in any high
level language
- Proper debugging: The flowchart helps in the debugging process
[Link]. Limitations of Flowcharts
- Complex: If the program is very large, the flowcharts cover many pages, making them hard to
follow.
- Costly: If the flowchart is to be drawn for a huge program, the time and cost factor of program
development may get out of proportion, making it a costly affair.
- Difficult to Modify: Due to its symbolic nature, any change or modification to a flowchart usually
requires redrawing the entire logic again, and redrawing a complex flowchart is not a simple task.
- No Update: Usually, programs are updated regularly. However, the corresponding update of
flowcharts may not take place, especially in the case of large programs.
1.3.2. Pseudo Code
Pseudo-code (pronounced Soo-Doh-Kohd) is made up of two words: Pseudo and code. 'Pseudo'
means imitation and 'Code' refers to instructions, written in a programming language. As the name
suggests, pseudo-code is not a real programming code, but it models and may even look like a
programming code. It is a generic way of describing an algorithm without using any specific
programming language notations. It uses plain English statements rather than symbols, to represent
the processes in a computer program [Pseudo-code can be defined as an algorithm representation
technique that describes algorithm in a generic manner without using any specific programming
language]. It is also known as program design language (PDL).
[Link]. Pseudo-code Structures
Pseudo-code allows the designer to focus on the logic of the algorithm without being distracted by
details of language syntax. The 'structured' part of pseudo-code is a notation for representing three
general programming constructs: sequence, selection and repetition. Each of these constructs can be
embedded inside any other construct. These constructs represent the logic or flow of control in an
algorithm. The following keywords are often used to indicate input, output and processing
operations.
• Input: READ, OBTAIN, GET and PROMPT
•Output: PRINT, DISPLAY and SHOW
• Compute: COMPUTE, CALCULATE and DETERMINE
• Initialize: SET and INITIALIZE
• Add One: INCREMENT
[Link]. Example of pseudo-code
The pseudo-code below calculates the area of a rectangle
Pseudo-code: To calculate the area of a rectangle
PROMPT the user to enter the length of the rectangle
PROMPT the user to enter the width of the rectangle
COMPUTE the area by multiplying the length with width
DISPLAY the area
STOP
TO-DO: Draw the corresponding flow chart for the pseudo code above
[Link]. Pseudo-code Guidelines
- Statements should be written in simple English (or any preferable natural language) and should be
programming language independent.
- Steps must be clear, that is, unambiguous and when the steps (instructions) are followed, they must suggest
a solution to the specified problem.
- Each instruction should be written in a separate line and each statement in pseudo-code should express just
one action for the computer.
- Capitalize keywords such as READ and PRINT.
- Each set of instructions is written from top to bottom, with only one entry and one exit.
[Link]. Advantages of Using Pseudo-code
Some of the most significant benefits of pseudo code are as follows:
• Since it is language independent, it can be used by most programmers. It allows the programmer to express
the problem logic in plain natural language.
• It is easier to develop a program from a pseudo code rather than from a flowchart or decision table.
• Often, it is easy to translate pseudo code into a programming language, a step which can be accomplished
by less-experienced programmers.
• Unlike flowcharts, pseudo code is compact and does not tend to run over many pages. Its simple structure
makes it easier to modify as well.
• Pseudo code allows programmers who work in different computer languages to talk to each other.
[Link]. Disadvantages of Using Pseudo-code
• There are no accepted standards for writing pseudo-codes. Different programmers use their own style of
writing pseudo code.
• It is quite difficult for the beginners to write pseudo code as compared to drawing a flowchart
To-Do: Give two advantages of pseudo-code over flowchart
1.3.3. Structured English
Structured English is a limited form of pseudo code. It uses English language with the syntax of structured
programming (note that with pseudo there is not any syntax) to communicate the design of a computer
program to non-technical users; by breaking it down into logical steps using straightforward English words.
It is the basis of some programming languages such as SQL (Structured Query Language) [for use by people
who have need for interaction with a large database but who are not trained programmers]
To-Do: What is the difference between structured English and pseudo code?
[Link]. Elements of Structured English
Structured English consists of the following elements:
- Operation statements (sequence): written as English phrases executed from the top down
- Conditional blocks (selection): indicated by keywords such as IF, THEN, and ELSE- Repetition blocks
(repetition): indicated by keywords such as DO, WHILE, and UNTIL
[Link]. Guideline for writing Structured English
1. All logic should be expressed in operational, conditional, and repetition blocks
2. Statements should be clear and unambiguous
3. Use one line per instruction
4. Keywords should begin with a capital letter
5. Mark comment lines with an asterisk
NB: For the purpose of this lesson, structured English will be used to write all algorithms. But where
necessary flowcharts might be brought in for clarity.
1.4. Algorithm Construct
There are three basic constructs sufficient for implanting any algorithm. These three constructs are:
sequence, selection and repetition. No matter how complex an algorithm may be, each instruction will
always fall under one of the following construct.
A sequence construct
A sequence construct is a linear progression where one task is performed sequentially after the other in the
order they appear. Examples of such instructions are Read/Write instructions, performing variable
assignments, etc
Selection construct is a process of deciding which choice is made between two or more alternative courses
of action depending on a certain condition. There are several ways of doing this. This will be discussed in
the chapters ahead.
Repetition construct also called looping construct is used when some particular task(s) is to be repeated for
a number of times according to specified condition.
1.5. Skeleton of an Algorithm
AN algorithm is written as follows:
Algorithm NameofAlgorithm
Start
Instructions 1
Instructions 2
.
.
.
Instructions N
End
NB:
- The key word algorithm begins with a capital letter, as well as the keywords Start and End
- Name of Algorithm is written without space
- Each instruction is written on a distinct line