PES Institute of Technology and Management

NH-206, Sagar Road,Shivamogga-577204

Department of Computer Science and Engineering

Affiliated to

VISVESVARAYA TECHNOLOGICAL UNIVERSITY

Jnana Sangama, Belagavi, Karnataka –590018c

Lecture Notes
on

Module 1-Analysis and Design of Algorithms

(BCS401)
2022 Scheme

Prepared By,
Mrs. Prathibha S ,
Assistant Professor,
Department of CSE,PESITM
 Module 1-ADA (BCS401)

MODULE -1
1. INTRODUCTION

What is an lgorithm?

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 finExite amount of time.
Algorithms should satisfy the following criteria :

1. Input: Zero or more quantities are externally supplied.

2. Ouput: At least one quantity is produced.

3. Definiteness : Each instruction is clear and unambiguous.

4. Finiteness: If we trace out the instruction of an algorithm For all input cases, the
algorithm must terminate after a finite number of steps.

5. EFFECTIVENESS Every nstruction must very basic so that it can be carried out,
in principle, by a person using only pencil & paper.

Algorithm Design And Analysis Process:

 Understanding the Problem - From a practical perspective, the first thing you need
to do before designing an algorithm is to understand completely the problem
[Link] input to an algorithm specifies an instance of the problem the algorithm
solves. It is very important to specify exactly the set of instances the algorithm needs
to handle.
 Ascertaining the Capabilities of the Computational Device - Once you completely
understand a problem, you need to ascertain the capabilities of the computational
device the algorithm is intended for. Select appropriate model from sequential or
parallel programming model.
 Choosing between Exact and Approximate Problem Solving – The next principal
decision is to choose between solving the problem exactly and solving it
approximately. Because, there are important problems that simply cannot be solved
exactly for most of their instances and some of the available algorithms for solving a
problem exactly can be unacceptably slow because of the problem’s intrinsic
complexity.
 Algorithm Design Technique- An algorithm design technique(or“strategy”or
“paradigm”) is a general approach to solving problems algorithmically that is
applicable toavariety of problems from different areas of [Link] provide
guidancefor designing algorithm for new problems.

PESITM, Dept of CSE Prepared By, Prathibha S Page 2

 Module 1-ADA (BCS401)

• Designing an Algorithm and Data Structures- One should pay close attention to
choosing data structures appropriate for the operations performed by the algorithm.
For example, the sieve of Eratosthenes would run longer if we used a linked list
instead of an array in its implementation. Algorithms + Data Structures = Programs.
 Methods of Specifying an Algorith- Once you have designed an algorithm; you need
to specify it in some [Link] is a mixture of a natural language and
programming language like constructs. Pseudocode is usually more precise than
natural language, and its usage often yields more effective algorithm descriptions.

 Proving an Algorithm’s Correctness - Once an algorithm has been specified, you

have to prove its correctness. That is, you have to prove that the algorithm yields a
required result for every legitimate input in a finite amount of time. For some
algorithms, a proof of correctness is quite easy; for others, it can be quite complex. A
common technique for proving correctness is to use mathematical induction because
an algorithm’s iterations provide a natural sequence of steps needed for such proofs.

 Analyzing an Algorithm - After correctness, by far the most important is efficiency.

In fact, there are two kinds of algorithm efficiency: time efficiency, indicating how
fast the algorithm runs, and space efficiency, indicatinghow much extra memoryit
uses. Another desirable characteristic of an algorithm is simplicity. Unlike efficiency,
which can be preciselydefined and investigated with mathematical rigor, simplicity,
like beauty, is to a considerable degree in the eye of the beholder.

 Coding an Algorithm - Most algorithms are destined to be ultimately implemented

as computer programs. Implementing an algorithm correctly is necessary but not
sufficient: you would not like to diminish your algorithm’s power by an inefficient
implementation. Modern compilers do provide a certain safety net in this regard,
especially when they are used in their code optimization mode.

PESITM, Dept of CSE Prepared By, Prathibha S Page 3

 Module 1-ADA (BCS401)

IMVarious problems to be solved in Computer Science:

1. Sorting
2. Searching
3. String Processing
4. Graph problems
5. Geometrical Problems
6. Numerical Problems
7. Combinatorial Problems

PESITM, Dept of CSE Prepared By, Prathibha S Page 4

 Module 1-ADA (BCS401)

There are two kinds of efficiency:

♦ Time efficiency-indicates how fast an algorithm in question runs.
♦ Space efficiency-deals with the extra space the algorithm requires.

