DESIGN AND ANALYSIS OF

ALGORITHMS CS19341

“A tour for designing new algorithms and analyze

their efficiency”

CS19341-DAA
COURSE OBJECTIVES:
• Learn and understand the algorithm analysis
techniques and complexity notations
• Become familiar with the different algorithm design
techniques for effective problem solving in
computing.
• Learn to apply the design techniques in solving
various kinds of problems in an efficient way.
• Understand the limitations of Algorithm power.
• Solve variety of problems using different design
techniques

CS19341-DAA
 SYLLABI
UNIT-I INTRODUCTION AND ANALYSIS OF ALGORITHMS
Introduction –Algorithm Specification –Important Problem types- Performance Analysis:
Space Complexity – Time Complexity - Asymptotic Notations - Using Limits for
Comparing Orders of Growth – Basic Efficiency Classes- Solving Recurrence Relations:
Substitution methods and Master Theorem Method
UNIT-II BRUTE FORCE AND DIVIDE-AND-CONQUER
Brute Force: Exhaustive Search - Travelling Salesman Problem - Knapsack Problem -
Assignment problem - Divide and Conquer Method: Analysis of Binary Search, Merge
sort and Quick sort Algorithms, Integer Multiplication-Finding Minimum and Maximum.
UNIT-III GREEDY TECHNIQUE AND DYNAMIC PROGRAMMING
Greedy Method – Minimum Spanning Trees: Kruskals Algorithm– Fractional Knapsack -
Huffman Codes - Dynamic Programming: General Method - String Editing - 0/1
Knapsack - Travelling Salesman Problem.
UNIT-IV BACKTRACKING AND BRANCH & BOUND
Backtracking: General Method - 8 Queen's Problem - Sum of Subsets Problem - Graph
Colouring - Hamiltonian Circuit Problem - Branch and Bound: LC branch and bound -
0/1 Knapsack - Travelling Salesman Problem.
UNIT-V STRING MATCHING AND NP COMPLETE & NP HARD
String Matching: Naive String Matching - Rabin Karp - Knuth Morris Pratt - NP Complete
and NP Hard Problems: Basic Concepts - Non Deterministic Algorithms - Class of NP
Complete and NP Hard – Approximation Algorithms :Travelling Salesman problem.
CS19341-DAA
TEXT BOOKS
 AnanyLevitin, “Introduction to the Design and
Analysis of Algorithms”, Third Edition,
Pearson Education, 2012.

 Ellis Horowitz, Shani,

SanguthevarRajasekaran, "Computer
Algorithms" Universities Press, Second
Edition 2008.

CS19341-DAA
Why do you need to study
algorithms?
•computer programs would not
exist without algorithms.
•studying algorithms is their special kinds of solutions to
usefulness in developing problems.
analytical Skills.
•"algorithm” can be used by a
computer for the solution of a
precisely defined
problem.
procedures for getting
•The study of algorithms is the answers.
cornerstone of computer
science.
•It can be recognized as the specific algorithm design
core of computer science. techniques can be
interpreted as problem
solving strategies.

CS19341-DAA
Why study algorithms?

Algorithms + Data Structures = Programs

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

CS19341-DAA
Study tour of Unit 1
Introduce algorithm and  What is an Algorithm?
algorithm analysis
 Designing algorithm
Discuss algorithm analysis  Analysing algorithm
methodologies

Introduce pseudo code of

algorithms

Asymptotic notion of algorithm

efficiency

CS19341-DAA
UNIT-I

INTRODUCTION AND ANALYSIS

OF ALGORITHMS

CS19341-DAA
INTRODUCTION
ALGORITHM SPECIFICATION
IMPORTANT PROBLEM TYPES
PERFORMANCE ANALYSIS:
SPACE COMPLEXITY - TIME COMPLEXITY
ASYMPTOTIC NOTATIONS
USING LIMITS FOR COMPARING ORDERS OF
GROWTH
BASIC EFFICIENCY CLASSES
SOLVING RECURRENCE RELATIONS:
SUBSTITUTION METHODS AND
MASTER THEOREM METHOD
UNIT-I Topics to learn,
CS19341-DAA
 What is an algorithm?
