Design and Analysis of Algorithms

MODULE-1
Dr. Shivanna K,
Associate Professor,
Computer Science and Engineering,
Sahyadri College of Engineering and Management,
Adyar, Mangalore-575007.
Email: shivannak4phd@[Link]
Mobile: +91-9686194749
1
What Is an Algorithm?
➢ An algorithm is a sequence of unambiguous instructions for
solving a problem, i.e., for obtaining a required output for
any legitimate input in a finite amount of time. The notion
of an algorithm is:

2
 Properties of an Algorithm

1. The nonambiguity requirement for each step of an algorithm cannot

be compromised.
2. The range of inputs for which an algorithm works has to be specified
carefully.
3. The same algorithm can be represented in several different ways.
4. There may exist several algorithms for solving the same problem.
5. Algorithms for the same problem can be based on very different ideas
and can solve the problem with dramatically different speeds.

3
Euclid’s algorithm for computing gcd(m, n)
➢ Step 1 If n = 0, return the value of m as the answer and
stop; otherwise, proceed to Step 2.
➢ Step 2 Divide m by n and assign the value of the remainder
to r.
➢ Step 3 Assign the value of n to m and the value of r to n. Go
to Step 1.

4
ALGORITHM Euclid(m, n)
➢ //Computes gcd(m, n) by Euclid’s algorithm
➢ //Input: Two nonnegative, not-both-zero integers m and n
➢ //Output: Greatest common divisor of m and n
➢ while n ≠ 0 do
➢ r ←m mod n
➢ m←n
➢ n←r
➢ return m
5
Middle-school procedure for computing gcd (m, n)
Step 1 Find the prime factors of m.
Step 2 Find the prime factors of n.
Step 3 Identify all the common factors in the two prime expansions
found in Step 1 and Step 2. (If p is a common factor occurring pm
and pn times in m and n, respectively, it should be repeated min{pm,
pn} times.)
Step 4 Compute the product of all the common factors and return it
as the greatest common divisor of the numbers given. Thus, for the
numbers 60 and 24, we get
60 = 2 . 2 . 3 . 5
24 = 2 . 2 . 2 . 3
gcd(60, 24) = 2 . 2 . 3 = 12. 6
Fundamentals of Algorithmic Problem Solving

7
Algorithm design and analysis process.
1. Understanding the Problem
2. Ascertaining the Capabilities of the Computational Device
3. Choosing between Exact and Approximate Problem Solving
4. Algorithm Design Techniques
5. Designing an Algorithm and Data Structures
6. Methods of Specifying an Algorithm
7. Proving an Algorithm’s Correctness
8. Analyzing an Algorithm
9. Coding an Algorithm

8
 The Analysis Framework
1. Measuring an Input’s Size
2. Measuring Space Complexity
3. Units for Measuring Running Time
4. Orders of Growth
5. Worst-Case, Best-Case, and Average-Case Efficiencies

9
Basic Efficiency Classes

10
Basic asymptotic efficiency classes
Mathematical Analysis of Nonrecursive Algorithms
 EXAMPLE 1 Consider the problem of finding the value of the
largest element in a list of n numbers.
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
11
General Plan for Analyzing the Time Efficiency of
Nonrecursive Algorithms
1. Decide on a parameter (or parameters) indicating an input’s size.
2. Identify the algorithm’s basic operation. (As a rule, it is located in the
innermost loop.)
3. Check whether the number of times the basic operation is executed
depends only on the size of an input. If it also depends on some
additional property, the worst-case, average-case, and, if necessary,
best-case efficiencies have to be investigated separately.
4. Set up a sum expressing the number of times the algorithm’s basic
operation is executed.
5. Using standard formulas and rules of sum manipulation, either find a
closed form formula for the count or, at the very least, establish its
order of growth. 12
 EXAMPLE 2 Consider the element uniqueness problem: check
whether all the elements in a given array of n elements are distinct.
This problem can be solved by the following straightforward
algorithm.
ALGORITHM UniqueElements(A[0..n − 1])
//Determines 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
13
return true
14
15
EXAMPLE 4 The following algorithm finds the number of
binary digits in the binary representation of a positive
decimal integer.
ALGORITHM Binary(n)
//Input: A positive decimal integer n
//Output: The number of binary digits in n’s binary representation
count ←1
while n > 1 do
count ←count + 1
n←n/2
return count
16
Mathematical Analysis of Recursive Algorithms
EXAMPLE 1 Compute the factorial function F(n) = n! for an
arbitrary nonnegative integer n. Since n!= 1 . . . . . (n − 1) . n = (n −
1)! . n for n ≥ 1 and 0!= 1 by definition, we can compute F(n) = F(n
− 1) . n with the following recursive algorithm.
ALGORITHM F(n)
//Computes n! recursively
//Input: A nonnegative integer n
//Output: The value of n!
if n = 0
return 1
else
return F(n − 1) ∗ n 17
General Plan for Analyzing the Time Efficiency of
Recursive Algorithms
1. Decide on a parameter (or parameters) indicating an input’s size.
2. Identify the algorithm’s basic operation.
3. Check whether the number of times the basic operation is executed
can vary on different inputs of the same size; if it can, the worst-case,
average-case, and best-case efficiencies must be investigated
separately.
4. Set up a recurrence relation, with an appropriate initial condition, for
the number of times the basic operation is executed.
5. Solve the recurrence or, at least, ascertain the order of growth of its
solution.
18
Brute force design techniques:
 Brute force is a straightforward approach to solving a problem,
usually directly based on the problem statement and definitions of
the concepts involved.
 Checks every possible solution until the correct one is found.
 In computer science, 'Brute Force' refers to a straightforward
approach to problem-solving, directly addressing the problem's
possible solutions without applying any strategic logic or
established algorithms, generating and testing all possible
solutions until the correct one is found.

19
Brute-Force 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 20

return −1
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 nondecreasing order
for i ←0 to n − 2 do
min←i
for j ←i + 1 to n − 1 do
if A[j ]<A[min]
min←j
swap A[i] and A[min]
21