FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.

AJAYPASHANKAR

DESIGN AND ANALYSIS OF ALGORITHM

F.Y.BSC.CS UNIT I,II,III NOTES

PREPARED BY:

PROF.AJAY PASHANKAR

om
r.c
ka
an
sh
pa
jay
ofa
pr
w.
ww

www.profajaypashankar.com Page 1 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
UNIT I:
Introduction to algorithms - What is algorithm, analysis of algorithm, Types of complexity, Running
time analysis, How to Compare Algorithms, Rate of Growth, Types of Analysis, Asymptotic Notation,
Big-O Notation, Omega-Ω Notation, Theta-Θ Notation, Asymptotic Analysis, Performance characteristics
of algorithms, Estimating running time / number of steps of executions on paper, Idea of Computability
Introduction to Data Structures - What is data structure, types, Introduction to Array(1-d & 2-d),
Stack and List data structures, operations on these data structures, advantages disadvantages and
applications of these data structures like solving linear equations, Polynomial Representation,
Infix-to-Postfix conversion .

UNIT II:
Recursion - What is recursion, Recursion vs Iteration, recursion applications like Factorial of a number,
Fibonacci series & their comparative analysis with respect to iterative version, Tower of Hanoi
problem

om
Basic Sorting Techniques - Bubble, Selection and Insertion Sort & their comparative analysis
Searching Techniques - Linear Search and its types, Binary Search and their comparative analysis
Selection Techniques - Selection by Sorting, Partition-based Selection Algorithm, Finding the Kth
Smallest Elements in Sorted Order & their comparative analysis

r.c
String Algorithms - Pattern matching in strings, Brute Force Method & their comparative analysis

UNIT III:

ka
Algorithm Design Techniques - Introduction to various types of classifications/design criteria and
design techniques

an
Greedy Technique - Concept, Advantages & Disadvantages, Applications, Implementation using
problems like - file merging problem
Divide-n-Conquer - Concept, Advantages & Disadvantages, Applications, Implementation using
problems like - merge sort, Strassen's Matrix Multiplication
sh
Dynamic Programming - Concept, Advantages & Disadvantages, Applications, Implementation using
problems like - Fibonacci series, Factorial of a number, Longest Common subsequence
Backtracking Programming - Concept, Advantages & Disadvantages, Applications, Implementation
pa
using problems like N-Queen Problem .
jay
ofa
pr
w.
ww

www.profajaypashankar.com Page 2 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
INDEX :

SR.NO TOPIC PAGE NO

1 Introduction to algorithms 3-11

2 Introduction to Data Structures 12-39

3 Recursion 40-46

4 Basic Sorting Techniques 47-57

5 Searching Techniques 58-62

om
6 Selection Techniques 63-63

7 String Algorithms 64-65

r.c
8 Algorithm Design Techniques 65-67

9 Greedy Technique 68-69

ka
10 Divide-n-Conquer 70-73

an
11 Dynamic Programming 74-79

12 Backtracking Programming 80-85

sh
pa
jay
ofa
pr
w.
ww

www.profajaypashankar.com Page 3 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
CHAPTER I: INTRODUCTION TO ALGORITHMS:

Topics covered:
What is algorithm, analysis of algorithm, Types of complexity, Running time analysis, How to Compare
Algorithms, Rate of Growth, Types of Analysis, Asymptotic Notation, Big-O Notation, Omega-Ω
Notation, Theta-Θ Notation, Asymptotic Analysis, Performance characteristics of algorithms, Estimating
running time / number of steps of executions on paper, Idea of Computability
-------------------------------------------------------------------------------------------------------------------
What is algorithm?

An algorithm is the step-by-step unambiguous instructions to solve a given problem.

An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for

om
obtaining a required output for any legitimate input in a finite amount of time.

There are two main criteria for judging the merits of algorithms:

● Correctness (does the algorithm give a solution to the problem in a finite number of steps?)

r.c
● Efficiency (how much resources (in terms of memory and time) does it take to execute the
algorithm).

ka
an
sh
pa
jay

As examples illustrating the notion of the algorithm, we consider in this section three methods for
ofa

solving the same problem: computing the greatest common divisor of two integers. These examples
will help us to illustrate several important points:
● The non-ambiguity requirement for each step of an algorithm cannot be compromised.
● The range of inputs for which an algorithm works has to be specified carefully.
pr

● The same algorithm can be represented in several different ways.

● There may exist several algorithms for solving the same problem.
● Algorithms for the same problem can be based on very different ideas and can solve the
w.

problem with dramatically different speeds.

ww

-------------------------------------------------------------------------------------------------------------------
Analysis of algorithm:
To go from city “A” to city “B”, there can be many ways of accomplishing this: by flight, by bus,
by train and also by bicycle. Depending on the availability and convenience, we choose the one
that suits us. Similarly, in computer science, multiple algorithms are available for solving the
same problem (for example, a sorting problem has many algorithms, like insertion sort, selection
sort, quick sort and many more). Algorithm analysis helps us to determine which algorithm is
most efficient in terms of time and space consumed.

Goal of the Analysis of Algorithms

The goal of the analysis of algorithms is to compare algorithms (or solutions) mainly in terms of
running time but also in terms of other factors (e.g., memory, developer effort, etc.)
www.profajaypashankar.com Page 4 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
-------------------------------------------------------------------------------------------------------------------
What is Running Time Analysis?
It is the process of determining how processing time increases as the size of the problem (input size)
increases. Input size is the number of elements in the input, and depending on the problem type, the
input may be of different types. The following are the common types of inputs.
• Size of an array
• Polynomial degree
• Number of elements in a matrix
• Number of bits in the binary representation of the input
• Vertices and edges in a graph.
-------------------------------------------------------------------------------------------------------------------
Types of complexity:

om
Types of Analysis

To analyze the given algorithm, we need to know with which inputs the algorithm takes less time
(Performing well) and with which inputs the algorithm takes a long time. We have already seen
that an algorithm can be represented in the form of an expression. That means we represent the

r.c
algorithm with multiple expressions: one for the case where it takes less time and another for the
case where it takes more time.

ka
In general, the first case is called the best case and the second case is called the worst case for
the algorithm. To analyze an algorithm we need some kind of syntax, and that forms the base for
asymptotic analysis/notation. There are three types of analysis:

an
• Worst case

● Defines the input for which the algorithm takes a long time (slowest time to complete).
● Input is the one for which the algorithm runs the slowest.
sh
• Best case
pa
● Defines the input for which the algorithm takes the least time (fastest time to complete).
● Input is the one for which the algorithm runs the fastest.

• Average case
jay

● Provides a prediction about the running time of the algorithm.

● Run the algorithm many times, using many different inputs that come from some distribution
that generates these inputs, compute the total running time (by adding the individual times),
ofa

and divide by the number of trials.

● Assumes that the input is random.

Lower Bound <= Average Time <= Upper Bound

pr

For a given algorithm, we can represent the best, worst and average cases in the form of
w.

expressions. As an example, let f(n) be the function which represents the given algorithm.

Similarly for the average case. The expression defines the inputs with which the algorithm takes
ww

the average running time (or memory).

-------------------------------------------------------------------------------------------------------------------

How to Compare Algorithms

To compare algorithms, let us define a few objective measures:

www.profajaypashankar.com Page 5 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
Execution times Not a good measure as execution times are specific to a particular computer.

Number of statements executed: Not a good measure, since the number of statements varies

with the programming language as well as the style of the individual programmer.

Ideal solution: Let us assume that we express the running time of a given algorithm as a function

of the input size n (i.e., f(n)) and compare these different functions corresponding to running

times. This kind of comparison is independent of machine time, programming style, etc.

-------------------------------------------------------------------------------------------------------------------

What is the Rate of Growth?

om
The rate at which the running time increases as a function of input is called rate of growth.

Let us assume that you go to a shop to buy a car and a bicycle. If your friend sees you there and asks
what you are buying, then in general you say buying a car. This is because the cost of the car is high

r.c
compared to the cost of the bicycle (approximating the cost of the bicycle to the cost of the car).

ka
an
For the above-mentioned example, we can represent the cost of the car and the cost of the bicycle in
terms of function, and for a given function ignore the low order terms that are relatively insignificant
sh
(for large value of input size, n). As an example, in the case below, n4, 2n2, 100n and 500 are the
individual costs of some function and approximate to n4 since n4 is the highest rate of growth.
pa
jay

Commonly Used Rates of Growth

The diagram below shows the relationship between different rates of growth.
ofa
pr
w.
ww

-------------------------------------------------------------------------------------------------------------------

Asymptotic Notation

Having the expressions for the best, average and worst cases, for all three cases we need to identify
the upper and lower bounds. To represent these upper and lower bounds, we need some kind of

www.profajaypashankar.com Page 6 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
syntax, and that is the subject of the following discussion. Let us assume that the given algorithm is
represented in the form of function f(n).

1.14 Big-O Notation [Upper Bounding Function]

This notation gives the tight upper bound of the given function. Generally, it is represented as

f(n)= O(g(n)). That means, at larger values of n, the upper bound of f(n) is g(n). For example, if f(n)

= n4 + 100n2 + 10n + 50 is the given algorithm, then n4 is g(n). That means g(n) gives the

maximum rate of growth for f(n) at larger values of n.

om
r.c
ka
an
sh
pa
jay

Let us see the O–notation with a little more detail. O–notation defined as O(g(n)) = {f(n): there

exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n > n0}. g(n) is an asymptotic
ofa

tight upper bound for f(n). Our objective is to give the smallest rate of growth g(n) which is

greater than or equal to the given algorithms’ rate of growth /(n).

pr

Generally we discard lower values of n. That means the rate of growth at lower values of n is not

important. In the figure, n0 is the point from which we need to consider the rate of growth for a
w.

given algorithm. Below n0, the rate of growth could be different. n0 is called threshold for the

given function.
ww

Big-O Visualization

O(g(n)) is the set of functions with smaller or the same order of growth as g(n). For example;

O(n2) includes O(1), O(n), O(nlogn), etc.

Note: Analyze the algorithms at larger values of n only. What this means is, below n0 we do not

care about the rate of growth.

Omega-Q Notation [Lower Bounding Function]

Similar to the O discussion, this notation gives the tighter lower bound of the given algorithm and

www.profajaypashankar.com Page 7 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
we represent it as f(n) = Ω(g(n)). That means, at larger values of n, the tighter lower bound of

f(n) is g(n). For example, if f(n) = 100n2 + 10n + 50, g(n) is Ω(n2).

om
r.c
ka
an
sh
The Ω notation can be defined as Ω(g(n)) = {f(n): there exist positive constants c and n0 such that
pa
0 ≤ cg(n) ≤ f(n) for all n ≥ n0}. g(n) is an asymptotic tight lower bound for f(n). Our objective is

to give the largest rate of growth g(n) which is less than or equal to the given algorithm’s rate of
jay

growth f(n).

-------------------------------------------------------------------------------------------------------------------
ofa

Theta-Θ Notation [Order Function]

This notation decides whether the upper and lower bounds of a given function (algorithm) are the
pr

same. The average running time of an algorithm is always between the lower bound and the upper

bound. If the upper bound (O) and lower bound (Ω) give the same result, then the Θ notation will
w.

also have the same rate of growth.

As an example, let us assume that f(n) = 10n + n is the expression. Then, its tight upper bound
ww

g(n) is O(n). The rate of growth in the best case is g(n) = O(n).

In this case, the rates of growth in the best case and worst case are the same. As a result, the

average case will also be the same. For a given function (algorithm), if the rates of growth

(bounds) for O and Ω are not the same, then the rate of growth for the Θ case may not be the same.

In this case, we need to consider all possible time complexities and take the average of those (for

example, for a quick sort average case, refer to the Sorting chapter).

Now consider the definition of Θ notation. It is defined as Θ(g(n)) = {f(n): there exist positive

www.profajaypashankar.com Page 8 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
constants c1,c2 and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0}. g(n) is an asymptotic

tight bound for f(n). Θ(g(n)) is the set of functions with the same order of growth as g(n).

om
r.c
ka
an
sh
-------------------------------------------------------------------------------------------------------------------
pa
Important Notes:

For analysis (best case, worst case and average), we try to give the upper bound (O) and lower
jay

bound (Ω) and average running time (Θ). From the above examples, it should also be clear that,
for a given function (algorithm), getting the upper bound (O) and lower bound (Ω) and average
running time (Θ) may not always be possible. For example, if we are discussing the best case of
an algorithm, we try to give the upper bound (O) and lower bound (Ω) and average running time
ofa

(Θ).
In the remaining chapters, we generally focus on the upper bound (O) because knowing the lower
bound (Ω) of an algorithm is of no practical importance, and we use the Θ notation if the upper
bound (O) and lower bound (Ω) are the same.
pr

-------------------------------------------------------------------------------------------------------------------

Why is it called Asymptotic Analysis?

w.

From the discussion above (for all three notations: worst case, best case, and average case), we
ww

can easily understand that, in every case for a given function f(n) we are trying to find another

function g(n) which approximates f(n) at higher values of n. That means g(n) is also a curve

which approximates f(n) at higher values of n.

In mathematics we call such a curve an asymptotic curve. In other terms, g(n) is the asymptotic

curve for f(n). For this reason, we call algorithm analysis asymptotic analysis.

Simplifying properties of asymptotic notations

• Transitivity: f(n) = Θ(g(n)) and g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n)). Valid for O and Ω as well.
• Reflexivity: f(n) = Θ(f(n)). Valid for O and Ω.
www.profajaypashankar.com Page 9 of 85
 FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
• Symmetry: f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n)).
• Transpose symmetry: f(n) = O(g(n)) if and only if g(n) = Ω(f(n)).
• If f(n) is in O(kg(n)) for any constant k > 0, then f(n) is in O(g(n)).
• If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n)), then (f1 + f2)(n) is in O(max(g1(n)),
(g1(n))).
• If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n)) then f1(n) f2(n) is in O(g1(n) g1(n)).

-------------------------------------------------------------------------------------------------------------------

Performance Characteristics of Algorithm

The Algorithm designed is language independent, i.e. they are just plain instructions set that can be
implemented in any language, and the output will be the same, as expected.

om
Following are the key characteristics of algorithm -

● Well-Defined Inputs: If an algorithm says to take inputs instance, it should be clear that
which type of inputs in required for processing.
● Well-Defined Outputs: The algorithm must clearly define that what type of output will be

r.c
generated.
o Finiteness: The algorithm should not end up in an infinite loop.

ka
o Feasibility: The algorithm must be generic and practical, such that it can be executed
upon available resources.
Language Independent: It must be just plain instructions set that can be implemented in

an
any language, and yet the output will be same, as expected.

There are some characteristics which every algorithm should follow. There are five different
characteristics which deal with various aspects of algorithm. They are as follows:
sh
● Input specified.
● Output specified.
pa
● Definiteness.
● Effectiveness.
jay

● Finiteness.
● Independent.
Generally, the performance of an algorithm depends on the following elements...
ofa

1. Whether that algorithm is providing the exact solution for the problem?
2. Whether it is easy to understand?
3. Whether it is easy to implement?
4. How much space (memory) it requires to solve the problem?
pr

5. How much time it takes to solve the problem? Etc.,

w.

Performance analysis of an algorithm is performed by using the following measures...

1. Space required to complete the task of that algorithm (Space Complexity). It includes
ww

program space and data space

2. Time required to complete the task of that algorithm (Time Complexity)

-------------------------------------------------------------------------------------------------------------------

Estimating running time / number of steps of executions on paper

To calculate the running time, find the maximum number of nested loops that go through a
significant portion of the input. Some algorithms use nested loops where the outer loop goes
through an input n while the inner loop goes through a different input m. The time complexity in such
cases is O(nm).

-------------------------------------------------------------------------------------------------------------------

