Algorithmic Problem Solving Algorithms: Introduction

Solving a Problem With a

Computer
Algorithmic Problem Solving Algorithms: Introduction

Solving a Problem With a

Computer
What is
Problem?

A problem is a question to which we seek an answer.

Examples
▪ Sorting - Sort a list S of n numbers in non-decreasing order

▪ Searching - Determine whether the number x is in a list S of n numbers.

▪ Shortest Path – Find shortest path between two nodes in a graph

▪ Fibonacci Number - What is the 25 Fibonacci number?

and many more
Algorithmic Problem Solving Algorithms: Introduction

Solving a Problem With a

Computer
Many of us start writing a computer program
directly
Program

Programming
Problem Language
Stateme Statements
nt
C/C++
you can’t start writing a computer Becaus Statements
program directly, e
In case of inefficient, incorrect computer
program
Creat Destro Creat Destroy
e y e etc.
You can’t construct anything on trial and
error basis.
Algorithmic Problem Solving Algorithms: Introduction

Solving a Problem With a

Computer You have to go through design and
analysis phase
Algorithm Design and Analysis
Program
Analysi
s1 Analysi
s2 Programming
Correctne
Problem Algorithm Analysin Language
ss of
Stateme Design g Statements
Algorithm
nt Algorith
m C/C++
Statements

If you want to solve the problem, the next step is

DESIGNING.
Algorithmic Problem Solving Algorithms: Introduction

Why Algorithm
Design ?
When we faced with a problem, the first thing we
should do is
▪ Draw a sketch of how we can solve the problem

▪ The next step towards solving the problem is developing the algorithm.

Thinking algorithmically is a necessary step towards solving a problem by computer

As there can be more than one algorithm to solve the same

problem.
and
Algorithms for the same problem can be based on very different
ideas and can solve the problem with dramatically different
speeds.
So,
We will select the best among them.
1
Algorithmic Problem Solving Algorithms: Introduction

Why Algorithm
Design ?
There can be more than one algorithm to solve the same
problem.
EXAMPLE

Problem: Sorting

Algorithms

▪ Insertion Sort
▪ Bubble Sort Brute force
▪ Selection
Sort Divide & Conquer
▪ Merge Sort
▪ Quick Sort
etc.
And we are concerned with a good
algorithm.
1
Algorithmic Problem Solving Algorithms: Introduction

Why Algorithm
Design ?
Good algorithm designers understand several fundamental algorithm
design techniques, including

Techniques (Problem Solving Strategies)

▪ Brute Force
ni q ues
▪ Divide and Conquer
et ech
o r t hes
f
▪ Dynamic Programming
a bl e to
a il
e av
▪ Greedy Algorithms
hms ar
o ri t
▪ Back Tracking i e nt a lg
c
Effi
▪ Branch and Bounds

▪ The knowledge of these problem solving strategies prevent us from investigating newer
strategy for our problem.

Problem can be designed by any one of the these techniques.

1
Algorithmic Problem Solving Algorithms: Introduction

Solving a Problem With a

Computer
Algorithm Design and Analysis
Program
Analysi
s1 Analysi
s2 Programming
Correctne
Problem Algorithm Analysin Language
ss of
Stateme Design g Statements
Algorithm
nt Algorith
(Development of m C/C++
Model) Statements
BF, D&C, DP, Greedy,
Back Tracking,
Branch and Bounds
etc.
We can find the resemblance of our problem with the problems that have been solved
using these techniques, so we can apply the same problem solving strategy to solve our
problem.
Algorithmic Problem Solving Algorithms: Introduction

Solving a Problem With a

Computer p is
t st e s
n ex nes
Algorithm Design and Analysis e t
Th rrec
Co Program
Analysi
s1 Analysi
s2 Programming
Correctne
Problem Algorithm Analysin Language
ss of
Stateme Design g Statements
Algorithm
nt Algorith
(Development of m C/C++
Model) Statements
BF, D&C, DP, Greedy,
Back Tracking,
Branch and Bounds
etc.
Algorithmic Problem Solving Algorithms: Introduction

Why Correctness of
Algorithm ?

Once the algorithm has been specified, you have to prove its correctness.

Algorithm yields a correct result for every legitimate input .

and

A correct Algorithm must terminate in a finite amount of time.

An incorrect algorithm

▪ might halt with an incorrect answer, or

▪ might not halt at all on some input instances

Algorithmic Problem Solving Algorithms: Introduction