For example,
Task:
to make a cup of tea.
Algorithm: •Algorithm is a set
add water and milk to
the kettle, of steps to
 boil it , complete a task.
 add tea leaves,
 Add sugar,
and then serve it in cup.

CS19341-DAA
 A sequence of
operations -----for
WHAT IS AN ALGORITHM?
solving a specific
type of problem
An algorithm is a finite set
Definition: of instructions that
accomplishes particular task
An algorithm is a
sequence of
unambiguous instructions
for solving a
computational problem,
i.e., for obtaining a
required output for any
legitimate input in a finite
amount of time.

CS19341-DAA
The notion of the algorithm
problem
algorithm
input
output

CS19341-DAA
 The nonambiguity requirement for each
step of an algorithm cannot be
compromised.
The range of inputs for which an
algorithm works has to be specified
carefully.
The same algorithm can be represented
in several different ways.
There may exist several algorithms for
solving the same problem.
Algorithms for the same problem can be
based on very different ideas and can
solve the problem with dramatically
different speeds.
CS19341-DAA
All algorithms must satisfy the
following criteria:
Input

Effectiveness Algorithm’s Finiteness

Features

Output Definiteness

CS19341-DAA
 Ouput

Criteria 3
2 Input and
Criteria 1 and
Definiteness

Algorithm’s
Criteria

eness
Effectiv
Criteria 4 5
Finiteness Criteria
CS19341-DAA
Algorithm’s Criteria

Input:
Output: Finiteness: Effectivenes
Zero or Definiteness s:Every
more At least Each The algorithm instruction
quantities one instruction is terminates must be very
clear and after a finite basics also it
are quantity is number of must be
unambiguous.
externally produced. steps feasible
supplied

CS19341-DAA
1.Input ::: Zero or more quantities are externally
supplied.
2. Output:::: At least one quantity is produced.
3.Definiteness:::::::Each instruction is clear and
unambiguous.
4.Finiteness:::::The algorithm terminates after a
finite number of steps.
5.Effectivenessv::::::::Every instruction must be
very basic so that it can be carried out, in
principle, by a person using only pencil and
paper. It also must be feasible

CS19341-DAA
Criteria 3
DEFINITENESS: Each operation must be
definite
Eg:
Directions such as
“add 6 or 7 to x”
or "compute 5/0“
are not permitted because it is not clear
which of the two possibilities should be
done ?
or
what the result is?

CS19341-DAA
Criteria 4
Finiteness- Algorithms that terminate after a
finite number of operations .
 The time for termination should be
reasonably short.
 For example,
 an algorithm could be devised that decides
whether any given position in the game of
chess is a winning position. The algorithm
works by examining all Possible moves and
countermoves that could be made from the
starting position.

CS19341-DAA
Criterion 5
Effectiveness - requires that each operation be
effective.
Example
 Performing arithmetic on integers is an
example of an effective operation, but
arithmetic with real numbers is not an
effective
 Since some values may be expressible only
by infinitely long decimal expansion. Adding
two such numbers would violate the
effectiveness property.
CS19341-DAA
 Algorithms that are definite and
effective are also called computational
Procedures
 One important example of
computational procedure is the
operating system of a digital computer.
 This procedure is designed to control
the execution of jobs, in such a way that
when no jobs are available, it does not
terminate but continues in a waiting
state until a new job is entered.
CS19341-DAA
 A program is the expression of an algorithm
in a programming language.
 Sometimes words such as procedure,
function,
and subroutine are used synonymously for
program.

CS19341-DAA
The study of algorithms includes,

1. How to devise algorithms study various

design techniques that they have yielded good
algorithms. By mastering these design strategies, it
will become easier to devise new and useful
algorithms.
2. How to validate algorithm Once an algorithm
is devised ,it is necessary to show that it computes
the correct answer for all possible legal inputs. We
refer to this process as algorithm validation.The
purpose of the validation is to assure us that this
algorithm will work correctly independently of the
issues concerning the programming language