Idea of Computability
www.profajaypashankar.com Page 10 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
A central idea in computability is that of a (computational) problem, which is a task whose
computability can be explored.

There are two key types of problems:

● A decision problem fixes a set S, which may be a set of strings, natural numbers, or other
objects taken from some larger set U. A particular instance of the problem is to decide, given
an element u of U, whether u is in S. For example, let U be the set of natural numbers
and S the set of prime numbers. The corresponding decision problem corresponds to primality
testing.

● A function problem consists of a function f from a set U to a set V. An instance of the problem is
to compute, given an element u in U, the corresponding element f(u) in V. For
example, U and V may be the set of all finite binary strings, and f may take a string and return

om
the string obtained by reversing the digits of the input (so f(0101) = 1010).

Other types of problems include search problems and optimization problems.

One goal of computability theory is to determine which problems, or classes of problems, can be solved

r.c
in each model of computation.

-------------------------------------------------------------------------------------------------------------------

ka
QUICK REVISION

an
● An algorithm is the step-by-step unambiguous instructions to solve a given problem.
● 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.
Algorithm analysis helps us to determine which algorithm is most efficient in terms of
sh
●
time and space consumed.
● The goal of the analysis of algorithms is to compare algorithms (or solutions) mainly in
pa
terms of running time but also in terms of other factors (e.g., memory, developer effort,
etc.)
● Complexity of algorithm is measured as Best Case , Worst Case and Average case .
jay

● Big-O Notation [Upper Bounding Function]

● Omega-Q Notation [Lower Bounding Function]
● Theta-Θ Notation [Order Function]
ofa
pr
w.
ww

CHAPTER II: INTRODUCTION TO DATA STRUCTURES

Topics Covered:
What is data structure, types, Introduction to Array(1-d & 2-d), Stack and List data structures,
operations on these data structures, advantages disadvantages and applications of these data
structures like solving linear equations, Polynomial Representation, Infix-to-Postfix conversion .

www.profajaypashankar.com Page 11 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
-------------------------------------------------------------------------------------------------------------------
What is data structure:

Data structure is a particular way of storing and organizing data in a computer so that it can be used
efficiently. A data structure is a special format for organizing and storing data. General data structure
types include arrays, files, linked lists, stacks, queues, trees, graphs and so on.

Depending on the organization of the elements, data structures are classified into two types:

1) Linear data structures: Elements are accessed in a sequential order but it is not compulsory to
store all elements sequentially. Examples: Linked Lists, Stacks and Queues.

2) Non – linear data structures: Elements of this data structure are stored/accessed in a non-linear
order. Examples: Trees and graphs.

om
Abstract Data Types (ADTs)

r.c
Abstract Data Types (ADTs).

An ADT consists of two parts:

ka
1. Declaration of data

2. Declaration of operations

an
Commonly used ADTs include: Linked Lists, Stacks, Queues, Priority Queues, Binary Trees,

Dictionaries, Disjoint Sets (Union and Find), Hash Tables, Graphs, and many others.
sh
ARRAYS
The most basic structure for storing and accessing a collection of data is the array.
pa
Arrays can be used to solve a wide range of problems in computer science. Most Programming
languages provide this structured data type as a primitive and allow for the creation of arrays with
multiple dimensions. In this chapter, we implement an array structure for a one-dimensional array and
then use it to implement a Two-dimensional array and the related matrix structure.
jay

The Array Structure

At the hardware level, most computer architectures provide a mechanism for creating and using
ofa

one-dimensional arrays. A one-dimensional array, as illustrated in Figure 2.1, is composed of multiple

sequential elements stored in contiguous bytes of memory and allows for random access to the
individual elements.
The entire contents of an array are identified by a single name. Individual elements within the array
can be accessed directly by specifying an integer subscript or index value, which indicates an offset
pr

from the start of the array. This is similar to the mathematics notation (xi), which allows for multiple
variables of the same name. The difference is that programming languages typically use square
w.

brackets following the array name to specify the subscript, x[i].

ww

The Array Abstract Data Type

The array structure is commonly found in most programming languages as a primitive type, but Python
only provides the list structure for creating mutable sequences. We can define the Array ADT to
represent a one-dimensional array for use in Python that works similarly to arrays found in other
languages. It will be used throughout the text when an array structure is required.
Some computer scientists consider the array a physical structure and not an abstraction since arrays
are implemented at the hardware level. But remember, there are only three basic operations available
with the hardware-implemented array. As part of our Array ADT, we have provided for these operations
but have also included an iterator and operations for obtaining the size of the array and for setting
www.profajaypashankar.com Page 12 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
every element to a given value. In this case, we have provided a higher level of abstraction than that
provided by the underlying hardware-implemented array.
The following simple program illustrates the creation and use of an array object based on the Array
ADT. Comments are provided to highlight the use of the operator methods.

# Fill a 1-D array with random values, then print them, one per line.
from array import Array
import random
# The constructor is called to create the array.
valueList = Array( 100 )
# Fill the array with random floating-point values.
for i in range( len( valueList ) ) :
valueList[ i ] = random.random()

om
# Print the values, one per line.
for value in valueList :
print( value )

r.c
ka
an
sh
pa
jay
ofa
pr
w.

Implementing the Array

Python is a scripting language built using the C language, a high-level language
ww

that requires a program's source code be compiled into executable code before it can
be used. The C language is a very powerful programming language that provides syntax for working
with the complete functionality available by the underlying
hardware. That syntax, however, can be somewhat cryptic compared to Python,
especially for a Python programmer who may not be familiar with C.

The ctypes Module

Many of the data types and classes available in Python are actually implemented
using appropriate types from the C language. While Python does not provide the
array structure as part of the language itself, it now includes the ctypes module as
part of the Python Standard Library. This module provides access to the diverse set
of data types available in the C language and the complete functionality provided
by a wide range of C libraries.

www.profajaypashankar.com Page 13 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
The ctypes module provides the capability to create hardware-supported ar-
rays just like the ones used to implement Python's string, list, tuple, and dictionary
collection types. But the ctypes module is not meant for everyday use in Python
programs as it was designed for use by module developers to aide in creating more
portable Python modules by bridging the gap between Python and the C language.
Much of the functionality provided by the ctypes module requires some knowledge
of the C language. Thus, the technique provided by the module for creating an
array should not typically be used directly within a Python program. But we can
use it within our Array class to provide the functionality defined by the Array
ADT since the details will be hidden within the class.

Creating a Hardware Array

The ctypes module provides a technique for creating arrays that can store references to Python

om
objects. The following code segment

import ctypes
ArrayType = ctypes.py_object * 5
slots = ArrayType()

r.c
creates an array named slots that contains five elements

ka
an
each of which can store a reference to an object. After the array has been created,
the elements can be accessed using the same integer subscript notation as used
with Python's own sequence types. For the slots array, the legal range is [0 : : : 4].
sh
The elements of the array have to be initialized before they can be used. If we
attempt to read the contents of an element in the slots array before it has been
initialized
pa
print( slots[0] )

an exception would be raised in the same way as if we tried to print the value of
a variable sum, that had not previously been assigned a value. Thus, the array
jay

should be initialized immediately after it has been created by assigning a value to

each element using the subscript notation. Any value can be used, but a logical
choice is to assign None to each element:
for i in range( 5 ) :
ofa

slots[i] = None
The elements of the array can now be treated like any other variable in Python
that contains a null reference:
pr
w.
ww

You may have noticed that we used the literal 5 with the range() function
to indicate the number of elements to be initialized. This was necessary because
a hardware-supported array does not keep track of the array size; it's up to the
programmer to remember or maintain this value. Likewise, the programmer must
also ensure they do not access an element outside the legal range.
References to any type of Python object can be stored in any element of the
array. For example, the following code segment stores three integers in various
elements of the array:
slots[1] = 12
slots[3] = 54
slots[4] = 37
the result of which is illustrated here:

www.profajaypashankar.com Page 14 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

The operations provided by the array only allow for setting a given element
to a given reference or accessing a reference stored in a given element. To remove
an item from the array, we simply set the corresponding element to None. For
example, suppose we want to remove value 54 from the array
slots[3] = None
which results in the following change to the slots array:

om
The size of the array can never change, so removing an item from an array
has no effect on the size of the array or on the items stored in other elements.
The array does not provide any of the list type operations such as appending or

r.c
popping items, searching for a specific item, or sorting the items. To use such an
Operation with an array, you would have to provide the necessary code yourself.

ka
The Class Definition
The implementation of the Array ADT using a hardware-supported array created
with the use of the ctypes module is provided in Listing 2.1.

an
sh
pa
jay
ofa
pr
w.
ww

www.profajaypashankar.com Page 15 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
sh
pa
jay