Why Correctness of
Algorithm ?
EXAMPLE
Greatest Common Divisor : (Consecutive Integer Checking Algorithm)
GCD ( m , n )
t = min(m, n)
while (t<=0) {
if (m % t = 0){
This algorithm does not work correctly when one
if (n % t = 0) of its input numbers is zero.
return t;
}
t = t – 1;
}
Observation:
An incorrect algorithm may work correctly for majority of inputs but crash on some
boundary value.
Algorithmic Problem Solving Algorithms: Introduction

Greatest Common Divisor (GCD):

Example: Find the greatest common divisor of 60, 24 The largest integer that divides both
numbers evenly

As we want Greatest Divisor

Solution: Start from 24
Obviously, such a common divisor can not be greater than the smaller of these numbers

60 mod 24 0 60 mod 19 0 60 mod 14 0

60 mod 23 0 60 mod 18 0 60 mod 13 0
60 mod 22 0 60 mod 17 0 60 mod 12 0
60 mod 21 0 60 mod 16 0
60 mod 20 0 60 mod 15 0 12 is the divisor of 60

20 is the divisor of 60 15 is the divisor of 60 Now check for 24

Now check for 24 Now check for 24 24 mod 12 0

24 mod 20 0 24 mod 15 0 12 is GCD

Algorithmic Problem Solving Algorithms: Introduction

Incorrect Algorithm
if we want to find GCD of (6,0),
Example: Find the greatest common divisor of 60, 24
It fails to produce correct result.
GCD(6,0):
6 mod 0 (Crash)
Solution:
Obviously, such a common divisor can not be greater than the smaller of these numbers

60 mod 24 0 60 mod 19 0 60 mod 14 0

60 mod 23 0 60 mod 18 0 60 mod 13 0
60 mod 22 0 60 mod 17 0 60 mod 12 0
60 mod 21 0 60 mod 16 0
60 mod 20 0 60 mod 15 0 12 is the divisor of 60

20 is the divisor of 60 15 is the divisor of 60 Now check for 24

Now check for 24 Now check for 24 24 mod 12 0

24 mod 20 0 24 mod 15 0 12 is GCD

Algorithmic Problem Solving Algorithms: Introduction

Why Correctness of
Algorithm ?
Why it is necessary ?

Imagine what will happen if the computer inside missile has an program implemented by
using incorrect algorithm due to which missile strike your own city rather than the enemy
site.

In applications like
▪ atomic power plants
▪ Industrial safety systems

program correctness has to be guaranteed.

1
Algorithmic Problem Solving Algorithms: Introduction

▪ One cannot demonstrate the correctness

by simply taking each of the possible input data, feeding it to the program, and
showing that the result is correct.

▪ Tracing the algorithm’s correctness for a few specific inputs is not sufficient
you have to prove it for every input instance.

One of the most difficult requirement to satisfy is to show that a program works correctly,
outputting results in complete range of data.

How can computer programmer be sure that program is correct, without exhaustive
testing.

Rigorous Proof: Mathematical Induction

Algorithmic Problem Solving Algorithms: Introduction

Solving a Problem With a C a se

e ct
n r
Computer I ofcor gn
In esi
D
Algorithm Design and Analysis
Try Another Design Program
Model
Analysi
s1 Analysi
s2 Programming
Correctne
Problem Algorithm Analysin Language
ss of
Stateme Design g Statements
Algorithm
nt Algorith
(Development of m C/C++
Model) Mathemati Statements
BF, D&C, DP, Greedy, cal
Back Tracking, Induction
Branch and Bounds
etc.
Algorithmic Problem Solving Algorithms: Introduction

Solving a Problem With a sing

n aly
Computer is
A
s tep
Algorithm Design and Analysis e xt
h e n ithm
Try Another Design T o r
g Program
Model
Analysi
Al
s1 Analysi
s2 Programming
Correctne
Problem Algorithm Analysin Language
ss of
Stateme Design g Statements
Algorithm
nt Algorith
(Development of m C/C++
Model) Mathemati Statements
BF, D&C, DP, Greedy, cal
Back Tracking, Induction
Branch and Bounds
etc.
Algorithmic Problem Solving Algorithms: Introduction

Why Analysing
Algorithms ?
Suppose a program runs for 4 hours, has not generated any result,
We do not know, either

▪ It is inefficient and simply consuming time or

▪ It is incorrect and is looping indefinitely,

We simply abort the program. Those 4 hours of computer time is lost.

To avoid this situation, we have to analyse the algorithm before constructing the program.

We have to find time complexity of the algorithm.

Time Complexity - an analysis of the time required to solve a problem

1
Algorithmic Problem Solving Algorithms: Introduction

Why Analysing
Algorithms ?

Time Complexity - an analysis of the time required to solve a problem

