CHAPTER ONE

INTRODUCTION TO
THEORY OF ALGORITHM

chapter 1
 OUTLINE
2

➢ Application of Algorithm
➢ Why we need to Study Algorithms
➢ Brain Storming examples on Algorithm
➢ Classification of Algorithm
➢ Classification of Algorithm by implementation
➢ Classification of Algorithm by design paradigm
➢ Important assumption in this course
➢ Elementary Sorting Algorithm
➢ Selection sort
➢ insertion sort
➢ Bubble sort

chapter 1
 ALGORITHM
3

➢ An algorithm is a finite sequence of well-defined and

unambiguous computational procedure that takes data
stored in a data structure as input and produces output
data stored in the same or different data structure

➢ From the above definitions, algorithm has the following

properties: finite, Sequence, Unambiguous, well-
defined, Generality, Input, Output, Finite

chapter 1
 PROPERTIES OF ALGORITHM
4

Finite
Every valid algorithm must complete or terminate after a
finite number of steps.
Every algorithm should have a beginning (start) and a halt
(end) step
The first step (start step) and last step (halt step) must be
clearly noted
If you trace out the instructions of an algorithm, then for all
cases the algorithm must terminate after a finite number of
steps
It must eventually stop either with the right output or with a
statement that no solution is possible

chapter 1
 PROPERTIES OF ALGORITHM
5

Finite
Finiteness is an issue for computer algorithms because
 Computer algorithms often repeat instructions
 If the algorithm doesn’t specify when to stop, the computer
will continue to repeat the instructions forever

chapter 1
 PROPERTIES OF ALGORITHM
6

 Sequence

It is a step-by-step procedure for solving a given problem

Between the two every step should have preceding and

succeeding steps

That is, each step must have a uniquely defined preceding

and succeeding step

chapter 1
 PROPERTIES OF ALGORITHM
7

 Unambiguous
Define rigorously the sequence of operations performed for
transforming the inputs into the outputs
No ambiguous statements are allowed:
Each step of an algorithm must be clearly and precisely
defined, having one and only one interpretation.
At each point in computation, one should be able to tell
exactly what will happen next
Algorithms must specify every step.
It must be composed of concrete steps

chapter 1
 PROPERTIES OF ALGORITHM
8

 Unambiguous
Every detail of each step must be spelled out, including how
to handle errors
This ensures that if the algorithm is performed at different
times or by different systems using the same data, the output
will be the same.

chapter 1
 PROPERTIES OF ALGORITHM
9

 Input specified
The inputs are the data that will be transformed during the
computation to produce the output
An input to an algorithm specifies an instance of the problem
the algorithm solves
Every algorithm should have a specified number (zero or
more) input values (or quantities) which are externally
supplied
 We must specify the type of data and the amount of data
Note that, correct algorithm is not one that works most of the
time but one that works correctly for all legitimate inputs
chapter 1
 PROPERTIES OF ALGORITHM
10

 Output specified
The output is the data resulting from the computation
 It is the intended result
Every algorithm should have one or a sequence of output
values
There must be one or more result values
A possible output for some computations is a statement that
there can be no output, i.e., no solution is possible
The algorithm can be proved to produce the correct output
given a valid input.

chapter 1
 CORRECT ALGORITHM
11

 A correct algorithm solves the given computational

problem
If the algorithm is not doing what it is supposed to do, it is
worthless
 An algorithm is said to be correct if, for every input
instance, it halts with the correct output
 How to prove the correctness of an algorithm ?
Common techniques are by mathematical induction &
contradiction

chapter 1
 INCORRECT ALGORITHM
12

 An incorrect algorithm
might not halt at all on some input instances, or
might halt with a wrong answer.

 In order to show that an algorithm is incorrect, you need just

one instance of its input for which the algorithm fails

chapter 1
APPLICATION OF ALGORITHM
13

➢ Every one of us follows certain procedure to achieve our

immediate or long term goal (which is an algorithm)

➢ Hence, algorithm is essential and it is the integrated part of

our life

➢ What matters for the success of our life is the effectiveness of

the algorithm that we use to solve our problems and the
resource available.

➢ The resource refers to the data that we can operate and the
format that it appears

chapter 1
APPLICATION OF ALGORITHM
14

➢ Lets assume two public buses start travelling from one city to
another city at almost the same time. However, one of the bus
arrive long time after arrival of the other bus. Why?

➢ Try to see this from Algorithmic and data structure

perspective

➢ In order to solve a problem by computers, we should also use

appropriate algorithm and data structure.

chapter 1
APPLICATION OF ALGORITHM
15

➢ Some of the problems that require appropriate algorithm to be

solved by computers given the data structure are:
➢ Internal Sorting
➢ External sorting
➢ Searching
➢ Text Summarization
➢ Document retrieval
➢ Pattern recognition
➢ Image processing
➢ Exploration
➢ Process and processor communication
➢ Network communication