The constructor, as shown in lines 6{13, handles the creation and initialization of the array using the
ofa

technique described earlier. It also defines two data fields needed for the implementation of the Array
ADT: one to store a reference to the array structure and another to store the number of elements
allocated for the array. The latter is needed since hardware-supported arrays do not keep track of
this value. The initialization of the array is done by calling the clear() method.
pr

The clear() method is used to set each element of the array to a given value, which it does by iterating
over the elements using an index variable. The len method, which returns the number of elements in
the array, simply returns the value of size that was saved in the constructor. The iter method creates
w.

and returns an instance of the ArrayIterator private iterator class, which is provided in lines 39{53 of
Listing 2.1.
The definition of the Array ADT calls for the implementation of the subscript operator, which allows for
ww

the use of array objects in a manner similar to other Python collection types. In Python, as in most
languages, the subscript notation can be used to read the contents of an array element or to modify an
element. Thus, there are two different methods that must be defined, as shown in lines 20{27. First,
the getitem operator method takes the array index as an argument and returns the value of the
corresponding element. The precondition must first be verified to ensure the subscript is within the
valid range.
When the subscript notation is used in a program, y = x[i], Python will call the getitem method,
passing the value of i to the index parameter. Since
Python expects the getitem method to return a value, it is your responsibility to make sure this occurs.
The setitem operator method is used to set or change the contents of a specific element of the array. It
takes two arguments: the array index of the element being modified and the new value that will be
stored in that element. Before the element is modified, the precondition must be tested to verify the
subscript is within the valid range. Python automatically calls the setitem method when
the subscript notation is used to assign a value to a specific element, x[i] = y.
www.profajaypashankar.com Page 16 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
The index, i, specified in the subscript is passed as the first argument and the
value to be assigned is passed as the second argument, __setitem__(i,y).
-------------------------------------------------------------------------------------------------------------------
The Python List
Python, as indicated earlier, is built using the C language with many of the data
types and classes available in Python actually implemented using appropriate types
available in C. Python's list structure is a mutable sequence container that can
change size as items are added or removed. It is an abstract data type that is
implemented using an array structure to store the items contained in the list.
In this section, we examine the implementation of Python's list, which can
be very beneficial not only for learning more about abstract data types and their
implementations but also to illustrate the major differences between an array and
Python's list structure. We explore some of the more common list operations and

om
describe how they are implemented using an array structure.

Creating a Python List

Suppose we create a list containing several values:
pyList = [ 4, 12, 2, 34, 17 ]

r.c
which results in the list() constructor being called to create a list object and _ll
it with the given values. When the list() constructor is called, an array structure
is created to store the items contained in the list. The array is initially created

ka
bigger than needed, leaving capacity for future expansion. The values stored in the
list comprise a subarray in which only a contiguous subset of the array elements
are actually used.

an
Figure 2.2 illustrates the abstract and physical views of our sample list. In
the physical view, the elements of the array structure used to store the actual
contents of the list are enclosed inside the dashed gray box. The elements with
sh
null references shown outside the dashed gray box are the remaining elements of
the underlying array structure that are still available for use. This notation will be
used throughout the section to illustrate the contents of the list and the underlying
pa
array used to implement it.
jay
ofa
pr
w.
ww

The length of the list, obtained using len(), is the number of items currently
in the subarray and not the size of the underlying array. The size or capacity of
the array used to implement the list must be maintained in order to know when
the array is full. Python does not provide a method to access the capacity value
since that information is not part of the list definition.
2.2.2 Appending Items
What happens when a new item is appended to the end of a list as in the following
statement?
pyList.append( 50 )
If there is room in the array, the item is stored in the next available slot of the
array and the length _eld is incremented by one. The result of appending 50 to
pyList is illustrated in Figure 2.3.

www.profajaypashankar.com Page 17 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

What happens when the array becomes full and there are no free elements in
which to add a new list item? For example, consider the following list operations:
pyList.append( 18 )

om
pyList.append( 64 )
pyList.append( 6 )

After the second statement is executed, the array becomes full and there is no
available space to add more values as illustrated in Figure 2.4.

r.c
By de_nition, a list can contain any number of items and never becomes full.
Thus, when the third statement is executed, the array will have to be expanded to
make room for value 6. From the discussion in the previous section, we know an

ka
array cannot change size once it has been created. To allow for the expansion of

an
sh
pa
the list, the following steps have to be performed: (1) a new array is created with
additional capacity, (2) the items from the original array are copied to the new
array, (3) the new larger array is set as the data structure for the list, and (4) the
jay

original smaller array is destroyed. After the array has been expanded, the value
can be appended to the end of the list. In Python, the amount by which the size
of the array is increased is proportional to the current array size. For illustration
ofa

purposes, we assume an expansion creates a new array that is double the size of
the original. The result of expanding the array and appending value 6 to the list
is shown in Figure 2.5.
pr
w.
ww

www.profajaypashankar.com Page 18 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
Extending A List
A list can be appended to a second list using the extend() method as shown in

ka
the following example:
pyListA = [ 34, 12 ]
pyListB = [ 4, 6, 31, 9 ]

an
pyListA.extend( pyListB )
If the list being extended has the capacity to store all of the elements from
the second list, the elements are simply copied, element by element. If there is not
sh
enough capacity for all of the elements, the underlying array has to be expanded as
was done with the append() method. Since Python knows how big the array needs
to be in order to store all of the elements from both lists, it only requires a single
pa
expansion of the destination list, pyListA. The new array will be created larger
than needed to allow more items to be added to the list without first requiring an
immediate expansion of the array. After the new array is created, elements from
jay

the destination list are copied to the new array followed by the elements from the
source list, pyListB, as illustrated in Figure 2.6.
ofa
pr
w.
ww

Inserting Items
An item can be inserted anywhere within the list using the insert() method. In
the following example
pyList.insert( 3, 79 )
we insert the value 79 at index position 3. Since there is already an item at that
position, we must make room for the new item by shifting all of the items down
one position starting with the item at index position 3. After shifting the items,

www.profajaypashankar.com Page 19 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
the value 79 is then inserted at position 3 as illustrated in Figure 2.7. If there are
no free slots for the new item, the list will be expanded in the same fashion as
described earlier.

om
r.c
ka
Removing Items
an
sh
An item can be removed from any position within the list using the pop() method.
Consider the following code segment, which removes both the _rst and last items
from the sample list:
pa
pyList.pop( 0 ) # remove the first item
pyList.pop() # remove the last item
The _rst statement removes the _rst item from the list. After the item is removed, typically by setting
jay

the reference variable to None, the items following it within the array are shifted down, from left to
right, to close the gap. Finally, the length of the list is decremented to reect the smaller size. Figure 2.8
on the next page illustrates the process of removing the _rst item from the sample list. The second
pop() operation in the example code removes the last item from the list.
ofa

Since there are no items following the last one, the only operations required are to remove the item
and decrement the size of the list.
After removing an item from the list, the size of the array may be reduced using a technique similar to
that for expansion. This reduction occurs when the number of available slots in the internal array falls
pr

below a certain threshold. For example, when more than half of the array elements are empty, the size
of the array may be cut in half.
-------------------------------------------------------------------------------------------------------------------
w.

List Slice
Slicing is an operation that creates a new list consisting of a contiguous subset of elements from the
original list. The original list is not modified by this operation.
ww

Instead, references to the corresponding elements are copied and stored in the specifying the
beginning element index and the number of elements included in the subset. Consider the following
example code segment, which creates a slice from our sample list:
aSlice = theVector[2:3]
new list. In Python, slicing is performed on a list using the colon operator and To slice a list, a new list
is created with a capacity large enough to store the entire subset of elements plus additional space for
future insertions. The elements within the specified range are then copied, element by element, to the
new list.
The result of creating the sample slice is illustrated in Figure 2.9.

www.profajaypashankar.com Page 20 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
sh
pa
jay
ofa
pr

-------------------------------------------------------------------------------------------------------------------
Two-Dimensional Arrays
w.

Arrays are not limited to a single dimension. Some problems require the use of a two-dimensional
array, which organizes data into rows and columns similar to a table or grid. The individual elements
are accessed by specifying two indices, one for the row and one for the column, [i,j]. Figure 2.10
ww

shows an abstract view of both a one- and a two-dimensional array.

While computer architectures provide a mechanism at the hardware level for creating and using
one-dimensional arrays, they do not typically support arrays of higher dimensions. Instead,
programming languages typically provide their own mechanism for creating and managing arrays that
consist of multiple dimensions.
In this section, we explore two-dimensional arrays while arrays of higher dimensions
are discussed later in the chapter.

www.profajaypashankar.com Page 21 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
The Array2D Abstract Data Type

As we saw earlier, Python does not directly support built-in arrays of any dimension. But, in the
previous section, we were able to use the ctypes module to create

r.c
a one-dimensional hardware-supported array that we used to implement the Array
ADT. Two-dimensional arrays are also very common in computer programming,
where they are used to solve problems that require data to be organized into rows

ka
and columns. Since 2-D arrays are not provided by Python, we define the Array2D
abstract data type for creating 2-D arrays. It consists of a limited set of operations
similar to those provided by the one-dimensional Array ADT.

an
sh
pa
jay
ofa
pr
w.
ww

To illustrate the use of a 2-D array, suppose we have a collection of exam

grades stored in a text _le for a group of students that we need to process. For
example, we may want to compute the average exam grade for each student or the
average grade for each exam, or both. A sample text _le is illustrated on the left in
Figure 2.11. The _le contains the grades for multiple students, each of whom have
grades for multiple exams. The _rst line indicates the number of students for whom

www.profajaypashankar.com Page 22 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
we have grades, and the second line indicates the number of exams for which each student has a
grade. The remaining lines contain the actual exam grades. Each line contains the grade for an
individual student, with the grades listed in exam order.
Since we have multiple grades for multiple students, we can store the grades in
a 2-D array in which each row contains the grades for an individual student and
each column contains the grades for a given exam. A 2-D array used to store the
exam grades from the sample _le is illustrated on the right in Figure 2.11.

om
r.c
ka
an
The following code segment shows the implementation needed to extract the
exam grades from the text _le and store them into a 2-D array. Notice that we
create the array after extracting the _rst two values from the _le. These values
sh
indicate the number of students and the number of exams that correspond to the
number of rows and columns needed in the array.
from array import Array2D
pa
# Open the text file for reading.
gradeFile = open( filename, "r" )
# Extract the first two values which indicate the size of the array.
jay

numExams = int( gradeFile.readline() )

numStudents = int( gradeFile.readline() )
# Create the 2-D array to store the grades.
examGrades = Array2D( numStudents, numExams )
ofa

# Extract the grades from the remaining lines.

i=0
for student in gradeFile :
grades = student.split()
pr

for j in range( numExams ):

examGrades[i,j] = int( grades[j] )
i += 1
w.

# Close the text file.

gradeFile.close()
With the grades extracted from the _le and stored in the 2-D array, we can
ww

now process the grades as needed. Suppose we want to compute and display each
student's exam grade, which we can do with the following code:
# Compute each student's average exam grade.
for i in range( numStudents ) :
# Tally the exam grades for the ith student.
total = 0
for j in range( numExams ) :
total += examGrades[i,j]
# Compute average for the ith student.
examAvg = total / numExams
print( "%2d: %6.2f" % (i+1, examAvg) )

Implementing the 2-D Array

www.profajaypashankar.com Page 23 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
We now turn our attention to the implementation of the 2-D array. There are
several approaches that we can use to store and organize the data for a 2-D array.
Two of the more common approaches include the use of a single 1-D array to
physically store the elements of the 2-D array by arranging them in order based on
either row or column, whereas the other uses an array of arrays. We are going to
use the latter approach to implement the Array2D abstract data type and delay
discussion of the former approach until later in the chapter.
When using an array of arrays to store the elements of a 2-D array, we store
each row of the 2-D array within its own 1-D array. Then, another 1-D array
is used to store references to each of the arrays used to store the row elements.
Figure 2.12 shows the abstract view of a 2-D array and the physical storage of that
2-D array using an array of arrays.

om
r.c
ka
an
Some languages that use the array of arrays approach for implementing a 2-D
sh
array provide access to the individual arrays used to store the row elements. Having
access to the given 1-D array, these languages use the subscript notation x[r][c]
for referencing an individual element. To be consistent in our approach of hiding
pa
the implementation details, we do not provide access to any of the 1-D arrays used
to store the elements of the 2-D array. Thus, our implementation requires the use
of the subscript notation x[r,c].
jay

The implementation of the Array2D abstract data type using an array of arrays
is provided in Listing 2.2. The constructor creates a data field named theRows
to which an Array object is assigned. This is the main array used to store the
references to the other arrays that are created for each row in the 2-D array.
ofa
pr
w.
ww

www.profajaypashankar.com Page 24 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
sh
pa
jay
ofa
pr
w.
ww

Basic Operations
Note that the size of the array that is passed as arguments to the constructor is
not saved in data fields. The numRows() method can obtain the number of rows by
checking the length of the main array, which contains an element for each row in the
2-D array. To determine the number of columns in the 2-D array, the numCols()
method can simply check the length of any of the 1-D arrays used to store the
individual rows.
The clear() method can set every element to the given value by calling the
clear() method on each of the 1-D arrays used to store the individual rows. This
is easily done by iterating over the array stored in theRows.
www.profajaypashankar.com Page 25 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

Element Access
Access to individual elements within an 2-D array requires a 2-tuple or two-
component subscript, one for each dimension. In mathematics, the 2-tuple sub-
script is generally notated as xr;c. In modern programming languages, a 2-tuple
subscript is given either as x[r][c] or x[r,c]. In Python, we can use the latter
notation in conjunction with the getitem and setitem subscript operators.
This will allow for a more natural use of the two-dimensional array instead of
having to invoke a named method.
The Python subscript operator method getitem , which is shown in lines
27{35, takes a single index argument as specified in the method definition. This
does not restrict the subscript to a single index value, however. When a multi-
component subscript is specified (i.e., y = x[i,j]), Python automatically stores

om
the components in a tuple in the order listed within the brackets and passes the
tuple to the ndxTuple argument of the getitem method.
The contents of the ndxTuple are used to extract the contents of the given
element. After verifying both subscripts are within the valid range, we extract,
from the data field theRows, the reference to the array used to store the given

r.c
row. With this reference stored in the local variable the1dArray, we can then
apply the subscript operator to the 1-D array using the column value.
You may notice a second assert statement within the getitem method at

ka
line 28. This is needed because Python does not examine the number of compo-
nents specified in the subscript before passing the tuple to the subscript operator
method. For example, there is nothing to prevent us from incorrectly supplying

an
three components such as box[i,j,k] instead of two. In fact, Python would have
no way of knowing that we only need two components for the 2-D array subscript.
Thus, we must _rst check to make sure the subscript tuple passed to the method
sh
contains only two elements.
When making the assertion about the size of the ndxTuple, we assume a tuple is passed to the
subscript operator and use the len() function to verify its length. When a single-component subscript
pa
x[0] is supplied to a subscript operator method, as is done with the Array class, the argument is a
single integer value. The len() method can only be used with the collection types and not individual
values. It does generate its own error, however, when used improperly.
Thus, Python's len() function is used to ensure two components are supplied for all Array2D objects.
jay

The setitem operator method can be implemented in a similar fashion to getitem . The major
differences are that this method requires a second argument to receive the value to which an element
is set and it modifies the indicated element with the new value instead of returning a value.
ofa

-------------------------------------------------------------------------------------------------------------------

The Stack ADT

∙ A stack is used to store data such that the last item inserted is the first item removed. It is used to
implement a last-in first-out (LIFO) type protocol. The stack is a linear data structure in which new
pr

items are added, or existing items are removed from the same end, commonly referred to as the top of
the stack. The opposite end is known as the base. Consider the example in Figure 7.1, which
w.
ww

www.profajaypashankar.com Page 26 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
sh
pa
jay
ofa
pr
w.
ww

To illustrate a simple use of the Stack ADT, we apply it to the problem of reversing a list of integer
values. The values will be extracted from the user until a negative value is entered,
which ags the end of the collection. The values will then be printed in reverse order from how they
were entered. We could use a simple list for this problem, but a stack is ideal since the values can be

www.profajaypashankar.com Page 27 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
pushed onto the stack as they are entered and then popped one at a time to print them in reverse
order.
A solution for this problem follows.

om
r.c
ka
When the outer while loop terminates after the negative value is extracted, the contents of

the stack will be as illustrated in Figure 7.2. Notice the last value entered is at the top and

an
the First is at the base. If we pop the values from the stack, they will be removed in the

reverse order from which they were pushed onto the stack, producing a reverse ordering.
sh
Implementing the Stack

The Stack ADT can be implemented in several ways. The two most common approaches in
pa
Python include the use of a Python list and a linked list. The choice depends on the type of

application involved.
jay

Using a Python List

The Python list-based implementation of the Stack ADT is the easiest to implement. The first decision
ofa

we have to make when using the list for the Stack ADT is which end of the list to use as the top and
which as the base. For the most efficient ordering, we let the end of the list represent the top of the
stack and the front represent the base. As the stack grows, items are appended to the end of the list
and when items are popped, they are removed from the same end. Listing 7.1on the next page
pr

provides the complete implementation of the Stack ADT using a Python list.

The peek() and pop() operations can only be used with a non-empty stack since you cannot remove or
w.

peek at something that is not there. To enforce this requirement, we first assert the stack is not empty
before performing the given operation. The peek() method simply returns a reference to the last item
in the list. To implement the pop() method, we call the pop() method of the list structure, which
ww

actually performs the same operation that we are trying to implement.

That is, it saves a copy of the last item in the list, removes the item from the list, and then returns the
saved copy. The push() method simply appends new items to the end of the list since that represents
the top of our stack.

www.profajaypashankar.com Page 28 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
The individual stack operations are easy to evaluate for the Python list-based
sh
implementation. isEmpty(), len , and peek() only require O(1) time. The
pop() and push() methods both require O(n) time in the worst case since the underlying array used to
implement the Python list may have to be reallocated to accommodate the addition or removal of the
pa
top stack item. When used in sequence, both operations have an amortized cost of O(1).
list operation may require a reallocation of the underlying array used to implement the list. A singly
linked list can be used to implement the Stack ADT, alleviating the concern over array reallocations.
jay

To use a linked list, we again must decide how to represent the stack structure. With the Python list
implementation of the stack, it was most efficient to use the end of the list as the top of the stack.
With a linked list, however, the front of the list provides the most efficient representation for the top of
the stack. In Chapter 6,
ofa

we saw how to easily prepend nodes to the linked list as well as remove the first node. The Stack ADT
implemented using a linked list is provided in Listing 7.2.

StackNode class is used to create the linked list nodes. Note the inclusion of the link argument in the
constructor, which is used to initialize the next field of the new node. By including this argument, we
pr

can simplify the prepend operation of the push() method. The two steps required to prepend a node to
a linked list are combined by passing the head reference top as the second argument of the
w.

StackNode() constructor and assigning a reference to the new node back to top.
The peek() method simply returns a reference to the data item in the first node after verifying the
stack is not empty. If the method were used on the stack represented by the linked list in Figure 7.3, a
ww

reference to 19 would be returned.

The peek operation is only meant to examine the item on top of the stack. It should not be used to
modify the top item as this would violate the definition of the Stack ADT.
www.profajaypashankar.com Page 29 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
The pop() method always removes the first node in the list. This operation is illustrated in
Figure 7.4(a). This is easy to implement and does not require a search to find the node
containing a specific item. The result of the linked list after popping the top item from the
stack is illustrated in Figure 7.4(b).
The linked list implementation of the Stack ADT is more efficient than the Python-list based
implementation. All of the operations are O(1) in the worst case, the proof of which is left as
an exercise.

om
r.c
ka
an
sh
7.3 Stack Applications
The Stack ADT is required by a number of applications encountered in computer
pa
science. In this section, we examine several basic applications that traditionally
are presented in a data structures course.
7.3.1 Balanced Delimiters
jay

A number of applications use delimiters to group strings of text or simple data into subparts
by marking the beginning and end of the group. Some common examples include
mathematical expressions, programming languages, and the HTML markup language used
by web browsers. There are typically strict rules as to how the delimiters can be used, which
ofa

includes the requirement of the delimiters being paired and balanced. Parentheses can be
used in mathematical expressions to group or override the order of precedence for various
operations. To aide in reading complicated expressions, the writer may choose to use
different types of symbol pairs, as illustrated here:
pr

{A + (B * C) - (D / [E + F])}
The delimiters must be used in pairs of corresponding types: {}, [], and ().
They must also be positioned such that an opening delimiter within an outer pair must be
w.

closed within the same outer pair. For example, the following expression
would be invalid since the pair of braces [] begin inside the pair of parentheses () but end
outside.
ww

(A + [B * C)] - {D / E}
Another common use of the three types of braces as delimiters is in the C++ programming
language. Consider the following code segment, which implements a function to compute
and return the sum of integer values contained in an array:
As with the arithmetic expression, the delimiters must be paired and balanced. However,
there are additional rules of the language that dictate the proper placement and use of the
symbol pairs. We can design and implement an algorithm that scans an input text _le
containing C++ source code and determines if the delimiters are properly paired. The
algorithm will need to remember not only the most recent opening delimiter but also all of
the preceding ones in order to match them with closing delimiters. In addition, the opening
delimiters will need to be remembered in reverse order with the most recent one available
First. The Stack ADT is a perfect structure for implementing such an algorithm.
Consider the C++ code segment from earlier. As the File is scanned, we can push each
opening delimiter onto the stack. When a closing delimiter is encountered, we pop the

www.profajaypashankar.com Page 30 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
opening delimiter from the stack and compare it to the closing delimiter. For properly paired
delimiters, the two should match. Thus, if the top
of the stack contains a left bracket [, then the next closing delimiter should be a right
bracket ]. If the two delimiters match, we know they are properly paired and can continue
processing the source code. But if they do not match, then we
know the delimiters are not correct and we can stop processing the File. Table 7.1 shows
the steps performed by our algorithm and the contents of the stack after each delimiter is
encountered in our sample code segment

om
r.c
ka
an
sh
pa
jay
ofa
pr

So far, we have assumed the delimiters are balanced with an equal number of opening and
w.

closing delimiters occurring in the proper order. But what happens if the delimiters are not
balanced and we encounter more opening or closing delimiters than the other? For
example, suppose the programmer introduced a typographical error in the function header:
ww

int sumList( int theList)], int size )

Our algorithm will find the first set of parentheses correct. But what happens
when the closing bracket ] is scanned? The result is illustrated in the top part of Table 7.2. You will
notice the stack is empty since the left parenthesis was popped and
matched with the preceding right parenthesis. Thus, unbalanced delimiters in which there
are more closing delimiters than opening ones can be detected when trying to pop from the
stack and we detect the stack is empty.

www.profajaypashankar.com Page 31 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
sh
pa
Delimiters can also be out of balance in the reverse case where there are more
opening delimiters than closing ones. Consider another version of the function
header, again containing a typographical error:
jay

int sumList( int (theList[], int size )

The result of applying our algorithm to this code fragment is illustrated in the bottom chart
in Table 7.2. If this were the complete code segment, you can see we would end up with
ofa

the stack not being empty since there are opening delimiters yet to be paired with closing
ones. Thus, in order to have a complete algorithm, we must check for both of these errors.
A Python implementation for the validation algorithm is provided in Listing 7.3.
The function isValidSource() accepts a _le object, which we assume was previously opened
and contains C++ source code. The _le is scanned one line at a time and each line is
pr

scanned one character at a time to determine if it contains properly paired and balanced
delimiters.
w.

A stack is used to store the opening delimiters and either implementation can
be used since the implementation is independent of the definition. Here, we have
chosen to use the linked list version. As the File is scanned, we need only examine
ww

the characters that correspond to one of the three types of delimiter pairs. All other
characters can be ignored. When an opening delimiter is encountered, we push it onto the
stack. When a closing delimiter occurs, we First check to make sure the stack is not empty.
If it is empty, then the delimiters are not properly paired and balanced and no further
processing is needed. We terminate the function and return False. When the stack is not
empty, the top item is popped and compared to the closing delimiter. The two delimiters do
match corresponding opening and closing delimiters; we again terminate the function and
return False. Finally, after the entire File is processed, the stack should be empty when the
delimiters are properly paired and balanced. For the Final test, we check to make sure the
stack is empty and return either True or False, accordingly.
7.3.2 Evaluating Postfix Expressions
We work with mathematical expressions on a regular basis and they are rather
easy for humans to evaluate. But the task is more difficult in a computer program
when an expression is represented as a string. Given the expression

www.profajaypashankar.com Page 32 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
A*B+C/D
we know A * B will be performed First, followed by the division and concluding
with addition. When evaluating this expression stored as a string and scanning
one character at a time from left to right, how do we know the addition has to wait
until after the division? Your First response is probably that we know the order
of the precedence for the operators. But how do we represent that in our string
scanning process? Suppose we are evaluating a string containing nine non-blank
characters and have scanned the First three:

At this point, we have no way of knowing if the addition operation is to be performed on the

om
two variables A and B or if we have to save this information for later. After moving to the
next character.

r.c
we encounter the division operator and know that the addition is not the First

ka
operation to be performed.

an
sh
Is the division the First operation to be performed? It
does have higher precedence than the addition, but it may not be the First operation
since parentheses can override the order of evaluation. We will have to scan more
pa
of the string to determine which operation is the First to be performed.
After determining the First operation to be performed, we must then decide
how to return to those previously skipped. This can become a tedious process if
jay

we have to continuously scanned forward and backward through the string in order
to properly evaluate the expression. To simplify the evaluation of a mathematical
expression, we need an alternative representation for the expression. A representation in
which the order the operators are performed is the order they are specified
ofa

would allow for a single left-to-right scan of the expression string.

Three different notations can be used to represent a mathematical expression.
The most common is the traditional algebraic or infix notation where the operator
is specified between the operands A+B. The prefix notation places the operator
pr

immediately preceding the two operands +AB, whereas in postfix notation, the
operator follows the two operands AB+.
At First glance, the different notations may seem to be nothing more than different operator
w.

placement. But the postfix and prefix notations have the advantages that neither uses
parentheses to override the order of precedence and both create expressions in unique
form. In other words, each expression is unique and produces a specific result unlike infix
ww

notation in which the same expression can be written in multiple ways.

Converting from Infix to Postfix
Infix expressions can be easily converted by hand to postfix notation.
The expression A + B - C would be written as AB+C- in postfix form.
The evaluation of this expression would involve first adding A and B and then subtracting C
from that result. We will examine the evaluation of postfix expressions later; for now we
focus on the conversion from infix to postfix.

www.profajaypashankar.com Page 33 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
Postfix Evaluation Algorithm
Parentheses are used with infix expressions to change the order of evaluation. But
in postfix notation, the order cannot be altered and thus there is no need for parentheses.
Given the unique form or single order of evaluation, postfix notation is a good choice when
evaluating a mathematical expression represented as a string.
Of course the expression would have to either be given in postfix notation or first converted
from infix to postfix. The latter can be easily done with an appropriate algorithm, but we
limit our discussion to the evaluation of existing postfix expressions.
Evaluating a postfix expression requires the use of a stack to store the operands or
variables at the beginning of the expression until they are needed. Assume we are given a
valid postfix expression stored in a string consisting of operators and single-letter variables.
We can evaluate the expression by scanning the string, one character or token at a time.
For each token, we perform the following steps:

om
r.c
ka
an
The Final result of the expression will be the last value on the stack. To illustrate
sh
the use of this algorithm, let's evaluate the postfix expression A B C + * D / from
our earlier example. Assume the existence of an empty stack and the following
variable assignments have been made:
pa
A=8C=3
B=2D=4
The complete sequence of algorithm steps and the contents of the stack after
jay

each operation are illustrated in Table 7.3.

The postfix evaluation algorithm assumes a valid expression. But what happens
if the expression is invalid? Consider the following invalid expression in which there
are more operands than available operators:
ofa

AB*CD+
After applying the algorithm to this expression, there are two values remaining
on the stack as illustrated in Table 7.4. What happens if there are too many
operators for the given number of operands? Consider such an invalid expression:
pr

AB*+C/
In this case, there are too few operands on the stack when we encounter the
addition operator, as illustrated in Table 7.5. If we attempt to perform two pops
w.

from the stack, an assertion error will be thrown since the stack will be empty
on the second pop. We can modify the algorithm to detect both types of errors.
ww

www.profajaypashankar.com Page 34 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
sh
pa
In step 2(a), we must first verify the stack is not empty before popping an item. If the stack is empty,
we can stop the evaluation and flag an error. The second modification occurs after the evaluation of the
entire expression. We can pop the result from the stack and then verify the stack is empty. If the stack
is not empty, the expression was invalid and we must fag an error.
jay
ofa
pr
w.
ww

www.profajaypashankar.com Page 35 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
sh
pa
jay

6.6.1 Polynomial Operations

A number of operations can be performed on polynomials. We review several of
ofa

these operations, beginning with addition.

pr
w.
ww

www.profajaypashankar.com Page 36 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
sh
pa
jay
ofa
pr
w.
ww

www.profajaypashankar.com Page 37 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
6.6.2 The Polynomial ADT

r.c
Given the overview of polynomials, we now turn our attention to defining the Polynomial ADT.

ka
an
sh
pa
jay
ofa
pr
w.
ww

www.profajaypashankar.com Page 38 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
sh
pa
jay
ofa
pr
w.
ww

www.profajaypashankar.com Page 39 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
CHAPTER III: RECURSION
Topics covered:
What is recursion, Recursion vs Iteration, recursion applications like Factorial of a number, Fibonacci
series & their comparative analysis with respect to iterative version, Tower of Hanoi
problem
-------------------------------------------------------------------------------------------------------------

What is recursion?
● Any function which calls itself is called recursive.
● A recursive method solves a problem by calling a copy of itself to work on a smaller problem.
● This is called the recursion step.
● The recursion step can result in many more such recursive calls.
● It is important to ensure that the recursion terminates.

om
● Each time the function calls itself with a slightly simpler version of the original problem. The
sequence of smaller problems must eventually converge on the base case.

-------------------------------------------------------------------------------------------------------------------
Why Recursion?

r.c
Recursion is a useful technique borrowed from mathematics. Recursive code is generally shorter
and easier to write than iterative code. Generally, loops are turned into recursive functions when
they are compiled or interpreted.

ka
Recursion is most useful for tasks that can be defined in terms of similar subtasks. For example,
sort, search, and traversal problems often have simple recursive solutions.
-------------------------------------------------------------------------------------------------------------------

an
Recursion versus Iteration

While discussing recursion, the basic question that comes to mind is: which way is better? – iteration
sh
or recursion? The answer to this question depends on what we are trying to do. A recursive approach
mirrors the problem that we are trying to solve. A recursive approach makes it simpler to solve a
problem that may not have the most obvious of answers. But, recursion adds overhead for each
pa
recursive call (needs space on the stack frame).

Recursion
• Terminates when a base case is reached.
jay

• Each recursive call requires extra space on the stack frame (memory).
• If we get infinite recursion, the program may run out of memory and result in stack overflow.
• Solutions to some problems are easier to formulate recursively.
ofa

Iteration
• Terminates when a condition is proven to be false.
• Each iteration does not require extra space.
• An infinite loop could loop forever since there is no extra memory being created.
• Iterative solutions to a problem may not always be as obvious as a recursive solution.
pr

-------------------------------------------------------------------------------------------------------------------
Points to remember:
Recursive algorithms have two types of cases, recursive cases and base cases.
w.

• Every recursive function case must terminate at a base case.

• Generally, iterative solutions are more efficient than recursive solutions [due to the overhead of
function calls].
ww

• A recursive algorithm can be implemented without recursive function calls using a stack, but it’s
usually more trouble than its worth. That means any problem that can be solved recursively can also
be solved iteratively.
• For some problems, there are no obvious iterative algorithms.
• Some problems are best suited for recursive solutions while others are not.
Properties of Recursion
All recursive solutions must satisfy three rules or properties:
1. A recursive solution must contain a base case.
2. A recursive solution must contain a recursive case.
3. A recursive solution must make progress toward the base case.

-------------------------------------------------------------------------------------------------------------------

www.profajaypashankar.com Page 40 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
Example Algorithms of Recursion
• Fibonacci Series, Factorial Finding
• Merge Sort, Quick Sort
• Binary Search
• Tree Traversals and many Tree Problems: InOrder, PreOrder PostOrder
• Graph Traversals: DFS [Depth First Search] and BFS [Breadth First Search]
• Dynamic Programming Examples
• Divide and Conquer Algorithms
• Towers of Hanoi
• Backtracking Algorithms
-------------------------------------------------------------------------------------------------------------------

Factorials

om
The factorial of a positive integer n can be used to calculate the number of permutations of
n elements. The function is defined as:

with the special case of 0! = 1. This problem can be solved easily using an iterative

r.c
implementation that loops through the individual values [1 : : : n] and computes a
product of those values. But it can also be solved with a recursive solution and
provides a simple example of recursion. Consider the factorial function on different

ka
integer values:

an
sh
pa
jay

After careful inspection of these equations, it becomes obvious each of the

successive equations, for n > 1, can be rewritten in terms of the previous equation:
ofa
pr
w.
ww

Since the function is defined in terms of itself and contains a base case, a recursive
definition can be produced for the factorial function as shown here. Listing 10.1
provides a recursive implementation of the factorial function.

www.profajaypashankar.com Page 41 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

Recursive Call Trees

om
Figure 10.1 used boxes to represent function invocations and to illustrate the flow of
execution for two recursive functions. The specific placement of the boxes illustrated the
different results that were achieved depending on the location of the recursive call within
the function. This type of illustration can be very helpful to visualize the flow of execution
within and between various functions, but it's not as useful in developing and understanding

r.c
recursive functions.
When developing or evaluating a recursive function, we typically use a recursive call tree
such as the one for the factorial function illustrated in Figure 10.2.

ka
The diagram consists of small boxes and directed edges between the boxes. Each box
represents a function call and is labeled with the name of the function and the actual
arguments passed to the function when it was invoked. The directed edges between the

an
boxes indicate the flow of execution. The solid edges indicate the function from which a call
originated. For example, in Figure 10.2, we see the call to fact(5) was made from the
main() function while the call to fact(4) was made during the execution of fact(5). The
sh
dashed edges indicate function returns and are labeled with the return value if a value is
returned to the caller.
pa
jay
ofa
pr
w.
ww

-------------------------------------------------------------------------------------------------------------------
The Fibonacci sequence
The Fibonacci sequence is a sequence of integer values in which the first two values are both 1 and
each subsequent value is the sum of the two previous values.
www.profajaypashankar.com Page 42 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
The First 11 terms of the sequence are:
1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; : : :
The nth Fibonacci number can be computed by the recurrence relation (for n > 0):
A recursive function for the computing the nth Fibonacci number is shown in Listing 10.2.
This function illustrates the use of multiple recursive calls from within the body of the
function. The call tree corresponding to the function call fib(6) is illustrated in Figure 10.4.

om
r.c
ka
an
-----------------------------------------------------------------------------------------------------------------
sh
Towers of Hanoi
The Towers of Hanoi puzzle, invented by the French mathematician Edouard Lucas in 1883, consists of
a board with three vertical poles and a stack of disks. The diameter of the disks increases as we
pa
progress from the top to bottom, creating a tower structure. The illustration in Figure 10.12 shows the
board, the three towers, and five disks. Any number of disks can be used with the puzzle, but we use
five for ease of illustration.
jay
ofa
pr
w.
ww

The objective is to move all of the disks from the starting pole to one of the other
two poles to create a new tower. There are, however, two restrictions: (1) only
one disk can be moved at a time, and (2) a larger disk can never be placed on top
of a smaller disk.
How would you go about solving this problem recursively? Of course you need to think about the base
case, the recursive case, and how each recursive call reduces the size of the problem. We will derive all
of these in time, but the easiest way to solve this problem is to think about the problem from the
bottom up. Instead of thinking about the easiest step, moving the top disk, let's start with the hardest
step of moving the bottom disk.

www.profajaypashankar.com Page 43 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
Suppose we already know how to move the top four disks from pole A to pole B, resulting in the board
shown in Figure 10.13. Moving the disk from pole A to pole C is now rather easy since it's the only disk
left on pole A and there are no disks on pole C. After moving the
largest disk, we then move the other four disks from pole B to pole C.

om
r.c
ka
Of course, we still have to Figure out how to move the top four disks. There is no reason we cannot use
the same technique to move the top four disks and in fact we must use the same technique, which

an
leads to a recursive solution. Given n disks and three poles labeled source (S), destination (D), and
intermediate (I), we can define the recursive operation as:
sh
pa
jay

The First and last steps are recursive calls to the same operation but using different poles as
the source, destination, and intermediate designations. The base case, which is implicit in
ofa

this description, occurs when there is a single disk to move, requiring that we skip the First
and last step. Finally, the solution makes progress toward the base case since the recursive
calls move one less disk than the current invocation. Eventually, we will end up with a single
disk to move.
pr

The high-level solution given above for solving the Towers of Hanoi puzzle can be easily
converted to a Python function, as shown in Listing 10.7. For the second step of the process
where we actually move a disk, we simply print a message indicating which disk was moved
w.

and the two poles it was moved between.

ww

To see how this recursive solution works, consider the puzzle using three disks and the execution of the
function call:
move( 3, 1, 3, 2 )
The output produced from the execution is shown here while the First four moves of the disks are
illustrated graphically in Figure 10.14.
www.profajaypashankar.com Page 44 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

To evaluate the time-complexity of the move() function, we need to determine the cost of each
invocation and the number of times the function is called for any value of n. Each function invocation
only requires O(1) time since there are only two non-recursive function call steps performed by the

om
function, both of which require constant time.
Next, we need to determine how many times the function is called. Consider the recursive call tree in
Figure 10.15, which results from the function invocation move(n, 1, 3, 2). The First invocation of
move() results in two recursive calls, both of which move n->1 disks. Both of these invocations each

r.c
make two recursive calls to move n - 2 disks. Those four invocations each make two recursive calls to
move n -3 disks and so on until there is a single disk to be moved.
To determine the total number of times the function is called, we need to calculate the number of times

ka
the function executes at each level of the call tree and then sum those values to obtain the Final result.
The number of function calls at each level is double the number of calls at the previous level. If we
label each level of the call tree starting with 0 at the top and going down to n - 1 at the

an
bottom, then the number of function calls at each level i is equal to 2i. Summing the number of calls at
each level results in the summation:
or a total of 2n - 1 function calls. Thus, the recursive solution for solving the
sh
Towers of Hanoi problem requires exponential time of O(2n) in the worst case.
pa
jay
ofa
pr
w.
ww

www.profajaypashankar.com Page 45 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
sh
pa
jay
ofa

Another way :
Problem-1 Discuss Towers of Hanoi puzzle.
Solution: The Towers of Hanoi is a mathematical puzzle. It consists of three rods (or pegs or
towers), and a number of disks of different sizes which can slide onto any rod. The puzzle starts
pr

with the disks on one rod in ascending order of size, the smallest at the top, thus making a conical
shape. The objective of the puzzle is to move the entire stack to another rod, satisfying the
following rules:
w.

• Only one disk may be moved at a time.

• Each move consists of taking the upper disk from one of the rods and sliding it onto
another rod, on top of the other disks that may already be present on that rod.
ww

• No disk may be placed on top of a smaller disk.

Algorithm:
• Move the top n – 1 disks from Source to Auxiliary tower,
• Move the nth disk from Source to Destination tower,
• Move the n – 1 disks from Auxiliary tower to Destination tower.
• Transferring the top n – 1 disks from Source to Auxiliary tower can again be thought
of as a fresh problem and can be solved in the same manner. Once we solve Towers
of Hanoi with three disks, we can solve it with any number of disks with the above
algorithm.

www.profajaypashankar.com Page 46 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
CHAPTER IV: BASIC SORTING TECHNIQUES
Topics covered:
Basic Sorting Techniques - Bubble, Selection and Insertion Sort & their comparative analysis
------------------------------------------------------------------------------------------------------------
What is Sorting?
Sorting is an algorithm that arranges the elements of a list in a certain order [either ascending or
descending]. The output is a permutation or reordering of the input.
10.2 Why is Sorting Necessary?
Sorting is one of the important categories of algorithms in computer science and a lot of research
has gone into this category. Sorting can significantly reduce the complexity of a problem, and is
often used for database algorithms and searches.
10.3 Classification of Sorting Algorithms
Sorting algorithms are generally categorized based on the following parameters.

om
By Number of Comparisons
In this method, sorting algorithms are classified based on the number of comparisons. For
comparison based sorting algorithms, best case behavior is O(nlogn) and worst case behavior is
O(n2). Comparison-based sorting algorithms evaluate the elements of the list by key comparison
operation and need at least O(nlogn) comparisons for most inputs.

r.c
Later in this chapter we will discuss a few non – comparison (linear) sorting algorithms like
Counting sort, Bucket sort, Radix sort, etc. Linear Sorting algorithms impose few restrictions on
the inputs to improve the complexity.

ka
By Number of Swaps
In this method, sorting algorithms are categorized by the number of swaps (also called
inversions).

an
By Memory Usage
Some sorting algorithms are “in place” and they need O(1) or O(logn) memory to create
auxiliary locations for sorting the data temporarily.
sh
By Recursion
Sorting algorithms are either recursive [quick sort] or non-recursive [selection sort, and insertion
sort], and there are some algorithms which use both (merge sort).
pa
By Stability
Sorting algorithm is stable if for all indices i and j such that the key A[i] equals key A[j], if record
R[i] precedes record R[j] in the original file, record R[i] precedes record R[j] in the sorted list.
Few sorting algorithms maintain the relative order of elements with equal keys (equivalent
jay

elements retain their relative positions even after sorting).

By Adaptability
With a few sorting algorithms, the complexity changes based on pre-sortedness [quick sort]:
ofa

presortedness
of the input affects the running time. Algorithms that take this into account are known to
be adaptive.
10.4 Other Classifications
Another method of classifying sorting algorithms is:
pr

• Internal Sort
• External Sort
Internal Sort
w.

Sort algorithms that use main memory exclusively during the sort are called internal sorting
algorithms. This kind of algorithm assumes high-speed random access to all memory.
External Sort
ww

Sorting algorithms that use external memory, such as tape or disk, during the sort come under this
category.
10.5 Bubble Sort
Bubble sort is the simplest sorting algorithm. It works by iterating the input array from the first
element to the last, comparing each pair of elements and swapping them if needed. Bubble sort
continues its iterations until no more swaps are needed. The algorithm gets its name from the way
smaller elements “bubble” to the top of the list. Generally, insertion sort has better performance
than bubble sort. Some researchers suggest that we should not teach bubble sort because of its
simplicity and high time complexity.
The only significant advantage that bubble sort has over other implementations is that it can detect
whether the input list is already sorted or not.

www.profajaypashankar.com Page 47 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
Performance
Worst case complexity : O(n2)
Best case complexity (Improved version) : O(n)
Average case complexity (Basic version) : O(n2)
Worst case space complexity : O(1) auxiliary

Sorting
Sorting is the process of arranging or ordering a collection of items such that each item and
its successor satisfy a prescribed relationship. The items can be simple values, such as
integers and reals, or more complex types, such as student records or dictionary entries. In
either case, the ordering of the items is based on the value of a sort key. The key is the
value itself when sorting simple types or it can be a specific component or a combination of

om
components when sorting complex types.
We encounter many examples of sorting in everyday life. Consider the listings of a phone
book, the definitions in a dictionary, or the terms in an index, all of which
are organized in alphabetical order to make finding an entry much easier. As we saw earlier
in the chapter, the efficiency of some applications can be improved when working with

r.c
sorted lists. Another common use of sorting is for the presentation of data in some
organized fashion. For example, we may want to sort a class roster by student name, sort a
list of cities by zip code or population, rank order SAT scores, or list entries on a bank

ka
statement by date.
Sorting is one of the most studied problems in computer science and extensive research has
been done in this area, resulting in many different algorithms. While

an
Python provides a sort() method for sorting a list, it cannot be used with an array or other
data structures. In addition, exploring the techniques used by some of the sorting
algorithms for improving the efficiency of the sort problem may provide ideas that can be
sh
used with other types of problems. In this section, we present three basic sorting
algorithms, all of which can be applied to data stored in a mutable sequence such as an
array or list.
pa
Bubble Sort
A simple solution to the sorting problem is the bubble sort algorithm, which rearranges
the values by iterating over the list multiple times, causing larger values
to bubble to the top or end of the list. To illustrate how the bubble sort algorithm
jay

works, suppose we have four playing cards (all of the same suit) that we want to
order from smallest to largest face value. We start by laying the cards out face up
on a table as shown here:
ofa
pr
w.

The algorithm requires multiple passes over the cards, with each pass starting at the first card and
ending one card earlier than on the previous iteration. During each pass, the cards in the first and
second positions are compared. If the first is larger than the second, the two cards are swapped.
ww

Next, the cards in positions two and three are compared. If the first one is larger
than the second, they are swapped. Otherwise, we leave them as they were.

www.profajaypashankar.com Page 48 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

This process continues for each successive pair of cards until the card with the
largest face value is positioned at the end.

om
r.c
ka
The next two passes over the cards are illustrated below. In the second pass the

an
card with the second largest face value is positioned in the next-to-last position.
In the third and final pass, the first two cards will be positioned correctly.
sh
pa
jay
ofa
pr
w.
ww

Listing 5.5 provides a Python implementation of the bubble sort algorithm.

Figure 5.5 illustrates the swaps performed during the first pass of the algorithm

www.profajaypashankar.com Page 49 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

Figure 5.5 illustrates the swaps performed during the first pass of the algorithm when
applied to an array containing 11 integer values. Figure 5.6 shows the ordering of the
values within the array after each iteration of the outer loop.
The efficiency of the bubble sort algorithm only depends on the number of keys in the array
and is independent of the specific values and the initial arrangement of those values. To
determine the efficiency, we must determine the total number of iterations performed by
the inner loop for a sequence containing n values. The outer loop is executed n-1 times
since the algorithm makes n-1 passes over the sequence. The number of iterations for the
inner loop is not fixed, but depends on the current iteration of the outer loop. On the first
pass over the sequence, the inner loop executes n - 1 times; on the second pass, n - 2

om
times; on the third, n -3 times, and so on until it executes once on the last pass. The total
number

r.c
ka
an
sh
pa
jay
ofa
pr
w.
ww

Figure 5.5: First complete pass of the bubble sort algorithm, which places 64 in its correct
position. Black boxes represent values being compared; arrows indicate exchanges.

www.profajaypashankar.com Page 50 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
sh
pa
jay
ofa
pr
w.
ww

Figure 5.6: Result of applying the bubble sort algorithm to the sample sequence.

www.profajaypashankar.com Page 51 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
The gray boxes show the values that are in order after each outer-loop traversal. of
iterations for the inner loop will be the sum of the first n - 1 integers, which equals
resulting in a run time of O(n2). Bubble sort is considered one of the most in-efficient
sorting algorithms due to the total number of swaps required. Given an array of keys in
reverse order, a swap is performed for every iteration of the inner
loop, which can be costly in practice.
The bubble sort algorithm as implemented in Listing 5.5 always performs n2 iterations of
the inner loop. But what if the sequence is already in sorted order?
In this case, there would be no need to sort the sequence. But our implementation still
performs all n2 iterations because it has no way of knowing the sequence is
already sorted.
The bubble sort algorithm can be improved by having it terminate early and not require it to
perform all n2 iterations when the sequence is in sorted order.

om
We can determine the sequence is in sorted order when no swaps are performed by the if
statement within the inner loop. At that point, the function can return immediately without
completing the remaining iterations. If a value is out of sorted order, then it will either be
smaller than its predecessor in the sequence or larger than its successor at which point the
condition of the if statement would be true.

r.c
This improvement, which is left as an exercise, introduces a best case that only requires
O(n) time when the initial input sequence is in sorted order.
-------------------------------------------------------------------------------------------------------------------

ka
Selection Sort
A second sorting algorithm, which improves on the bubble sort and works in a fashion
similar to what a human may use to sort a list of values, is known as the selection sort. We

an
can again use the set of playing cards to illustrate the algorithm and start by placing five
cards face up on a table that are to be sorted in ascending order.
sh
pa
jay
ofa
pr
w.
ww

www.profajaypashankar.com Page 52 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
sh
pa
jay
ofa

The process we used to sort the set of five cards is similar to the approach used
by the selection sort algorithm. But when implementing insertion sort in code, the
algorithm maintains both the sorted and unsorted values within the same sequence
structure. The selection sort, which improves on the bubble sort, makes multiple
pr

passes over the sequence, but unlike the bubble sort, it only makes a single swap
after each pass. The implementation of the selection sort algorithm is provided in
Listing 5.6.
w.

The process starts by finding the smallest value in the sequence and swaps it with the value
in the first position of the sequence. The second smallest value is then found and swapped
with the value in the second position. This process continues positioning each successive
ww

value by selecting them from those not yet sorted and swapping with the values in the
respective positions. Figure 5.7 shows the results after each iteration of the algorithm when
applied to the sample array of integers. The grayed boxes represent those items already
placed in their proper position while the black boxes show the two values that are swapped.
The selection sort, which makes n-1 passes over the array to reposition n-1 values, is also
O(n2). The difference between the selection and bubble sorts is that the selection sort
reduces the number of swaps required to sort the list to O(n).
Insertion Sort
Another commonly studied sorting algorithm is the insertion sort. Continuing with our
analogy of sorting a set of playing cards to illustrate the sorting algorithms, consider five
cards stacked in a deck face up:

www.profajaypashankar.com Page 53 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
sh
pa
jay
ofa
pr
w.
ww

www.profajaypashankar.com Page 54 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
sh
pa
jay
ofa
pr
w.
ww

www.profajaypashankar.com Page 55 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
sh
pa
jay
ofa

This process continues, one card at a time, until all of the cards have been removed from
the table and placed into our hand in their proper sorted position.
The insertion sort maintains a collection of sorted items and a collection of items to be
sorted. In the playing card analogy, the deck represents the collection to be sorted and the
pr

cards in our hand represents those already sorted. When implementing insertion sort in a
program, the algorithm maintains both the sorted and unsorted collections within the same
sequence structure. The algorithm keeps the list of sorted values at the front of the
w.

sequence and picks the next unsorted value from the first of those yet to be positioned. To
position the next item, the correct spot within the sequence of sorted values is found by
performing a search.
ww

After finding the proper position, the slot has to be opened by shifting the items down one
position. A Python implementation of the insertion sort algorithm is provided in Listing 5.7.
The insertionSort() function starts by assuming the first item is in its proper position. Next,
an iteration is performed over the remaining items so each value can be inserted into its
proper position within the sorted portion of the sequence .The ordered portion of the
sequence is at the front while those yet to be inserted are at the end. The i loop index
variable marks the separation point between the two parts. The inner loop is used to find
the insertion point within the sorted sequence and at the same time, shifts the items down
to make room for the next item. Thus, the inner loop starts from the end of the sorted
subsequence and works its way to the front. After finding the proper position, the item is
inserted.
Figure 5.8 illustrates the application of this algorithm on an array of integer values.
The insertion sort is an example of a sorting algorithm in which the best and worst cases
are different. Determining the different cases and the corresponding run times is left as an
www.profajaypashankar.com Page 56 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
exercise.

om
r.c
ka
an
sh
pa
jay
ofa
pr
w.
ww

Figure 5.8: Result of applying the insertion sort algorithm to the sample array. The gray
boxes show values that have been sorted; the black boxes show the next value to be
positioned; and the lighter gray boxes with black text are the sorted values that have to be
shifted to the right to open a spot for the next value.

www.profajaypashankar.com Page 57 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
CHAPTER V: Searching Techniques
Searching
Searching is the process of selecting particular information from a collection of data based
on specific criteria. You are familiar with this concept from your experience in performing
web searches to locate pages containing certain words or phrases or when looking up a
phone number in the telephone book. In this text, we restrict the term searching to refer to
the process of finding a specific item in a collection of data items.
The search operation can be performed on many different data structures. The sequence
search, which is the focus in this chapter, involves finding an item within a sequence using a
search key to identify the specific item. A key is a unique value used to identify the data
elements of a collection. In collections containing simple types such as integers or reals, the
values themselves are the keys.
For collections of complex types, a specific data component has to be identified as the key.

om
In some instances, a key may consist of multiple components, which is also known as a
compound key.

The Linear Search

The simplest solution to the sequence search problem is the sequential or linear search

r.c
algorithm. This technique iterates over the sequence, one item at a time, until the specific
item is found or all items have been examined. In Python, a target item can be found in a
sequence using the in operator:

ka
if key in theArray :
print( "The key is in the array." )
else :

an
print( "The key is not in the array." )
The use of the in operator makes our code simple and easy to read but it hides the inner
workings. Underneath, the in operator is implemented as a linear search. Consider the
sh
unsorted 1-D array of integer values shown in Figure 5.1(a).
To determine if value 31 is in the array, the search begins with the value in the first
element. Since the first element does not contain the target value, the next element in
pa
sequential order is compared to value 31. This process is repeated until the item is found in
the sixth position. What if the item is not in the array? For example, suppose we want to
search for value 8 in the sample array. The search begins at the first entry as before, but
this time every item in the array is compared to the target value. It cannot be determined
jay

that the value is not in the sequence until the entire array has been traversed, as illustrated
in Figure 5.1(b).
ofa
pr
w.
ww

Finding a Specific Item

The function in Listing 5.1 implements the sequential search algorithm, which results in a
boolean value indicating success or failure of the search. This is the same operation
performed by the Python in operator. A count-controlled loop is used to traverse through
the sequence during which each element is compared against the target value. If the item is

www.profajaypashankar.com Page 58 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
in the sequence, the loop is terminated and True is returned. Otherwise, a full traversal is
performed and False is returned after the loop terminates.

om
To analyze the sequential search algorithm for the worst case, we must first determine what
conditions constitute the worst case. Remember, the worst case occurs when the algorithm
performs the maximum number of steps. For a sequential search, that occurs when the

r.c
target item is not in the sequence and the loop iterates over the entire sequence. Assuming
the sequence contains n items, the linear search has a worst case time of O(n).
Searching a Sorted Sequence

ka
A linear search can also be performed on a sorted sequence, which is a sequence containing
values in a specific order. For example, the values in the array illustrated in Figure 5.2 are
in ascending or increasing numerical order. That is, each value in the array is larger than its
predecessor.

an
sh
pa
jay
ofa

A linear search on a sorted sequence works in the same fashion as that for the unsorted
sequence, with one exception. It's possible to terminate the search early when the value is
not in the sequence instead of always having to perform a complete traversal. For example,
suppose we want to search for 8 in the array from Figure 5.2. When the fourth item, which
pr

is value 10, is examined, we know value 8 cannot be in the sorted sequence or it would
come before 10. The implementation of a linear search on a sorted sequence is shown in
Listing 5.2 on the next page.
w.

The only modification to the earlier version is the inclusion of a test to deter- mine if the
current item within the sequence is larger than the target value. If a larger value is
encountered, the loop terminates and False is returned. With the modification to the linear
ww

search algorithm, we have produced a better version, but the time-complexity remains the
same. The reason is that the worst case occurs when the value is not in the sequence and is
larger than the last element. In this case, we must still traverse the entire sequence of n
items.
Finding the Smallest Value
Instead of searching for a specific value in an unsorted sequence, suppose we wanted
to search for the smallest value, which is equivalent to applying Python's min()
function to the sequence. A linear search is performed as before, but this time we must
keep track of the smallest value found for each iteration through the loop, as illustrated in
Listing 5.3.
To prime the loop, we assume the first value in the sequence is the smallest and start the
comparisons at the second item. Since the smallest value can occur anywhere in the
sequence, we must always perform a complete traversal, resulting in a worst case time of
O(n).
www.profajaypashankar.com Page 59 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
-------------------------------------------------------------------------------------------------------------------

r.c
The Binary Search
The linear search algorithm for a sorted sequence produced a slight improvement
over the linear search with an unsorted sequence, but both have a linear timecomplexity

ka
in the worst case. To improve the search time for a sorted sequence,
we can modify the search technique itself.
Consider an example where you are given a stack of exams, which are in alphabetical order,

an
and are asked to find the exam for \Jessica Roberts." In performing
this task, most people would not begin with the first exam and ip through one at
a time until the requested exam is found, as would be done with a linear search.
Instead, you would probably ip to the middle and determine if the requested exam
sh
comes alphabetically before or after that one. Assuming Jessica's paper follows
alphabetically after the middle one, you know it cannot possibly be in the top half of
the stack. Instead, you would probably continue searching in a similar fashion by
pa
splitting the remaining stack of exams in half to determine which portion contains
Jessica's exam. This is an example of a divide and conquer strategy, which entails dividing a
larger problem into smaller parts and conquering the smaller part.
jay

Algorithm Description
The binary search algorithm works in a similar fashion to the process described above and
can be applied to a sorted sequence. The algorithm starts by examining the middle item of
ofa

the sorted sequence, resulting in one of three possible conditions:

the middle item is the target value, the target value is less than the middle item, or the
target is larger than the middle item. Since the sequence is ordered, we can eliminate half
the values in the list when the target value is not found at the middle position.
pr

Consider the task of searching for value 10 in the sorted array from Figure 5.2.
We first determine which element contains the middle entry. As illustrated in
Figure 5.3, the middle entry contains 18, which is greater than our target of 10.
w.

Thus, we can discard the upper half of the array from consideration since 10 cannot possibly
be in that part. Having eliminated the upper half, we repeat the process on the lower half of
the array. We then find the middle item of the lower half and compare its value to the
ww

target. Since that entry, which contains 5, is less than the target, we can eliminate the
lower fourth of the array. The process is repeated on the remaining items. Upon finding
value 10 in the middle entry from among those remaining, the process terminates
successfully. If we had not found the target, the process would continue until either the
target value was found or we had eliminated all values from consideration.

www.profajaypashankar.com Page 60 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
Implementation
The Python implementation of the binary search algorithm is provided in Listing 5.4. The

an
variables low and high are used to mark the range of elements in the sequence currently
under consideration. When the search begins, this range is the entire sequence since the
target item can be anywhere within the sequence. The first step in each iteration is to
sh
determine the midpoint of the sequence. If the sequence contains an even number of
elements, the mid point will be chosen such that the left sequence contains one less item
than the right. Figure 5.4 illustrates the positioning of the low, high, and mid markers as the
pa
algorithm progresses.
jay
ofa
pr
w.
ww

computing the midpoint, the corresponding element in that position is examined. If the
midpoint contains the target, we immediately return True.
Otherwise, we determine if the target is less than the item at the midpoint or greater. If it is

www.profajaypashankar.com Page 61 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
less, we adjust the high marker to be one less than the mid-point and if it is greater, we
adjust the low marker to be one greater than the midpoint. In the next iteration of the loop,
the only portion of the sequence considered are those elements between the low and high
markers, as adjusted. This process is repeated until the item is found or the low marker
becomes greater than the high marker. This condition occurs when there are no items left to
be processed, indicating the target is not in the sorted sequence.
Run Time Analysis
To evaluate the efficiency of the binary search algorithm, assume the sorted sequence
contains n items. We need to determine the maximum number of times the

om
r.c
ka
an
sh
pa
jay
ofa
pr

while loop is executed. The worst case occurs when the target value is not in the sequence,
the same as for the linear search. The difference with the binary search is that not every
w.

item in the sequence has to be examined before determining the target is not in the
sequence, even in the worst case. Since the sequence is sorted, each iteration of the loop
can eliminate from consideration half of the remaining values. As we saw earlier in Section
ww

4.1.2, when the input size is repeatedly reduced by half during each iteration of a loop,
there will be log n iterations in the worst case. Thus, the binary search algorithm has a
worst case time-complexity of O(log n), which is more efficient than the linear search
-------------------------------------------------------------------------------------------------------------------

www.profajaypashankar.com Page 62 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
CHAPTER VI:Selection Techniques
What are Selection Algorithms?
Selection algorithm is an algorithm for finding the kth smallest/largest number in a list (also
called as kth order statistic). This includes finding the minimum, maximum, and median elements.
For finding the kth order statistic, there are multiple solutions which provide different
complexities, and in this chapter we will enumerate those possibilities.
Selection by Sorting
A selection problem can be converted to a sorting problem. In this method, we first sort the input
elements and then get the desired element. It is efficient if we want to perform many selections.
For example, let us say we want to get the minimum element. After sorting the input elements we
can simply return the first element (assuming the array is sorted in ascending order). Now, if we
want to find the second smallest element, we can simply return the second element from the sorted
list.

om
That means, for the second smallest element we are not performing the sorting again. The same is
also the case with subsequent queries. Even if we want to get kth smallest element, just one scan
of the sorted list is enough to find the element (or we can return the kth-indexed value if the
elements are in the array).
From the above discussion what we can say is, with the initial sorting we can answer any query

r.c
in one scan, O(n). In general, this method requires O(nlogn) time (for sorting), where n is the
length of the input list. Suppose we are performing n queries, then the average cost per operation

ka
is just . This kind of analysis is called amortized analysis.

an
Linear Selection Algorithm - Median of Medians Algorithm
Worst-case performance O(n)
sh
Best-case performance O(n)
Worst-case space complexity O(1) auxiliary
Refer to Problem-11.
pa
Finding the K Smallest Elements in Sorted Order
For the algorithm check Problem-6.
Problem-6 Find the k-smallest elements in an array S of n elements using partitioning
jay

method.
Solution: Brute Force Approach: Scan through the numbers k times to have the desired element.
This method is the one used in bubble sort (and selection sort), every time we find out the
smallest element in the whole sequence by comparing every element. In this method, the sequence
ofa

has to be traversed k times. So the complexity is O(n × k).

This algorithm is similar to Quick sort.

Quicksort
Quick sort is an example of a divide-and-conquer algorithmic technique. It is also called
pr

partition exchange sort. It uses recursive calls for sorting the elements, and it is one of the
famous algorithms among comparison-based sorting algorithms.
w.

Divide: The array A[low ...high] is partitioned into two non-empty sub arrays A[low ...q] and A[q
+ 1... high], such that each element of A[low ... high] is less than or equal to each element of A[q
+ 1... high]. The index q is computed as part of this partitioning procedure.
ww

Conquer: The two sub arrays A[low ...q] and A[q + 1 ...high] are sorted by recursive calls to
Quick sort.
Algorithm
The recursive algorithm consists of four steps:
1) If there are one or no elements in the array to be sorted, return.
2) Pick an element in the array to serve as the “pivot” point. (Usually the left-most
element in the array is used.)
3) Split the array into two parts – one with elements larger than the pivot and the other
with elements smaller than the pivot.
4) Recursively repeat the algorithm for both halves of the original array.
Implementation
Selection Algorithms: Problems & Solutions
Problem-1 Find the largest element in an array A of size n.
Solution: Scan the complete array and return the largest element.

