Design and Analysis of Algorithms

Vandana M L
Department of Computer Science & Engineering
DESIGN AND ANALYSIS OF ALGORITHMS

Introduction to Algorithms,
Design Techniques and Analysis
Slides courtesy of Anany Levitin

Vandana M L
Department of Computer Science & Engineering
 Design and Analysis of Algorithms
Syllabus
 UNIT I (12 Hours)
• Introduction
• Analysis of Algorithm Efficiency,
• Algebric structures
 UNIT II (12 Hours)
• Brute Force,
• Divide-and-Conquer
 UNIT III (10 Hours)
• Decrease-and-Conquer
• Transform-and-Conquer
 UNIT IV (10 Hours)
• Space and Time Tradeoffs
• Greedy Technique
 UNIT V (12 Hours)
• Limitations of Algorithm Power
• Coping with the Limitations of Algorithm Power
• Dynamic Programming
Design and Analysis of Algorithms
Text Books

Publication Information
Book Type Code Title & Author
Edition Publisher Year

Introduction to The Design and Analysis of Algorithms

Text Book T1 2 Pearson 2012
Anany Levitin

Introduction to Algorithms Prentice-Hall India

Reference Book R1 3 2009
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

Fundamentals of Computer Algorithms

Reference Book R2 2 Universities Press 2007
Horowitz, Sahni, Rajasekaran,

Algorithm Design
Reference Book R3 1 Pearson Education 2006
Jon Kleinberg, Eva Tardos,
 Design and Analysis of Algorithms
Algorithm

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
Important Points about Algorithms
 The non-ambiguity 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 implemented in several different ways

 There may exist several algorithms for solving the same problem.
Design and Analysis of Algorithms
Characteristics of Algorithm

Input: Zero or more quantities are externally supplied

Definiteness: Each instruction is clear and unambiguous

Finiteness: The algorithm terminates in a finite number of steps.

Effectiveness: Each instruction must be primitive and feasible

Output: At least one quantity is produced

 Design and Analysis of Algorithms
Algorithm

Why do we need Algorithms?

 It is a tool for solving well-specified Computational Problem.
 Problem statement specifies in general terms relation between input and output
 Algorithm describes computational procedure for achieving input/output relationship
This Procedure is irrespective of implementation details

Why do we need to study algorithms?

Exposure to different algorithms for solving various problems helps
develop skills to design algorithms for the problems for which
there are no published algorithms to solve it
Design and Analysis of Algorithms
Basic Issues related to Algorithms

 How to design algorithms

 How to express algorithms

 Proving correctness of designed algorithm

 Efficiency
 Theoretical analysis

 Empirical analysis
Design and Analysis of Algorithms
Basic Issues related to Algorithms

 How to design algorithms

 How to express algorithms

 Proving correctness of designed algorithm

 Efficiency
 Theoretical analysis

 Empirical analysis
 Design and Analysis of Algorithms
Algorithm Design Technique
What do you mean by Algorithm Design Techniques?
General Approach to solving problems algorithmically .
Applicable to a variety of problems from different areas of computing
Various Algorithm Design Techniques
 Brute Force
 Divide and Conquer

 Decrease and Conquer

 Transform and Conquer

 Dynamic Programming

 Greedy Technique

 Branch and Bound

 Backtracking

Importance Framework for designing and analyzing algorithms

for new problems
Design and Analysis of Algorithms
Basic Issues related to Algorithms

 How to design algorithms

 How to express algorithms

 Proving correctness of designed algorithm

 Efficiency
 Theoretical analysis

 Empirical analysis
Design and Analysis of Algorithms
Methods of Specifying an Algorithm

 Natural language
 Ambiguous

 Pseudocode
 A mixture of a natural language and programming language-like structures

 Precise and succinct.

 Pseudocode in this course

 omits declarations of variables

 use indentation to show the scope of such statements

as for, if, and while.

 use  for assignment

 Flowchart
 Method of expressing algorithm by collection of

connected geometric shapes

Design and Analysis of Algorithms
Methods of Specifying an 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.

Example: gcd(60,24) = gcd(24,12) = gcd(12,0) = 12

Design and Analysis of Algorithms
Methods of Specifying an Algorithm

Two descriptions of Euclid’s algorithm

Euclid’s algorithm for computing gcd(m,n)
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.

ALGORITHM Euclid(m,n)
//computes gcd(m,n) by Euclid’s method
//Input: Two nonnegative,not both zero integers
//Output:Greatest common divisor of m and n
while n ≠ 0 do
r ← m mod n
m← n
n←r
return m
Design and Analysis of Algorithms
Algorithm for Sequential Search
Design and Analysis of Algorithms
Basic Issues related to Algorithms

 How to design algorithms

 How to express algorithms

 Proving correctness of designed algorithm

 Efficiency
 Theoretical analysis

 Empirical analysis
Design and Analysis of Algorithms
Basic Issues related to Algorithms

 How to design algorithms

 How to express algorithms

 Proving correctness of designed algorithm

 Efficiency
 Theoretical analysis

 Empirical analysis
 Design and Analysis of Algorithms
Need of Analysis

 To determine resource consumption

 CPU time

 Memory space

 Compare different methods for solving the same problem before actually
implementing them and running the programs.

 To find an efficient algorithm for solving the problem

 Design and Analysis of Algorithms
Complexity of an algorithm

 A measure of the performance of an algorithm

 An algorithm’s performance is characterized by

 Time complexity
How fast an algorithm maps input to output as a function of input
 Space complexity

amount of memory units required by the algorithm in addition to the

memory needed for its input and output
 Design and Analysis of Algorithms
Complexity of an algorithm

How to determine complexity of an algorithm?

 Experimental study(Performance Measurement)

 Theoretical Analysis (Performance Analysis)

Design and Analysis of Algorithms
Limitations of Performance Measurement

 It is necessary to implement the algorithm, which may be difficult

 Results may not be indicative of the running time on other inputs

not included in the experiment.

 In order to compare two algorithms, the same hardware and

software environments must be used

 Experimental data though important is not sufficient

Design and Analysis of Algorithms
Performance Analysis

 Uses a high-level description of the algorithm instead of an implementation

 Characterizes running time as a function of the input size, n.

 Takes into account all possible inputs

 Allows us to evaluate the speed of an algorithm independent of the

hardware/software environment
THANK YOU

Vandana M L
Department of Computer Science & Engineering
vandanamd@pes.edu
Design and Analysis of Algorithms
Vandana M L
Department of Computer Science & Engineering
DESIGN AND ANALYSIS OF ALGORITHMS

Fundamentals of Algorithmic Problem Solving

Slides courtesy of Anany Levitin

Vandana M L
Department of Computer Science & Engineering
Design and Analysis of Algorithms
Algorithm Design and Analysis Process

Understand the problem

Decide on computational means

Exact vs approximate solution
Data structures
Algorithm design technique

Design an algorithm

Prove correctness

Analyze the algorithm

Code the algorithm

Design and Analysis of Algorithms
Computational Means

Computational Device the algorithm is intended for

RAM Sequential Algorithms

PRAM Parallel Algorithms
Design and Analysis of Algorithms
Exact vs approximate solution

Travelling Salesman Problem

NP complete!!!

Approximate algorithm can be used to solve it