After finding the time complexity, you have to see it

Is it to give solution to the problem in reasonable time or not ?

▪ If solution to the problem obtained in reasonable time and there are more than one
solution exist then decide which one is the best.

▪ If not, then change your strategy (try for another solution)

1
 Algorithmic Problem Solving Algorithms: Introduction

Case 1:
If solution to the problem obtained in reasonable time and there are more than one solution exist

EXAMPLE:
Describe the algorithm for finding the maximum value in a finite sequence of integer.

Algorithm 1 Algorithm 2
Algorithm maximum (a1, a2, a3, . . . , an) Algorithm maximum (A)
max = a1 for j = 2 to n // Using Insertion Sort
for i = 2 to n key = A[ j ]
if max < i then i=j–1
max = ai while i > 0 and A[ i ] > key
return max A[ i+1 ] = A[ i ]
i=i–1
A[ i+1 ] = key
Time Complexity: n comparisons
return A[size-1]

Conclusion: Algorithm 1 is Time Complexity: n2 comparisons

better.
1
 Algorithmic Problem Solving Algorithms: Introduction

Case 2:
If solution is not obtained in reasonable time, change your strategy (try for another solution)

EXAMPLE: ( Divide and Conquer )

Fibonacii Number

Algorithm: Time Complexity > 2n/2

int fib ( int n ){
if (n ≤ 1)
return n;
else
return fib(n-1) + fib(n-2);
}
Takes
40,000 years to compute 200th term.

(which is intolerable compared with a human life span)

1
 Algorithmic Problem Solving Algorithms: Introduction

Case 2:
If solution is not obtained in reasonable time, change your strategy (try for another solution)

EXAMPLE: ( Dynamic Programming )

Fibonacii Number
Algorithm: Time Complexity: n+1
int fib2 ( int n ) {
int i; int f[0..n];
f[0] = 0; Takes
if (n > 0) 201 nanoseconds to compute 200th term.

f[1]=1; (which is quite reasonable – highly efficient)

for ( i=2; i<=n; i++)
f[i] = f[i-1] + f[i-2];
}
return f[n];

}
1
Algorithmic Problem Solving Algorithms: Introduction

Solving a Problem With a

Computer
Algorithm Design and Analysis
Try Another Design Program
Model
Analysi
s1 Analysi
s2 Programming
Correctne
Problem Algorithm Analysin Language
ss of
Stateme Design g Statements
Algorithm
nt Algorith
(Development of m C/C++
Model) Mathemati Time Statements
BF, D&C, DP, Greedy, cal Complexity
Back Tracking, Induction
Branch and Bounds
etc.
Algorithmic Problem Solving Algorithms: Introduction

Solving a Problem With a a se ient

C c
Computer In onfeffi ign
I s
De
Algorithm Design and Analysis
Try Another Design Program
Model
Analysi
s1 Analysi Efficie
s2 nt
Programming
Correctne And
Problem Algorithm Analysin Correc Language
ss of
Stateme Design g t Statements
Algorithm
nt Algorith
(Development of m C/C++
Model) Mathemati Time Statements
BF, D&C, DP, Greedy, cal Complexity
Back Tracking, Induction
Branch and Bounds
etc. Try Another Design Now you can start
Model Implementation

Choose data structure appropriate for the

algorithm Data Structures
Sometimes linked list version run longer than array in implementation
Algorithmic Problem Solving Algorithms: Introduction

Solving a Problem With a a se ient

C c
Computer In onfeffi ign
I s
De
Algorithm Design and Analysis
Try Another Design Program
Model
Analysi
s1 Analysi Efficie
s2 nt
Programming
Correctne And
Problem Algorithm Analysin Correc Language
ss of
Stateme Design g t Statements
Algorithm
nt Algorith
(Development of m C/C++
Model) Mathemati Time Statements
BF, D&C, DP, Greedy, cal Complexity
Back Tracking, Induction
Branch and Bounds
etc. Try Another Design Program
Model

Algorithm Data Structures

Algorithmic Problem Solving Algorithms: Introduction

Solving a Problem With a

Computer
Try Another Design
Model
Program

Programming
Correctne
Problem Algorithm Analysin Language
ss of
Stateme Design g Statements
Algorithm
nt Algorith
m C/C++
Statements

Try Another Design

Model
Algorithmic Problem Solving Algorithms: Introduction

Solving a Problem With a

Computer

Program

Exact
Vs Programming
Algorith Correctne
Problem Analysin Language
Approxim m ss of
Stateme g Statements
ate Design Algorithm
nt Algorith
Design
Technique m C/C++
Statements

Thank You