www.profajaypashankar.com Page 63 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
-------------------------------------------------------------------------------------------------------------------
CHAPTER VII: String Algorithms

Topics covered:
String Algorithms - Pattern matching in strings, Brute Force Method & their comparative analysis

-------------------------------------------------------------------------------------------------------------------
Given a string, how do we search a substring (pattern)? This is called a string matching problem.

String Matching Algorithms

In this section, we concentrate on checking whether a pattern P is a substring of another string T
(T stands for text) or not. Since we are trying to check a fixed string P, sometimes these
algorithms are called exact string matching algorithms. To simplify our discussion, let us assume

om
that the length of given text T is n and the length of the pattern P which we are trying to match has
the length m. That means, T has the characters from 0 to n – 1 (T[0 ...n – 1]) and P has the
characters from 0 to m – 1 (T[0 ...m – 1]). This algorithm is implemented in C + + as strstr().

r.c
In the subsequent sections, we start with the brute force method and gradually move towards
better algorithms.
• Brute Force Method

ka
• Rabin-Karp String Matching Algorithm
• String Matching with Finite Automata
• KMP Algorithm

an
• Boyer-Moore Algorithm
• Suffix Trees

Brute Force Method

sh
In this method, for each possible position in the text T we check whether the pattern P matches or
not. Since the length of T is n, we have n – m + 1 possible choices for comparisons. This is
because we do not need to check the last m – 1 locations of T as the pattern length is m. The
pa
following algorithm searches for the first occurrence of a pattern string P in a text string T.
Algorithm
jay
ofa
pr
w.
ww

