Module-1:Introduction to Algorithm

Contents

1. Introduction 3.5. Mathematical analysis

1.1. What is an Algorithm? 4. Important Problem Types
1.2. Algorithm Specification 4.1. Sorting
1.3. Analysis Framework 4.2. Searching
2. Performance Analysis 4.3. String processing
2.1. Space complexity 4.4. Graph Problems
2.2. Time complexity 4.5. Combinatorial Problems
3. Asymptotic Notations 5. Fundamental Data Structures
3.1. Big-Oh notation 5.1. Linear Data Structures
3.2. Omega notation 5.2. Graphs
3.3. Theta notation 5.3. Trees
3.4. Little-oh notation 5.4. Sets and Dictionaries
 MODULE 1: Introduction to Algorithms

Module-1: Introduction
1.1 Introduction

1.1.1 What is an Algorithm?

Algorithm: An algorithm is a finite sequence of unambiguous instructions to solve a
particular problem.

Input. Zero or more quantities are externally supplied.

a. Output. At least one quantity is produced.
b. Definiteness. Each instruction is clear and unambiguous. It must be perfectly clear
what should be done.
c. Finiteness. If we trace out the instruction of an algorithm, then for all cases, the
algorithm terminates after a finite number of steps.
d. Effectiveness. Every instruction must be very basic so that it can be carried out, in
principle, by a person using only pencil and paper. It is not enough that each
operation be definite as in criterion c; it also must be feasible.
1.1.2. Algorithm Specification
An algorithm can be specified in
1) Simple English
2) Graphical representation like flow chart
3) Programming language like c++/java
4) Combination of above methods.
Example: Combination of simple English and C++, the algorithm for selection sort is
specified as follows.

Example: In C++ the same algorithm can be specified as follows. Here Type is a basic or user
defined data type.
 MODULE 1: Introduction to Algorithms

1.1.3. Analysis Framework

Measuring an Input’s Size
It is observed that 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.
There are situations, where the choice of a parameter indicating an input size does matter.
The choice of an appropriate size metric can be influenced by operations of the algorithm in
question. For example, how should we measure an input's size for a spell-checking
algorithm? If the algorithm examines individual characters of its input, then we should
measure the size by the number of characters; if it works by processing words, we should
count their number in the input.
We should make a special note about measuring the size of inputs for algorithms involving
properties of numbers (e.g., checking whether a given integer n is prime). For such
algorithms, computer scientists prefer measuring size by the number b of bits in the n's binary
representation: b = [log2 n ] + 1. This metric usually gives a better idea about the efficiency
of algorithms in question.

Units for Measuring Running lime

To measure an algorithm's efficiency, we would like to have 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 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.
For example, most sorting algorithms work by comparing elements (keys) of a list being
sorted with each other; for such algorithms, the basic operation is a key comparison.
As another example, algorithms for matrix multiplication and polynomial evaluation
require two arithmetic operations: multiplication and addition.
Let cop be the execution time of an algorithm's basic operation on a particular computer, and
let 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 formula:
T(n) = copC(n)
Unless n is extremely large or very small, the formula can give a reasonable estimate of the
algorithm's running time.
It is for these reasons that the efficiency analysis framework ignores multiplicative constants
and concentrates on the count's order of growth to within a constant multiple for large-size
inputs.
 MODULE 1: Introduction to Algorithms

Orders of Growth
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.
Table: Values of several functions important for analysis of algorithms

Algorithms that require an exponential number of operations are practical for solving only
problems of very small sizes.

1.2. Performance Analysis

There are two kinds of efficiency: time efficiency and space efficiency.
 Time efficiency indicates how fast an algorithm in question runs;
 Space efficiency deals with the extra space the algorithm requires.
In the early days of electronic computing, both resources time and space were at a premium.
The research experience has shown that for most problems, we can achieve much more
spectacular progress in speed than inspace. Therefore, we primarily concentrate on time
efficiency.
1.2.1 Space complexity
Total amount of computer memory required by an algorithm to complete its execution is called
as space complexity of that algorithm. The Space required by an algorithm is the sum of
following components
 A fixed part that is independent of the input and output. This includes memory space
for codes, variables, constants and so on.
 A variable part that depends on the input, output and recursion stack. ( We call these
parameters as instance characteristics)
Space requirement S(P) of an algorithm P, S(P) = c + Sp where c is a constant depends on the
fixed part, Sp is the instance characteristics\
Example-1: Consider following algorithm abc()

Here fixed component depends on the size of a, b and c. Also instance characteristics Sp=0
 MODULE 1: Introduction to Algorithms

Example-2: Let us consider the algorithm to find sum of array. For the algorithm given here
the problem instances are characterized by n, the number of elements to be summed. The space
needed by a[ ]depends on n. So the space complexity can be written as; Ssum(n) ≥ (n+3); n for
a[ ], One each for n, i and s.

