Subject: Analysis and Design of Algorithms

Subject Code:BCS401
Faculty: Dr. Naveenkumar T. Rudrappa
 Course outcome
1. Apply asymptotic notational method to analyze the
performance of the algorithms in terms of time complexity.
2. Demonstrate divide & conquer approaches and decrease &
conquer approaches to solve computational problems.
3. Make use of transform & conquer and dynamic
programming design approaches to solve the given real
world or complex computational problems.
4. Apply greedy and input enhancement methods to solve
graph & string based computational problems.
5. Analyze various classes (P,NP and NP Complete) of
problems.
6. Illustrate backtracking, branch & bound and approximation
methods.
 Module 1
• What is an Algorithm?
• Fundamentals of Algorithmic Problem Solving.
• Analysis Framework.
• Asymptotic Notations and Basic Efficiency Classes.
• Mathematical Analysis of Non recursive Algorithms.
• Mathematical Analysis of Recursive Algorithms.
• Brute Force Approaches: Selection Sort and Bubble Sort.
• Sequential Search and Brute Force String Matching.
 Algorithm

• Exact specification of how to solve a computational problem.

• Specifies every step completely, so a computer can implement it without
any understanding.
• Must work for all possible inputs of the problem.
• Help in developing analytical skills.
• One should be able to construct, manipulate, understand and analyze
Algorithms.
• Algorithms must be:
1. Correct: For each input produce an appropriate output.
2. Efficient: Run’s as quickly as possible, using less memory.
3. There can be different algorithms for 1 computational problem.
 What is an Algorithm?
An algorithm is a sequence of unambiguous instructions for solving a problem, i.e.,
for obtaining a required output for any legitimate input in a finite amount of time.

problem

algorithm

input “computer” output