Time Complexity: O((n – m + 1) × m) ≈ O(n × m). Space Complexity: O(1).

Brute Force • The Brute Force algorithm compares the pattern to the text, one character at a time,
until unmatching characters are found:

www.profajaypashankar.com Page 64 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
Compared characters are italicized. - Correct matches are in boldface type.

ka
• The algorithm can be designed to stop on either the first occurrence of the pattern, or upon reaching
the end of the text.
Brute Force-Complexity

an
• Given a pattern M characters in length, and a text N characters in length...
• Worst case: compares pattern to each substring of text of length M. For example, M=5.
Time Complexity: O((n – m + 1) × m) ≈ O(n × m). Space Complexity: O(1).
sh
Worst case time complexity: Ο(MN)
Best case time complexity: Ο(M)
pa
Rabin-Karp
• The Rabin-Karp string searching algorithm uses a hash function to speed up the search.
jay

The Rabin-Karp string searching algorithm calculates a hash value for the pattern, and for each
M-character subsequence of text to be compared.
• If the hash values are unequal, the algorithm will calculate the hash value for next M-character
ofa

sequence.
• If the hash values are equal, the algorithm will do a Brute Force comparison between the pattern and
the M-character sequence.
• In this way, there is only one comparison per text subsequence, and Brute Force is only needed when
hash values match.
pr