Design and Analysis of Algorithms
Deciding on Data Structure

 Linear
Linear list, Stack, Queues
 Non Linear

Trees, Graphs

Choice of Data structure for solving a problem using an algorithm may

dramatically impact its time complexity

Dijkstra Algorithm
O(VlogV+E) with Fibonacci heap
Design and Analysis of Algorithms
Algorithm Design Technique

General approach to solving problems algorithmically that is applicable to

variety of problems from different areas of computing

ADT serves as heuristic for designing algorithms for new problems for which
no satisfactory algorithm exists!!!

Algorithm Designer’s Toolkit

Design and Analysis of Algorithms
Specifying an algorithm

 Natural Language

 Pseudo Code

 Flowchart
Design and Analysis of Algorithms
Specifying an algorithm

 Natural Language

 Pseudo Code

 Flowchart
Design and Analysis of Algorithms
Proving Correctness

Exact algorithms
Proving that algorithm yields a correct result for legitimate input in finite
amount of time

Approximation algorithms
Error produced by algorithm does not exceed a predefined limit
Design and Analysis of Algorithms
Analyzing an algorithm

 Efficiency
 Time efficiency

 Space efficiency

 Simplicity

 Generality
 Design an algorithm for the problem posed in more general terms

 Design an algorithm that can handle a range of inputs that is natural for
the problem at hand
Design and Analysis of Algorithms
Coding an algorithm

 Efficient implementation

 Correctness of program
 Mathematical Approach: Formal verification for small programs
 Practical Methods: Testing and Debugging

 Code optimization
THANK YOU

Vandana M L
Department of Computer Science & Engineering
vandanamd@pes.edu
Design and Analysis of Algorithms
Vandana M L
Department of Computer Science & Engineering
DESIGN AND ANALYSIS OF ALGORITHMS

Important Problem Types

Slides courtesy of Anany Levitin

Vandana M L
Department of Computer Science & Engineering
Design and Analysis of Algorithms
Important Problem Types

 sorting

 searching

 string processing

 graph problems

 combinatorial problems

 geometric problems

 numerical problems
Design and Analysis of Algorithms
Important Problem Types: Sorting

 Rearrange the items of a given list in ascending order.

 Input: A sequence of n numbers <a1, a2, …, an>
 Output: A reordering <a´1, a´2, …, a´n> of the input sequence such
that a´1≤ a´2 ≤ … ≤ a´n.
 Why sorting?

 Help searching
 Algorithms often use sorting as a key subroutine.
 Sorting key

A specially chosen piece of information used to guide sorting.

Example: sort student records by SRN.
Design and Analysis of Algorithms
Important Problem Types: Sorting

 Rearrange the items of a given list in ascending order.

 Examples of sorting algorithms

 Selection sort
 Bubble sort
 Insertion sort
 Merge sort
 Heap sort …
 Evaluate sorting algorithm complexity: the number of key comparisons.

 Two properties

 Stability: A sorting algorithm is called stable if it preserves the relative order

of any two equal elements in its input.
 In place : A sorting algorithm is in place if it does not require extra memory,
except, possibly for a few memory units.
Design and Analysis of Algorithms
Important Problem Types: Searching

Find a given value, called a search key, in a given set.

Examples of searching algorithms

 Sequential searching

 Binary searching…
Design and Analysis of Algorithms
Important Problem Types: String Processing

A string is a sequence of characters from an alphabet.

Text strings: letters, numbers, and special characters.

String matching: searching for a given word/pattern in a text.

Text: I am a computer science graduate

Pattern: computer
Design and Analysis of Algorithms
Important Problem Types: Graph Problems

Definition
Graph G is represented as a pair G= (V, E),
where V is a finite set of vertices and E is a finite set of edges
Modeling real-life problems
 Modeling WWW

 communication networks

 Project scheduling …

Examples of graph algorithms

 Graph traversal algorithms

 Shortest-path algorithms

 Topological sorting
Design and Analysis of Algorithms
Important Problem Types: Combinatorial Problems

Shortest paths in a graph

To find the distances from each vertex to all other vertices.
Design and Analysis of Algorithms
Important Problem Types: Combinatorial Problems

Minimum cost spanning tree

• A spanning tree of a connected graph is its connected acyclic sub graph (i.e. a tree).
Design and Analysis of Algorithms
Important Problem Types: Geometric Problems

Closest Pair problem

Convex Hull Problem

Design and Analysis of Algorithms
Important Problem Types: Numerical Problems

 Solving Equations

 Computing definite integrals

 Evaluating functions
THANK YOU

Vandana M L
Department of Computer Science & Engineering
vandanamd@pes.edu
Design and Analysis of Algorithms
Vandana M L
Department of Computer Science & Engineering
DESIGN AND ANALYSIS OF ALGORITHMS

Analysis Framework
Slides courtesy of Anany Levitin

Vandana M L
Department of Computer Science & Engineering
Design and Analysis of Algorithms
Analysis Framework

What do you mean by analysing an algorithm?

Investigation of Algorithm’s efficiency with respect to two resources
 Time

 Space

What is the need for Analysing an algorithm?

 To determine resource consumption

 CPU time

 Memory space

 Compare different methods for solving the same problem before actually
implementing them and running the programs.
 To find an efficient algorithm
Design and Analysis of Algorithms
Complexity of an Algorithm

 A measure of the performance of an algorithm

 An algorithm’s performance depends on

 internal factors

 Time required to run

 Space (memory storage)required to run
 external factors

 Speed of the computer on which it is run

 Quality of the compiler

 Size of the input to the algorithm

Design and Analysis of Algorithms
Performance of Algorithm

important Criteria for performance:

 Space efficiency - the memory required, also called, space complexity

 Time efficiency - the time required, also called time complexity

Design and Analysis of Algorithms
Space Complexity

S(P)=C+SP(I)
 Fixed Space Requirements (C)
Independent of the characteristics of the inputs and outputs
 instruction space

 space for simple variables, fixed-size structured variable,

constants
 Variable Space Requirements (SP(I))
dependent on the instance characteristic I
 number, size, values of inputs and outputs associated with I

 recursive stack space, formal parameters, local variables,

return address
Design and Analysis of Algorithms
Space Complexity

S(P)=C+SP(I)
float rsum(float list[ ], int n)
{ Ssum(I)=Ssum(n)=6n
if (n)
return rsum(list, n-1) + list[n-1]
return 0
}
Type Name Number of bytes
parameter: float list [ ] 2
parameter: integer n 2
return address:(used 2
internally)
TOTAL per recursive call 6
Design and Analysis of Algorithms
Time Complexity

T(P)=C+TP(I)

 Compile time (C)

independent of instance characteristics

 run (execution) time TP

Design and Analysis of Algorithms
Time Complexity

How to measure time complexity?

 Theoretical Analysis

 Experimental study
Design and Analysis of Algorithms
Time Complexity

Experimental study

 Write a program implementing the algorithm

 Run the program with inputs of varying size and composition

 Get an accurate measure of the actual running time

 Use a method like System.currentTimeMillis()

 Plot the results

Design and Analysis of Algorithms
Limitations of Experimental study

 It is necessary to implement the algorithm, which may be difficult

 Results may not be indicative of the running time on other inputs not
included in the experiment.

 In order to compare two algorithms, the same hardware and software

