21CSC204J

Design and Analysis of Algorithms

Prepared by
Dr L Josephine Usha
Asst.Professor/CSE
SRM Institute of Science and Technology
Course Description

• This course describes various algorithm design and analysis

techniques that help the students to write efficient algorithm for any
real world problems and also analyze the time and space complexity
of different computing algorithms.
Course Objectives
• CLR-1 : Design efficient algorithms in solving complex real time problems.
• CLR-2 : Analyze various algorithm design techniques to solve real time
problems in polynomial time.
• CLR-3 : Utilize various approaches to solve greedy and dynamic algorithms.
• CLR-4 : Utilize back tracking and branch and bound paradigms to solve
exponential time problems.
• CLR-5 : Analyze the need of approximation and randomization algorithms,
utilize the importance Non polynomial algorithms.

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 3

Course Outcomes
• At the end of this course, learners will be able to::
• CO-1 : Apply efficient algorithms to reduce space and time complexity of
both recurrent and non-recurrent relations.
• CO-2 : Solve problems using divide and conquer approaches.
• CO-3 : Apply greedy and dynamic programming types techniques to solve
polynomial time problems.
• CO-4 : Create exponential problems using backtracking and branch and
bound approaches..
• CO-5 : Interpret various approximation algorithms and interpret solutions to
evaluate P type, NP Type, NPC, NP Hard problems.

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 4

Mapping of Course Outcomes
Mapping of Course Outcomes to Program Outcomes
Program Outcomes

Analysi
Engineer Environ Project
CO Design/ s, Individua
ing Problem Modern Society & ment & Commun Managem Life-long
develop Design, Ethics l & Team
knowled analysis Tool Usage Culture Sustaina ication ent & Learning
ment Resear work
ge bility Finance
ch

CLO1 2 1 2 1 - - - - - 3 - 3

CLO2 2 1 2 1 - - - - - 3 - 3

CLO3 2 1 2 1 - - - - - 3 - 3

CLO4 2 1 2 1 - - - - - 3 - 3

CLO5 2 1 2 1 - - - - - 3 - 3

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 5

Syllabus Outline
• Unit I - Introduction
• Unit II - Divide-and-conquer
• Unit III - Greedy and Dynamic Programing
• Unit IV - Backtracking
• Unit V - Introduction to randomized and approximation algorithm

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 6

 Unit I Outline

• Introduction-Algorithm Design - Fundamentals of Algorithms- Correctness of

algorithm - Time complexity analysis - Insertion sort-Line count, Operation
count
• Algorithm Design paradigms - Designing an algorithm and its analysis-Best,
Worst and Average case
• Asymptotic notations Based on growth functions. O,Ө, ω, Ω
• Mathematical analysis - Induction, Recurrence relations -Solution of recurrence
relations - Substitution method - Solution of recurrence relations - Recursion
tree - Solution of recurrence relations - examples.

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 7

INTRODUCTION

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 8

Introduction – Algorithms
• A finite set of instructions or logic, written in order, to accomplish a
certain predefined task.
• Algorithm is not the complete code or program.
• It is just the core logic (solution) of a problem.
• Can be expressed either as an informal high level description as
pseudo code or using a flowchart.

Prepared by: Dr.L.Josephine Usha, AP/CSE, SRMIST 9

Notion of Algorithm
Characteristics of an Algorithm
• Input
An algorithm should have 0 or more well defined inputs.
• Output
An algorithm should have 1 or more well defined outputs
• Unambiguous
Algorithm should be clear and unambiguous.
• Finiteness
Algorithms must terminate after a finite no. of steps.
• Feasibility
Should be feasible with the available resources.
• Independent
An algorithm should have step-by-step directions which should be independent of any
programming code.
Pseudo code
• It is one of the methods that could be used to represent an algorithm.

• It is not written in a specific syntax

• Cannot be executed

• Can be read and understood by programmers who are familiar with different programming
languages.

• Transformation from pseudo code to the corresponding program code easier.

• Pseudo code allows to include control structures such as WHILE, IF-THEN-ELSE, REPEAT-
UNTIL, FOR, and CASE, which are available in many high level languages.
Difference b/w Algorithm and Pseudocode

Algorithm Pseudo code

