Prepared & presented by
Trainer: NIZEYIMANA ERASTE
1
2
What is an algorithm?
An algorithm is “a finite set of precise
instructions for performing a computation
or for solving a problem”
A program is one type of algorithm
All programs are algorithms
Not all algorithms are programs!
Directions to somebody’s house is an algorithm
A recipe for cooking a cake is an algorithm
The steps to compute the cosine of 90° is an
algorithm
Algorithms : is a plan, a set of step-by-step instructions to resolve a
problem. In an algorithm, each instruction is identified and the
order in which they should be carried out is planned.
3
From the data structure point of view, following are
some important categories
of algorithms
Search - Algorithm to search an item in a
data structure.
Sort - Algorithm to sort items in a certain
order.
Insert - Algorithm to insert item in a data
structure.
Update - Algorithm to update an existing
item in a data structure.
Delete - Algorithm to delete an existing
item from a data structure.
4
Characteristics of an Algorithm
Not all procedures can be called an algorithm. An algorithm should have the
following
characteristics –
Unambiguous/ Definiteness - Algorithm should be clear and unambiguous.
Each of its steps (or phases), and their inputs/outputs should be clear and
must lead to only one meaning.
Input - An algorithm should have 0 or more well-defined inputs.
Output - An algorithm should have 1 or more well-defined outputs, and
should match the desired output.
Finiteness - Algorithms must terminate after a finite number of steps.
Feasibility - Should be feasible with the available resources.
Independent - An algorithm should have step-by-step directions, which
should be independent of any programming code.
Correctness- should produce the correct output
Generality: the algorithm should be applicable to all problems of a similar
form
Effectiveness: each step must be able to be performed in a finite amount of
time
5
Properties of algorithms
Algorithms generally share a set of
properties:
Input: what the algorithm takes in as input
Output: what the algorithm produces as output
Definiteness: the steps are defined precisely
Correctness: should produce the correct output
Finiteness: the steps required should be finite
Effectiveness: each step must be able to be
performed in a finite amount of time
Generality: the algorithm should be applicable to
all problems of a similar form
6
Representing an algorithm
There are two main ways that algorithms can
be represented
pseudocode
flowcharts.
7
What is an pseudocode?
Pseudocode is an artificial and informal
language that helps programmers to
develop algorithms.
Pseudocode is not a programming language, it is a simple
way of describing a set of instructions that does not have to
use specific syntax.
Writing in pseudocode is similar to writing in a
programming language. Each step of the algorithm is
written on a line of its own in sequence.
Usually, instructions are written in
uppercase, variables in lowercase and messages in
sentence case.
8
Example1 of pseudocode
A simple program could be created to ask someone their name and
age, and to make a comment based on these. This program
represented in pseudocode would look like this:
START
OUTPUT 'What is your name?'
INPUT user inputs their name
STORE the user's input in the name variable
OUTPUT 'Hello' + name
OUTPUT 'How old are you?'
INPUT user inputs their age
STORE the user's input in the age variable
IF age >= 70 THEN
OUTPUT 'You are aged to perfection!'
ELSE
OUTPUT 'You are a spring chicken!‘
END
9
Example2 of pseudocode
Problem - Design an algorithm to add two
numbers and display the result.
Step 1 – START
Step 2 - declare three integers a, b & c
Step 3 - define values of a & b
Step 4 - add values of a & b
Step 5 - store output of step 4 to c
Step 6 - print c
Step 7 - STOP
10
Flowcharts
A flowchart is a diagram that represents a
set of instructions. Flowcharts normally use
standard symbols to represent the different
types of instructions.
11
Common basic flowchart symbols
These symbols are
used to construct
the flowchart and
show the step-by-
step solution to
the problem.
12
Example of flowchart
Planning a program that asks people what
the best subject they take is, would look
like this as a flowchart:
13
Algorithm Analysis
Algorithm Analysis Efficiency of an algorithm can be
analyzed at two different stages, before implementation and
after implementation. They are the following –
A Priori Analysis - This is a theoretical analysis of an
algorithm. Efficiency of an algorithm is measured by
assuming that all other factors, for example, processor speed,
are constant and have no effect on the implementation.
A Posterior Analysis - This is an empirical analysis of an
algorithm. The selected algorithm is implemented using
programming language. This is then executed on target
computer machine. In this analysis, actual statistics like
running time and space required, are collected.
14
Algorithm Efficiency
Two areas are important for
performance:
space efficiency - the memory required,
also called, space complexity
time efficiency - the time required, also
called time complexity
15
Some algorithms are more efficient than others. We would prefer to
chose an efficient algorithm, so it would be nice to have metrics for
comparing algorithm efficiency.
The complexity of an algorithm is a function describing the efficiency of
the algorithm in terms of the amount of data the algorithm must process.
Usually there are natural units for the domain and range of this function.
There are two main complexity measures of the efficiency of an algorithm:
Time complexity is a function describing the amount of time an
algorithm takes in terms of the amount of input to the algorithm. "Time"
can mean the number of memory accesses performed, the number of
comparisons between integers, the number of times some inner loop is
executed, or some other natural unit related to the amount of real time the
algorithm will take.
Space complexity is a function describing the amount of memory (space)
an algorithm takes in terms of the amount of input to the algorithm. We
often speak of "extra" memory needed, not counting the memory needed
to store the input itself. Again, we use natural (but fixed-length) units to
measure this. We can use bytes, but it's easier to use, say, number of
integers used, number of fixed-sized structures, etc. In the end, the
function we come up with will be independent of the actual number of
16
bytes needed to represent the unit.
Questions
17
quiz
What is time complexity of algorithm
Identify 6 characteristics/ properties of
algorithm
What are difference between priori and
posterior analysis of algorithm?
Write a pseudocode and flowchart which get
age of use and decide If he has ID or not ( age
of get ID is 16 and above).
18