1.2.2 Time complexity

Usually, the execution time or run-time of the program is refereed as its time complexity
denoted by tp(instance characteristics). This is the sum of the time taken to execute all
instructions in the program. Exact estimation runtime is a complex task, as the number of
instructions executed is dependent on the input data. Also different instructions will take
different time to execute. So for the estimation of the time complexity we count only the
number of program steps. We can determine the steps needed by a program to solve a
particular problem instance in two ways.
Method-1: We introduce a new variable count to the program which is initialized to zero. We
also introduce statements to increment count by an appropriate amount into the program. So
when each time original program executes, the count also incremented by the step count.
Example: Consider the algorithm sum(). After the introduction of the count the program will
be as follows. We can estimate that invocation of sum() executes total number of 2n+3 steps.

Method-2: Determine the step count of an algorithm by building a table in which we list the
total number of steps contributed by each statement. An example is shown below. The code
will find the sum of n numbers
 MODULE 1: Introduction to Algorithms

Example: Matrix addition

The above method is both excessively difficult and, 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.

Trade-off
There is often a time-space-tradeoff involved in a problem, that is, it cannot be solved with
few computing time and low memory consumption. One has to make a compromise and to
exchange computing time for memory consumption or vice versa, depending on which
algorithm one chooses and how one parameterizes it.

1.3. 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(big oh), Ω(big omega),
Θ (big theta) and o(little oh)
1.3.1. Big-Oh notation
Definition: A function t(n) is said to be in O(g(n)),
denoted t(n)∈O(g(n)), if t (n) is bounded above by
some constant multiple of g(n) for all large n, i.e.,
if there exist some positive constant c and some
nonnegative integer n0 such that
t(n) ≤ cg(n) for all n ≥ n0.

Informally, O(g(n)) is the set of all functions with a lower or same order of growth as g(n).
Note that the definition gives us a lot of freedom in choosing specific values for constants c
and n0.

Examples: n c 0(n2 ), 100n + 5 c 0(n2 ), 1 n(n — 1)c0(n2 )

2

n3 ∉ 0(n2 ), 0.00001n3 ∉ 0(n2 ), n4 + n + 1 ∉ 0(n2 )

 MODULE 1: Introduction to Algorithms

Strategies to prove Big-O: Sometimes the easiest way to prove that f (n) = O(g(n)) is to take c
to be the sum of the positive coefficients off(n). We can usually ignore the negative coefficients.

Example: To prove 100n + 5 ∈ O(n2)

100n + 5 ≤ 105n2. (c=105, n0=1)
Example: To prove n2 + n = O(n3)
Take c = 1+1=2, if n ≥n0=1, then n2 + n =
O(n3)

i) Prove 3n+2=O(n) ii) Prove 1000n2+100n-6 = O(n2)

1.3.2. Omega notation
Definition: A function t(n) is said to be in Ω(g(n)),
denoted t(n)∈Ω(g(n)), if t(n) is bounded below by
some positive constant multiple of g(n) for all large
n,i.e., if there exist some positive constant c and
some nonnegative integer n0 such that t(n) ≥ c g(n)
for all n ≥ n0.

Here is an example of the formal proof that n3 ∈Ω(n2):n3 ≥ n2 for all n ≥ 0, i.e., we can
select c = 1 and n0 = 0.

Example:

Example: To prove n3 + 4n2 = Ω(n2)

We see that, if n≥0, n3+4n2≥ n3≥ n2; Therefore n3+4n2 ≥ 1n2for alln≥0
Thus, we have shown that n3+4n2 =Ω(n2) where c = 1 & n0=0

1.3.3. Theta notation

A function t(n) is said to be in Θ(g(n)), denoted t(n)
∈ Θ(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 constants
c1 and c2 and some nonnegative integer n0 such that
c2g(n) ≤ t(n) ≤c1g(n) for all n ≥ n0.
 MODULE 1: Introduction to Algorithms

Example: n2 + 5n + 7 = Θ(n2)

Strategies for Ω and Θ

 Proving that a f(n) = Ω(g(n)) often requires more thought.
– Quite often, we have to pick c < 1.
– A good strategy is to pick a value of c which you think will work, and determine
which value of n0 is needed.
– Being able to do a little algebra helps.
– We can sometimes simplify by ignoring terms of f(n) with the positive
coefficients.

 The following theorem shows us that proving f(n) = Θ(g(n)) is nothing new:
Theorem: f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) =
Ω(g(n)).
Thus, we just apply the previous two strategies.
 MODULE 1: Introduction to Algorithms