A finite set of instructions or logic, written in order, A generic way of describing an algorithm without using any
to accomplish a certain predefined task. specific programming language-related notations.
It is just the core logic (solution) of a problem It is an outline of a program, written in a form which can easily
be converted into real programming statements.
Easy to understand the logic of a problem Can be read and understood by programmers who are familiar
with different programming languages.

Can be expressed either as an informal high level It is not written in a specific syntax. It allows to include control
description as pseudo code or using a flowchart. structures such as WHILE, IF-THEN-ELSE, REPEAT-UNTIL, FOR,
and CASE, which are present in many high level languages.
Notion of Algorithm: Example

• Finding the GCD (Greatest Common Divisor) of two non-negative

and non-both-zero integers ‘m’ and ‘n’.
• defines the largest integer that divides both evenly (remainder zero).
Notion of Algorithm
• The three methods for solving this problem are
• Euclid’s algorithm
• Consecutive Integer checking Algorithm
• Middle School procedure
Notion of Algorithm
• Euclid’s algorithm
Notion of Algorithm
• Euclid’s algorithm
Notion of Algorithm
• Euclid’s algorithm
Notion of Algorithm
• Consecutive Integer checking Algorithm
• gcd(m,n)  must be smaller than these 2 numbers. It can be written as
Notion of Algorithm
• Consecutive Integer checking Algorithm
• Example

• Disadvantage:
• This Algorithm does not work properly when one of its input numbers is zero.
Notion of Algorithm
• Middle School procedure

Disadvantage:
• This algorithm is slower than
Euclid’s algorithm
• If the prime numbers list is very
long sorted list, the efficiency
of this algorithm is very less.
Fundamentals Of Algorithmic Problem Solving
Fundamentals Of Algorithmic Problem Solving
• The steps in designing and analyzing an algorithm are
• Understanding the Problem
• Ascertaining the Capabilities of a Computational Device
• Choosing between Exact and Approximate Problem Solving
• Deciding on Appropriate Data Structures
• Algorithm Design Techniques
• Methods of specifying an Algorithm
• Proving an Algorithm’s Correctness
• Analyzing an Algorithm
• Coding an Algorithm
Important Problem Types
1. Sorting

2. Searching

3. String processing

4. Graph problems

5. Combinational problems

6. Geometric problems

7. Numerical problems
Important Problem Types
1. Sorting:
✓ Rearranging the items of a given list in ascending order.
✓ The list may be numbers, alphabets, character strings records (in schools, libraries, companies).
✓ Every sorting algorithm has 2 properties.
a) Stable
b) In place
a) Stable:
If an algorithm preserves the relative order of any 2 equal elements in its input, then the
algorithm is called stable. Eg, When sorting the students based on University rank, students with same
rank must be ordered.
b) In-place:
If an algorithm does not require extra memory, except, for a few memory units, then the
algorithm is said to be in place.
Important Problem Types
2. Searching:

Finding a given value called a search key in a given set. There are many algorithms for
searching.

a. Sequential,

b. Binary
Important Problem Types
Important Problem Types
Important Problem Types
Important Problem Types
Important Problem Types
Introduction To Algorithm Design
Why to design an algorithm?
• General approaches to the construction of efficient solutions to problems
• They provide templates suited for solving a broad range of diverse problems.

• They can be translated into common control and data structures provided by most high-
level languages.

• The temporal and spatial requirements of the algorithms which result can be precisely
analyzed.
Algorithm Design Approaches
• Based on the architecture
• Top Down Approach
• Bottom up Approach
Algorithm Design Techniques
1. Brute Force
• To solve a problem based on the problem’s statement and definitions
of the concepts involved.
• Easiest approach to apply
• Useful for solving small – size instances of a problem.
• Some examples of brute force algorithms are:
• Computing an (a > 0, n a nonnegative integer) by multiplying a*a*…
*a
• Computing n!
• Selection sort, Bubble sort
• Sequential search
Algorithm Design Techniques
2. Divide-and-Conquer & Decrease-and-Conquer
• Step 1
Split the given instance of the problem into several smaller sub-instances
• Step 2
Independently solve each of the sub-instances
• Step 3
Combine the sub-instance solutions.
• With the divide-and-conquer method the size of the problem instance is reduced by a
factor (e.g. half the input size),
• With the decrease-and-conquer method the size is reduced by a constant.
Algorithm Design Techniques