Units for Measuring Running Time

To measure an algorithm's efficiency, we would like to have a metric that does not
depend on these extraneous factors.(like processor speed). One possible approach is to
count the number of times each of the algorithm's operations is executed. This approach is
both excessively difficult and, as we shall see, usually unnecessary. 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.

Orders ofGrowth
Why this emphasis on the count's order of growth for large input sizes? Because for large
values of n, it is the function's order of growth that counts: just look at table which
contains values of a few functions particularly important for analysis of algorithms.




Worst-Case, Best-Case, AverageCaseEfficiencies
♦Algorithm efficiency depends on the inputsize n. And for some algorithms
efficiency not only on input size but also on the specifics of particular or type of

PESITM, Dept of CSE Prepared By, Prathibha S Page 5

 Module 1-ADA (BCS401)

input.
♦We have best, worst&average ecase efficiencies.
Worst-case efficiency: Efficiency(numberoftimesthebasicoperationwillbeexecuted)
for the worst case input of size [Link] algorithm runs the longest among all possible
inputs of size n.

Best-case efficiency: Efficiency(number of times the basic operation will be

executed)for the best case input of size [Link] algorithm runs the fastest among all
possible inputs of size n.

Average-case efficiency: Average time taken(number of times the basic operation will be
executed)to solve all the possible instances(random)of the input.

ASYMPTOTIC NOTATIONS

The efficiency analysis framework concentrates on the order of growth of an

algorithm‘s basic operation count as the principal indicator of the algorithm‘s efficiency.
To compare and rank such orders of growth, computer scientists use three
notations: O(bigoh),Ω(bigomega),andΘ (big theta).

Big-O Notation (O-notation):

It returns the highest possible output value (big-O)for a given input.

The execution time serves as an upper bound on the algorithm’s time complexity.

If f(n) describes the running time of an algorithm, f(n) is O(g(n)) if there exist a positive
constant C and n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0

PESITM, Dept of CSE Prepared By, Prathibha S Page 6

 Module 1-ADA (BCS401)

Omega Notation (Ω-Notation):

The execution time serves as a lower bound on the algorithm’s time complexity.
execution in the shortest amount of time.

Let g and f be the function from the set of natural numbers to itself. The function f is said
to be Ω(g), if there is a constant c > 0 and a natural number n0 such that c*g(n) ≤ f(n) for
all n ≥ n0

Theta Notation (Θ-Notation) :

Theta notation encloses the function from above and below. Since it represents the
upper and the lower bound of the running time of an algorithm, it is used for
analyzing the average-case complexity of an algorithm.

Let g and f be the function from the set of natural numbers to itself. The function f is said
to be Θ(g), if there are constants c1, c2 > 0 and a natural number n0 such that c1* g(n) ≤
f(n) ≤ c2 * g(n) for all n ≥ n0.

PESITM, Dept of CSE Prepared By, Prathibha S Page 7

 Module 1-ADA (BCS401)

Analysis of Non-recursiveAlgorithms
Genera lPlan for Analyzing the Time Efficiency of Non recursive Algorithms
1. Decide on a parameter(or parameters)indicating an input’ssize.
2. Identify the algorithm’s basic operation.(As a rule,it is located in innermost loop.)
3. Check whether the number of times the basic operation is executed depends only
on the size of an [Link] it also depends on some additional property, the worst-
case, average case and if necessary , best case effeciencies have to be
investigated .Set up a sum expressing the number of times the algorithm’ basic
operation is executed.
4. Using standard formulas and rules of sum manipulation, either find a close formula
for the counter or at the very least ,establish its order of growth.

u Example-1:To find maximum element in the given array.

Mathematical Analysis
1. Input size is the number of elements=n(size of the array)
2. Comparison statement is considered to be the basic operation of the
algorithm.
3. No best, worst, average cases-because the number of comparisons will be same for
all arrays of size n and it is not dependent on type of input.
4. Let C(n) denotes number of comparisons: Algorithm makes one comparison on each
execution of the loop, which is repeated for each value of the loop‘s variable

C(n)= n

5. Order of growth or Time complexity of algorithm belongs to Ɵ(n)

PESITM, Dept of CSE Prepared By, Prathibha S Page 8
 Module 1-ADA (BCS401)

Example-2:To check whether all the elements in the given array are distinct

Mathematical Analysis

1. Input size is the number of elements=n(size of the array)