Worst case time complexity: Ο(MN)

Best case time complexity: Ο(M)
w.

The Knuth-Morris-Pratt Algorithm

• The Knuth-Morris-Pratt (KMP) string searching algorithm differs from the brute-force algorithm by
keeping track of information gained from previous comparisons.
ww

• A failure function (f) is computed that indicates how much of the last comparison can be reused if it
fails.
• Specifically, f is defined to be the longest prefix of the pattern P[0,..,j] that is also a suffix of P[1,..,j]
- Note: not a suffix of P[0,..,j]

www.profajaypashankar.com Page 65 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
CHAPTER VIII: ALGORITHM DESIGN TECHNIQUES

Algorithm Design Techniques - Introduction to various types of classifications/design criteria and

design techniques

Classification
There are many ways of classifying algorithms and a few of them are shown below:
• Implementation Method
• Design Method
• Other Classifications

Classification by Implementation Method

om
Recursion or Iteration
A recursive algorithm is one that calls itself repeatedly until a base condition is satisfied. It is a
common method used in functional programming languages like C,C + +, etc.
Iterative algorithms use constructs like loops and sometimes other data structures like stacks and
queues to solve the problems.

r.c
Some problems are suited for recursive and others are suited for iterative. For example, the
Towers of Hanoi problem can be easily understood in recursive implementation. Every recursive
version has an iterative version, and vice versa.

ka
Procedural or Declarative (non-Procedural)
In declarative programming languages, we say what we want without having to say how to do it.

an
With procedural programming, we have to specify the exact steps to get the result. For example,
SQL is more declarative than procedural, because the queries don’t specify the steps to produce
the result. Examples of procedural languages include: C, PHP, and PERL.
sh
Serial or Parallel or Distributed
In general, while discussing the algorithms we assume that computers execute one instruction at a
pa
time. These are called serial algorithms.
Parallel algorithms take advantage of computer architectures to process several instructions at a
time. They divide the problem into subproblems and serve them to several processors or threads.
jay

Iterative algorithms are generally parallelizable.

If the parallel algorithms are distributed on to different machines then we call such algorithms
distributed algorithms.
ofa

Deterministic or Non-Deterministic
Deterministic algorithms solve the problem with a predefined process, whereas non – deterministic
algorithms guess the best solution at each step through the use of heuristics.

Exact or Approximate
pr

As we have seen, for many problems we are not able to find the optimal solutions. That means,
the algorithms for which we are able to find the optimal solutions are called exact algorithms. In
w.

computer science, if we do not have the optimal solution, we give approximation algorithms.
Approximation algorithms are generally associated with NP-hard problems (refer to the
Complexity Classes chapter for more details).
ww

Classification by Design Method

Another way of classifying algorithms is by their design method.
Greedy Method
Greedy algorithms work in stages. In each stage, a decision is made that is good at that point,
without bothering about the future consequences. Generally, this means that some local best is
chosen. It assumes that the local best selection also makes for the global optimal solution.

Divide and Conquer

The D & C strategy solves a problem by:
1) Divide: Breaking the problem into sub problems that are themselves smaller
instances of the same type of problem.
2) Recursion: Recursively solving these sub problems.
3) Conquer: Appropriately combining their answers.

www.profajaypashankar.com Page 66 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
Examples: merge sort and binary search algorithms.

Dynamic Programming
Dynamic programming (DP) and memoization work together. The difference between DP and
divide and conquer is that in the case of the latter there is no dependency among the sub problems,
whereas in DP there will be an overlap of sub-problems. By using memoization [maintaining a
table for already solved sub problems], DP reduces the exponential complexity to polynomial
complexity (O(n2), O(n3), etc.) for many problems.
The difference between dynamic programming and recursion is in the memoization of recursive
calls. When sub problems are independent and if there is no repetition, memoization does not
help, hence dynamic programming is not a solution for all problems.
By using memoization [maintaining a table of sub problems already solved], dynamic
programming reduces the complexity from exponential to polynomial.