Notion of Algorithm
Euclid’s algorithm: gcd(m, n)=gcd(n, m mod 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.
while n ≠ 0 do
r ← m mod n
m← n
n←r
return m
Step 4: n eventually becomes zero and Algorithm stops.
Consecutive integer checking algorithm: check whether t divides both m and n
Step 1 : Assign the value of min{m,n} to t
Step 2 : Divide m by t. If the remainder is 0, go to Step 3.
otherwise, go to Step 4
Step 3 : Divide n by t. If the remainder is 0, return t and stop;
otherwise, go to Step 4
Step 4 : Decrease t by 1 and go to Step 2
Note: Does not work correctly when one of the input is zero
Middle-school procedure: Compute gcd (m,n)
Step 1: Find the prime factors of m
Step 2: Find the prime factors of n
Step 3: Find common prime factors
Step 4: Compute the product of all the common prime factors and return it as
gcd(m,n)
 Sieve of Eratosthenes
Input: Integer n ≥ 2
Output: List of primes less than or equal to n
for p ← 2 to n do A[p] ← p
for p ← 2 to √n do
if A[p] != 0 //p hasn’t been previously eliminated from the list
j ← p* p
while j ≤ n do
A[j] ← 0 //mark element as eliminated
j←j+p
Example: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2 3 5 7 9 11 13 15 17 19
2 3 5 7 11 13 17 19
2 3 5 7 11 13 17 19
 Take Away

• Non-ambiguity in each step.

• Range of inputs clearly specified.
• 1 algorithm n representations.
• 1 problem m Algorithms.
• m Algorithms n Speeds.
 How do we compare algorithms?
1. Compare execution times?
Not good: times are specific to a particular computer hardware.
2. Count the number of statements executed?
Not good: number of statements vary with the programming language and style
of the individual programmer.

Comparative measures
1. Express running time as a function of the input size n (f(n)).

2. Compare different functions corresponding to running times.

3. Such an analysis is independent of machine time, programming style etc.

Fundamentals of Algorithmic Problem solving

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

What does it mean to understand the problem?
• Read problem description carefully.
• Input to an algorithm specifies an instance for the problem.
Note: Correct algorithm works correctly for all legitimate inputs.
Deciding on computational means
• Algorithm designed close to Von Neumann Architecture, machine called
Random Access Machine.
• Instructions executed 1 after another called Sequential Algorithms
• Recent computers execute operations in parallel. Instructions executed on
such machines are called parallel algorithms.
Choosing between Exact and Approximate Problem Solving
• Exact Algorithm (getting solution may be unacceptably slow due to
problem complexity)
• Approximate Algorithm(Part of sophisticated algorithm for exact
solving is not possible, Square roots)
Deciding on appropriate data structures
Algorithms+ Data Structures= Programs
• Integer, floating point values, strings, varchar.
Design an algorithm
• General approach to solve problems algorithmically applicable
to a variety of problems from different areas of computing.
• Build a computational model of the solving process.
Advantage: 1. Provide guidance for designing algorithms for new
problems.
2. A natural way to categorize and study algorithms.
Specifying an algorithm.
1.Pseudocode: Mixture of natural language and
programming language constructs.
2. Flowchart: Expressing an algorithm by different
geometric shapes containing algorithm steps.
Prove correctness
• Correct output for every legitimate input in finite time.
• Based on correct mathematical formula.
• By mathematical induction
• To prove an algorithm is incorrect: 1 input is sufficient.
• Solution: Error produced by algorithm does not exceed predefined limit
Analyze the algorithm
• Time Efficiency: How fast algorithm runs.
• Space Efficiency: How much extra memory the algorithm needs.
• Simplicity: As viewed by other person.(Qualitative Parameter)
• Generality: Range of inputs, Special cases.
• Optimality: No other algorithm can do better.
Coding
• Transition from algorithm to program.
• How the objects and operations in the algorithm are represented in the
chosen programming language?
 Analysis Of Algorithms
Algorithms efficiency: 2 resources
Running Time
Memory Space
Memory Space
Analysis : 1. Time efficiency: How fast algorithm runs?

2.Space efficiency: How much extra space algorithm needs?

1. Measuring an input’s size?

2. Units of measuring running time?

3. Orders of growth?
 Asymptotic Analysis
• To compare two algorithms with running times f(n) and g(n), we need a
rough measure that characterizes how fast each function grows.

• Hint: use rate of growth

• Compare functions in the limit for large values of n.

 Sequential Search

a[0] a[1] a[2] a[3] a[4] a[5]

1 2 3 4 5 6
1. Worst Case Efficiency: Cworst(n)=n
Search Key value: K=7 Value returned= -1
Search Key value: K=6 Value returned= a[5]
2. Best Case Efficiency: Cbest (n)=1
Search Key value: K=1 Value returned= a[0]
 Asymptotic Notation

Notation Function
O notation: asymptotic “less than”: f(n)=O(g(n)) implies: f(n) “≤” g(n)
Upper bound
Ω notation: asymptotic “greater than”: f(n)= Ω (g(n)) implies: f(n) “≥” g(n)
Lower bound
θ notation: asymptotic “equality”: f(n)= θ (g(n)) implies: f(n) “=” g(n)
Class Interval, Range
O-notation Upper Bound

f(n)=2n+3<=2n+3n<=5n (n=>1)
=O(n)
f(n)=2n+3<=2n2+3n2<=5n2=(n=>1)
=O(n2)
Ω – notation Lower Bound

f(n)=2n+3>=1n (n>=1)
=Ω(n)
=Ω(logn)
θ –notation Average bound

f(n)=2n+3
1*n<=2n+3<=5n (n=>1)
= θ(n)
f(n)=1n2<=2n2+3n2<=5n2=(n=>1)
= θ(n2)
 Property of Asymptotic Notations

Problem: Sorting an array.

To check whether an array has identical elements.
Step 1: Sort the array by applying any algorithm.
Algorithm makes< comparisons. Therefore it is in O(n2)
Step 2: Scan sorted array to check whether consecutive elements are equal.
Algorithm makes<n-1 comparisons. Therefore it is in O(n).

Efficiency of the entire algorithm will be in

O(max{n2,n}=O(n2))
 Limits for comparing orders of growth

0 order of growth of t(n) < order of growth of g(n)

c > 0 order of growth of t(n) = order of growth of g(n)

lim t(n)/g(n) =
n→∞
∞ order of growth of t(n) > order of growth of g(n)
 Basic asymptotic efficiency classes
1 constant Running time goes to infinity as input size grows infinitely large.

log n logarithmic Reducing a problem’s size by a constant factor on each iteration.

n linear Algorithms that scan a list of size n.

n log n “n-log-n” Divide Conquer algorithms, Merge sort, Quick sort in average case.

n2 quadratic Algorithms with 2 embedded loops. Operations on n by n matrices.

n3 cubic Algorithms with 3 embedded loops. Linear Algebra Algorithms.

2n exponential Algorithms that generate subset of an n element set.

n! Factorial Algorithms that generate permutation of an n element set.

 Mathematical Analysis Of Non Recursive Algorithms
General Plan for Analysis

• Decide on parameter n indicating input size.

• Identify algorithm’s basic operation.

• Determine worst, average, best cases for input of size n.

• Set up a sum for the number of times the basic operation is

executed.

• Simplify the sum using standard formulas and rules.

 Example 1: Maximum element

Input: Count of array elements.

Basic operation: for loop
Comparison executed once for each n-1 values
C(n) є Θ(n)

Example 2: Element uniqueness problem

Worst Case input:

1.Array with no equal elements.
2. Array with last 2 elements equal.
C(n) є Θ(n2)
Example 3: Matrix multiplication

C(n) є Θ(n3)
 Mathematical Analysis of Recursive Algorithms
• Decide on a parameter indicating an input’s size.

• Identify the algorithm’s basic operation.

• Check whether the number of times the basic operation is

executed may vary on different inputs of the same size.

• Set up a recurrence relation with an initial condition expressing

the number of times the basic operation is executed.

• Solve the recurrence or establish its order of growth.

 Example 1: Recursive evaluation of n!
Recursive definition of n!: F(n) = F(n-1)  n for n ≥ 1 and
F(0) = 1

To solve 3 factorial using recursion

M(n) ε Θ(n)
 Tower of Hanoi
A B C A B C

Given: Solving Strategy

Three Pegs A, B and C Step 1. Generalize: Consider n disks for all n  1.
Consider n=4
Peg A initially has n disks, Step 2. Find solutions to smaller instances:
Different size, stacked up, 1. n=1: “Move disk 1 from A to C”
Larger disks are below smaller disks.
2. n=2: “Move disk 1 from A to B”
Problem: “Move disk 2 from A to C”
To move the n disks to Peg C, with conditions “Move disk 1 from B to C”
3. n=3: “Move disk 1 from A to C”
1. Can move only one disk at a time. “Move disk 2 from A to B”
2. Smaller disk placed above larger disk. “Move disk 1 from C to B”
3. Can use other peg as intermediate.
“Move disk 3 from A to C”
General Method:
Move first (n-1) disks from A to B “Move disk 1 from B to A”
Move largest disk from A to C “Move disk 1 from B to C”
Move first (n-1) disks from B to C “Move disk 1 from A to C”
 Algorithm for Tower of Hanoi (Recursive)
Hanoi(n, A, B, C);
(* Move n disks from A to C via B *)
begin
if (n=1) then “Move top disk from A to C”
else (* when n>1 *)
Hanoi (n-1, A, C, B);
“Move top disk from A to C”
Hanoi (n-1, B, C, A);
endif
end;
Recursive relation for moving n discs
M(n) = M(n-1) + 1 + M(n-1) = 2M(n-1) + 1
IC: M(1) = 1
Solve using backward substitution
M(n) = 2M(n-1) + 1
= 2[2M(n-2) + 1] +1 = 22M(n-2) + 2+1
=22[2M(n-3) +1] + 2+1 = 23M(n-3) + 22 + 2 + 1
..
M(n) = 2iM(n-i) + ∑j=0-i2j = 2iM(n-i) + 2i-1
...
M(n) = 2n-1M(n-(n-1)) + 2n-1-1 = 2n-1M(1) + 2n-1-1 = 2n-1 + 2n-1-1 = 2n-1

M(n) ε Θ(2n)

Note: Recursive techniques are more complicated to solve by hand but very
simple to implement on a computer hardware.
 Brute Force
• Based directly on the problem’s statement and definitions of the concepts involved.
• Can solve small sized instances of a problem
• To compare an algorithm with more efficient ones.

Examples:
1. Computing an (a > 0, n a nonnegative integer)

2. Computing n!

3. Multiplying two matrices

4. Searching for a key of a given value in a list

 Brute-force Sorting Algorithm
Selection Sort Algorithm:
• Scan the array to find its smallest element and swap it with the first element.
• Start 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.
• 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[i-1] | A[i], . . . , A[min], . . ., A[n-1]
in their final positions
 Bubble Sort
• Compare adjacent elements and exchange them if out of order.
• Essentially, it bubbles up the largest element to the last position.
A0, … …, Aj <-> Aj+1, … …, An-i-1 | An-i ≤ … ≤ An-1
ALGORITHM BubbleSort(A[0..n-1])
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]
Example : 89, 45, 68, 90, 29, 34, 17

C(n) є Θ(n2)

Sworst(n) = C(n)
 Sequential Search

Input size: n
Basic op: <, ≠
Cworst(n) = n

Algorithm Compares successive elements of a input list with a given search

key K until
1. Match found: Successful Search.
2. List exhausted No match found: Unsuccessful Search.

Algorithm can be improved if Input list is already Sorted.

Searching stopped as soon as element equal to or greater than is encountered.
 Brute-force String Matching
• 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.

Time efficiency: Θ(mn) comparisons (in the worst case).

Θ(n+m) (in the average case)