2. Comparison statement is considered to be the basic operation of the
algorithm.
3. Best, worst, average cases-exist .because the number of comparisons will be same
for all arrays of size n and it is not dependent on type of input.
4. Let C(n) denotes number of comparisons:
Best case exist when first pair of elements are unique with one comparison . C(n)=1
Worst Case exist with maximum number of comparisons when all elements in array are
distinct

[Link] of growth or Time complexity of algorithm belongs to Ɵ(n2)

PESITM, Dept of CSE Prepared By, Prathibha S Page 9

 Module 1-ADA (BCS401)

Example-3:To perfor mmatrix multiplication

Algorithm

Mathematical Analysis
1. Input size is order of the square matrix n(no of rows or columns)
2. Multiplication is considered to be the basic operation of the algorithm.
[Link] best, worst, average cases-exist .
[Link] M(n) denotes number of comparisons:

[Link] of growth or Time complexity of algorithm belongs to Ɵ(n3)

Example-4:To count the bits in the binary representation

Algorithm:

PESITM, Dept of CSE Prepared By, Prathibha S Page 10

 Module 1-ADA (BCS401)

PESITM, Dept of CSE Prepared By, Prathibha S Page 11

 Module 1-ADA (BCS401)

Mathematical Analysis
1. Input size is decimal number n.
2. Division by number by 2 is considered to be the basic operation of the algorithm.
3. No best, worst, average cases-exist .

4. The basic operation is counted by count=count+1which repeats

5. Order of growth or Time complexity of algorithm belongs to Ɵ(log n)

Analysis of Recursive Algorithms

General plan for analyzing the time efficiency of recursive algorithms
1. Decide on a parameter(or parameters)indicating an input’ss ize.
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. Setup are recurrence relation,
with an appropriate initial condition, for the number of times the basic operation is
executed.
4. Solve the recurrence to determine the order of growth of its solution.

Example1:

PESITM, Dept of CSE Prepared By, Prathibha S Page 12

 Module 1-ADA (BCS401)

Mathematical Analysis
[Link] size is positive number n.
[Link] basic operation is multiplication .
3. No best, worst, average cases-exist .

4. Set up the recurrence relation as :

The number of multiplications M(n) needed to compute it must satisfy the equality

Based on this, the recurrence relation is

Solving by Backward Substtituion,

5. Time complexity depends on no of multiplications .

So,Order of growth or Time complexity of algorithm belongs to Ɵ(n)

Example-2:Tower of Hanoi puzzle

Tower of Hanoi is a mathematical puzzle where we have three rods (A, B, and C)
and N disks. Initially, all the disks are stacked in decreasing value of diameter i.e., the
smallest disk is placed on the top and they are on rod A. The objective of the puzzle is to
move the entire stack to another rod (here considered C), obeying the following simple
rules:
 Only one disk can be moved at a time.
 Each move consists of taking the upper disk from one of the stacks and placing it on
top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
 No disk may be placed on top of a smaller disk.

The idea is to use the helper node to reach the destination using recursion. Below is the
pattern for this problem:
 Shift ‘N-1’ disks from ‘A’ to ‘B’, using C.
 Shift last disk from ‘A’ to ‘C’.

PESITM, Dept of CSE Prepared By, Prathibha S Page 13

 Module 1-ADA (BCS401)

 Shift ‘N-1’ disks from ‘B’ to ‘C’, using A

Mathematical Analysis

[Link] size is n, no of disks.

[Link] basic operation is movement of disks..
3. No best, worst, average cases-exist .

4. Set up the recurrence relation as:

The number of moves M(n)depends only on [Link]

oi puzzle The number of movesM(n)depends only on [Link]

We have the following recurrence relation for the number of movesM(n):

Solving by Backward Substitution

After i substitutions, we get

If i=n-1,

5. Time complexity depends on no of movements .

So, Order of growth or Time complexity of algorithm belongs to Ɵ(2n)

PESITM, Dept of CSE Prepared By, Prathibha S Page 14

 Module 1-ADA (BCS401)

EXAMPLE 3 :A recursive versionof the algorithm that computes number of binary

digits in n‘sbinary representation.

Mathematical Analysis
[Link] size is positive number n.
[Link] by number by 2 is considered to be the basic operation of the algorithm.
3. No best, worst, average cases-exist .
4. Set up the recurrence relation as:

The number of additions gives the count of bits so A(n) will be

A(1)=0

, Taking n=2k

Solving by Backward Substitution

5. Time complexity depends on no of additions.

So, Order of growth or Time complexity of algorithm belongs to Ɵ(log n)

PESITM, Dept of CSE Prepared By, Prathibha S Page 15