• Examples of divide-and-conquer algorithms:

• Computing an (a > 0, n a nonnegative integer) by recursion
• Binary search in a sorted array (recursion)
• Mergesort algorithm, Quicksort algorithm recursion)
• The algorithm for solving the fake coin problem (recursion)
Algorithm Design Techniques
3. Greedy Algorithms "take what you can get now" strategy
• At each step the choice must be locally optimal
• Works well on optimization problems
• Characteristics
1. Greedy-choice property: A global optimum can be arrived at by selecting a local optimum.
2. Optimal substructure: An optimal solution to the problem contains an optimal solution to sub
problems.
• Examples:
• Minimal spanning tree
• Shortest distance in graphs
• Greedy algorithm for the Knapsack problem
• The coin exchange problem
• Huffman trees for optimal encoding
Algorithm Design Techniques
4.Dynamic Programming
• Finds solutions to subproblems and stores them in memory for later use.
• Characteristics
1. Optimal substructure:
Optimal solution to problem consists of optimal solutions to subproblems
2. Overlapping subproblems:
Few subproblems in total, many recurring instances of each
3. Bottom up approach:
Solve bottom-up, building a table of solved subproblems that are used to solve larger
ones.
• Examples:
• Fibonacci numbers computed by iteration.
• Warshall’s algorithm implemented by iterations
Algorithm Design Techniques
5. Backtracking methods
• The method is used for state-space search problems.
• What is State-space search problems
• State-space search problems are problems, where the problem representation consists of:
• initial state
• goal state(s)
• a set of intermediate states
• a set of operators that transform one state into another.
• a cost function – evaluates the cost of the operations (optional)
• a utility function – evaluates how close is a given state to the goal state (optional)
• The solving process solution is based on the construction of a state-space tree
• The solution is obtained by searching the tree until a goal state is found.
• Examples:
• DFS problem
• Maze problems
Algorithm Design Techniques
• Backtracking
Algorithm Design Techniques

6. Branch-and-bound
• Branch and bound is used when we can evaluate each node using the cost
and utility functions.
• At each step we choose the best node to proceed further.
• Branch-and bound algorithms are implemented using a priority queue.
• The state-space tree is built in a breadth-first manner.
• Example:
• 8-puzzle problem.
• N queens problem
Recollect

• Different design Approaches/ Design Paradigms

• Brute force
• Divide and Conquer Unit 2
• Greedy Algorithms
• Dynamic Programming
} Unit 3

• Backtracking
Unit 4
• Branch and Bound Unit 5
Algorithm Analysis
Fundamentals of the Analysis of Algorithm Efficiency
Fundamentals of the Analysis of Algorithm Efficiency
• The analytical frame work for analyzing both the time and space efficiency are,

1) Measuring an Input’s size.

2) Units for measuring running time.

3) Orders of Growth

4) Worst-Case, Best-Case & Average-Case efficiencies.

Fundamentals of the Analysis of Algorithm Efficiency
1) Measuring an Input’s size.

✓ Algorithms efficiency can be investigated as a function of some parameter ‘n’ indicating the algorithm’s input
size.

✓ Computing the product of two n x n matrices. Two measures of input size are

✓ a) Matrix order, ‘n’

✓ b) Total number of elements (N) in the matrices

✓ If an algorithm examines individual characters of the input, then the size can be measured as, the number of
characters/elements(N).

✓ If an algorithm works by processing words, then the input size is number of words.

✓ If the size of inputs for an algorithm involves to finding the number of binary digits in the n’s binary
representation is
Fundamentals of the Analysis of Algorithm Efficiency
2. Units for Measuring Running Time:

✓ It concerns with the units used to measure the algorithms running time.
✓ One possible approach to measure the algorithm’s efficiency is to count the number of
times each of the algorithm’s operation is executed
✓ Basic Operation
Fundamentals of the Analysis of Algorithm Efficiency
3. Orders of growth:

