MODULE 1

INTRODUCTION
1. Preheat the oven
2. Gather the ingredients
3. Measure out the ingredients
4. Mix together the ingredients to make the batter
5. Grease a pan
6. Pour the batter into the pan
7. Put the pan in the oven
8. Set a timer
9. When the timer goes off, take the pan out of the oven
10. Enjoy!
 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.
all algorithms must satisfy the following
criteria’s
1. Input
2. Output
3. Definiteness
4. Finiteness
5. Efffectiveness
• The nonambiguity requirement for each step of
an algorithm cannot be compromised.
• The range of inputs for which an algorithm works
has to be specified carefully.
• The same algorithm can be represented in several
different ways.
• Several algorithms for solving the same problem
• Algorithms for the same problem can be based
on very different ideas and can solve the problem
with dramatically different speeds.
 Euclid's algorithm for computing
gcd(m, n)
Step 1: If n = 0, return the value of m as the
answer and stop; otherwise, proceed to Step
2.
Step 2 :Divide m by n and assign the value of the
remainder to r.
Step 3 :Assign the value of n to m and the value
of r to n. Go to Step 1.
 ALGORITHM Euclid(m, n)
//Computes gcd(m, n) by Euclid's algorithm
//Input: Two nonnegative, not -both-zero integers
m and n
//Output: Greatest common divisor of m and n
while n != 0
do
r = m mod n
m =n
n =r
return m
 Consecutive integer checking
algorithm for computing gcd(m, n)
Step 1 :Assign the value of min{m, n) to t.
Step 2 :Divide m by t. If the remainder of this
division is 0, go to Step 3; otherwise, go to Step 4.
Step 3 :Divide n by t. If the remainder of this
division is 0, return the value of t as the answer
and stop; otherwise, proceed to Step 4.
Step 4 :Decrease the value of t by 1. Go to Step 2.
 Middle-school procedure for
computing gcd(m, n)
Step 1 :Find the prime factors of m.
Step 2: Find the prime factors of n.
Step 3 :Identify all the common factors in the two
prime expansions found in Step 1 and Step 2.
Step 4: Compute the product of all the common
factors and return it as the greatest common
divisor of the numbers given.
49.16.41,3,2,37,119,42,8,45,50,21,53,32,33,26,61,6
2,48,35,44,27,39,7,30,14
• The nonambiguity requirement for each step
of an algorithm cannot be compromised.
• The range of inputs for which an algorithm
works has to be specified carefully.
• The same algorithm can be represented in
several different ways.
• Several algorithms for solving the same
problem may exist.
• Algorithms for the same problem can be
based on very different ideas and can solve
the problem with dramatically different
speeds.
Fundamentals of Algorithmic Problem
Solving
 1. Understanding the Problem
• Before designing an algorithm understand
completely the problem given
• Identify the problem types and use existing
algorithm to find solution.
• Input (instance) to the problem and range of
the input get fixed
 2. Ascertaining the Capabilities of a
Computational Device
• you need to ascertain the capabilities of the
computational device the algorithm is
intended for.
• majority of algorithms in use today are still
destined to be programmed for a computer
resembling the von Neumann machine
• Select appropriate model from sequential
and parallel programming model
 Choosing between Exact and
Approximate Problem Solving
• The next principal decision is to choose
between solving the problem exactly or
solving it approximately.
• there are important problems that simply
cannot be solved exactly for most of their
instances
• available algorithms for solving a problem
exactly can be unacceptably slow
 Deciding on Appropriate Data
Structures
• data structures remain crucially important for
both design and analysis of algorithms.
Algorithms + Data Structures = Programs
 Algorithm Design Techniques
• An algorithm design technique is a general
approach to solving problems algorithmically
that is applicable to a variety of problems
from different areas of computing.
 Methods of Specifying an Algorithm
• Algorithms are specified by using 2 options
1. Natural language
2. Pseudo code
 Proving an Algorithm's Correctness
• After specifying an algorithm we have to
prove its correctness.
• The correctness is to prove that the algorithm
yields a required result for every Legitimate
input in a finite amount of time.
• Done using mathematical induction
 Analyzing an algorithm