environments must be used

 Experimental data though important is not sufficient

Design and Analysis of Algorithms
Theoretical Analysis

 Uses a high-level description of the algorithm instead of an implementation

 Characterizes running time as a function of the input size, n.

 Takes into account all possible inputs

 Allows us to evaluate the speed of an algorithm independent of the

hardware/software environment
Design and Analysis of Algorithms
Theoretical Analysis

Two approaches:

1.Order of magnitude/asymptotic categorization –

This uses coarse categories and gives a general idea of performance.
If algorithms fall into the same category, if data size is small,
or if performance is critical, use method 2

2.Estimation of running time -

1. operation counts - select operation(s) that are executed most frequently

and determine how many times each is executed.
2. step counts - determine the total number of steps, possibly lines of code,
executed by the program.
Design and Analysis of Algorithms
Analysis Framework

 Measuring an input’s size

 Measuring running time

 Orders of growth (of the algorithm’s efficiency function)

 Worst-base, best-case and average efficiency

Design and Analysis of Algorithms
Measuring an input’s size

Efficiency is defined as a function of input size.

Input size depends on the problem.

Example 1, what is the input size of the problem of sorting n numbers?
Example 2, what is the input size of adding two n by n matrices?
Design and Analysis of Algorithms
Units for Measuring Running Time

 Measure the running time using standard unit of time measurements, such
as seconds, minutes?
Depends on the speed of the computer.

 count the number of times each of an algorithm’s operations is executed.

(step count method)
Difficult and unnecessary

 count the number of times an algorithm’s basic operation is executed.

Basic operation: the most important operation of the algorithm, the

operation contributing the most to the total running time.

For example, the basic operation is usually the most time-consuming

operation in the algorithm’s innermost loop.
Design and Analysis of Algorithms
Measuring Running Time: Step Count Method
Design and Analysis of Algorithms
Measuring Running Time: Basic operation count

Input Size and Basic Operation Examples

Problem Input size measure Basic operation

Search for a key in a Number of items in
Key comparison
list of n items list, n
Add two n by n Dimensions of
addition
matrices matrices, n
Dimensions of
multiply two matrices matrices, n multiplication
Design and Analysis of Algorithms
Theoretical Analysis of Time Efficiency: Basic operation count

Time efficiency is analyzed by determining the number of

repetitions of the basic operation as a function of input size.

input size

T(n) ≈ copC (n)

running time execution time Number of times the
for the basic operation basic operation is
executed
Design and Analysis of Algorithms
Order of Growth

C(n) Basic Operation Count

 The efficiency analysis framework ignores the multiplicative constants of C(n)

and focuses on the orders of growth of the C(n).

 Simple characterization of the algorithm's efficiency by identifying relatively

significant term in the C(n).
 Design and Analysis of Algorithms
Order of Growth

Why do we care about the order of growth of an algorithm’s efficiency

function, i.e., the total number of basic operations?
 Because, for smaller inputs, it is difficult to distinguish inefficient
algorithms vs. efficient ones.
 For example, if the number of basic operations of two algorithms to solve a
particular problem are n and n2 respectively, then
– if n = 2, Basic operation will be executed 2 and 4 times respectively for
algorithm1 and 2.
Not much difference!!!
– On the other hand, if n = 10000, then it does makes a difference whether
the number of times the basic operation is executed is n or n2.
Design and Analysis of Algorithms
Order of Growth

Exponential-growth functions

Orders of growth:
• consider only the leading term of a formula
• ignore the constant coefficient.
22
Design and Analysis of Algorithms
Order of Growth

700

600

500

n*n*n
400 n*n
n log(n)
300 n
log(n)

200

100

0
1 2 3 4 5 6 7 8
Design and Analysis of Algorithms
Basic Efficiency Classes

1 constant

log n logarithmic

n linear

n log n n-log-n

n2 quadratic

n3 cubic

2n exponential

n! factorial
Design and Analysis of Algorithms
Best, Worst and Average case Analysis

 Algorithm efficiency depends on the input size n

 For some algorithms efficiency depends on type of input.

Example: Sequential Search

Problem: Given a list of n elements and a search key K, find an
element equal to K, if any.
Algorithm: Scan the list and compare its successive elements with
K until either a matching element is found (successful search) or
the list is exhausted (unsuccessful search)

Given a sequential search problem of an input size of n,