chapter 1
WHY WE NEED TO STUDY ALGORITHM
16

➢ While solving a problem, we need to optimize

➢ Speed (CPU time usage): Measured using Time Complexity
➢ Memory Usage: Measured using Space Complexity

➢ Communication Network usage: measured using Bandwidth

and latency
➢ Getting solution if the problem has one: Measures
completeness
➢ Getting the best solution among all the alternatives:
Measures optimality
➢ Others

chapter 1
 BRAIN STORMING
(Example on algorithm)
17
Example
➢ Find the Greatest Common Divisor (GCD) of two integer
numbers (n, m)
➢ k is said to be the GCD of n and m if k is the largest
possible integer less than or equal to both n and m that
divides both n and m without remainder
➢ i.e k  s such that s = min(n,m), m mod k = n mod k = 0
➢ Properties of GCD(n,m)
➢ GCD(n,m) = GCD(m,n)
➢ GCD(0,n) = GCD(n,0) = n

chapter 1
 BRAIN STORMING
(Example on algorithm)
18

Example
➢ Three different algorithm will be reviewed in this discussion
to computer GCD(n,m) each differ in
➢ Idea of implementation,
➢ Level of sophistication, and
➢ Efficiency

chapter 1
 BRAIN STORMING
(Example on algorithm)
19

Example
➢ The three approaches are:
1. Middle-school procedure
➢ Prime factorization
2. Consecutive integer checking algorithm
3. Euclid’s algorithm (option 1)
4. Euclid’s algorithm (option 2)

chapter 1
 BRAIN STORMING
(Example on algorithm)
20

Middle-school procedure
➢ Is a procedure for finding GCD using our knowledge of
middle-school
➢ To do this,
➢ Find prime factors (divisors) of the given inputs: m and n
➢ Identify the common prime factors of m and n
➢ Compute the product of all the common factors which
will be the GCD(n,m)

chapter 1
 BRAIN STORMING
(Example on algorithm)
21

Example1: Find GCD(60,12) using middle school procedure

➢ Prime factor of 60= 22 x 3 x 5
➢ Prime factor of 12 = 22 x 3
➢ Common factor of 60 and 12 are 22 and 3
➢ Hence, GCD(60,12) = 22 x 3 =12

chapter 1
 BRAIN STORMING
(Example on algorithm)
22

Example 2: Find GCD(150,12) using middle school procedure

➢ Prime factor of 75= 52 x 3 x 2
➢ Prime factor of 12 = 22 x 3
➢ Common factor of 150 and 12 are 2 and 3
➢ Hence, GCD(150,12) = 2 x 3 =6

chapter 1
 BRAIN STORMING
(Example on algorithm)
23

Euclid’s algorithm (option1)

➢ An algorithm outlined by Euclid of Alexandria for solving
GCD problem
➢ It is based on the recursive definition of GCD relation defined
as follows

chapter 1
 BRAIN STORMING
(Example on algorithm)
24

Example 4: find GCD(60,12) using Euclid’s algorithm

(option1)
➢ GCD(60,12) = GCD(48, 12) as 60 -12 = 48
➢ GCD(48,12) = GCD(36, 12) as 48 -12 = 36
➢ GCD(36,12) = GCD(24, 12) as 36 -12 = 24
➢ GCD(24,12) = GCD(12, 12) as 24 -12 = 12
➢ GCD(12,12) = GCD(0, 12) = 12 (definition)

chapter 1
 BRAIN STORMING
(Example on algorithm)
25

Example 5: find GCD(150,12) using Euclid’s algorithm (option1)

➢ GCD(150,12) = GCD(138, 12) as 150 -12 = 138
➢ GCD(138,12) = GCD(126, 12) as 138 -12 = 126
➢ GCD(126,12) = GCD(114, 12) as 126 -12 = 114
➢ GCD(114,12) = GCD(102, 12) as 114 -12 = 102
➢ GCD(102,12) = GCD(90, 12) as 102 -12 = 90
➢ GCD(90,12) = GCD(78, 12) as 90 -12 = 78
➢ GCD(78,12) = GCD(66, 12) as 78 -12 = 66
➢ GCD(66,12) = GCD(54, 12) as 66 -12 = 54
➢ GCD(54,12) = GCD(42, 12) as 54 -12 = 42
➢ GCD(42,12) = GCD(30, 12) as 42 -12 = 30
➢ GCD(30,12) = GCD(18, 12) as 30 - 12 = 18
➢ GCD(18,12) = GCD(6, 12) as 18 - 12 = 6
➢ GCD(6,12) = GCD(6, 6) as 12 - 6 = 6
➢ GCD(6,6) = GCD(6,0) = 6 (definition)
chapter 1
 BRAIN STORMING