• After correctness, efficiency has to be
estimated.
1. Time efficiency
2. Space efficiency.
3. Simplicity
 Code the algorithm
• Most algorithms are destined to be ultimately
implemented as computer programs
• Selection of programming language should
support the features mentioned in the design
phase.
 Analysis Framework
• a general framework for analyzing the
efficiency of algorithms consists of two kinds
of efficiency:
1. time efficiency
2. space efficiency
 Measuring an Input's Size
• almost all algorithms run longer on larger
inputs.
For example,
• it takes longer to sort larger arrays, multiply
larger matrices, and so on.
• Therefore, it is logical to investigate an
algorithm's efficiency as a function of some
parameter n indicating the algorithm's input
size.
• a special note about measuring the size of
inputs for algorithms involving properties of
numbers
• For such algorithms, computer scientists
prefer measuring size by the number b of bits
in the n's binary representation
• b= |log2n| +1.
 Units for Measuring Running time
• a second, a millisecond, and so on to measure the
running time of a program implementing the
algorithm
• There are obvious drawbacks to such an
approach
1.dependence on the speed of a particular
computer,
2.dependence on the quality of a program
implementing the algorithm
3.the compiler used in generating the machine code
• a metric that does not depend on these
extraneous factors.
• One possible approach is to count the number
of times each of the algorithm's operations is
executed. This approach is both excessively
difficult
• The thing to do is to identify the most
important operation of the algorithm, called
the basic operation,
• the operation contributing the most to the
total running time, and compute the number
of times the basic operation is executed.
49,16.41,1,6,50,12,405,121,408,45,3,42,8,40,5,4
00,14,30,31,13,35.7,27,39,35,43,62,9,33,53,32,4
4,52,22,29,63,28,34,59,61,26
• Cop- be the execution time of an algorithm's
basic operation on a particular computer,
• C(n) be the number of times this operation
needs to be executed for this algorithm.
• Then
• we can estimate the running time T (n) of a
program implementing this algorithm on that
computer by the formul
• T(n) =Cop C(n).
• 49,16.41,1,6,50,12,3,42,8,40,5,400,14,30,31,13,3
5.7,27,39,35,62,9,44,52, 46.47
 Order of growth
• Used to measure the behavior of an algorithm
• the "order of growth" refers to the rate at
which the resource requirements (such as
time or space) of an algorithm increase as the
input size grows.
• It helps in understanding how the algorithm
will perform as the input size becomes very
large.
• It is expressed by using classes called basic
efficiency classes
 Basic efficiency classes
1 constant Best case
log n logarithmic Divide
Ignore part

n linear Examine each

Online/Stream Algs

n log n n-log-n or Divide

linearithmic Use all parts

n2 quadratic Nested loops

n3 cubic Nested loops

nk Examine all k-tuples

2n exponential All subsets

n! factorial All permutations

30
*Figure 1.7:Function values (p.38)

CHAPTER 1 31
Worst-Case, Best-Case, and Average-Case
Efficiencies
• an algorithm's efficiency as a function of a
parameter indicating the size of the
algorithm's input.
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: 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
return i
else
return -1
• The worst-case efficiency of an algorithm is its efficiency
for the worst-case input of size n, which is an input (or
inputs) of size n for which the algorithm runs the longest
among all possible inputs of that size.
• analyze the algorithm to see what kind of inputs yield the
largest value of the basic operation's count C(n) among
all possible inputs of size n and then compute this worst-
case value Cworst(n)

• C worst(n)=n
• The best-case efficiency of an algorithm is its
efficiency for the best-case input of size n,
which is an input (or inputs) of size n for which
the algorithm runs the fastest among all
possible inputs of that size
• for sequential search, best-case inputs are lists
of size n with their first elements equal to a
search key; accordingly, Cbest(n) = 1.
Asymptotic Notations
 Asymptotic Notation (O)
Big O:A function t(n) is said to be in O(g(n)),
denoted t(n) E O(g(n)),such that there exist a
positive constant c and nonnegative integer n0
satisfying the constraint
t(n)  cg(n) for all n, n  n0
 Big-Oh

Big-Oh notation: t(n) ∈ O(g(n))

