Course: Analysis and Design of Algoriths
Semester :IV
Outline of chapter 1
1.1 What Is an Algorithm?
1.2 Fundamentals of Algorithmic Problem
Solving
1.1 Introduction
What is an Algorithm?
Characteristics of an algorithm.
1.1 What is an algorithm?
Recipe, process, method, technique, procedure,
routine,… with the following requirements:
1. Finiteness
terminates after a finite number of steps
2. Definiteness
rigorously and unambiguously specified
3. Clearly specified input
valid inputs are clearly specified
4. Clearly specified/expected output
can be proved to produce the correct output given a
valid input
5. Effectiveness
steps are sufficiently simple and basic
1.1 What is an algorithm?
An algorithm is a sequence of unambiguous
instructions for solving a problem, i.e., for
obtaining a required output for any
legitimate input in a finite amount of time.
problem
algorithm
input “computer” output
1.1 What is Algorithm?
Algorithm
is a tool for solving a well - specified
computational problem.
Any special method of solving a certain kind of
problem
Good algorithm is
like a knife – does
exactly what it is
supposed to with
minimum efforts
Using wrong
algorithm is like
trying to cut an apple
with a screw driver
U may obtain result,
but u would have
spent more effort.
1.1 Algorithms are all around us in
everyday life.
In the recipe of a cook book.
In assembling a toy.
In setting the table.
In preparing a cup of tea.
In calling your friend on the phone.
…. There are countless examples!
1.1 Example
Finding GCD of two numbers:
1. Euclid’s Algorithm
2. Consecutive Integer Checking
3. High School algorithm
Euclid’s Algorithm
Problem: Find gcd(m,n), the greatest common divisor of
two nonnegative, not both zero integers m and n
Examples: gcd(60,24) = 12, gcd(60,0) = 60, gcd(0,0)
=?
Euclid’s algorithm is based on repeated application of
equality
gcd(m,n) = gcd(n, m mod n)
until the second number becomes 0, which makes the
problem
trivial.
Two descriptions of Euclid’s algorithm
Step 1 If n = 0, return m and stop; otherwise go to
Step 2
Step 2 Divide m by n and assign the value of the
remainder to r
Step 3 Assign the value of n to m and the value of r to
n. Go to
Step 1.
while n ≠ 0 do
r ← m mod n
m← n
n←r
return m
Other methods for computing gcd(m,n)
Consecutive integer checking algorithm
Step 1 Assign the value of min{m,n} to t
Step 2 Divide m by t. If the remainder is 0, go
to Step 3;
otherwise, go to Step 4
Step 3 Divide n by t. If the remainder is 0,
return t and stop;
otherwise, go to Step 4
Step
Is this 4 Decrease
slower t by
than Euclid’s 1 and How
algorithm? go to Step 2
much slower?
O(n), if n <= m , vs O(log n)
1-12
Other methods for gcd(m,n) [cont.]
Middle-school procedure
Step 1 Find the prime factorization of m
Step 2 Find the prime factorization of n
Step 3 Find all the common prime factors
Step 4 Compute the product of all the common
prime factors
and return it as gcd(m,n)
Is this an algorithm?
Time complexity: O(sqrt(n))
How efficient is it?
1.2 Fundamentals of algorithmic problem
solving
What does it mean to understand the problem?
What are the problem objects?
What are the operations applied to the objects?
Deciding on: computational means
How the objects would be represented?
Static or dynamic
How the operations would be implemented?
Sequential or parallel
Deciding on: Exact Vs Approximate solving
Exact- factorial of a number
Approximate- solving nonlinear equations, extracting square roots, integrals
…
Deciding on: algorithm design technique
Choose the best method for the problem
15
Design an algorithm
• Build a computational model of
the solving process
Prove correctness
• Correct output for every
legitimate input in finite time
• Based on correct math formula
• By induction
16
Analyze the algorithm
Efficiency: time and space
Simplicity
Generality: range of inputs, special
cases
Optimality:
no other algorithm can do
better
Coding
How the objects and operations in the
17
Important problem
types
Sorting
Searching
String processing
Graph problems
Combinatorial problems
Geometric problems
Numerical problems
18
Two main issues related to algorithms
How to design algorithms
How to analyze algorithm efficiency
Why study algorithms?
Theoretical importance
the core of computer science
Practical importance
A practitioner’s toolkit of known algorithms
Framework for designing and analyzing
algorithms for new problems
Donald Knuth:
“ A person does not
understand something until
after teaching it to someone
else.
Actually: A person does not
understand something until
after he teaches it to a ……
COMPUTER!”
Algorithm design techniques/strategies
Greedy method Brute force
Decrease and conquer
Divide and conquer
Transform and conquer
Dynamic Programming Space and time tradeoffs
Backtracking
Branch and Bound
Analysis of algorithms
How good is the algorithm?
time efficiency
space efficiency
correctness ignored in this course