(Example on algorithm)

Euclid’s algorithm (option2)

➢ An algorithm outlined by Euclid of Alexandria for solving
GCD problem
➢ It is based on the recursive definition of GCD relation defined
as follows

chapter 1
 BRAIN STORMING
(Example on algorithm)
27

Example 6: find GCD(60,12) using Euclid’s algorithm

(option2)
➢ For example GCD(60,12)
➢ GCD(60,12) = GCD(0, 12) as 60 mod 12 = 0
➢ GCD(0,12) = 12 (definition)

chapter 1
 BRAIN STORMING
(Example on algorithm)
28

Example 7: find GCD(150,12) using Euclid’s algorithm

(option2)
➢ GCD(150,12) = GCD(12, 6) as 150 mod 12 = 6
➢ GCD(12,6) = GCD(0, 6) as 12 mod 6 = 0
➢ GCD(0,6) = 6 (definition)

chapter 1
 29

 #include <iostream>
 using namespace std;
 int gcd(int a, int b)
 {
 if (b == 0)
 return a;
 return gcd(b, a % b); }
 int main()
 { int a , b; cout<<"Enter the values of a and b: "<<endl;
cin>>a>>b; cout<<"GCD of "<< a <<" and "<< b <<" is
"<< gcd(a, b); return 0; }

chapter 1
 BRAIN STORMING
(Example on algorithm)
30

Example:
➢ How do you compute whether a given number is prime or
not?
➢ Is there any other mechanism to do that?

➢ If yes, please list the possible ways?

➢ Are all provide the same result?

➢ If No why? if Yes which one is efficient?

chapter 1
 BRAIN STORMING
(Example on algorithm)
31

Example:
➢ Design an algorithm that identify the common factors in two
prime expressions

chapter 1
 CLASSIFICATION OF ALGORITHM
32

➢ Algorithms can be classified into different classes based on

various factors.
➢ One can classify algorithm by
➢ looking at how the algorithm is implemented or
➢ looking at how the algorithm is designed

chapter 1
 CLASSIFICATION OF ALGORITHM
(by implementation)
33

➢ Algorithm can be classified differently based on the

implementation strategy
➢ The following are the four different ways of classifying
algorithm based on its implementation
1. recursive vs. iterative
2. Serial vs. parallel
3. Deterministic vs. non-deterministic
4. Exact vs. approximate

chapter 1
 CLASSIFICATION OF ALGORITHM
(by implementation)
34

1. Recursive vs. iterative

➢ Recursive implementation invokes itself repeatedly until
a certain condition (base condition) matches
➢ Iterative algorithms use repetitive constructs like loops
for its implementation

chapter 1
 CLASSIFICATION OF ALGORITHM
(by implementation)
35

2. Serial vs. parallel

➢ Serial algorithm is an algorithm that assume a single
processor is available and execute its instruction one at
a time in that processor
➢ Parallel algorithms take advantage of computer
architectures where several processes can work on a
problem concurrently being in the same machine or
machines connected to each other via networks
➢ Various names are common in parallel algorithm such as
cluster computing, massively parallel computers, distributed
systems, cloud computing, grid computing
chapter 1
 CLASSIFICATION OF ALGORITHM
(by implementation)
36

3.Deterministic vs. Non-Deterministic

➢ deterministic algorithms solve the problem with exact
decision at every step of the algorithm whereas
nondeterministic algorithm solve problems via guessing
(probabilistically)
➢ The result from both may be correct or not
➢ What is the sum of 1/x for all integer x > 0 (can be
implemented deterministically by stopping at some x value
➢ How many students will attend the next class given the
previous attendance statistics
chapter 1
 CLASSIFICATION OF ALGORITHM
(by implementation)
37

4. Exact vs. approximate

➢ Exact algorithm reach into exact solution of the problem
where as approximate type of algorithm generate an
approximation to the problem solution
5. Others

chapter 1
 CLASSIFICATION OF ALGORITHM
(by design paradigm)
38

➢ There are also three ways of classifying algorithm by design

paradigm identified
➢ These are:
1. Divide and conquer method
2. Dynamic programming method
3. Greedy method

chapter 1
 CLASSIFICATION OF ALGORITHM
(by design paradigm)
39

1.Divide and conquer

➢ A divide and conquer algorithm repeatedly reduces an
instance of a problem to one or more smaller instances of
the same problem (usually recursively), until the instances
are small enough to solve easily.

➢ Divide and conquer has a combine phase to combine

solutions of the smaller size problem to get the solution of
the larger problem

chapter 1
 CLASSIFICATION OF ALGORITHM
(by design paradigm)
40

1.Divide and conquer

➢ The divide and conquer approach of algorithm design break
the problem into several sub-problems that are similar to the
original problem which are smaller in size, solve the sub-
problems recursively, and then combine these solutions to
create a solution to the original problem.

chapter 1
 CLASSIFICATION OF ALGORITHM
(by design paradigm)
41

2. dynamic programming
➢ “Programming” in this context refers to a tabular method of
solving problem, not written code in computer programming
language
➢ In dymamic programming, every subproblem share the same
subsubproblems and each of the subsubproblems will be
solved once and answer will be stored in a table so that
every subproblems will not solve the subsubproblems again
and again

chapter 1
 CLASSIFICATION OF ALGORITHM
(by design paradigm)
42

2. dynamic programming
➢ For example you may wish to move from start to goal as shown
bellow. You may have three options at the start with different cost
which you don’t know the best route either through A, B or C
➢ Moreover, you may change the start location to be A, B and C
and find the best route and add with the cost from start to A, B,
and C respectively to answer the problem

chapter 1
 CLASSIFICATION OF ALGORITHM
(by design paradigm)
43

3. The greedy method

➢ is similar to a dynamic programming algorithm, but the
solutions to the sub-problems do not have to be known at
each stage; instead a "greedy" choice can be made of what
looks best for the moment.
➢ What looks best for the moment is determined by a
heuristics that helps the greedy to chose one of the
alternatives

chapter 1
 CLASSIFICATION OF ALGORITHM
(by design paradigm)
44

3. The greedy method

➢ For example, in the previous problem, greedy will not store
the suboptimal solution of moving from start to A, B and C
rather choose one of this as a path to the solution and
continue to the rest process

chapter 1
 IMPORTANT ASSUMPTIONS
(for the course)
45

3. The greedy method

➢ In order to have clear image for the lesson of this course, we
should assume the model of the machine
➢ In our machine model we assume instructions are executed
one after another on a single machine with single CPU
➢ Hence, there is no concurrent operations performed in a
parallel environment

chapter 1
 ELEMENTARY SORTING ALGORITHM
46

 Statement of the sorting problem

 Input: a sequence of n number a1, a2, …,an
 Output: a permutation (reordering) a1', a2', …,an' such
that a1' a2'  …  an '.

chapter 1
 ELEMENTARY SORTING ALGORITHM
47

 Sorting is generally understood to be the process of

rearranging a given set of objects in a specific order.
 Simple sorting algorithm includes
1. Selection sort

2. Bubble sort

3. Insertion sort

 All this sorting algorithms work on array data structure on

objects which are of ordinal type

chapter 1
 ELEMENTARY SORTING ALGORITHM
48

1. Selection sort
 Given a list of objects from index [i, MAX], it searches for
the minIndex which holds the minimum element of all and
swap this element with the element at index i.
 Do this fom all possible value of i from 0 to (MAX-1)
where MAX is the size of the list

chapter 1
 ELEMENTARY SORTING ALGORITHM
49

SelectionSort (A, n)
for i  0 to n-1
minIndex  i
//find the actual minIndex from index [I, n]
for j i+1 to n
if(A[j] < A[minIndex])
minIndex  j
temp A[minIndex]

A[minIndex] A[i] Aswap(A, I, minIndex)

A[i] temp

chapter 1
 ELEMENTARY SORTING ALGORITHM
50

2. insertion sort
 Given a sub list of object in the index range [0,i] where all the
element in the index range [0 , i-1] are sorted; find the place
where the element at index i will be inserted by shifting all the
elements in the range [0, i-1] one step to the right until we found
the index for the element at index i.
 This produce the list of objects in the range [0,i] to be sorted
 Process this for all i from 1 to n

chapter 1
 ELEMENTARY SORTING ALGORITHM
51

2. insertion sort

10 24 45 19
Insert 19 (Given i=3)
10 24 24 45 To Insert 19 we found index 1 by
10 19 24 45 replacing 24

chapter 1
 ELEMENTARY SORTING ALGORITHM
52

2. Insertion Sort Algorithm

InsertionSort (A, n)
for j  1 to n-1
key A[j]
//Insert key into the list A[0…j-1] so that A[0..j] becomes sorted
i  j-1
while (i >= 0 and A[i] > key)// i is valid index
and A[i] > the key
A[i+1]  A[i]
i  i-1
A[i+1]  key
chapter 1
 ELEMENTARY SORTING ALGORITHM
53

3. Bubble sort
 Given a list of unsorted object from index 0 to j, compare
each of the adjacent objects and do swapping when they are
no in order from left to right
 This permit the element at index j be the maximum of the
list
 Continue by reducing the last index (j) by one until j
becomes 0.
 Start j at n-1

chapter 1
 ELEMENTARY SORTING ALGORITHM
54

3. Bubble sort algorithm

BubbleSort (A, n)
for j  0 to n-2
for i 1 to n -1 -j
if( A[i-1] > A[i])
//Swap A[i] and A[i-1]
swap(A, i-1, i);

chapter 1