CS19341-DAA
3. How to analyze algorithms This field of study is called
analysis of algorithms. As an algorithm is executed, it uses the
computer's central Processing unit (CPU)to perform operations
and its memory (both immediate and auxiliary) to hold the
program and data. Analysis of algorithms or performance
analysis refers to the task of determining how much computing
time and storage an algorithm requires.
4. How to test a program Testing a program consists of
two phases:
Debugging and profiling (or performance measurement).
Debugging is the process of executing programs on sample data
sets to determine whether faulty results occur and, if so, to
correct them. A proof of correctness is much more valuable
than a thousand tests(if that proof is correct),since it
guarantees that the program will work correctly for all possible
inputs.
Profiling or performance measurement is the process of
executing a correct program on datasets and measuring the
time and space it takes to compute the result.
CS19341-DAA
EXAMPLE
Greatest common divisor of two nonnegative,
not-both-zero integers m and n,
denoted gcd(m, n)

CS19341-DAA
gcd(m, n), is defined as the largest integer that divides
both m and n evenly, i.e., with a remainder of zero.

We consider three methods for computing the greatest

common divisor of two integers. they are

a. Euclid’s algorithm
b. Consecutive integer checking algorithm
c. Middle-school procedure for computing gcd(m,
n)

Note :
Algorithms for the same problem can be based on very different ideas
and can solve the problem with dramatically different speeds.
CS19341-DAA
1. EUCLID’S ALGORITHM
The algorithm was proposed by Euclid about 2250 years ago.
Euclid’s algorithm is an example of a “Decrease and Conquer”
and it is described as,
gcd(m, n) = gcd(n, m mod n),
where m mod n is the remainder of the division of m by n, until
m mod n is equal to 0. Since gcd(m, 0) = m.
For example,
gcd(60, 24) can be computed as follows:
gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12.

In Euclid’s, the remainder m mod n is computed by repeated

subtraction of n from m .
it improves time efficiency.
Euclid’s algorithm eventually comes to a stop. How ?
the value of the second integer eventually becomes 0, and
the algorithm stops.

CS19341-DAA
Example:
m=12 and n=30 m=123 and n=36 m=1220 and n=516

CS19341-DAA
EUCLID’S ALGORITHM FOR COMPUTING
GCD(M, N)
Step 1 If n = 0, return the value of m as the answer and stop;
otherwise, proceed 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.
ALGORITHM Euclid(m, n)
//Computes gcd(m, n) by Euclid’s algorithm
//Input: Two nonnegative, not-both-zero integers m and n
//Output: Greatest common divisor of m and n
while n = 0 do
r ←m mod n
m←n
n←r
return m

CS19341-DAA
2. CONSECUTIVE INTEGER
CHECKING ALGORITHM FOR
COMPUTING GCD(M, N)
 Based on the definition of the greatest common
divisor,
 a common divisor cannot be greater than the smaller
of given 2 numbers, which we will denote by t =
min{m, n}.
 So we can start by checking whether t divides both m
and n:
 if it does, t is the answer;
 if it does not, we simply decrease t by 1 and try again.
 For example, for numbers 60 and 24,
 the algorithm will try first 24, then 23, and so on, until
it reaches 12, where it stops.
CS19341-DAA
2. CONSECUTIVE INTEGER
CHECKING ALGORITHM FOR
COMPUTING GCD(M, N)
Step 1 Assign the value of min{m, n} to t.
Step 2 Divide m by t. If the remainder of this division is
0,
go to Step 3; otherwise, go to Step 4.
Step 3 Divide n by t. If the remainder of this division is 0,
return the value of “t” as the answer and stop;
otherwise, proceed to Step 4.
Step 4 Decrease the value of t by 1. Go to Step 2.

Disadvantage : This algorithm does not work correctly

when one of its input numbers is zero and it illustrates
why it is so important to specify the set of an
algorithm’s inputs explicitly and carefully.