what kind of input would make the running time the longest?
How many key comparisons?
Design and Analysis of Algorithms
Best, Worst and Average case Analysis

 Worst case Efficiency

 Efficiency (# of times the basic operation will be executed) for the worst case input
of size n.
 The algorithm runs the longest among all possible inputs of size n.
 Best case
 Efficiency (# of times the basic operation will be executed) for the best case input of
size n.
 The algorithm runs the fastest among all possible inputs of size n.
 Average case:
 Efficiency (#of times the basic operation will be executed) for a typical/random
input of size n.
 NOT the average of worst and best case
 How to find the average case efficiency?
Design and Analysis of Algorithms
Best, Worst and Average case Analysis

ALGORITHM SequentialSearch(A[0..n-1], K)
//Searches for a given value in a given array by sequential
search
//Input: An array A[0..n-1] and a search key K
//Output: Returns the index of the first element of A that
matches K or –1 if there are no matching elements
i 0
while i < n and A[i] ‡ K do
ii+1
if i < n //A[I] = K
return i
else
27
return -1
 Design and Analysis of Algorithms
Best, Worst and Average case Analysis: Sequential Search

 Worst-Case: Cworst(n) = n

 Best-Case: Cbest(n) = 1

 Average-Case
from (n+1)/2 to (n+1)

28
Design and Analysis of Algorithms
Average case Analysis: Sequential Search

Let ‘p’ be the probability that key is found in the list

Assumption: All positions are equally probable
Case1: key is found in the list
Cavg,case1(n) = p*(1 + 2 + … + n) / n=p*(n + 1) / 2
Case2: key is not found in the list
Cavg, case2(n) = (1-p)*(n)
Cavg(n) = p(n + 1) / 2 + (1 - p)(n)

29
THANK YOU

Vandana M L
Department of Computer Science & Engineering
vandanamd@pes.edu
Design and Analysis of Algorithms
Vandana M L
Department of Computer Science & Engineering
DESIGN AND ANALYSIS OF ALGORITHMS

Asymptotic Notations
Slides courtesy of Anany Levitin

Vandana M L
Department of Computer Science & Engineering
Design and Analysis of Algorithms
Asymptotic Notations

Order of growth of an algorithm’s basic operation count is important

How do we compare order of growth??
Using Asymptotic Notations
A way of comparing functions that ignores constant factors and small
input sizes
O(g(n)): class of functions f(n) that grow no faster than g(n)
Ω(g(n)): class of functions f(n) that grow at least as fast as g(n)
Θ (g(n)): class of functions f(n) that grow at same rate as g(n)
o(g(n)): class of functions f(n) that grow at slower rate than g(n)
(g(n)): class of functions f(n) that grow at faster rate than g(n)
Design and Analysis of Algorithms
O-notation
Design and Analysis of Algorithms
O-notation

Formal definition
A function t(n) is said to be in O(g(n)), denoted t(n) O(g(n)),
if t(n) is bounded above by some constant multiple of g(n) for all
large n,
i.e., if there exist some positive constant c and some nonnegative
integer n0 such that

t(n)  cg(n) for all n  n0

Example: 100n+5 ∈ O(n)

Design and Analysis of Algorithms
-notation
Design and Analysis of Algorithms
-notation

Formal definition
A function t(n) is said to be in (g(n)), denoted t(n)  (g(n)), if
t(n) is bounded below by some constant multiple of g(n) for all
large n,
i.e., if there exist some positive constant c and some nonnegative
integer n0 such that

t(n)  cg(n) for all n  n0

Example: 10n2  (n2)

Design and Analysis of Algorithms
-notation
Design and Analysis of Algorithms
-notation

Formal definition
A function t(n) is said to be in (g(n)), denoted t(n)  (g(n)),
if t(n) is bounded both above and below by some positive
constant multiples of g(n) for all large n,
i.e., if there exist some positive constants c1 and c2 and some
nonnegative integer n0 such that

c2 g(n)  t(n)  c1 g(n) for all n  n0

Example: (1/2)n(n-1)  (n2)

Design and Analysis of Algorithms

>=
(g(n)), functions that grow at least as fast as g(n)

=
(g(n)), functions that grow at the same rate as g(n)
g(n)

<=
O(g(n)), functions that grow no faster than g(n)
Design and Analysis of Algorithms
Little-o Notation

Formal Definition:
A function t(n) is said to be in Little-o(g(n)), denoted t(n) o(g(n)),
if for any positive constant c and some nonnegative integer n0

0  t(n) < cg(n) for all n  n0

Example: n  o(n2)
Design and Analysis of Algorithms
Little Omega Notation

Formal Definition:
A function t(n) is said to be in Little- (g(n)), denoted t(n)  (g(n)),
if for any positive constant c and some nonnegative integer n0
t(n) >cg(n) 0 for all n  n0

Example: 3 n2+ 2  (n)

Design and Analysis of Algorithms
Theorems

 If t1(n)  O(g1(n)) and t2(n)  O(g2(n)), then

t1(n) + t2(n)  O(max{g1(n), g2(n)}).
For example,
5n2 + 3nlogn  O(n2)

 If t1 ( n) ∈ Θ ( g 1 ( n)) and t2 ( n) ∈ Θ ( g2 ( n)) , then

t1 ( n) + t2 ( n) ∈ Θ(max{ g 1 ( n), g2 ( n)})

 t1(n) ∈ Ω(g1(n)) and t2(n) ∈ Ω(g2(n)), then

t1(n) + t2(n) ∈ Ω(max{g1(n), g2(n)})

Implication: The algorithm’s overall efficiency will be determined by the part with a larger
order of growth, I.e., its least efficient part.
THANK YOU

Vandana M L
Department of Computer Science & Engineering
vandanamd@pes.edu
Design and Analysis of Algorithms
Vandana M L
Department of Computer Science & Engineering
DESIGN AND ANALYSIS OF ALGORITHMS

Method of Limits for comparing order of Growth

Slides courtesy of Anany Levitin

Vandana M L
Department of Computer Science & Engineering
Design and Analysis of Algorithms
Using Limits to Compare Order of Growth

Case1: t(n)  O(g(n)

Case2: t(n)  Θ(g(n))
Case3: g(n)  O(t(n)) t’(n) and g’(n) are first-order derivatives of t(n) and g(n)

L’Hopital’s Rule

Stirling’s Formula
Design and Analysis of Algorithms
Using Limits to Compare Order of Growth: Example 1

Compare the order of growth of f(n) and g(n) using method

of limits

t(n) = 5n3 + 6n + 2 , g(n) = n4

t(n) 5n3  6n  2  5  6  2   0
lim  lim  lim
n g(n) n n 4 n n n3 n 4 
As per case1
t(n) = O(g(n))
5n3 + 6n + 2 = O(n4)
Design and Analysis of Algorithms
Using Limits to Compare Order of Growth: Example 2

t (n)  5n2  4n  2
using the Limits approach determine g(n) such that f(n) = Θ(g(n))
Leading term in square root n2

g(n)  n2  n
t(n) 5n2  4n  2
lim  lim
n g(n) n
n2
5n2  4n  2 4 2
 lim 2
 lim 5   2  5
n n n n n
non-zero constant
Hence, t(n) = Θ(g(n)) = Θ(n)
Design and Analysis of Algorithms
Using Limits to Compare Order of Growth
 Design and Analysis of Algorithms
Using Limits to Compare Order of Growth: Example 3

Compare the order of growth of t(n) and g(n) using method of limits
t(n)  log2 n, g(n) 
 Design and Analysis of Algorithms
Orders of growth of some important functions

 All logarithmic functions loga n belong to the same class

(log n) no matter what the logarithm’s base a > 1 is

log10 n ∈ Θ(log2 n)

All polynomials of the same degree k belong to the same class:

aknk + ak-1nk-1 + … + a0  (nk)

 Exponential functions an have different orders of growth for different a’s

3n ∉ Θ(2n)

order log n < order n (>0) < order an < order n! < order nn
Design and Analysis of Algorithms
How to Establish Orders of Growth of an Algorithm’s Basic Operation Count

Summary
• Method 1: Using limits.
• L’ Hôpital’s rule
• Method 2: Using the theorem.
• Method 3: Using the definitions of O-, -, and -notation.
THANK YOU

Vandana M L
Department of Computer Science & Engineering
vandanamd@pes.edu
Design and Analysis of Algorithms
Vandana M L
Department of Computer Science & Engineering
DESIGN AND ANALYSIS OF ALGORITHMS

Mathematical Analysis of Non-recursive Algorithms

Slides courtesy of Anany Levitin

Vandana M L
Department of Computer Science & Engineering
 Design and Analysis of Algorithms
Time Efficiency of Non-recursive Algorithms

Steps in mathematical analysis of non-recursive algorithms:

 Decide on parameter n indicating input size

 Identify algorithm’s basic operation

 Check whether the number of times the basic operation is
executed depends only on the input size n. If it also depends on
the type of input, investigate worst, average, and best case
efficiency separately.
 Set up summation for C(n) reflecting the number of times the
algorithm’s basic operation is executed.
 Simplify summation using standard formulas
Design and Analysis of Algorithms
Useful Summation Formulas and Rules

liu1 = 1+1+…+1 = u - l + 1

1in i = 1+2+…+n = n(n+1)/2

1in i2 = 12+22+…+n2 = n(n+1)(2n+1)/6

0in ai = 1 + a +…+ an = (an+1 - 1)/(a - 1) for any a  1

(ai ± bi ) = ai ± bi cai = cai

liuai = limai + m+1iuai

u

1  (u  l 1)
il
Design and Analysis of Algorithms
Example 1: Finding Max Element in a list
Algorithm MaxElement (A[0..n-1])
//Determines the value of the largest element
in a given array
//Input: An array A[0..n-1] of real numbers
//Output: The value of the largest element in A
maxval  A[0]
for i  1 to n-1 do
if A[i] > maxval
maxval  A[i]
return maxval
• The basic operation- comparison
• Number of comparisons is the same for all arrays of size n.
• Number of comparisons
Design and Analysis of Algorithms
Example 2: Element Uniqueness Problem

Algorithm UniqueElements (A[0..n-1])

//Checks whether all the elements in a given
array are distinct
//Input: An array A[0..n-1]
//Output: Returns true if all the elements in A
are distinct and false otherwise
for i  0 to n - 2 do
for j  i + 1 to n – 1 do
if A[i] = A[j] return false
return true
Best-case:
If the two first elements of the array are the same
No of comparisons in Best case = 1 comparison
Worst-case:
– Arrays with no equal elements
– Arrays in which only the last two elements are the
pair of equal elements
Design and Analysis of Algorithms
Example 2: Element Uniqueness Problem

Best-case: 1 comparison
Worst-case: n2/2 comparisons
T(n)worst case = O(n2)
Design and Analysis of Algorithms
Example 3:Matrix Multiplication

Algorithm MatrixMultiplication(A[0..n-1, 0..n-1], B[0..n-1, 0..n-1] )

//Multiplies two square matrices of order n by the definition-based algorithm
//Input: two n-by-n matrices A and B
//Output: Matrix C = AB
for i  0 to n - 1 do
for j  0 to n – 1 do
C[i, j]  0.0
for k  0 to n – 1 do
C[i, j]  C[i, j] + A[i, k] * B[k, j]
return C

M(n) € Θ (n3)
8
THANK YOU

Vandana M L
Department of Computer Science & Engineering
vandanamd@pes.edu
Design and Analysis of Algorithms
Vandana M L
Department of Computer Science & Engineering
DESIGN AND ANALYSIS OF ALGORITHMS

Mathematical Analysis of Recursive Algorithms

Slides courtesy of Anany Levitin

Vandana M L
Department of Computer Science & Engineering
 Design and Analysis of Algorithms
Steps in Mathematical Analysis of Recursive Algorithms

 Decide on parameter n indicating input size

 Identify algorithm’s basic operation
 If the number of times the basic operation is executed varies with different inputs of
same sizes , investigate worst, average, and best case efficiency separately
 Set up a recurrence relation and initial condition(s) for C(n)-the number of times the
basic operation will be executed for an input of size n
 Solve the recurrence or estimate the order of magnitude of the solution
 Design and Analysis of Algorithms
Important Recurrence Types

 Decrease-by-one recurrences
A decrease-by-one algorithm solves a problem by exploiting a relationship between a
given instance of size n and a smaller size n – 1.
Example: n!
The recurrence equation has the form
T(n) = T(n-1) + f(n)

 Decrease-by-a-constant-factor recurrences
A decrease-by-a-constant algorithm solves a problem by dividing its given instance of
size n into several smaller instances of size n/b, solving each of them recursively, and
then, if necessary, combining the solutions to the smaller instances into a solution to
the given instance.
Example: binary search.
The recurrence has the form
T(n) = aT(n/b) + f (n)
 Design and Analysis of Algorithms
Decrease-by-one Recurrences

 One (constant) operation reduces problem size by one.

T(n) = T(n-1) + c T(1) = d
Solution: T(n) = (n-1)c + d linear

 A pass through input reduces problem size by one.

T(n) = T(n-1) + c n T(1) = d
Solution: T(n) = [n(n+1)/2 – 1] c + d quadratic
Design and Analysis of Algorithms
Methods to solve recurrences

 Substitution Method
 Mathematical Induction
 Backward substitution
 Recursion Tree Method
 Master Method (Decrease by constant factor recurrences)
Design and Analysis of Algorithms
Recursive Evaluation of n!

n ! = 1  2  … (n-1)  n for n ≥ 1 and 0! = 1

Recursive definition of n!:
F(n) = F(n-1)  n for n ≥ 1 input size?
F(0) = 1
basic operation?

Best/Worst/Average Case?

M(n-1) = M(n-2) + 1; M(n-2) = M(n-3)+1

M(n) = n

Overall time Complexity: Θ(n)

Design and Analysis of Algorithms
Counting number of binary digits in binary representation of a number

input size?

basic operation?

Best/Worst/Average Case?
Design and Analysis of Algorithms
Tower of Hanoi
Algorithm TowerOfHanoi(n, Src, Aux, Dst)
if (n = 0)
return
TowerOfHanoi(n-1, Src, Dst, Aux)
Move disk n from Src to Dst
TowerOfHanoi(n-1, Aux, Src, Dst)

Input Size: n
Basic Operation : Move disk n from Src to Dst
C(n) = 2C(n-1) + 1 for n > 0 and C(0)=0
= 2n - 1 ∈ Θ(2n)
Design and Analysis of Algorithms
Tower of Hanoi : Tree of Recursive calls
THANK YOU

Vandana M L
Department of Computer Science & Engineering
vandanamd@pes.edu
Design and Analysis of Algorithms
Vandana M L
Department of Computer Science & Engineering
DESIGN AND ANALYSIS OF ALGORITHMS

Solving Recurrences
Slides courtesy of Anany Levitin

Vandana M L
Department of Computer Science & Engineering
Design and Analysis of Algorithms
Solving Recurrences: Example1

T(n) = T(n-1) + 1 n>0 T(0) = 1

T(n) = T(n-1) + 1
= T(n-2) + 1 + 1 = T(n-2) + 2
= T(n-3) + 1 + 2 = T(n-3) + 3
…
= T(n-i) + i
…
= T(n-n) + n = n=O(n)
 Design and Analysis of Algorithms
Solving Recurrences: Example2

T(n) = T(n-1) + 2n – 1 T(0)=0

= [T(n-2) + 2(n-1) - 1] + 2n - 1
= T(n-2) + 2(n-1) + 2n - 2
= [T(n-3) + 2(n-2) -1] + 2(n-1) + 2n - 2
= T(n-3) + 2(n-2) + 2(n-1) + 2n - 3
...
= T(n-i) + 2(n-i+1) +...+ 2n - i
...
= T(n-n) + 2(n-n+1) +...+ 2n - n
= 0 + 2 + 4 +...+ 2n - n
= 2 + 4 +...+ 2n - n
= 2*n*(n+1)/2 - n
// arithmetic progression formula 1+...+n = n(n+1)/2 //
= O(n2)
Design and Analysis of Algorithms
Solving Recurrences: Example3

T (n)  T (n / 2)  1 n 1
T (1)  1

T (n)  T (n / 2)  1
 T (n / 2 2 )  1  1
 T (n / 23 )  1  1  1
......
 T (n / 2i )  i
......
 T (n / 2 k )  k (k  log n)
 1  log n
 O( log n)
Design and Analysis of Algorithms
Solving Recurrences: Example4

T (n)  2T (n / 2)  cn n 1 T (1)  c

T (n)  2T (n / 2)  cn
 2(2T (n / 2 2 )  c(n / 2))  cn  2 2 T (n / 2 2 )  cn  cn
 2 2 (2T (n / 23 )  c(n / 2 2 ))  cn  cn  23 T (n / 23 )  3cn
......
 2i T (n / 2i )  icn
......
 2 k T (n / 2 k )  kcn (k  log n)
 nT (1)  cn log n  cn  cn log n
 O(n log n)
THANK YOU

Vandana M L
Department of Computer Science & Engineering
vandanamd@pes.edu
Design and Analysis of Algorithms
Vandana M L
Department of Computer Science & Engineering
DESIGN AND ANALYSIS OF ALGORITHMS

Performance Analysis Vs Performance Measurement

Slides courtesy of Anany Levitin

Vandana M L
Department of Computer Science & Engineering
Design and Analysis of Algorithms
Performance Evaluation of Algorithm

Performance Analysis
 Machine Independent
 Prior Evaluation
Performance Measurement
 Machine Dependent
 Posterior Evaluation
Design and Analysis of Algorithms
Performance Analysis of Sequential search :Worst Case
ALGORITHM SequentialSearch(A[0..n-1], K)
//Searches for a given value in a given array by sequential search
//Input: An array A[0..n-1] and a search key K
//Output: Returns the index of the first element of A that matches K or –1 if there are no
matching elements
i 0
while i < n and A[i] ‡ K do Basic operation: A[i] ‡ K
ii+1 Basic operation count: n
if i < n //A[i] = K Time Complexity: T(n) ∈O(n)
return i
else
return -1
Design and Analysis of Algorithms
Performance Analysis of Sequential Search

Sequential Search Sequential Search

Input Size C(n)worst C(n)worst
5000
1000 1000 4500
4000
1500 1500 3500
3000
2000 2000 2500
2000
2500 2500 1500
1000
3000 3000 500
0
3500 3500 0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000

4000 4000
4500 4500
Design and Analysis of Algorithms
Performance Measurement of Sequential Search

Sequential Search Sequential Search

Input Size Actual Running Time(ms) Running time(ms)
0.014

1000 0.001907 0.012

1500 0.004053 0.01

0.008
2000 0.00596 0.006

2500 0.007153 0.004

0.002
3000 0.007868 0

3500 0.008821 0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000

4000 0.010014
4500 0.011921
THANK YOU

Vandana M L
Department of Computer Science & Engineering
vandanamd@pes.edu
DESIGN AND ANALYSIS
OF ALGORITHMS
UE19CS251

Shylaja S S
Department of Computer Science
& Engineering
DESIGN AND ANALYSIS OF ALGORITHMS

Brute Force: Selection Sort

Major Slides Content: Anany Levitin

Shylaja S S
Department of Computer Science & Engineering
DESIGN AND ANALYSIS OF ALGORITHMS
Brute Force
DESIGN AND ANALYSIS OF ALGORITHMS
Brute Force

• Brute Force is a straightforward approach to solving a

problem, usually directly based on the problem statement
and definitions of the concepts involved
DESIGN AND ANALYSIS OF ALGORITHMS
Brute Force
• In computer science, brute-force search or exhaustive
search, also known as generate and test, is a very
general problem-solving technique and algorithmic
paradigm that consists of:
• systematically enumerating all possible candidates for
the solution
• checking whether each candidate satisfies the
problem's statement

https://en.wikipedia.org/wiki/Brute-force_search
DESIGN AND ANALYSIS OF ALGORITHMS
Brute Force
• A brute-force algorithm to find the divisors of a natural
number n would
• enumerate all integers from 1 to n
• check whether each of them divides n without
remainder
• A brute-force approach for the eight queens puzzle would
• examine all possible arrangements of 8 pieces on the
64-square chessboard
• check whether each (queen) piece can attack any other,
for each arrangement
• The brute-force method for finding an item in a table (linear
search)
• checks all entries of the table, sequentially, with the
item
DESIGN AND ANALYSIS OF ALGORITHMS
Brute Force
• A brute-force search is simple to implement, and will always
find a solution if it exists
• But, its cost is proportional to the number of candidate
solutions – which in many practical problems tends to grow
very quickly as the size of the problem increases
(Combinatorial explosion)
• Brute-force search is typically used
• when the problem size is limited
• when there are problem-specific heuristics that can be
used to reduce the set of candidate solutions to a
manageable size
• when the simplicity of implementation is more
important than speed
DESIGN AND ANALYSIS OF ALGORITHMS
Brute Force Sorting Algorithms

• Selection Sort
• Bubble Sort
 DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort
• Scan the array to find its smallest element and swap it with
the first element, putting the smallest element in its final
position in the sorted list
• Then, starting with the second element, scan the elements to
the right of it to find the smallest among them and swap it
with the second element, putting the second smallest element
in its final position
• Generally, on pass i (0  i  n-2), find the smallest element in
A[i..n-1] and swap it with A[i ]

• A[0]  A[1]  A[2] …  A[i-1] | A[i], ….., A[min], …., A[n-1]

• in their final positions the last n – i elements
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 89 45 68 90 29 34 17
Pass 0 i=0 0 1 2 3 4 5 6

min j
45 < 89 ??

min = 01 j=1
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 89 45 68 90 29 34 17
i=0 0 1 2 3 4 5 6

min j
68 < 45 ??

min = 1 j=2
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 89 45 68 90 29 34 17
i=0 0 1 2 3 4 5 6

min j
90 < 45 ??

min = 1 j=3
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 89 45 68 90 29 34 17
i=0 0 1 2 3 4 5 6

min j
29 < 45 ??

min = 14 j=4
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 89 45 68 90 29 34 17
i=0 0 1 2 3 4 5 6

min j
34 < 29 ??

min = 4 j=5
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 89 45 68 90 29 34 17
i=0 0 1 2 3 4 5 6

min j
17 < 29 ??

min = 46 j=6
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 89 45 68 90 29 34 17
i=0 0 1 2 3 4 5 6

min
swap a[i] and a[min]

min = 6
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 17 45 68 90 29 34 89
i=0 0 1 2 3 4 5 6
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 17 45 68 90 29 34 89
Pass 1 i=1 0 1 2 3 4 5 6

min min
j

swap a[i] and a[min]

min = 4
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 17 29 68 90 45 34 89
i=1 0 1 2 3 4 5 6
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 17 29 68 90 45 34 89
Pass 2 i=2 0 1 2 3 4 5 6

min min
j

swap a[i] and a[min]

min = 5
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 17 29 34 90 45 68 89
i=2 0 1 2 3 4 5 6
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 17 29 34 90 45 68 89
Pass 3 i=3 0 1 2 3 4 5 6

min min
j

swap a[i] and a[min]

min = 4
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 17 29 34 45 90 68 89
i=3 0 1 2 3 4 5 6
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 17 29 34 45 90 68 89
Pass 4 i=4 0 1 2 3 4 5 6

min min
j

swap a[i] and a[min]

min = 5
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 17 29 34 45 68 90 89
i=4 0 1 2 3 4 5 6
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 17 29 34 45 68 90 89
Pass 5 i=5 0 1 2 3 4 5 6

min min
j

swap a[i] and a[min]

min = 6
 DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

elements in
final position
a 17 29 34 45 68 89 90
i=5 0 1 2 3 4 5 6

Original array 89 45 68 90 29 34 17
0 1 2 3 4 5 6

Array after sorting 17 29 34 45 68 89 90

0 1 2 3 4 5 6
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

ALGORITHM SelectionSort(A[0 .. n -1])

//Sorts a given array by selection sort
//Input: An array A[0 .. n - 1] of orderable elements
//Output: Array A[0 .. n - 1] sorted in ascending order
for i <- 0 to n - 2 do
min <- i
for j <- i+l to n-1 do
if A[j] < A[min] min <- j
swap A[i] and A[min]
DESIGN AND ANALYSIS OF ALGORITHMS
Selection Sort

Selection Sort Analysis

Selection Sort is a Θ(n2) algorithm

THANK YOU

Shylaja S S
Department of Computer Science
& Engineering
shylaja.sharath@pes.edu
DESIGN AND ANALYSIS
OF ALGORITHMS
UE19CS251

Shylaja S S
Department of Computer Science
& Engineering
DESIGN AND ANALYSIS OF ALGORITHMS

Bubble Sort
Major Slides Content: Anany Levitin

Shylaja S S
Department of Computer Science & Engineering
 DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort

• Compare adjacent elements of the list and exchange them if they

are out of order
• By doing it repeatedly, we end up bubbling the largest element to
the last position on the list
• The next pass bubbles up the second largest element and so on
and after n – 1 passes, the list is sorted
• Pass i (0  i  n – 2) can be represented as follows:
A[0], A[1], A[2], …, A[j] ? A[j+1], …, A[n-i-1] | A[n-i]  ….  A[n-1]
in their final positions
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
elements in
final position
89 45 68 90 29 34 17
i=0 0 1 2 3 4 5 6

j=0 89 45
45 89 68 90 29 34 17
0 1 2 3 4 5 6

45 < 89 swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
elements in
final position
45 89 68 90 29 34 17
i=0 0 1 2 3 4 5 6

j=1 45 68
89 68
89 90 29 34 17
0 1 2 3 4 5 6

68 < 89 swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
elements in
final position
45 68 89 90 29 34 17
i=0 0 1 2 3 4 5 6

j=2 45 68 89 90 29 34 17
0 1 2 3 4 5 6

90 < 89 no swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
elements in
final position
45 68 89 90 29 34 17
i=0 0 1 2 3 4 5 6

j=3 45 68 89 90 29
29 90 34 17
0 1 2 3 4 5 6

29 < 90 swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
elements in
final position
45 68 89 29 90 34 17
i=0 0 1 2 3 4 5 6

j=4 45 68 89 29 34
90 90
34 17
0 1 2 3 4 5 6

34 < 90 swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
elements in
final position
45 68 89 29 34 90 17
i=0 0 1 2 3 4 5 6

j=5 45 68 89 29 34 17
90 90
17
0 1 2 3 4 5 6

17 < 90 swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
After elements in
first final position
iteration 45 68 89 29 34 17 90
i=1 0 1 2 3 4 5 6

j=0 45 68 89 29 34 17 90
0 1 2 3 4 5 6

68 < 45 no swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
elements in
final position
45 68 89 29 34 17 90
i=1 0 1 2 3 4 5 6

j=1 45 68 89 29 34 17 90
0 1 2 3 4 5 6

89 < 68 no swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
elements in
final position
45 68 89 29 34 17 90
i=1 0 1 2 3 4 5 6

j=2 29 89
45 68 89 29 34 17 90
0 1 2 3 4 5 6

29 < 89 swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
elements in
final position
45 68 29 89 34 17 90
i=1 0 1 2 3 4 5 6

j=3 45 68 29 34 34
89 89 17 90
0 1 2 3 4 5 6

34 < 89 swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
elements in
final position
45 68 29 34 89 17 90
i=1 0 1 2 3 4 5 6

j=4 45 68 29 34 17
89 89
17 90
0 1 2 3 4 5 6

17 < 89 swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
After elements in
second final position
iteration 45 68 29 34 17 89 90
i=2 0 1 2 3 4 5 6

j=0 45 68 29 34 17 89 90
0 1 2 3 4 5 6

68 < 45 no swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
elements in
final position
45 68 29 34 17 89 90
i=2 0 1 2 3 4 5 6

j=1 29 29
45 68 68 34 17 89 90
0 1 2 3 4 5 6

29 < 68 swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
elements in
final position
45 29 68 34 17 89 90
i=2 0 1 2 3 4 5 6

j=2 34 68
45 29 68 34 17 89 90
0 1 2 3 4 5 6

34 < 68 swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
elements in
final position
45 29 34 68 17 89 90
i=2 0 1 2 3 4 5 6

j=3 45 29 34 17 68 89 90
68 17
0 1 2 3 4 5 6

17 < 68 swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
After elements in
third final position
iteration 45 29 34 17 68 89 90
i=3 0 1 2 3 4 5 6

j=0 29
45 45
29 34 17 68 89 90
0 1 2 3 4 5 6

29 < 45 swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
elements in
final position
29 45 34 17 68 89 90
i=3 0 1 2 3 4 5 6

j=1 29 34
45 45
34 17 68 89 90
0 1 2 3 4 5 6

34 < 45 swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
elements in
final position
29 34 45 17 68 89 90
i=3 0 1 2 3 4 5 6

j=2 17 45
29 34 45 17 68 89 90
0 1 2 3 4 5 6

17 < 45 swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
After elements in
fourth final position
iteration 29 34 17 45 68 89 90
i=4 0 1 2 3 4 5 6

j=0 29 34 17 45 68 89 90
0 1 2 3 4 5 6

34 < 29 no swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
elements in
final position
29 34 17 45 68 89 90
i=4 0 1 2 3 4 5 6

j=1 29 17 17
34 34 45 68 89 90
0 1 2 3 4 5 6

17 < 34 swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
After elements in
fifth final position
iteration 29 17 34 45 68 89 90
i=5 0 1 2 3 4 5 6

j=0 17 17
29 29 34 45 68 89 90
0 1 2 3 4 5 6

17 < 29 swap
DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort
After elements in
sixth final position
iteration 17 29 34 45 68 89 90
0 1 2 3 4 5 6
 DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort

ALGORITHM BubbleSort(A[0 .. n - 1])

//Sorts a given array by bubble sort in their final positions
//Input: An array A[0 .. n - 1] of orderable elements
//Output: Array A[0 .. n- 1] sorted in ascending order
for i <-- 0 to n - 2 do
for j <-- 0 to n - 2 - i do
if A[ j + 1 ] < A[ j ] swap A[ j ] and A[ j + 1 ]
 DESIGN AND ANALYSIS OF ALGORITHMS
Bubble Sort

Bubble Sort Analysis

Bubble Sort is a Θ(n2) algorithm

THANK YOU

Shylaja S S
Department of Computer Science
& Engineering
shylaja.sharath@pes.edu
DESIGN AND ANALYSIS
OF ALGORITHMS
UE19CS251

Shylaja S S
Department of Computer Science
& Engineering
DESIGN AND ANALYSIS OF ALGORITHMS

Sequential Search
Major Slides Content: Anany Levitin

Shylaja S S
Department of Computer Science & Engineering
 DESIGN AND ANALYSIS OF ALGORITHMS
Sequential Search

• Compares successive elements of a given list with a given search

key until:
• A match is encountered (Successful Search)
• List is exhausted without finding a match (Unsuccessful Search)
• An improvisation to the algorithm is to append the key to the end
of the list
• This means the search has to be successful always and we can
eliminate the end of list check
 DESIGN AND ANALYSIS OF ALGORITHMS
Sequential Search

• Sequential / Linear Search

10 14 19 26 27 31 33 35 42 44
0 1 2 3 4 5 6 7 8 9

• For key = 33, 6 is returned

• For key = 50, -1 is returned
 DESIGN AND ANALYSIS OF ALGORITHMS
Sequential Search

AlGORITHM SequentialSearch2(A[0 .. n ], K)
//Implements sequential search with a search key as a sentinel
//Input: An array A of n elements and a search key K
//Output: The index of the first element in A[0 .. n -1] whose value is
// equal to K or -1 if no such element is found
A[n]<---K
i<---0
while A[i] ≠K do
i<--- i + 1
if i < n return i
else return -1
 DESIGN AND ANALYSIS OF ALGORITHMS
Sequential Search

Sequential Search Analysis

• Sequential Search is a Θ(n) algorithm

THANK YOU

Shylaja S S
Department of Computer Science
& Engineering
shylaja.sharath@pes.edu
DESIGN AND ANALYSIS
OF ALGORITHMS
UE19CS251

Shylaja S S
Department of Computer Science
& Engineering
DESIGN AND ANALYSIS OF ALGORITHMS

String Matching
Major Slides Content: Anany Levitin

Shylaja S S
Department of Computer Science & Engineering
 DESIGN AND ANALYSIS OF ALGORITHMS
Brute – Force String Matching

String Matching - Terms

• pattern:
a string of m characters to search for
• text:
a (longer) string of n characters to search in
• problem:
find a substring in the text that matches the pattern
 DESIGN AND ANALYSIS OF ALGORITHMS
String Matching Idea

Step 1: Align pattern at beginning of text

Step 2: Moving from left to right, compare each character of pattern

to the corresponding character in text until:
• all characters are found to match (successful search); or
• a mismatch is detected

Step 3: While pattern is not found and the text is not yet exhausted,
realign pattern one position to the right and repeat Step 2
 DESIGN AND ANALYSIS OF ALGORITHMS
String Matching

ALGORITHM BruteForceStringMatch(T[0 .. n -1], P[0 .. m -1])

//Implements brute-force string matching
//Input: An array T[0 .. n - 1] of n characters representing a text
// and an array P[0 .. m - 1] of m characters representing a pattern
//Output: The index of the first character in the text that starts a
//matching substring or -1 if the search is unsuccessful
for i  0 to n-m do
j0
while j < m and P[j] = T[i + j] do
j j+1
if j = m return i
return -1
DESIGN AND ANALYSIS OF ALGORITHMS
String Matching Example
 DESIGN AND ANALYSIS OF ALGORITHMS
String Matching Analysis

Worst Case:
• The algorithm might have to make all the ‘m’ comparisons for
each of the (n-m+1) tries
• Therefore, the algorithm makes m(n-m+1) comparisons
• Brute Force String Matching is a O(nm) algorithm
THANK YOU

Shylaja S S
Department of Computer Science
& Engineering
shylaja.sharath@pes.edu
DESIGN AND ANALYSIS
OF ALGORITHMS
UE19CS251

Shylaja S S
Department of Computer Science
& Engineering
DESIGN AND ANALYSIS OF ALGORITHMS

Travelling Salesman Problem

Major Slides Content: Anany Levitin

Shylaja S S
Department of Computer Science & Engineering
 DESIGN AND ANALYSIS OF ALGORITHMS
Exhaustive Search

• Exhaustive Search is a brute – force problem solving technique

• It suggests generating each and every element of the problem
domain, selecting those of them that satisfy all the constraints
and then finding a desired element
• The desired element might be one which minimizes or maximizes
a certain characteristic
• Typically the problem domain involves combinatorial objects
such as permutations, combinations and subsets of a given set
 DESIGN AND ANALYSIS OF ALGORITHMS
Exhaustive Search - Method

• Generate a list of all potential solutions to the problem in a

systematic manner
• Evaluate potential solutions one by one, disqualifying infeasible
ones and, for an optimization problem, keeping track of the best
one found so far
• When search ends, announce the solution(s) found
 DESIGN AND ANALYSIS OF ALGORITHMS
Travelling Salesman Problem

• Given a list of cities and the distances between each pair of

cities, what is the shortest possible route that visits each city and
returns to the origin city?

Alternative way to state the problem:

• Find the shortest Hamiltonian Circuit in a weighted connected
graph
 DESIGN AND ANALYSIS OF ALGORITHMS
TSP: History and Relevance

• The Travelling Salesman Problem

was mathematically formulated by
Irish Mathematician Sir William
Rowan Hamilton
• It is one of the most intensively
studied problems in optimization
• It has applications in logistics and
planning
 DESIGN AND ANALYSIS OF ALGORITHMS
Travelling Salesman Problem

Example
Tour Length
2
a 5 3
b a→b→c→d→a

a→b→d→c→a
2+3+7+5 = 17

2+4+7+8 = 21

8 4 a→c→b→d→a 8+3+4+5 = 20

a→c→d→b→a 8+7+4+2 = 21

a→d→b→c→a 5+4+3+8 = 20
c 7 d a→d→c→b→a 5+7+3+2 = 17
 DESIGN AND ANALYSIS OF ALGORITHMS
Travelling Salesman Problem

Efficiency
• The Exhaustive Search solution to the Travelling Salesman
problem can be obtained by keeping the origin city constant and
generating permutations of all the other n – 1 cities
• Thus, the total number of permutations needed will be (n – 1)!
THANK YOU

Shylaja S S
Department of Computer Science
& Engineering
shylaja.sharath@pes.edu
DESIGN AND ANALYSIS
OF ALGORITHMS
UE19CS251

Shylaja S S
Department of Computer Science
& Engineering
DESIGN AND ANALYSIS OF ALGORITHMS

Knapsack Problem
Major Slides Content: Anany Levitin

Shylaja S S
Department of Computer Science & Engineering
 DESIGN AND ANALYSIS OF ALGORITHMS
Knapsack Problem

Given n items:
• weights: w1 w2 … wn
• values: v1 v2 … vn
• a knapsack of capacity W
Find the most valuable subset of items that fit into the knapsack
 DESIGN AND ANALYSIS OF ALGORITHMS
Knapsack Problem

Example
Knapsack Capacity W = 16

Item Weight Value

1 2 20

2 5 30

3 10 50

4 5 10
DESIGN AND ANALYSIS OF ALGORITHMS
Knapsack Problem
Subset Total Weight Total Value
{1} 2 20
{2} 5 30
{3} 10 50
Knapsack Problem by
{4} 5 10
Exhaustive Search
{1, 2} 7 50
{1, 3} 12 70
{1, 4} 7 30
{2, 3} 15 80
{2, 4} 10 40
{3, 4} 15 60
{1, 2, 3} 17 Not Feasible
{1, 2, 4} 12 60
{1, 3, 4} 17 Not Feasible
{2, 3, 4} 20 Not Feasible
{1, 2, 3, 4} 22 Not Feasible
 DESIGN AND ANALYSIS OF ALGORITHMS
Knapsack Problem

• The Exhaustive Search solution to the Knapsack Problem is

obtained by generating all subsets of the set of n items given and
computing the total weight of each subset in order to identify
the feasible subsets
• The number of subsets for a set of n elements is 2n
• The Exhaustive Search solution to the Knapsack Problem belongs
to Ω(2n)
THANK YOU

Shylaja S S
Department of Computer Science
& Engineering
shylaja.sharath@pes.edu