om
Linear Programming
In linear programming, there are inequalities in terms of inputs and maximizing (or minimizing)
some linear function of the inputs. Many problems (example: maximum flow for directed graphs)
can be discussed using linear programming.

r.c
Reduction [Transform and Conquer]
In this method we solve a difficult problem by transforming it into a known problem for which we

ka
have asymptotically optimal algorithms. In this method, the goal is to find a reducing algorithm
whose complexity is not dominated by the resulting reduced algorithms. For example, the
selection algorithm for finding the median in a list involves first sorting the list and then finding

an
out the middle element in the sorted list. These techniques are also called transform and conquer.

Other Classifications
sh
Classification by Research Area
In computer science each field has its own problems and needs efficient algorithms. Examples:
search algorithms, sorting algorithms, merge algorithms, numerical algorithms, graph algorithms,
pa
string algorithms, geometric algorithms, combinatorial algorithms, machine learning,
cryptography, parallel algorithms, data compression algorithms, parsing techniques, and more.

Classification by Complexity
jay

In this classification, algorithms are classified by the time they take to find a solution based on
their input size. Some algorithms take linear time complexity (O(n)) and others take exponential
time, and some never halt. Note that some problems may have multiple algorithms with different
ofa

complexities.

Randomized Algorithms
A few algorithms make choices randomly. For some problems, the fastest solutions must involve
randomness. Example: Quick Sort.
pr

Branch and Bound Enumeration and Backtracking

These were used in Artificial Intelligence and we do not need to explore these fully. For the
w.

Backtracking method refer to the Recursion and Backtracking chapter.

What is Backtracking?
ww

Backtracking is an improvement of the brute force approach. It systematically searches for a

solution to a problem among all available options. In backtracking, we start with one possible
option out of many available options and try to solve the problem if we are able to solve the
problem with the selected move then we will print the solution else we will backtrack and select
some other option and try to solve it. If none if the options work out we will claim that there is no
solution for the problem.

Note: In the next few chapters we discuss the Greedy, Divide and Conquer, and Dynamic
Programming] design methods. These methods are emphasized because they are used more often
than other methods to solve problems.

www.profajaypashankar.com Page 67 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
CHAPTER IX: GREEDY TECHNIQUE

Greedy Technique - Concept, Advantages & Disadvantages, Applications, Implementation using

problems like - file merging problem

Greedy Strategy : Greedy algorithms work in stages.

In each stage, a decision is made that is good at that point, without bothering about the future. This
means that some local best is chosen.
It assumes that a local good selection makes for a global optimal solution.

Elements of Greedy Algorithms

The two basic properties of optimal Greedy algorithms are:
1) Greedy choice property

om
2) Optimal substructure Greedy choice property

This property says that the globally optimal solution can be obtained by making a locally optimal
solution (Greedy).
The choice made by a Greedy algorithm may depend on earlier choices but not on the future.

r.c
It iteratively makes one Greedy choice after another and reduces the given problem to a smaller one.
Optimal substructure A problem exhibits optimal substructure if an optimal solution to the problem
contains optimal solutions to the subproblems. That means we can solve subproblems and build up the

ka
solutions to solve larger problems.

17.4 Does Greedy Always Work? Making locally optimal choices does not always work. Hence,

an
Greedy algorithms will not always give the best solutions. We will see particular examples in the
Problems section and in the Dynamic Programming chapter.
sh
17.5 Advantages and Disadvantages of Greedy Method The main advantage of the Greedy
method is that it is straightforward, easy to understand and easy to code. In Greedy algorithms, once
we make a decision, we do not have to spend time reexamining the already computed values.
pa
Its main disadvantage is that for many problems there is no greedy algorithm. That means, in many
cases there is no guarantee that making locally optimal improvements in a locally optimal solution
gives the optimal global solution.
jay

17.6 Greedy Applications

• Sorting: Selection sort, Topological sort
• Priority Queues: Heap sort
ofa

• Huffman coding compression algorithm

• Prim’s and Kruskal’s algorithms
• Shortest path in Weighted Graph [Dijkstra’s]
• Coin change problem
• Fractional Knapsack problem
pr

• Disjoint sets-UNION by size and UNION by height (or rank)

• Job scheduling algorithm
w.

• Greedy techniques can be used as an approximation algorithm for complex problems

17.7 Understanding Greedy Technique For better understanding let us go through an example.
ww

Huffman Coding Algorithm Definition Given a set of n characters from the alphabet A [each character c
∈ A] and their associated frequency freq(c), find a binary code for each character c ∈ A, such that ∑c
∈ A freq(c)|binarycode(c)| is minimum, where /binarycode(c)/represents the length of binary code of
character c. That means the sum of the lengths of all character codes should be minimum [the sum of
each character’s frequency multiplied by the number of bits in the representation]. The basic idea
behind the Huffman coding algorithm is to use fewer bits for more frequently occurring characters. The
Huffman coding algorithm compresses the storage of data using variable length codes. We know that
each character takes 8 bits for representation. But in general, we do not use all of them. Also, we use
some characters more frequently than others. When reading a file, the system generally reads 8 bits at
a time to read a single character. But this coding scheme is inefficient. The reason for this is that some
characters are more frequently used than other characters. Let’s say that the character ′e′ is used 10
times more frequently than the character ′q′. It would then be advantageous for us to instead use a 7
bit code for e and a 9 bit code for q because that could reduce our overall message length. On average,
using Huffman coding on standard files can reduce them anywhere from 10% to 30% depending on the

www.profajaypashankar.com Page 68 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
character frequencies. The idea behind the character coding is to give longer binary codes for less
frequent characters and groups of characters. Also, the character coding is constructed in such a way
that no two character codes are prefixes of each other.
An Example Let’s assume that after scanning a file we find the following character frequencies

om
r.c
Given this, create a binary tree for each character that also stores the frequency with which it occurs
(as shown below).

ka
Greedy Algorithms: Problems & Solutions

an
Problem-1 Given an array F with size n.
Assume the array content F[i] indicates the length of the i th file and we want to merge all these files
into one single file. Check whether the following algorithm gives the best solution for this problem or
sh
not.
Algorithm: Merge the files contiguously.
That means select the first two files and merge them.
pa
Then select the output of the previous merge and merge with the third file, and keep going…

Note: Given two files A and B with sizes m and n, the complexity of merging is O(m + n).
jay

Solution: This algorithm will not produce the optimal solution.

For a counter example, let us consider the following file sizes array. F = {10,5,100,50,20,15} As per
the above algorithm, we need to merge the first two files (10 and 5 size files), and as a result we get
ofa

the following list of files. In the list below, 15 indicates the cost of merging two files with sizes 10 and
5. {15,100,50,20,15} Similarly, merging 15 with the next file 100 produces: {115,50,20,15}. For the
subsequent steps the list becomes {165,20,15}, {185,15} Finally, {200} The total cost of merging =
Cost of all merging operations = 15 + 115 + 165 + 185 + 200 = 680. To see whether the above result
pr

is optimal or not, consider the order: {5,10,15,20,50,100}. For this example, following the same
approach, the total cost of merging = 15 + 30 + 50 + 100 + 200 = 395. So, the given algorithm is not
giving the best (optimal) solution
w.

Problem-2 Similar to Problem-1, does the following algorithm give the optimal solution?
ww

Algorithm: Merge the files in pairs. That means after the first step, the algorithm produces the n/2
intermediate files. For the next step, we need to consider these intermediate files and merge them in
pairs and keep going.
Note: Sometimes this algorithm is called 2-way merging. Instead of two files at a time, if we merge K
files at a time then we call it K-way merging.
Solution: This algorithm will not produce the optimal solution and consider the previous example for a
counter example. As per the above algorithm, we need to merge the first pair of files (10 and 5 size
files), the second pair of files (100 and 50) and the third pair of files (20 and 15). As a result we get
the following list of files. {15,150,35} Similarly, merge the output in pairs and this step produces
[below, the third element does not have a pair element, so keep it the same]: {165,35} Finally, {185}
The total cost of merging = Cost of all merging operations = 15 + 150 + 35 + 165 + 185 = 550. This
is much more than 395 (of the previous problem). So, the given algorithm is not giving the best
(optimal) solution.

www.profajaypashankar.com Page 69 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
CHAPTER X:Divide-n-Conquer -

Concept, Advantages & Disadvantages, Applications, Implementation using problems like - merge sort,
Strassen's Matrix Multiplication
—-----------------------------------------------------------------------------------------------------------------
In the Greedy chapter, we have seen that for many problems the Greedy strategy failed to provide
optimal solutions. Among those problems, there are some that can be easily solved by using the Divide
and Conquer (D & C) technique.

Divide and Conquer is an important algorithm design technique based on recursion.

The D & C algorithm works by recursively breaking down a problem into two or more sub problems of
the same type, until they become simple enough to be solved directly.

om
The solutions to the sub problems are then combined to give a solution to the original problem.

What is Divide and Conquer Strategy?

r.c
The D & C strategy solves a problem by:
1) Divide: Breaking the problem into sub problems that are themselves smaller instances of the same
type of problem.

ka
2) Recursion: Recursively solving these sub problems.
3) Conquer: Appropriately combining their answers.

an
Does Divide and Conquer Always Work?
It’s not possible to solve all the problems with the Divide & Conquer technique. As per the definition of
D & C, the recursion solves the subproblems which are of the same type. For all problems it is not
sh
possible to find the subproblems which are the same size and D & C is not a choice for all problems.

18.4 Divide and Conquer Visualization For better understanding, consider the following visualization.
pa
Assume that n is the size of the original problem. As described above, we can see that the problem is
divided into sub problems with each of size n/b (for some constant b). We solve the sub problems
recursively and combine their solutions to get the solution for the original problem
jay
ofa
pr
w.
ww

www.profajaypashankar.com Page 70 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
Understanding Divide and Conquer For a clear understanding of D & C, let us consider a story. There
was an old man who was a rich farmer and had seven sons. He was afraid that when he died, his land
and his possessions would be divided among his seven sons, and that they would quarrel with one

ka
another. So he gathered them together and showed them seven sticks that he had tied together and
told them that anyone who could break the bundle would inherit everything. They all tried, but no one
could break the bundle. Then the old man untied the bundle and broke the sticks one by one. The

an
brothers decided that they should stay together and work together and succeed together. The moral for
problem solvers is different. If we can’t solve the problem, divide it into parts, and solve one part at a
time. In earlier chapters we have already solved many problems based on D & C strategy: like Binary
sh
Search, Merge Sort, Quick Sort, etc.... Refer to those topics to get an idea of how D & C works. Below
are a few other real-time problems which can easily be solved with D & C strategy. For all these
problems we can find the subproblems which are similar to the original problem.
pa
• Looking for a name in a phone book: We have a phone book with names in alphabetical order. Given
a name, how do we find whether that name is there in the phone book or not?
• Breaking a stone into dust: We want to convert a stone into dust (very small stones).
• Finding the exit in a hotel: We are at the end of a very long hotel lobby with a long series of doors,
jay

with one door next to us. We are looking for the door that leads to the exit.
• Finding our car in a parking lot.
ofa

18.6 Advantages of Divide and Conquer Solving difficult problems: D & C is a powerful method for
solving difficult problems. As an example, consider the Tower of Hanoi problem. This requires breaking
the problem into subproblems, solving the trivial cases and combining the subproblems to solve the
original problem.
Dividing the problem into subproblems so that subproblems can be combined again is a major difficulty
pr

in designing a new algorithm. For many such problems D & C provides a simple solution.

Parallelism: Since D & C allows us to solve the subproblems independently, this allows for execution
w.

in multiprocessor machines, especially shared-memory systems where the communication of data

between processors does not need to be planned in advance, because different subproblems can be
executed on different processors.
ww

Memory access: D & C algorithms naturally tend to make efficient use of memory caches. This is
because once a subproblem is small, all its subproblems can be solved within the cache, without
accessing the slower main memory.

18.7 Disadvantages of Divide and Conquer One disadvantage of the D & C approach is that
recursion is slow. This is because of the overhead of the repeated subproblem calls. Also, the D & C
approach needs a stack for storing the calls (the state at each point in the recursion). Actually this
depends upon the implementation style. With large enough recursive base cases, the overhead of
recursion can become negligible for many problems. Another problem with D & C is that, for some
problems, it may be more complicated than an iterative approach. For example, to add n numbers, a
simple loop to add them up in sequence is much easier than a D & C approach that breaks the set of
numbers into two halves, adds them recursively, and then adds the sums.

www.profajaypashankar.com Page 71 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

Starssen’s Matrix:

Discuss Strassen’s Matrix Multiplication Algorithm using Divide and Conquer.

That means, given two n × n matrices, A and B, compute the n × n matrix C = A × B, where
the elements of C are given by

Solution: Before Strassen’s algorithm, first let us see the basic divide and conquer algorithm. The

om
general approach we follow for solving this problem is given below. To determine, C[i,j] we
need to multiply the ith row of A with j th column of B.

r.c
ka
The matrix multiplication problem can be solved with the D & C technique. To implement a D &

an
C algorithm we need to break the given problem into several subproblems that are similar to the
original one. In this instance we view each of the n × n matrices as a 2 × 2 matrix, the elements of
which are submatrices. So, the original matrix multiplication, C = A × B can be written as:
sh
pa
jay

From the given definition o f Ci,j

, we get that the result sub matrices can be computed as follows:
ofa
pr
w.

Here the symbols + and × are taken to mean addition and multiplication (respectively) of
ww

matrices.

In order to compute the original n × n matrix multiplication we must compute eight matrix

products (divide) followed by four matrix sums (conquer) . Since matrix addition is an O(n
2
)
operation, the total running time for the multiplication operation is given by the recurrence:

www.profajaypashankar.com Page 72 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

Using master theorem, we get T(n) = O(n).

Fortunately, it turns out that one of the eight matrix multiplications is redundant (found by
Strassen). Consider the following series of seven matrices:

om
r.c
ka
Each equation above has only one multiplication. Ten additions and seven multiplications are

an
required to compute M0 through M6 . Given M0 through M6

, we can compute the elements of the product matrix C as follows:

sh
pa
jay
ofa

This approach requires seven matrix multiplications and 18 additions. Therefore, the
worst-case running time is given by the following recurrence:
pr
w.

Using master theorem, we get,

ww

www.profajaypashankar.com Page 73 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
CHAPTER XI:Dynamic Programming
Topics Covered:

Concept, Advantages & Disadvantages, Applications, Implementation using problems like - Fibonacci
series, Factorial of a number, Longest Common subsequence
—-----------------------------------------------------------------------------------------------------------------
Dynamic Programming
(DP) is a simple technique but it can be difficult to master. One easy way to identify and solve DP
problems is by solving as many problems as possible. The term Programming is not related to
coding but it is from literature, and means filling tables (similar to Linear Programming).

What is Dynamic Programming Strategy?

Dynamic programming and memoization work together. The main difference between dynamic

om
programming and divide and conquer is that in the case of the latter, sub problems are
independent, whereas in DP there can be an overlap of sub problems. By using memoization
[maintaining a table of sub problems already solved], dynamic programming reduces the
exponential complexity to polynomial complexity (O(n2), O(n3), etc.) for many problems. The

r.c
major components of DP are:
• Recursion: Solves sub problems recursively.
Memoization: Stores already computed values in table (Memoization means caching).

ka
Dynamic Programming = Recursion + Memoization

an
Properties of Dynamic Programming Strategy

The two dynamic programming properties which can tell whether it can solve the given problem
sh
or not are:
• Optimal substructure: an optimal solution to a problem contains optimal solutions
to sub problems.
pa
• Overlapping subproblems: a recursive solution contains a small number of distinct
sub problems repeated many times.

Can Dynamic Programming Solve All Problems?

jay