CS19341-DAA
3. MIDDLE-SCHOOL PROCEDURE FOR
COMPUTING GCD(M, N)
Step 1 Find the prime factors of m.
Step 2 Find the prime factors of n.
Step 3 Identify all the common factors in the two
prime
expansions found in Step 1 and Step 2.
Step 4 Compute the product of all the common
factors and
return it as the greatest common divisor of the
numbers given.
Example : For the numbers 60 and 24,
we get 60 = 2 . 2 . 3 . 5
24 = 2 . 2 . 2 . 3
gcd(60, 24) = 2 . 2 . 3 CS19341-DAA
Disadvantages : More complex, slower than
Euclid’s algorithm, inferior efficiency and not
legitimate algorithm.
Because the prime factorization steps are not
defined unambiguously. They require a list of
prime numbers.
Step 3 is also not defined clearly enough. Its
ambiguity is much easier to rectify than that of
the factorization steps, however. How would you
find common elements in two sorted lists?
So, let us introduce a simple algorithm for
generating consecutive primes not exceeding
any given integer n > 1.
It was probably invented in ancient Greece and is
known as the sieve of Eratosthenes

CS19341-DAA
A SIMPLE ALGORITHM FOR GENERATING
CONSECUTIVE PRIMES
1.The algorithm starts by initializing a list of prime
candidates with consecutive integers from 2 to n.
2. Then, on its first iteration, the algorithm eliminates
from the list all multiples of 2, i.e., 4, 6, and so on.
3.Then it moves to the next item on the list, which is 3,
and eliminates its multiples.
4.No pass for number 4 is needed: since 4 itself and all
its multiples are also multiples of 2, they were already
eliminated on a previous pass.
5.The next remaining number on the list, which is used
on the third pass, is 5.

The algorithm continues in this fashion until no more

numbers can be eliminated from the list.
The remaining integers of the list are the primes needed
CS19341-DAA
As an example, finding the list of primes not
exceeding n = 25:

The remaining numbers on the list are the

consecutive primes less than or equal to 25.

CS19341-DAA
 What is the largest number p whose multiples can still
remain on the list to make further iterations of the
algorithm necessary?
How to avoid eliminating the same number more than once?
 Let p is a number whose multiples are being eliminated on
the current pass, then the first multiple we should consider
is p.p
 because all its smaller multiples 2p, . . . , (p − 1)p have been
eliminated on earlier passes through the list.
 This observation helps to avoid eliminating the same
number more than once.
 Obviously, p.p should not be greater than n, and therefore
p cannot exceed √n rounded down.
Note:
So now we can incorporate the sieve of Eratosthenes into
the middle-school procedure to get a legitimate algorithm
for computing the greatest common divisor of two
positive integers.

CS19341-DAA
ALGORITHM Sieve(n)
//Implements the sieve of Eratosthenes
//Input: A positive integer n > 1
//Output: Array L of all prime numbers less than or equal to n
for p←2 to n do A[p]←p
for p←2 to √n
if A[p] != 0 //p hasn’t been eliminated on previous passes
j←p∗p
while j ≤ n do
A[j ]←0 //mark element as eliminated
j ←j + p
//copy the remaining elements of A to array L of the primes
i ←0
for p←2 to n do
if A[p] = 0
L[i]←A[p]
i ←i + 1 CS19341-DAA
FUNDAMENTALS OF
ALGORITHMIC PROBLEM
SOLVING

Note: sequence of steps one typically goes

through in designing and analyzing an algorithm

CS19341-DAA
 Algorithms are procedural solutions to problems.
These solutions are not answers but specific
instructions for getting answers.
STEPS IN DESIGNING AND ANALYZING AN
ALGORITHM
 We now list and briefly discuss a sequence of steps
in designing and analyzing an algorithm
1. Understanding the Problem
2. Ascertaining the Capabilities of the Computational
Device
3. Choosing between Exact and Approximate Problem
Solving
4. Algorithm Design Techniques
5. Designing an Algorithm and Data Structures
6. Methods of Specifying an Algorithm
7. Proving an Algorithm’s Correctness
CS19341-DAA
CS19341-DAA
1. Understanding the Problem
First thing need to do before designing an algorithm is to
understand completely the problem given.
Read the problem’s description carefully and ask
questions,
do a few small examples by hand,
think about special cases, and ask questions again if
needed.
use a known algorithm for solving it.. It helps to
understand how such an algorithm works and to know its
strengths and weaknesses, especially if you have to
choose among several available algorithms.
If you will not find a readily available algorithm then you
have to design your own.
An input to an algorithm specifies an instance of the
problem the algorithm solves.
 It is very important to specify exactly the set of instances