Big Ω:A function t(n) is said to be in Ω(g(n)),
denoted t(n)  Ω(g(n)),such that there exist a
positive constant c and nonnegative integer n0
satisfying the constraint
t(n)>=c g(n) for all n, n  n0
 Big theta
• A function t(n) is said to be in E>(g(n)),
denoted t(n) E E>(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 constant c1 and c2 and
some nonnegative integer n0 such that c2g(n)
s t(n) s qg(11) for all 11 2: 110.
 Using property involving the
asymptotic notation
Theorem : If t1(n)  O(g1(n)) and t2(n)  O(g
2(n)), then t1(n) + t2(n)  O(max{g1(n),
g2(n))).
Proof:
Lets take four arbitrary real numbers a1,
b1,a2,b2
if a1 <= b1 and a 2 <= b 2, then
a1 + a2 <= 2 max{b 1, b2}
• Since If t1(n)  O(g1(n)) there exist some
positive constant c1 and some nonnegative
integer n1 such that
t1(n)  c1g1(n) for all n  n1
Similarly
t2(n)  O(g2(n))

t2(n)  c2g2(n) for all n  n2

Establishing order of growth using limits
0 order of growth of t(n) < order of growth of g(n)

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

n→∞
∞ order of growth of t(n) > order of growth of g(n)

Examples:
• 10n vs. n2

• n(n+1)/2 vs. n2

44
Stirling’s formula

For large values of n

1.Compare the orders of growth of 1/2n(n - 1)
and n2
2. n! and 2^n
 Properties of asymptotic notations
• Transitivity
f(n) = (g(n)) and g(n) = (h(n))
=> f(n) = (h(n))
(holds true for o, O, , and  as well).

• Symmetry
f(n) = (g(n)) if and only if g(n) = (f(n))

6/2/2024 47
48
Mathematical Analysis of Nonrecursive
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 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.
Example 1: Maximum element

51
Example 2: Element uniqueness
problem

. 52
Example 3: Matrix multiplication
 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  Ln/2
return count
 Mathematical Analysis of Recursive
Algorithms
• Compute the factorial function F(n) = n! for an
arbitrary nonnegative integer n.
Since
n!=1· ... ·(n-l)·n=(n-l)!·n for all n>=1 and
0! = 1 by definition,
we can compute F(n) = F(n- 1) · n
 General Plan for Analyzing 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.
• 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
 Tower of Hanoi Problem
• In this problem, we have n disks of different sizes and
three pegs.
• Initially, all the disks are on the first peg in order of
size, the largest on the bottom and the smallest on
top.
• The goal is to move all the disks to the third peg,
using the second one as an auxiliary if necessary.
• We can move only one disk at a time, and it is
forbidden to place a larger disk on top of a smaller
one.

Department of ISE Department of ISE BMS Institute of TechnologyBMS

andInstitute
Mgmt of Technology and Mgmt
60
 Example 2: The Tower of Hanoi
Puzzle

1 3

Recurrence for number of moves:

Department of ISE Department of ISE BMS Institute of TechnologyBMS

andInstitute
Mgmt of Technology and Mgmt
61
Department of ISE Department of ISE BMS Institute of TechnologyBMS
andInstitute
Mgmt of Technology and Mgmt
62
Solving recurrence for number of
moves

BMS Institute of Technology and Mgmt

• ALGORITHM BinRec(n)
//Input: A positive decimal integer n //Output:
The number of binary digits in n's binary
representation
if n = 1 return 1
else
return BinRec(Ln/2J) + 1
 Brute Force
A straightforward approach, usually based directly on the
problem’s statement and definitions of the concepts involved

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

Department of ISE BMS Institute of Technology and Mgmt

 Analysis of Selection Sort

Time efficiency: Θ(n^2)

 ALGORITHM SequentialSearch2(A[O .. n], K)
//Searches for a given value in a given array by sequential search
//Input: An array A[O .. n ] and a search key K
//Output: The index of the first element of A that matches K II or -1
if there are no matching elements
A[n]k
i0
while A[i]!=k do
ii+1
If i < n return i
else
return -1
 Pseudocode and Efficiency

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