✓ For large values of n, the functions order of growth, that counts the number of basic
operation.
Fundamentals of the Analysis of Algorithm Efficiency
4. Worst case, Best case & Average case Efficiencies:
✓ There are many algorithms for which the running time, not only depends on the input size, but also on
the specifics of a particular input.
Fundamentals of the Analysis of Algorithm Efficiency
4. Worst case, Best case & Average case Efficiencies:
Fundamentals of the Analysis of Algorithm Efficiency
✓ In the case of the successful search the probability of the first match occurring in the ith position of the
list is p/n.
Asymptotic Notations and its Properties
To compare and rank the order of growth
Asymptotic Notations and its Properties
Asymptotic Notations and its Properties
Asymptotic Notations and its Properties
Asymptotic Notations and its Properties
Asymptotic Notations and its Properties
Asymptotic Notations and its Properties
Basic Efficiency Classes
Algorithm Analysis
• Space Complexity
• The amount of memory space required by the algorithm in its life cycle.

• A fixed part For example simple variables & constant used and program size etc.

• A variable part For example dynamic memory allocation, recursion stacks space etc.

• Space complexity S(P) of any algorithm P is

S(P) = C + S(I)

Where C is the fixed part

S(I) is the variable part of the algorithm

Mathematical Analysis of Non - recursive
Algorithms
• The general plan to be followed to analyze non recursive algorithm are
1. Decide the parameter (parameters) indicating the input size.
2. Identify the algorithms basic operation.
3. Check, whether the number of times, the basic operation is executed, depends
only on the input size.
4. Set up a sum, expressing the no of times the algorithms basic operation is
executed.
5. Using standard formulas and rules of sum manipulation find a closed form
formula for the count or at least establish its order of growth.
Mathematical Analysis of Non - recursive Algorithms
Mathematical Analysis of Non - recursive Algorithms
• Example 1: Consider the problem of finding the value of largest element in a list
of ‘n’ numbers.
Mathematical Analysis of Non - recursive Algorithms
• Example 2: Consider the element uniqueness problem: check whether all the
elements in a given array are distinct.
Mathematical Analysis of Non - recursive Algorithms
Mathematical Analysis of Non - recursive Algorithms
 Mathematical Analysis of Non - recursive Algorithms
• Example 4: Find the number of binary digits in the binary representation of a
positive decimal integer.

The number of comparison n>1 executed exactly is ⌊ 2 ⌋ + 1.

𝑙
𝑜
𝑔
𝑛
Mathematical Analysis
• For Non-recursive Algorithms
• There are four rules to count the operations:
• Rule 1: for loops - the size of the loop times the running time of the body
• Find the running time of statements when executed only once
• Find how many times each statement is executed
• Rule 2 : Nested loops
• The product of the size of the loops times the running time of the body
• Rule 3: Consecutive program fragments
• The total running time is the maximum of the running time of the individual fragments
• Rule 4: If statement
• The running time is the maximum of the running times of if stmt and else stmt.
Mathematical Analysis
• Rule 1: for loops
for( i = 0; i < n; i++) // i = 0; executed only once: O(1)
// i < n; n + 1 times O(n)
// i++ n times O(n)
// total time of the loop heading:
// O(1) + O(n) + O(n) = O(n)
sum = sum + i; // executed n times, O(n)
The loop heading plus the loop body will give: O(n) + O(n) = O(n).
IF
1. The size of the loop is n (loop variable runs from 0, or some fixed constant, to n)
2. The body has constant running time (no nested loops)
Loop running time is: O(n)
Mathematical Analysis
Rule 2 : Nested loops
sum = 0;
for( i = 0; i < n; i++)
for( j = 0; j < n; j++)
sum++;
• Applying Rule 1 for the nested loop (the ‘j’ loop) we get O(n) for the body of the outer loop. The outer loop
runs n times, therefore the total time for the nested loops will be O(n) * O(n) = O(n*n) = O(n^2)
Mathematical Analysis
for( i = 0; i < n; i++)
for( j = i; j < n; j++)
sum++;
• Here, the number of the times the inner loop is executed depends on the value of i
i = 0, inner loop runs n times
i = 1, inner loop runs (n-1) times
i = 2, inner loop runs (n-2) times
…
i = n – 2, inner loop runs 2 times
i = n – 1, inner loop runs once.
Thus we get: ( 1 + 2 + … + n) = n*(n+1)/2 = O(n^2)
Running time is the product of the size of the loops times the running
time of the body.
Mathematical Analysis
Rule 3: Consecutive program fragment
sum = 0;
for( i = 0; i < n; i++)
sum = sum + i;
sum = 0;
for( i = 0; i < n; i++)
for( j = 0; j < 2*n; j++)
sum++;