the algorithm needs to handle.
A correct algorithm is not one that works most of the
time, but one that works correctly for all legitimate inputs.

CS19341-DAA
2. Ascertaining the Capabilities of the Computational Device
 Once you completely understand a problem, you need to find out
the capabilities of the computational device the algorithm is
intended for.
Sequential algorithms :
Algorithms designed to be executed on random-access machine
(RAM) are called sequential algorithms. In random access
machine, instructions are executed one after another, one
operation at a time.
Parallel algorithms :
Algorithms that take advantage of executing operations concurrently
are called parallel algorithms.

 If the problems are very complex in nature, or have to process

huge volumes of data, or deal with applications where the time is
critical, it is imperative to be aware of the speed and memory
available on a particular computer system.

 Otherwise it is not required, because most computer scientists

prefer to study algorithms in terms independent of specification
parameters for a particular computer.
CS19341-DAA
3. Choosing between Exact and Approximate Problem Solving
There are 2 ways to solve the problems. They are
a) Exact Problem solving
b) Approximate Problem Solving
 Exact Problem solving algorithm is called an exact algorithm;
 Approximate Problem Solving algorithm is called an approximation
algorithm.
Why would one opt for an approximation algorithm?
 First ,Some Problems cannot be solved exactly for most of their
instances.
 Eg.
 Extracting square roots,
 Solving nonlinear equations, and
 Evaluating definite integrals.
 Second, available algorithms for solving a problem exactly can be
 unacceptably slow because of the problem’s intrinsic complexity
 Third, an approximation algorithm can be a part of a more
sophisticated algorithm that solves a problem
CS19341-DAAexactly.
4. Algorithm Design Techniques
How do you design an algorithm to solve a given problem?
What is an algorithm design technique?
 An algorithm design technique (or “strategy” or “paradigm”) is a
general approach to solving problems algorithmically that is applicable
to a variety of problems from different areas of computing.
 They provide guidance for designing algorithms for new problems, i.e.,
problems for which there is no known satisfactory algorithm.
 Algorithm design techniques make it possible to classify algorithms
according to an underlying design idea;

Examples some algorithm design techniques are,

1. Brute Force and Exhaustive Search
2. Decrease-and-Conquer
3. Divide-and-Conquer
4. Dynamic Programming
5. Greedy Technique etc.

CS19341-DAA
5. Designing an Algorithm and Data Structures
Algorithms+ Data Structures = Programs
Designing an algorithm:
 Designing an algorithm for a particular problem is a challenging task and
it provides a powerful set of general approaches to algorithmic problem
solving.
 Some design techniques can be simply inapplicable to the problem in
question. Sometimes, several techniques need to be combined,
 Even when a particular design technique is applicable, getting an
algorithm often requires a nontrivial ingenuity on the part of the
algorithm designer.
 With practice, both tasks—choosing among the general techniques and
applying them— get easier, but they are rarely easy.
Data Structures:
 Should pay close attention to choosing data structures appropriate for
the operations performed by the algorithm.
 Some of the algorithm design techniques depend intimately on
structuring or restructuring data specifying a problem’s instance.
 In object-oriented programming, data structures remain crucially
important for both design and analysis of algorithms.

CS19341-DAA
6. Methods of Specifying an Algorithm
Once you have designed an algorithm, you need to specify it in some
fashion.
Euclid’s algorithm is described in words (in a free and also a step-by-step
form) and in pseudocode.
These are the two options that are most widely used nowadays for
specifying algorithms.
Options for specifying algorithms:
a) In words
b) In pseudo code (E.g. Euclid’s algorithm )
Pseudo code is a mixture of a natural language and programming
language like constructs.
 Pseudo code is usually more precise than natural language, and its