Like Greedy and Divide and Conquer techniques, DP cannot solve every problem. There are
problems which cannot be solved by any algorithmic technique [Greedy, Divide and Conquer and
Dynamic Programming].
ofa

The difference between Dynamic Programming and straightforward recursion is in memoization

of recursive calls. If the sub problems are independent and there is no repetition then memoization
does not help, so dynamic programming is not a solution for all problems.

Dynamic Programming Approaches

pr

Basically there are two approaches for solving DP problems:

• Bottom-up dynamic programming
• Top-down dynamic programming
w.

Bottom-up Dynamic Programming

In this method, we evaluate the function starting with the smallest possible input argument value
ww

and then we step through possible values, slowly increasing the input argument value. While
computing the values we store all computed values in a table (memory). As larger arguments are
evaluated, pre-computed values for smaller arguments can be used.

Top-down Dynamic Programming

In this method, the problem is broken into sub problems; each of these sub problems is solved;
and the solutions remembered, in case they need to be solved. Also, we save each computed
value as the final action of the recursive function, and as the first action we check if pre-computed
value exists.

Bottom-up versus Top-down Programming

In bottom-up programming, the programmer has to select values to calculate and decide the order

www.profajaypashankar.com Page 74 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
of calculation. In this case, all sub problems that might be needed are solved in advance and then
used to build up solutions to larger problems. In top-down programming, the recursive structure
of the original code is preserved, but unnecessary recalculation is avoided. The problem is
broken into sub problems, these sub problems are solved and the solutions remembered, in case
they need to be solved again.
Note: Some problems can be solved with both the techniques and we will see examples in the
next section.

Examples of Dynamic Programming Algorithms

• Many string algorithms including longest common subsequence, longest increasing

subsequence, longest common substring, edit distance.
• Algorithms on graphs can be solved efficiently: Bellman-Ford algorithm for finding

om
the shortest distance in a graph, Floyd’s All-Pairs shortest path algorithm, etc.
• Chain matrix multiplication
• Subset Sum
• 0/1 Knapsack
• Travelling salesman problem, and many more

r.c
Understanding Dynamic Programming
Before going to problems, let us understand how DP works through examples.

ka
Fibonacci Series
In Fibonacci series, the current number is the sum of previous two numbers. The Fibonacci series

an
is defined as follows:sh
pa
jay
ofa
pr
w.
ww

How does Memoization help?

Calling fib(5) produces a call tree that calls the function on the same value many times:
fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

www.profajaypashankar.com Page 75 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
In the above example, fib(2) was calculated three times (overlapping of subproblems). If n is big,
then many more values of fib (sub problems) are recalculated, which leads to an exponential time
algorithm. Instead of solving the same sub problems again and again we can store the previous
calculated values and reduce the complexity.

Memoization works like this: Start with a recursive function and add a table that maps the
function’s parameter values to the results computed by the function. Then if this function is called
twice with the same parameters, we simply look up the answer in the table.
Improving: Now, we see how DP reduces this problem complexity from exponential to
polynomial. As discussed earlier, there are two ways of doing this. One approach is bottom-up:
these methods start with lower values of input and keep building the solutions for higher values.

om
r.c
ka
an
sh
pa
jay
ofa
pr
w.
ww

Note: For all problems, it may not be possible to find both top-down and bottom-up programming
solutions.

Both versions of the Fibonacci series implementations clearly reduce the problem complexity to
O(n). This is because if a value is already computed then we are not calling the subproblems
again. Instead, we are directly taking its value from the table.
Time Complexity: O(n). Space Complexity: O(n), for table.
Further Improving: One more observation from the Fibonacci series is: The current value is the
sum of the previous two calculations only. This indicates that we don’t have to store all the
previous values. Instead, if we store just the last two values, we can calculate the current value.
The implementation for this is given below:

www.profajaypashankar.com Page 76 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
Time Complexity: O(n). Space Complexity: O(1).
Note: This method may not be applicable (available) for all problems.

Observations

r.c
While solving the problems using DP, try to figure out the following:
• See how the problems are defined in terms of subproblems recursively.
• See if we can use some table [memoization] to avoid the repeated calculations.

ka
—-----------------------------------------------------------------------------------------------------------------
Factorial of a Number
As another example, consider the factorial problem: n! is the product of all integers between n

an
and 1. The definition of recursive factorial can be given as:
sh
pa

This definition can easily be converted to implementation. Here the problem is finding the value
of n!, and the sub-problem is finding the value of (n – l)!. In the recursive case, when n is greater
jay

than 1, the function calls itself to find the value of (n – l)! and multiplies that with n. In the base
case, when n is 0 or 1, the function simply returns 1.
ofa
pr
w.

The recurrence for the above implementation can be given as: T(n) = n × T(n – 1) ≈ O(n)
Time Complexity: O(n).
ww

Space Complexity: O(n),

recursive calls need a stack of size n.
In the above recurrence relation and implementation, for any n value, there are no repetitive
calculations (no overlapping of sub problems) and the factorial function is not getting any benefits
with dynamic programming. Now, let us say we want to compute a series of m! for some arbitrary
value m. Using the above algorithm, for each such call we can compute it in O(m). For example,
to find both n! and m! we can use the above approach, wherein the total complexity for finding n!
and m! is O(m + n).
Time Complexity: O(n + m).
Space Complexity: O(max(m,n)), recursive calls need a stack of size equal to the maximum of m
and n.
Improving: Now let us see how DP reduces the complexity. From the above recursive definition
it can be seen that fact(n) is calculated from fact(n -1) and n and nothing else. Instead of calling
fact(n) every time, we can store the previous calculated values in a table and use these values to
www.profajaypashankar.com Page 77 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
calculate a new value. This implementation can be given as:

om
r.c
For simplicity, let us assume that we have already calculated n! and want to find m!. For finding
m!, we just need to see the table and use the existing entries if they are already computed. If m < n
then we do not have to recalculate m!. If m > n then we can use n! and call the factorial on the

ka
remaining numbers only.
The above implementation clearly reduces the complexity to O(max(m,n)). This is because if the
fact(n) is already there, then we are not recalculating the value again. If we fill these newly

an
computed values, then the subsequent calls further reduce the complexity.
Time Complexity: O(max(m,n)). Space Complexity: O(max(m,n)) for table.
—-----------------------------------------------------------------------------------------------------------------
sh
Longest Common Subsequence
Given two strings: string X of length m [X(1..m)], and string Y of length n [Y(1..n)], find the
longest common subsequence: the longest sequence of characters that appear left-to-right (but not
pa
necessarily in a contiguous block) in both strings. For example, if X = “ABCBDAB” and Y =
“BDCABA”, the LCS(X, Y) = {“BCBA”, “BDAB”, “BCAB”}. We can see there are several
optimal solutions.
jay

Brute Force Approach: One simple idea is to check every subsequence of X[1.. m] (m is the
length of sequence X) to see if it is also a subsequence of Y[1..n] (n is the length of sequence Y).
Checking takes O(n) time, and there are 2m subsequences of X. The running time thus is
exponential O(n. 2m) and is not good for large sequences.
ofa

Recursive Solution: Before going to DP solution, let us form the recursive solution for this and
later we can add memoization to reduce the complexity. Let’s start with some simple observations
about the LCS problem. If we have two strings, say “ABCBDAB” and “BDCABA”, and if we
pr

draw lines from the letters in the first string to the corresponding letters in the second, no two
lines cross:
w.
ww

From the above observation, we can see that the current characters of X and Y may or may not
match. That means, suppose that the two first characters differ. Then it is not possible for both of
them to be part of a common subsequence - one or the other (or maybe both) will have to be
removed. Finally, observe that once we have decided what to do with the first characters of the
strings, the remaining sub problem is again a LCS problem, on two shorter strings. Therefore we
can solve it recursively.
The solution to LCS should find two sequences in X and Y and let us say the starting index of
sequence in X is i and the starting index of sequence in Y is j. Also, assume that X[i ...m] is a
substring of X starting at character i and going until the end of X, and that Y[j ...n] is a substring of
Y starting at character j and going until the end of Y.
Based on the above discussion, here we get the possibilities as described below:

www.profajaypashankar.com Page 78 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
1) If X[i] == Y[j] : 1 + LCS(i + 1,j + 1)
2) If X[i] ≠ Y[j]. LCS(i,j + 1) // skipping j

th character of Y

3) If X[i] ≠ Y[j]. LCS(i + 1,j) // skipping i

th character of X

In the first case, if X[i] is equal to Y[j], we get a matching pair and can count it towards the total
length of the LCS. Otherwise, we need to skip either i

th character of X or j

om
th character of Y and

find the longest common subsequence. Now, LCS(i,j) can be defined as:

r.c
ka
an
sh
pa
jay
ofa
pr
w.
ww

www.profajaypashankar.com Page 79 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
CHAPTER XII:Backtracking Programming

Topics Covered:
Concept, Advantages & Disadvantages, Applications, Implementation using problems like N-Queen
Problem .
—-----------------------------------------------------------------------------------------------------------------
What is Backtracking?
Backtracking is an improvement of the brute force approach. It systematically searches for a
solution to a problem among all available options. In backtracking, we start with one possible
option out of many available options and try to solve the problem if we are able to solve the
problem with the selected move then we will print the solution else we will backtrack and select
some other option and try to solve it. If none if the options work out we will claim that there is no
solution for the problem.

om
Backtracking is a form of recursion.
The usual scenario is that you are faced with a number of
options, and you must choose one of these. After you make your choice you will get a new set of
options; just what set of options you get depends on what choice you made. This procedure is

r.c
repeated over and over until you reach a final state. If you made a good sequence of choices, your
final state is a goal state; if you didn’t, it isn’t.

ka
Backtracking can be thought of as a selective tree/graph traversal method. The tree is a way of
representing some initial starting position (the root node) and a final goal state (one of the
leaves). Backtracking allows us to deal with situations in which a raw brute-force approach

an
would explode into an impossible number of options to consider. Backtracking is a sort of refined
brute force. At each node, we eliminate choices that are obviously not possible and proceed to
recursively check only those that have potential.
sh
What’s interesting about backtracking is that we back up only as far as needed to reach a previous
decision point with an as-yet-unexplored alternative. In general, that will be at the most recent
pa
decision point. Eventually, more and more of these decision points will have been fully explored,
and we will have to backtrack further and further. If we backtrack all the way to our initial state
and have explored all alternatives from there, we can conclude the particular problem is
unsolvable. In such a case, we will have done all the work of the exhaustive recursion and known
jay

that there is no viable solution possible.

• Sometimes the best algorithm for a problem is to try all possibilities.

ofa

• This is always slow, but there are standard tools that can be used to help.
• Tools: algorithms for generating basic objects, such as binary strings [2n possibilities for n-bit string],
permutations [n!], combinations [n!/r!(n – r)!],general strings [k –ary strings of length n has k n
possibilities], etc...
pr

• Backtracking speeds the exhaustive search by pruning.

2.11 Example Algorithms of Backtracking

w.

• Binary Strings: generating all binary strings

• Generating k – ary Strings
• N-Queens Problem
ww

• The Knapsack Problem

• Generalized Strings
• Hamiltonian Cycles [refer to Graphs chapter]
• Graph Coloring Problem

www.profajaypashankar.com Page 80 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens
attack each other. For example, following is a solution for 4 Queen problem.

om
r.c
ka
an
sh
pa
jay
ofa

The expected output is a binary matrix which has 1s for the blocks where queens are placed. For
pr

example, following is the output matrix for above 4 queen solution.

w.

{ 0, 1, 0, 0}
{ 0, 0, 0, 1}
ww

{ 1, 0, 0, 0}
{ 0, 0, 1, 0}

N-Queens Problem

N - Queens problem is to place n - queens in such a manner on an n x n chessboard that no queens

attack each other by being in the same row, column or diagonal.

It can be seen that for n =1, the problem has a trivial solution, and no solution exists for n =2 and n
=3. So first we will consider the 4 queens problem and then generate it to n - queens problem.

www.profajaypashankar.com Page 81 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR
Given a 4 x 4 chessboard and number the rows and column of the chessboard 1 through 4.

om
r.c
ka
Since, we have to place 4 queens such as q1 q2 q3 and q4 on the chessboard, such that no two queens
attack each other. In such a conditional each queen must be placed on a different row, i.e., we put
queen "i" on row "i."

an
Now, we place queen q1 in the very first acceptable position (1, 1). Next, we put queen q2 so that both
these queens do not attack each other. We find that if we place q2 in column 1 and 2, then the dead
sh
end is encountered. Thus the first acceptable position for q2 in column 3, i.e. (2, 3) but then no
position is left for placing queen 'q3' safely. So we backtrack one step and place the queen 'q2' in (2, 4),
the next best possible solution. Then we obtain the position for placing 'q3' which is (3, 2). But later
pa
this position also leads to a dead end, and no place is found where 'q4' can be placed safely. Then we
have to backtrack till 'q1' and place it to (1, 2) and then all other queens are placed safely by moving q2
to (2, 4), q3 to (3, 1) and q4 to (4, 3). That is, we get the solution (2, 4, 1, 3). This is one possible
jay

solution for the 4-queens problem. For another possible solution, the whole method is repeated for all
partial solutions. The other solutions for 4 - queens problems is (3, 1, 4, 2) i.e.
ofa
pr
w.
ww

The implicit tree for 4 - queen problem for a solution (2, 4, 1, 3) is as follows:

www.profajaypashankar.com Page 82 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
an
sh
pa
jay
ofa
pr
w.

Fig shows the complete state space for 4 - queens problem. But we can use backtracking method to
generate the necessary node and stop if the next node violates the rule, i.e., if two queens are
attacking.
ww

www.profajaypashankar.com Page 83 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

om
r.c
ka
4 - Queens solution space with nodes numbered in DFS

It can be seen that all the solutions to the 4 queens problem can be represented as 4 - tuples (x1, x2,

an
x3, x4) where xi represents the column on which queen "qi" is placed.

One possible solution for 8 queens problem is shown in fig:

sh
pa
jay
ofa
pr
w.
ww

1. Thus, the solution for 8 -queen problem for (4, 6, 8, 2, 7, 1, 3, 5).

2. If two queens are placed at position (i, j) and (k, l).
3. Then they are on same diagonal only if (i - j) = k - l or i + j = k + l.
4. The first equation implies that j - l = i - k.
5. The second equation implies that j - l = k - i.
6. Therefore, two queens lie on the duplicate diagonal if and only if |j-l|=|i-k|

www.profajaypashankar.com Page 84 of 85
FYCS_SEM_II DESIGN AND ANALYSIS OF ALGORITHM BY: PROF.AJAYPASHANKAR

Place (k, i) returns a Boolean value that is true if the kth queen can be placed in column i. It tests both
whether i is distinct from all previous costs x1, x2,....xk-1 and whether there is no other queen on the
same diagonal.

Using place, we give a precise solution to then n- queens problem.

1. Place (k, i)
2. {
3. For j ← 1 to k - 1
4. do if (x [j] = i)

om
5. or (Abs x [j]) - i) = (Abs (j - k))
6. then return false;
7. return true;

r.c
8. }

ka
Place (k, i) return true if a queen can be placed in the kth row and ith column otherwise return is false.

x [] is a global array whose final k - 1 values have been set. Abs (r) returns the absolute value of r.

1. N - Queens (k, n)
2. {
an
sh
3. For i ← 1 to n
4. do if Place (k, i) then
pa
5. {
6. x [k] ← i;
jay

7. if (k ==n) then
8. write (x [1....n));
ofa

9. else
10. N - Queens (k + 1, n);
11. }
pr

12. }

VISIT : site :
w.

www.profajaypashankar.com
ww

visit youtube channel :

https://www.youtube.com/channel/UCu4Bd22zM6RpvHWC9
YHBh5Q

Telegram Channel : https://t.me/profajaypashankar

www.profajaypashankar.com Page 85 of 85