• The first loop runs in O(n) time, the second - O(n^2) time, the maximum is O(n^2)

The total running time is the maximum of the running

time of the individual fragments
Mathematical Analysis
Rule 4: If statement

if C
S1;
else
S2;
The running time is the maximum of the running times of S1 and S2.

The running time is the maximum of the running

times of if stmt and else stmt
Exercise
a. c.
sum = 0; sum = 0;
for( i = 0; i < n; i++) for( i = 0; i < n; i++)
for( j = 0; j < n * n; j++) for( j = 0; j < i*i; j++)
sum++; for( k = 0; k < j; k++)
Ans : O(n^3) sum++;

Ans : O(n^5)
d.
b. sum = 0;
sum = 0; for( i = 0; i < n; i++)
for( i = 0; i < n; i++) sum++;
for( j = 0; j < i; j++) val = 1;
sum++; for( j = 0; j < n*n; j++)
Ans : O(n^2) val = val * j;
Ans : O(n^2)
Mathematical Analysis of recursive Algorithms
Mathematical Analysis of recursive Algorithms
• Example 1: Computing the factorial function F(n) = n!, for an arbitrary non–
negative integer n
Mathematical Analysis of recursive Algorithms
• Example 2: Solve the Towers of Hanoi puzzle
• Problem:
• Given ‘n’ disks of different sizes and 3 pegs. Initially, all the disks on
the first peg, in order of size (largest on the bottom and smallest on the
top). Move all the disks to the third peg, using the second one as
auxiliary. The constraints are
1. Move only one disk at a time
2. Don’t place a larger disk on top of a smaller one.
Mathematical Analysis of recursive Algorithms
Mathematical Analysis of recursive Algorithms
• Solution:
• To move n > 1 disks from peg 1 to peg 3, move recursively (n-1)
disks from peg 1 to peg 2 using peg 3 as auxiliary.
• Then move the largest disk directly from peg 1 to peg 3 and finally,
move recursively (n-1) disks from peg 2 to peg 3 using peg 1 as
auxiliary.
• If n=1, simply move the single disk directly from the source peg 1 to
destination peg 3.
Mathematical Analysis of recursive Algorithms
• Apply the general plan to this problem.
• The input size is the number of disks ‘n’.
• The algorithm’s basic operation is moving the disk from one peg to another.
• The number of moves M(n) depends on ‘n’ only and so the recurrence
equation is given as
M(n) = M(n-1) + 1+ M(n-1)for n>1
Mathematical Analysis of recursive Algorithms
Mathematical Analysis of recursive Algorithms
Mathematical Analysis of recursive Algorithms
• Example 3: Find the number of binary digits in the binary representation of a
positive decimal integer.
Mathematical Analysis of recursive Algorithms
Mathematical Analysis of recursive Algorithms
Mathematical Analysis of recursive Algorithms
QUIZ
Question No: 1
• Two main measures for the efficiency of an algorithm are
A. Processor and memory
B. Complexity and capacity
C. Time and space
D. Data and space
• Answer : Time and space
Question No: 2
The space factor when determining the efficiency of algorithm is
measured by
A. Counting the maximum memory needed by the algorithm
B. Counting the minimum memory needed by the algorithm
C. Counting the average memory needed by the algorithm
D. Counting the maximum disk space needed by the algorithm

• Answer : Counting the maximum memory needed by the algorithm

Question No: 3
The time factor when determining the efficiency of algorithm is
measured by
A. Counting microseconds
B. Counting the number of key operations
C. Counting the number of statements
D. Counting the kilobytes of algorithm

• Answer : Counting the number of key operations

Question No: 4
• Which of the following case does not exist in complexity theory?
• A. Best case
• B. Worst case
• C. Average case
• D. Null case

• Answer : Null Case

Question No: 5
• ______is the first step in solving the problem
• A. Understanding the Problem
• B. Identify the Problem
• C. Evaluate the Solution
• D. None of these

• Answer : Understanding the Problem

Question No: 6
• Following is true for understanding of a problem
A. Knowing the knowledge base
B. Understanding the subject on which the problem is based
C. Communication with the client
D. All of the above
Answer : All of the above