usage often yields more succinct algorithm descriptions.
c) Flowchart (Used in the earlier days of computing for specifying
algorithms)
It is a method of expressing an algorithm by a collection of connected
geometric shapes containing descriptions of the algorithm’s steps.
 Inconvenient for all but very simple algorithms.
d) Computer program
 Program is yet another way of specifying the algorithm and it is
preferable to consider it as the algorithm’s implementation.
Ambiguity of any natural language makes a clear description of
algorithms difficult.
CS19341-DAA
7. Proving an Algorithm’s Correctness
 Once an algorithm has been specified, we have to prove its
correctness. That is, we have to prove that the algorithm yields a
required result for every legitimate input in a finite amount of time.
 Eg. Greatest common divisor Algorithm is correct.
 gcd(m, n) = gcd(n, m mod n)
 Second integer gets smaller on every iteration of the algorithm, and
the algorithm stops when the second integer becomes 0.
 A common technique for proving correctness is to use
mathematical induction because an algorithm’s iterations provide
a natural sequence of steps needed for such proofs.
 Tracing the algorithm’s performance for a few specific inputs alone
cannot prove the algorithm’s correctness conclusively. But one
instance of its input for which the algorithm fails is enough to
show that an algorithm is incorrect.
 The notion of correctness for approximation algorithms is less
straight forward than it is for exact algorithms.
 For an approximation algorithm, we have to be able to show that
the error produced by the algorithm does not exceed a predefined
limit.

CS19341-DAA
8. Analyzing an Algorithm
Qualities or Characteristic of an algorithm are,
1. Efficiency
2. Simplicity
3. Generality
1.Efficiency
There are two kinds of algorithm efficiency:
Time efficiency, - indicating how fast the algorithm runs, and
space efficiency, -indicating how much extra memory it uses.
2. Simplicity
 Simplicity is an important algorithm characteristic. Because simpler
algorithms are easier to understand and easier to program;
consequently, the resulting programs usually contain fewer bugs
 Sometimes simpler algorithms are also more efficient than more
complicated alternatives.
 Unfortunately, it is not always true, in which case a judicious
compromise needs to be made.
CS19341-DAA
8. Analyzing an Algorithm ......(continued........)
3.Generality
There are, two issues here:
1. Generality of the problem the algorithm solves and
2. The set of inputs it accepts.
Generality of the problem the algorithm solves:
1. On the first issue, it is sometimes easier to design an algorithm for a
problem in more general terms.
Eg. The problem of determining whether two integers are relatively prime,
i.e., whether their only common divisor is equal to 1
2. There are situations, however, where designing a more general algorithm is
unnecessary or difficult or even impossible.
For example, it is unnecessary to sort a list of n numbers to find its median
and the standard formula for roots of a quadratic equation cannot be
generalized to handle polynomials of arbitrary degrees.
The set of inputs it accepts:
1. Should design an algorithm that can handle a set of inputs that is natural
for the problem at hand.
2. Eg Excluding integers equal to 1 as possible inputs for a greatest
common divisor algorithm would be quite unnatural.
If the algorithm’s efficiency, simplicity, or generality is not satisfied
then we must redesign, fine-tune and make several improvements in the
algorithm.
CS19341-DAA
9. Coding an Algorithm
Most algorithms are destined to be ultimately implemented as
computer programs.
A difficulty lies in the possibility of making the transition from an
algorithm to a program either incorrectly or very inefficiently.
As a practical matter, the validity of programs is still established by
testing.
Test and debug the programs thoroughly whenever we implement
an algorithm.
 When implementing algorithms as programs to be used in actual
applications, we should provide verifications for the inputs.
 Algorithms must be implemented correctly and efficiently.
A better algorithm can make a difference in running time by orders of
magnitude. But once an algorithm is selected, a 10–50% speedup
may be worth an effort.
 A working program provides an additional opportunity in allowing
an empirical analysis of the underlying algorithm. Such an analysis is
based on timing the program on several inputs and then analyzing the
results obtained.
In conclusion, a good algorithm is a result of repeated effort and
rework.

CS19341-DAA
THANK YOU
CS19341-DAA