Theorem: If t1(n) ∈ O(g1(n)) and t2(n) ∈ O(g2(n)), then t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}).
(The analogous assertions are true for the Ω and Ө notations as well.)
Proof: The proof extends to orders of growth the following simple fact about four arbitrary
real numbers a1, b1, a2, b2: if a1 ≤ b1 and a2 ≤ b2, then a1 + a2 ≤ 2 max{b1, b2}.
Since 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, since t2(n) ∈ O(g2(n)), t2(n) ≤ c2g2(n) for all n ≥ n2.
Let us denote c3 = max{c1, c2} and consider n ≥ max{n1, n2} so that we can use both

inequalities. Adding them yields the following:

t1(n) + t2(n) ≤ c1g1(n) + c2g2(n)
≤ c3 g1(n) + c3g2(n) = c3[g1(n) + g2(n)]
≤ c32 max{g1(n), g2(n)}.
Hence, t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}), with the constants c and n0 required by the O
definition being 2c3 = 2 max{c1, c2} and max{n1, n2}, respectively.

3.4. Little Oh The function f(n)= o(g(n)) [ i.e f of n is a little oh of g of n ] if and only if
ƒ(n)
lim =0
n→
œ g(n)
Example:

For comparing the order of growth limit is used

If the case-1 holds good in the above limit, we represent it by little-oh.

 MODULE 1: Introduction to Algorithms

1.3.5. Basic asymptotic efficiency Classes

Class Name Comments
 MODULE 1: Introduction to Algorithms

1.3.6. Mathematical Analysis of Non-recursive & Recursive Algorithms

Analysis of Non-recursive Algorithms
General Plan for Analyzing the Time Efficiency of Non-recursive 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 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 closedform
formula for the count or, at the very least, establish its order of growth.
Example-1: To find maximum element in the given array

Here comparison is the basic operation. Note that number of comparisions will be same for
all arrays of size n. Therefore, no need to distinguish worst, best and average cases. Total
number of basic operations (comparison)
are,

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

Here basic operation is comparison. The maximum no. of comparisons happen in the worst
case. (i.e. all the elements in the array are distinct and algorithms return true).
Total number of basic operations (comparison) in the worst case are,
 MODULE 1: Introduction to Algorithms

1
Other than the worst case, the total comparisons are less than n2. For example if the first
2
two elements of the array are equal, only one comparison is computed.
So in general C(n) =O(n2)
Example-3: To perform matrix multiplication

Number of basic operations

(multiplications) is

Total running time:

Suppose if we take into account of addition; Algorithm also have same number of additions
A(n) = n3
Total running time:

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

 MODULE 1: Introduction to Algorithms

The basic operation is count=count + 1 repeats no. of times

Analysis of Recursive Algorithms
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. Set up a recurrence relation, with an
appropriate initial condition, for the number of times the basic operation is executed.
4. Solve the recurrence or, at least, ascertain the order of growth of its solution.
Example-1

Since the function F(n) is computed according to the formula

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

Such equations are called recurrence relations

Condition that makes the algorithm stop if n = 0 return 1. Thus recurrence relation and initial
condition for the algorithm’s number of multiplications M(n) can be stated as

We can use backward substitutions method to solve this

….
 MODULE 1: Introduction to Algorithms

Example-2: Tower of Hanoi puzzle. In this puzzle, There are n disks of different sizes that
canslide onto any of 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. The problem has an elegant recursive
solution, which is illustrated in Figure.
1. If n = 1, we move the single disk directly from the source peg to the destination peg.
2. To move n>1 disks from peg 1 to peg 3 (with peg 2 as auxiliary),
o we first move recursively n-1 disks from peg 1 to peg 2 (with peg 3 as auxiliary),
o then move the largest disk directly from peg 1 to peg 3, and,
o finally, move recursively n-1 disks from peg 2 to peg 3 (using peg 1 as auxiliary).

Figure: Recursive solution to the Tower of Hanoi puzzle

Algorithm: TowerOfHanoi(n, source, dest, aux)

If n == 1, THEN
move disk from source to dest
else
TowerOfHanoi (n - 1, source, aux, dest)
move disk from source to dest
TowerOfHanoi (n - 1, aux, dest, source)
End if

Computation of Number of Moves

The number of moves M(n) depends only on n. The recurrence equation is

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

We solve this recurrence by t e same method of backward substitutions:

 MODULE 1: Introduction to Algorithms

The pattern of the first three sums on the left suggests that the next one will be
24M(n − 4) + 23 + 22 + 2 + 1, and generally, after i substitutions, we get

Since the initial condition is specified for n = 1, which is achieved for i = n-1, we get the
following formula for the solution to recurrence,

Example-3: To count bits of a decimal number in its binary representation

The recurrence relation can b written as

.
Also note that A(1) = 0.

The standard approach to solving such a recurrence is to solve it only for n = 2k and then take
advantage of the theorem called the smoothness rule which claims that under very broad
assumptions the order of growth observed for n = 2k gives a correct answer about the order of
growth for all values of n.