Fundamental of Algorithms

Fundamental of Algorithms

1. Fundamentals of
Algorithm
Prof. Shashikant V. Athawale
Assistant Professor | Computer Engineering
Department | AISSMS College of Engineering,
Kennedy Road, Pune , MH, India -411001

2. Content
What are algorithms
Algorithms as technology
Evolution of algorithm
Design of algorithm
Need of correctness of algorithm
Confirming correctness of algorithm
Iterative algorithm design issues
Algorithmic Strategies

3. What are algorithms ?
Step by step method for problem solving
A process or set of rules to be followed in calculations
or other problem-solving operations, especially by a
computer.

4. Evolution of Algorithm
Origin of algorithm is Persian
attributed to Persian astronomer and
mathematician, Abu Abdullah Muhammad ibn Musa
Al-Khwarizmi
21
st
century English philosopher used term
“Algorismus”

5. Design of Algorithm
Written as pseudo code or flowchart
What are inputs of problem?
What will be the output of problem?
In what order do instructions need to be carried out
?
What decisions need to be made in problem?
Are any areas of the problem repeated?

6. Need of correctness of algorithm
Algorithmshould be correct with respect to a
specification.
Algorithm should yield a required result for every
legitimate input
Should run for finite amount of time
Functionalcorrectnessrefers to the input-output
behavior of thealgorithm

7. Confirming correctness of algorithm
An algorithm Is called totally correct for the given
speciation if and only if for any correct input data it:
1.stops and
2.returns correct output
correct input data is the data which satisfies the initial
condition of the speciation
correct output data is the data which satisfies the final
condition of the speciation

8. Iterative algorithm design issues
Use of loops
1. To establish initial condition
set loop variables to value which are appropriate for
solving smallest instance of problem
2.To find iterative condition
loop variables are changed in every iteration
3. Loop termination
The termination condition occurs when it is known in
prior the number of times is to be iterated

9. Iterative algorithm design issues
Efficiency of algorithm
1. Removing redundant computations outside loop
-When it is embedded in loop
-executed many times unnecessarily
2. Referencing of array element
-Arrays are processed by iterative constructs
3. Inefficiency due to late termination
 -When more tests are carried out than required
4. Early detection of designed output conditions
 -establishes the desired output condition before general
condition for termination

10. Iterative algorithm design issues
Estimating and specifying Execution time
1. Performance is measured by computational model
2. Reflects the specified input conditions
3. independent of specific programming languages
4. Performance can be measured in terms of size of problem
being solved

11. Iterative algorithm design issues
Order Notation
1.Big-O Notation
2. Little-O Notation
3. Omega Notation
4. Theta Notation

12. Algorithmic Strategies
Divide and conquer
Backtracking
Branch and Bound
Dynamic programming
Greedy technique
Backtracking and Branch and bound
Brute force algorithms
Heuristic algorithms

13. Thank you