Design and Analysis of Algorithms

Chapter I
Introduction and Analysis of Algorithms

Aim
The aim of this chapter is to:

• define algorithm

• classify algorithm and approaches to algorithm design

• explain the RAM model

Objectives

The objectives of this chapter are to:

• enlist various qualities of good algorithm

• explain the ways in which algorithms are expressed

• analyse the analysis of algorithm

Learning outcome
At the end of this chapter, you will be able to:

• understand the concept of algorithm with its definition

• identify the approaches to algorithm design

• describe the RAM model

1
 Design and Analysis of Algorithms

1.1 Introduction to Algorithms

• An algorithm is any well-defined computational procedure that takes some value or set of values as input,
and produces some value or set of values as output. An algorithm is thus, a sequence of computational steps
that transform the input into the output.
• It is also a tool for solving a well-specified computational problem. The statement of the problem specifies
the desired input/output relationship in general terms. The algorithm describes a specific computational
procedure for achieving that input/output relationship.
• In general, an instance of a problem consists of the input (satisfying whatever constraints are imposed in the
problem statement) needed to compute a solution to the problem.
• An algorithm is said to be correct if, for every input instance, it halts with the correct output. We say that a
correct algorithm solves the given computational problem. An incorrect algorithm might not at all halt some
input instances, or it might halt with an answer other than the desired one. Contrary to what one might
expect, incorrect algorithms can sometimes be useful if their error rate can be controlled.
• Each algorithm is a list of well-defined instructions for completing a task. Starting from an initial state, the
instructions describe a computation that proceeds through a well-defined series of successive states,
eventually terminating in a final ending state.

In short, we can say an algorithm is

• a set of rules for carrying out calculation either by hand or on a machine
• a finite step-by-step procedure to achieve a required result
• a sequence of computational steps that transform the input into the output
• a sequence of operations performed on data that have to be organised in data structures
• an abstraction of a program to be executed on a physical machine (model of computation)

An algorithmic problem is specified by describing the set of instances it must work on and the desired properties
that the output must have. All algorithms must satisfy the following criteria
• Input: Zero or more quantities that are externally supplied.
• Output: At least one quantity is produced.
• Definiteness: Each instruction is clear and unambiguous.
• Finiteness: If we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a
finite number of steps.
• Effectiveness: Every instruction must be very basic, so that it can be carried out in principal by a person
using only pencil and paper.

Good algorithms usually have the following qualities and capabilities

• They are simple but powerful and general solutions.
• They can be easily understood by others, that is, the implementation is clear.
• They can be easily modified if necessary.
• They can work correctly according to the specifications of the task.
• They are economical in the utilisation of computer time and computer storage.
• They are documented well enough to be used by others.
• They are independent of computer and its operating system.
• They are able to support for sub-functions.
• The solution of an algorithm is correct and satisfying to its designer.

2
 1.2 The Classification of Algorithms
An algorithm is an effective method for solving a problem expressed as a finite sequence of steps. While there is
no universally accepted breakdown for the various types of algorithms, there are common classes that algorithms
are frequently agreed to belong to. Among these are:
• Dynamic programming algorithms: This class remembers older results and attempts to use these to speed the
process of finding new results.
• Greedy algorithms: Greedy algorithms attempt not only to find a solution but also find the ideal solution to any
given problem.
• Brute force algorithms: The brute force approach starts at some random point and iterates through every
possibility until it finds the solution.
• Randomised algorithms: This class includes any algorithm that uses a random number at any point during its
process.
• Branch and bound algorithms: Branch and bound algorithms form a tree of sub problems to the primary
problem, following each branch until it is either solved or lumped in with another branch.
• Simple recursive algorithms: This type of algorithm goes for a direct solution immediately and then backtracks
to find a simpler solution.
• Backtracking algorithms: Backtracking algorithms test for a solution, if a solution is found the algorithm has
solved, if not it recurs once and tests again, continuing until a solution is found.
• Divide and conquer algorithms: Divide and conquer algorithm is similar to a branch and bound algorithm,
except that it uses the backtracking method of recurring in tandem with dividing a problem into sub
problems.

1.3 Expressing Algorithm

We need some way to express the sequence of steps comprising an algorithm in the following way:
• English
• Pseudo code
• Real programming language

Mostly, people prefer to describe the ideas of an algorithm in English, moving to pseudo code to clarify sufficiently
tricky details of the algorithm.

1.3.1 Format Convention for Formulation of Algorithms

The following subsections summarise the basic format conventions used in the formulation of algorithms.

Name of algorithm
Every algorithm is given an identifying name written in capital letters.

Introductory comment
The algorithm name is followed by a brief description of the tasks the algorithm performs and any assumptions
that have been made. The description gives the names and types of the variables used in the algorithm.

Steps
The actual algorithm is made up of a sequence of numbered steps, each beginning with a phrase enclosed in
square brackets which gives an abbreviated description of that step. Following this phrase is an ordered sequence
of statements which describe actions to be executed or tasks to be performed. The statements in each step are
executed in a left-to-right order.

Comments
An algorithm step may terminate with a comment enclosed in round parentheses intended to help the reader better
understand that step. Comments specify no action and are included only for clarity.

3
Design and Analysis of Algorithms

1.3.2 Pseudo Code Convention for Designing Algorithm

Pseudo code consists of keywords and English-like phrase which specify the flow of control. The pseudo code hides
the implementation details and thus one can solely focus on the computational aspects of an algorithm.

Few of the notations used for algorithms are given below:

i. An algorithm is described within a pair of lines:

Procedure Name

.........................

.........................

.........................
End Name
ii. Assignment is denoted as:

Variable name  Expression

 assignment operator
iii. The symbol  indicates comment.
iv. Arrow in both directions  is used to show exchange

For example, x  y
v. If condition is shown as:

If condition

Then

statement(s);

Else

statement(s);

End if
vi. Do-loop is shown as:

For variable = Initial value to final value [step step-size]

Do

.............................

.............................

End for
vii. Comment is shown as:

/* statement */
viii. While construct is used as:

While condition Do

4
..........................

5
Design and Analysis of Algorithms

..........................

..........................

End while
ix. Case construct is used as:

Case

......................

......................

......................

End case
x. Length [A] shows length of array.
xi. A [i...j] shows array from i to j.
xii. Arithmetic operators +, -, *, / and % are used.
xiii.Returning results is shown as:

Return (value(s))

Example:
To understand the expressing method by using pseudo code, let us consider an algorithm which sum n number.

Algorithm without pseudo code: Step 1: Select n number Algorithm

Step 2: Set
without
sum S pseudo
to zero code:
Step 3: Repeat from first number to nth number i.e. S = S+A
Sum[i](A,
Step
n) 4: Return sum(S).
1. S0
For i1 to n
SS + A[i]
Return S

Fig. 1.1 Algorithm with and without pseudo code

6
 Design and Analysis of Algorithms

1.4 Operators and Precedence

Precedence Operator

1 Parentheses

2 Arithmetic

3 Relational

4 Logical

Table 1.1 Various operators with their precedence

Operation Symbol Order of Evaluation

1. Parentheses () Inner to outer

2. Exponentiation unary plus, minus Right to left
+, 
*
3. Multiplication division Left to right
/
+
4. Addition subtraction Left to right


Table 1.2 Arithmetic operators and precedence

Operator Notation
negation not
logical and and
logical or or

Table 1.3 Logical operators and their notation

1.5 The RAM Model

RAM stands for "Random Access Machine". It is one accumulator computer in which instructions are not permitted
to modify itself. Now, the figure below shows the diagram of RAM model.

6
 Input Tape

Accumulator

Program
Program Counter

Memory

Output Tape

Fig. 1.2 The RAM model

The RAM model consists of the following elements:

• Input tape
• Output tape
• A program
• A memory
• Program counter

The input tape consists of a sequence of squares, each of which can store an integer. Whenever one square is read
from the tape, head moves one square to the right.

Input Tape

R/
W

Fig. 1.3 Input tape for RAM model

The output tape is also a sequence of squares, in each square an integer can be written. Initially, the tape is
empty. Output is written on the square under the tape head and after the writing, the tape head moves one square
to the right. Over writing on the same square is not permitted.

7
 Design and Analysis of Algorithms

Output Tape

O1 O2 O3 On-1 On

R/W Head

Fig. 1.4 Output tape for RAM model

The memory consists of a sequence of registers, each of which is capable of holding an integer of arbitrary size.
The program for RAM is not stored in the memory and so is not subject to modification.
A program for RAM contains a sequence of labelled instructions resembling those found in assembly language
programs. All computations take place in the first register called accumulator. The program counter determines
the next instruction to be executed.

A RAM program defines a mapping from input tape to the output tape. Since the program may not have all input
tapes, the mapping may be undefined for certain inputs.

I O
N U
P T
U P
T U
RAM PROGRAM
T

T
A T
P A
E P
E

Fig. 1.5 Mapping by RAM program from input tape to the output tape

1.6 Analysis of Algorithms

For analysing algorithm, we use "RAM Model" and algorithm will be implemented as a computer program. Here,
instructions are executed one after another with no concurrent operations.
Analysing of an algorithm is concerned of three cases:
• Worst case complexity
• Best case complexity
• Average case complexity

8
 Worst
Case
Complexity

Average
Case complexity
No. of

Best
Case complexity

1 2 3 4 5 6 N

Fig. 1.6 Graphical representation of Worst Case, Average Case and Best Case complexity

Worst Case complexity

The Worst case complexity of an algorithm is the function defined by the maximum number of steps taken on
any instance of size n.

Best Case complexity

The Best case complexity of an algorithm is the function defined by the minimum number of steps taken on any
instance of size n.

Average Case complexity

The Average case complexity of an algorithm is the function defined by an average number of steps taken on any
instance of size n.

Each of this function defines a numerical function:

• Time
• Space

1.7 Approaches to Algorithms Design

There are basically two approaches for designing an algorithm which are as given below:
• Incremental approach
• Divide and conquer approach

9
Design and Analysis of Algorithms

Incremental Approach

Approach to design an algorithm

Divide and Conquer Approach

Fig. 1.7 Approaches to design an algorithm

Incremental approach
In this approach, we increase the index to insert the element in proper place every time. Good example of this
approach is "insertion sort".

Divide and Conquer approach

Divide and Conquer is a recursive approach. A good example of this approach is merge sort. This approach
works as follows:
• Divide problem into sub problems of the same kind.
• For sub problems that are really small (trivial) solve them directly. Else, solve them recursively (conquer).
• Combine sub problem solutions to solve the whole things.

Divide-and-conquer:
Example: Divide: Separate list in to two pieces.
12345678
Conquer: recursively count inversions in each half.
Combine: Count inversions where ai and aj are in different halves.

1234
5 6 7 8

12 34 56 78

2 3 5 7
1 4 6 8

[ Top-down Approach]

Fig. 1.8 Top down approach

10
Solved examples 1
Design an algorithm for finding square of any number.

Solution:
SQUARE (n)

1. if n = 0 then return 0
2. else
3. return square (n)  2n + square (n  1)  1

For instance,
Square (0) = 0
Square (1) = 2 × 1 + Square (1  1)  1 = 2 + Square (0)  1 = 2 + 0  1 = 2  1 = 1
Square (2) = 2 × 2 + Square (2  1)  1 = 4 + Square (1)  1 = 4 + 1  1 = 5  1 = 4

Solved example 2:
Write an algorithm using Pseudo code for finding GCD of two positive integers A and B.
Solution:

GCD (A, B)

1. Input A and B
2. If (A = B) then
3. return “either is the GCD”
4. If A > B then
5. replace A by the difference of A and B
6. else
7. replace B B˜A
8. go to step 2 to 3

11
Design and Analysis of Algorithms

Exercises 1
1. An algorithm is any well-defined procedure that takes some value or set of values as input, and
produces some value or set of values as output.
a. numerical
b. computational
c. randomised
d. bottom up

2. is a tool for solving a well-specified computational problem.

a. Data structure
b. RAM model
c. Algorithm
d. Program

3. Incorrect algorithms can sometimes be useful, if their can be controlled.

a. error rate
b. procedure
c. steps
d. inputs

4. attempts not only to find a solution, but to find the ideal solution to any given problem.
a. Branch and bound algorithms
b. Randomised algorithms
c. Dynamic programming algorithms
d. Greedy algorithms

5. Which algorithm uses the backtracking method of recurring?

a. Randomised algorithms
b. Divide and conquer algorithms
c. Dynamic programming algorithms
d. Greedy algorithms

6. An algorithm step may terminate with a comment enclosed in parentheses intended to help the
reader better understand that step.
a. round
b. square
c. circular
d. bracket

7. The hides the implementation details and thus one can solely focus on the computational
aspects of an algorithm.
a. algorithm
b. data structures
c. comments
d. pseudo code

12
Design and Analysis of Algorithms

8. What does the symbol ∇ indicate?

a. algorithm
b. heading of algorithm
c. comment
d. operator

9. Logical operators have the precedence .

a. 4
b. 3
c. 2
d. 1

10. The consists of a sequence of squares, each of which can store an integer.
a. output tape
b. input tape
c. magnetic tape
d. video tape

14
Chapter II
Elementary Data Structures

Aim
The aim of this chapter is to:

• explain the concept data structures

• define arrays with its representation, algorithm and applications

• explain stacks with the help of its representation, standard operations, algorithms,
illustrations and applications

Objectives
The objectives of this chapter are to:

• explain the basic terminologies of stacks, queues, linked lists, trees and graphs

• explicate linked lists, singly linked lists, doubly linked lists with their representation and illustrations

• enlist various types of graphs with their representation and basic operations performed on graphs

Learning outcome
At the end of this chapter, you will be able to:

• classify the various types of elementary data structures

• explain the meaning of tress with its definition, representation, common operations, basic terminologies used

in tress and the three types of traversal

• understand stacks, queues, linked lists, trees and graphs

15
 Design and Analysis of Algorithms

2.1 Introduction to Data Structures

Data structures are abstract structures or classes that are used to organise data and provide various operations upon
their data. Data structures are generally based on the ability of a computer to fetch and store data at any place in
its memory, specified by an address — a bit string that itself can be stored in memory and manipulated by the
program. In computer science, a data structure is a particular way of storing and organising data in a computer so
that it can be used efficiently.

2.2 Elementary Data Structures

The various elementary data structures are as given below:

2.2.1 Arrays
Array is a consecutive group of memory locations, where all them have the same name and are of identical type.
In computer science, an array data structure or simply array is a data structure consisting of a collection of
elements (values or variables), each identified by at least one index. An array is stored, so that the position of
each element can be computed from its index type by a mathematical formula. Arrays are among the oldest and
most important data structures and are used by almost every program and are used to implement many other data
structures, such as lists and strings. They effectively exploit the addressing logic of computers. In most modern
computers and many external storage devices, the memory is a one-dimensional array of words, whose indices
are their addresses.

651 322 763 911 550 826

Grades

Grades 5
Grades 0

Fig. 2.1 Example of an array

• Array declaration

type Array Name[ ]= new type[<array size>]

Example:
float Grades[ ] = new float[7];
• Grades is an array of type float with size 7.
• Grades[0], Grades[1], …, Grades[6] are the elements of the Grades, each is of type float.
• 0, 1, 2,…,6 are the indices of the array which are also called as subscripts. (Note that the indices start at 0 and
not at 1)
• During array declaration we may also put the brackets before the variable name:
• i.e., float [ ]Grades = new float[7];

16
Initialising arrays
Arrays may be initialised in the following ways:

int n[ ] = { 2, 4, 6, 8, 10 };

which creates and initialises a five element array with specified values.

int n[ ] = new int[10];

This creates and initialises a 10 element array of zeros.

If the data type is a non primitive type then above expression would create and initialise a 10 element array of
null.

Note:
• You cannot assign data to arrays like:
List = {1, 2, 3, 4, 5};

• Array elements are indexed between zero and the size of the array minus one.
• Arrays can have any type.

Traversing linear arrays

• Usual way to traverse a linear 1-d array is to use a loop.
• E.g. getting the overall average grade.

Pseudo-Code: Get_Average (Array [ ])

Begin
index = 0;
sum = 0;
for index = 0 to index = ArraySize -1
}
sum = sum + Array[index];
}
average = sum / ArraySize;
End

Inserting elements
Adding an element to an array/list at an arbitrary position without overwriting the previous values requires that,
you move all elements "below" that position.

17
Design and Analysis of Algorithms

12
1 3 1 1 3 1 3
2
2 7 2 7 2 7

3 9 3 9 3 9

4 13 4 4 12

5 22 5 13 5 13

6 6 22 6 22

Fig. 2.2 Inserting element

Algorithm
Algorithm: Insert (List [ ], position, element, ArraySize)
• Start at the top element of the array.
• Traverse the array backwards so as not to overwrite any previous data.
• Replace the current element that we are on with the element before it.
• Stop once we have reached our insertion position in the array.
• Insert our data into that position.

Sample Pseudo-Code

Pseudo-Code: Insert (List [ ], position, element)

Begin
for index = ArraySize-1 to index = position+1
}
List[index] = List[index-1];
{
List[position] = element;
End

Applications
• Arrays are used to implement mathematical vectors and matrices as well as other kinds of rectangular tables.
Many databases, small and large consist of (or include) one-dimensional arrays whose elements are records.
• Arrays are used to implement other data structures such as heaps, hash tables, deques, queues, stack, strings
etc.
• One or more large arrays are sometimes used to emulate in-program dynamic memory allocation, particularly
memory pool allocation. Historically, this has sometimes been the only way to allocate "dynamic memory"
portably.
• Arrays can be used to determine partial or complete control flow in programs, as a compact alternative to
(otherwise repetitive) multiple IF statements. They are known in this context as control tables and are used in
conjunction with a purpose built interpreter whose control flow is altered according to values contained in the
array. The array may contain subroutine pointers (or relative subroutine numbers that can be acted upon by
SWITCH statements) - that direct the path of the execution.

18
2.2.2 Stacks
In the most general form of a linear list, we are allowed to delete an element from and insert an element to any
position in the list. An important subclass of lists permits the insertion or deletion of an element to occur only at
one end. A linear list belonging to this subclass is called a stack.

DATA Link NODE

Fig. 2.3 Linked or pointer representation of a stack

Node contains Data and Link; data field contains an item of stack; link points to the node with next item.

Example:

Stack top

E D C B A E
0
D

The mathematical model of a stack is LIFO (Last In First Out). Data placed in the stack is accessed through one
path. The next available data is the last data to be placed in the stack. In other words, the "newest" data is
withdrawn.

Push
Pop

Fig. 2.4 Representation of a stack

19
Design and Analysis of Algorithms

Standard operations
The standard operations performed on a stack are as follows:

Operation Description

PUSH (S, Data) Put 'Data' in stack 'S'.

POP (S) Withdraw next available data from stack 'S'.

MAKENULL (S) Clear stack 'S' of all data

EMPTY (S) Return boolean value 'True' if stack 'S' is empty; returns 'False' otherwise.

Views the next available data on stack 'S'. This operation is redundant since
TOP (S)
one can simply POP(S), view the data, then PUSH(S, Data).

Table 2.1 Standard operations of a stack

Algorithm
• STACK-EMPTY (S)

If top [S] = 0

then return TRUE

else return FALSE

• POP (S)
If STACK-EMPTY(S)
then error "underflow"
else top [S]  top [S]  1
return S [top [S] + 1]

• PUSH (S, x)
top [S]  top [S] + 1
S [top [S]]  x

Illustration of PUSH

20
 S 15 6 2 9

top [S]=4
PUSH (S, 17)

S top [S] top[S] + 1 (top [S] = 5)

15 6 2 9 17
S [top [S]] x (S [5] = 17)

top [S]=4

top [S]=5

Illustration of POP

Applications

Direct applications
• page-visited history in a web browser
• undo sequence in a text editor
• saving local variables when one function calls another, and this one calls another, and so on

Indirect applications
• auxiliary data structure for algorithms
• component of other data structures

2.2.3 Queues
A queue is a particular kind of collection in which the entities in the collection are kept in order and the principal
(or only) operations on the collection are the addition of entities to the rear terminal position and removal of
entities from the front terminal position. This makes the queue a First-In-First-Out (FIFO) data structure. In a
FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the
requirement that once an element is added, all elements that were added before have to be removed before the
new element can be invoked. A queue is an example of a linear data structure.

21
Design and Analysis of Algorithms

Front Rear

DEQUEUE ENQUEUE
Deletion Insertion

Fig. 2.5 Representation of a queue

Standard operations
The standard operations performed on a queue are as follows:

Operation Description

ENQUEUE (Q, Data) Put 'Data' in the rear path of queue 'Q'

DEQUEUE (Q) Withdraw next available data from front path of queue 'Q'

FRONT (Q) Views the next available data on queue 'Q'

REAR (Q) Views the last data entered on queue 'Q'

MAKENULL (Q) Clear queue 'Q' of all data

Table 2.2 Standard operations of a queue

Algorithm
• ENQUEUE (Q, x)
Q [tail [Q]]  x
if tail [Q] = length [Q]
then tail [Q]  1
else tail [Q]  tail [Q] + 1

• DEQUEUE (Q)
x  Q [head [Q]]
if head [Q] = length [Q]
then head [Q]  1
else head [Q]  head [Q] +1
return x

Illustration of a queue

22
 1 2 3 4 5 6 7 8 9 10 11 12

(a) Q 15 6 9 8 4

head [Q] = 7 tail[Q] = 12

1 2 3 4 5 6 7 8 9 10 11 12

(b) Q 3 5 15 6 9 8 4 17

tail[Q] = 3 head [Q] = 7

1 2 3 4 5 6 7 8 9 10 11 12

(c) Q 3 5 15 6 9 8 4 17

tail[Q] = 3 head [Q] = 8

In the above illustration, a queue is implemented using an array Q [1...12]. Queue elements appear only in the
lightly shaded positions.
• The queue has 5 elements, in locations Q [7...11].
• The configuration of the queue after the calls ENQUEUE (Q, 17), ENQUEUE (Q, 3) and ENQUEUE (Q, 5).
• The configuration of the queue after the call DEQUEUE (Q) returns the key value 15 formerly at the head of
the queue. The new head has key 6.

Applications

Direct applications
• waiting lines
• access to shared resources (e.g., printer)
• multiprogramming

Indirect applications
• auxiliary data structure for algorithms
• component of other data structures

2.2.4 Linked Lists

A linked list is an ordered collection of items from which items may be deleted and inserted in any place. Linked
list is a data structure in which each element contains a pointer to the next element thus forming a linear list. A
linked list is a data structure in which the objects are arranged in linear order and the order in a linked list is
determined by pointers in each object.

Linked lists are among the simplest and most common data structures; they provide an easy implementation for
several important abstract data structures including stacks and queues.

23
Design and Analysis of Algorithms

The principal benefit of a linked list over a conventional array is that the order of the linked items may be
different from the order that the data items are stored in memory or on disk. For that reason, linked lists allow
insertion and removal of nodes at any point in the list, with a constant number of operations.

Each record of a linked list is often called an element or node. The field of each node that contains the address of
the next node is usually called the next link or next pointer. The remaining fields are known as the data, information,
value etc. The head of a list is its first node and the tail is the list minus that node (or a pointer).

In the last node of a list, the link field often contains a null reference, a special value that is interpreted by
programs meaning "there is no such node". A less common convention is to make it point to the first node of the
list; in that case the list is said to be circular or circularly linked; otherwise it is said to be open or linear.

Singly linked list

A singly linked list is a concrete data structure consisting of a sequence of nodes and each node stores element and
links to the next node as shown in the figure below.

Link to next node

null

Element
A B C D

Fig. 2.6 Representation of a singly linked list

Doubly linked list
In a doubly-linked list, each node contains, besides the next-node link, a second link field pointing to the
previous node in the sequence. The two links may be called forward and backward or next and previous. In a
doubly linked list, the front element is stored at the first node and the rear element is stored at the last node as
shown in the figure below:

Forward or Next

first last

Element A B C D

Backward or Previous

head [L]

Fig. 2.7 Representation of a doubly linked list

24
Algorithm
Searching a linked list
LIST-SEARCH (L, k): finds the first element with key k in list L by a simple linear search, returning a pointer to
this element. If no object with key k appears in the list, then NIL is returned. The algorithm is given as:
LIST-SEARCH (L, k)
x  head [L]
while x ≠ NIL and key [x] ≠ k
do x  next [x]
return x

Inserting into a linked list

LIST-INSERT (L, x): given an element pointed by x, inserts x onto the front of the linked list. The algorithm is
given as:
LIST-INSERT (L, x)
next [x]  head [L]
if head [L] ≠ NIL
then prev [head[L]]  x
head [L]  x
prev [x]  NIL

Deleting from a linked list

LIST-DELETE (L, x): given an element pointed by x, removes x from the linked list. The algorithm is given
as: LIST-DELETE (L, x)
if prev [x] ≠ NIL
then next [prev [x]]  next [x]
else head [L]  next [x]
if next [x] ≠ NIL
then prev [next [x]]  prev [x]

Illustration of a doubly linked list

The above illustration shows,

• A doubly linked list L representing the dynamic set {1, 4, 9, 16}. Each element in the list is an object with fields
for the key and pointers (shown by arrows) to the next and previous objects. The next field of the tail and the
prev field of the head are NIL, indicated by a diagonal slash. The attribute head [L] points to the head.
• Following the execution of LIST-INSERT (L, x) where key [x] = 25, the linked list has a new object with key
25 as the new head. This new object points to the old head with key 9.
• The results of the subsequent call LIST-DELETE (L, x) where x points to the object with key 4.

25
Design and Analysis of Algorithms

2.2.5 Trees
A tree is a set of related interconnected nodes in a hierarchical structure. It is a non-empty collection of vertices and
edges that satisfies certain requirements. The structure resembles branches of a “tree”, hence the name.

Different types of trees are:

• rooted tree
• ordered tree
• M-ary tree and binary tree

Fig. 2.8 Tree

Tree Terminology
• A vertex (or node) is a simple object that can have a name and can carry other associated information.
• The first or top node in a tree is called the root node.
• An edge is a connection between two vertices
• A path in a tree is a list of distinct vertices in which successive vertices are connected by edges in the tree.
• Example :{ a, b, d, i} is path.
• The defining property of a tree is that there is precisely one path connecting any two nodes.
• A disjoint set of trees is called a forest.
• Nodes with no children are leaves or terminal nodes.

26
 Fig. 2.9 Tree terminology
Root
This is the unique node in the tree to which further sub trees are attached.

Degree of the node

The total number of sub trees attached to that node is called the degree of the node. For node a degree is 2.

Leaves
These are the terminal nodes of the tree. The nodes with degree 0 are always the leaves. Here, nodes e, f, g, h, i.

Internal Nodes
The nodes other than the root node and the leaves are called the internal node. Here, b, c, d and f are internal
nodes.

Parent Node
The node which is having further sub branches is called the parent node of those sub branches. In fig. 1.8, node b is
parent node of d, e and f and c is parent node of g and h, whereas d, e, f, g and h are child of b and c parent.

Rooted tree
• A Rooted tree is one where we designate one node as the root (i.e., the tree examples we have been looking
at so far are all rooted trees).
• In computer science, we normally reserve the term tree to refer to rooted trees. The more general structure is
a free tree.
• In a rooted tree, any node is the root of a sub tree consisting of it and the nodes below it.
• There is exactly one path between the root and each of the other nodes in the tree.
• Each node except the root has exactly one node above it in the tree, (i.e., it is parent), and we extend the
family analogy talking of children, siblings, or grandparents.

27
Design and Analysis of Algorithms

Root

Vertex Vertex

Leaf Leaf Leaf Leaf

Fig. 2.10 Rooted tree

Ordered tree
• An ordered tree is a rooted tree in which the order of the children at every node is specified.
• If each node must have a specific number of children appearing in a specific order, then we have an M-ary
tree.
• The simplest type of M-ary tree is the binary tree.
Binary Trees
A binary tree is a tree where each node has exactly zero, one or two children. i.e., each parent can have not more
than 2 children. As with any abstract data structure we can implement a binary tree in a number of ways, using
arrays, strings, or structures and pointers.

Fig. 2.11 Binary tree

28
Example of trees

Fig. 2.12 Example of trees

Types of Traversal
The following are the types of traversal:

• Preorder Traversal (visits and processes each node in a tree BEFORE visiting and processing its children)
 visit the root node first and process
 do pre-order traversal of left sub tree
 do pre-order traversal of right sub tree

• Postorder Traversal (visits and processes each node in the tree AFTER visiting and processing its children)
 do post-order traversal of left sub tree
 do post-order traversal of right sub tree
 visit the root node last and process
• Inorder Traversal (processes nodes in the tree in an ascending sorted order)
 do in-order traversal of left sub tree
 visit the root node and process
 do in-order traversal of right sub tree

29
Design and Analysis of Algorithms

For the above tree,

• The inorder traversal results in the following processing order: C B A E F D G
• The preorder traversal results in the following processing order: A B C D E F G
• The postorder traversal results in the following processing order: C B F E G D A

Common operations of a tree are

• enumerating all the items
• enumerating a section of a tree
• searching for an item
• adding a new item at a certain position on the tree
• deleting an item
• removing a whole section of a tree (called pruning)
• adding a whole section to a tree (called grafting)
• finding the root for any node

2.2.6 Graphs
A simple graph G consists of a set of vertices V and a set of edges E. The elements of E are defined as pairs of
elements of V, ek = (u,v) such that u is not equal to v and (u,v) an element of E implies that (v,u) is also an
element of E. (In other words (u,v) and (v,u) represent the same edge).
Graphs can be represented pictorially by nodes and lines as shown below:

30
 Fig. 2.13 Types of graphs
• Multigraphs allow multiple edges between the same pair or vertices and edges from and to the same vertex.
• The edges of a directed graph are called arcs and have a direction as indicated by an arrow. Unlike graphs,
an arc (u,v) in a directed graph does not imply that the arc (v,u) is also in the directed graph.
• An acyclic graph is a graph with no cycles. That is, there is no path along edges in the graph (or along arcs
in a directed graph) that leads from a vertex back to the same vertex.
• Two vertices u, v in a graph are said to be adjacent if there is an edge e (or arc) connecting u to v. The vertices
u and v are called the endpoints of e.
• The degree of a vertex v is given as deg (v) and is the number of edges incident with v. That is, the number
of edges for which v is an endpoint.
• A complete graph is one in which there is an edge between every pair of vertices.

In a graph G = (V, E), an edge which is directed from one node to another is called a directed edge, while an edge
which has no specific direction is called an undirected edge. A graph in which every edge is directed is called a
directed graph or a digraph. A graph in which every edge is undirected is called an undirected graph. If some of
the edges are directed and some are undirected in a graph, then the graph is a mixed graph. All of these graphs
are as shown in fig. 2.13.

31
Design and Analysis of Algorithms

The basic operations provided by a graph data structure G usually include:

• adjacent(G, x, y): tests whether there is an edge from node x to node y
• neighbors(G, x): lists all nodes y such that there is an edge from x to y
• add(G, x, y): adds to G the edge from x to y, if it is not there
• delete(G, x, y): removes the edge from x to y, if it is there
• get_node_value(G, x): returns the value associated with the node x
• set_node_value(G, x, a): sets the value associated with the node x to a

Structures that associate values to the edges usually also provide:

• get_edge_value(G, x, y): returns the value associated to the edge (x, y)
• set_edge_value(G, x, y, v): sets the value associated to the edge (x, y) to v

2.2.7 A Data Structure for Disjoint Sets

Union by rank
One way to store a set is as a directed tree, as shown in the figure below. Nodes of the tree are elements of the set,
arranged in no particular order and each has parent pointers that eventually lead up to the root of the tree. This
root element is a convenient representative, or name, for the set. It is distinguished from the other elements by the
fact that its parent pointer is a self-loop.

Fig. 2.14 A directed-tree representation of two sets {B, E} and {A, C, D, F, G, H}

In addition to a parent pointer, each node also has a rank that for the time being, should be interpreted as the
height of the sub tree hanging from that node.
procedure makeset (x)
 (x) = x
rank (x) = 0
function find (x)
while x  (x) : x = (x)
return x

As can be expected, makeset is a constant-time operation. On the other hand, find follows parent pointers to the
root of the tree and therefore, takes time proportional to the height of the tree. The tree actually gets built via the
third operation union, and so we must make sure that this procedure keeps trees shallow.
Merging two sets is easy: make the root of one point to the root of the other. But we have a choice here. If the
representatives (roots) of the sets are rx and ry, do we make rx point to ry or the other way around? Since tree
height
32
is the main impediment to computational efficiency, a good strategy is to make the root of the shorter tree point
to the root of the taller tree. This way, the overall height increases only if the two trees which are being merged
are equally tall. Instead of explicitly computing heights of trees, we will use the rank numbers of their root nodes,
which is why this scheme is called union by rank.

See fig. 2.15 for an example.

By design, the rank of a node is exactly the height of the subtree rooted at that node. This means, for instance,
that as you move up a path toward a root node, the rank values along the way are strictly increasing.

Property 1: For any x, rank (x) < rank ((x))

A root node with rank k is created by the merger of two trees with roots of rank k  1.

Property 2: Any root node of rank k has at least 2k nodes in its tree.

This extends to internal (nonroot) nodes as well: a node of rank k has at least 2k descendants. After all, any internal
node was once a root, and neither its rank nor its set of descendants has changed since then. Moreover, different
rank-k nodes cannot have common descendants, since by Property 1 any element has at most one ancestor of rank
k.

Property 3: If there are n elements overall, there can be at most n2k nodes of rank k.

This last observation implies, crucially, that the maximum rank is log n. Therefore, all the trees have height  log
n, and this is an upper bound on the running time of find and union.

Fig. 2.15 A sequence of disjoint-set operations (Superscripts denote rank)

33
Design and Analysis of Algorithms

2.2.8 Heaps and Heap Sort

The heap data structure is an array object which can be easily visualised as a complete binary tree. There is a one
to one correspondence between elements of the array and nodes of the tree. The tree is completely filled on all
levels except possibly the lowest, which is filled from the left up to a point. All nodes of heap also satisfy the
relation that the key value at each node is at least as large as the value at its children.

We represent heaps in level order, going from left to right. The array corresponding to the heap above is [25, 13,
17, 5, 8, 3].
The root of the tree A[1] and given index i of a node, the indices of its parent, left child and right child can be computed as:

PARENT (i)
return floor (i/2)
LEFT (i)
return 2i
RIGHT (i)
return 2i + 1
Let's try these out on a heap to make sure we believe they are correct. Take this heap,

which is represented by the array [20, 14, 17, 8, 6, 9, 4, 1].

We'll go from the 20 to the 6 first. The index of the 20 is 1. To find the index of the left child, we calculate 1 × 2 = 2.
This takes us (correctly) to the 14. Now, we go right, so we calculate 2 × 2 + 1 = 5. This takes us (again,
correctly) to the 6.
Now let's try going from the 4 to the 20. 4's index is 7. We want to go to the parent, so we calculate 7 / 2 = 3,
which takes us to the 17. Now, to get 17's parent, we calculate 3 / 2 = 1, which takes us to the 20.

Heap property
In a heap, for every node i other than the root, the value of a node is greater than or equal (at most) to the value of
its parent.
A [PARENT (i)] ≥ A[i]
Thus, the largest element in a heap is stored at the root.

34
Following is an example of Heap:
By the definition of a heap, all the tree levels are completely filled except possibly for the lowest level, which is filled
from the left up to a point. Clearly a heap of height h has the minimum number of elements when it has just one
node at the lowest level. The levels above the lowest level form a complete binary tree of height h -1 and 2h -1
nodes. Hence the minimum number of nodes possible in a heap of height h is 2h. Clearly a heap of height h has
the maximum

number of elements when its lowest level is completely filled. In this case the heap is a complete binary tree of
height h and hence has 2h+1 -1 nodes.

Following is not a heap, because it only has the heap property - it is not a complete binary tree. Recall that to be
complete; a binary tree has to fill up all of its levels with the possible exception of the last one, which must be
filled in from the left side.

Height of a node
We define the height of a node in a tree to be a number of edges on the longest simple downward path from a node
to a leaf.

Height of a tree
It is defined as the number of edges on a simple downward path from a root to a leaf. Note that the height of a tree
with n node is log n which is (log n). This implies that an n-element heap has height log n.

In order to show this, let the height of the n-element heap be h. From the bounds obtained on maximum and
minimum number of elements in a heap, we get
2h ≤ n ≤ 2h+1-1
Where n is the number of elements in a
heap.
2h ≤ n ≤ 2h+1

Taking logarithms to the base

h ≤ log n ≤ h +1

2 It follows that h = log n.

We known from above that, the largest element resides in root, A [1]. The natural question to ask is, where in a
heap the smallest element reside? Consider any path from root of the tree to a leaf. Because of the heap property,
as we follow that path, the elements are either decreasing or staying the same. If it happens to be the case that all
elements in the heap are distinct, then the above implies that the smallest is in a leaf of the tree. It could also be
that an entire sub tree of the heap is the smallest element or indeed that there is only one element in the heap,
which is the smallest element, so the smallest element is everywhere. Note that anything below the smallest
element must equal the smallest element, so in general, only the entire sub trees of the heap can contain the
smallest element.

35
Design and Analysis of Algorithms

Inserting element in the heap

Suppose we have a heap as follows:
Let's suppose we want to add a node with key 15 to the heap. First, we add the node to the tree at the next spot
available at the lowest level of the tree. This is to ensure that the tree remains complete.

Let's suppose we want to add a node with key 15 to the heap. First, we add the node to the tree at the next spot
available at the lowest level of the tree. This is to ensure that the tree remains complete.

Now we do the same thing again, comparing the new node to its parent. Since 14 < 15, we have to do another
swap:

Now we are done, because 15 20.

Four basic procedures on heap are:

 Heapify, which runs in O (log n) time.
 Build-Heap, which runs in linear time.
 Heap Sort, which runs in O (n log n) time.
 Extract-Max, which runs in O (log n) time.

36
• Outline of procedure heapify
Heapify picks the largest child key and compares it with the parent key. If the parent key is larger then heapify
quits, otherwise it swaps the parent key with the largest child key. So that, the parent is now larger than its
children. It is important to note that the swap may destroy the heap property of the subtree rooted at the largest
child node. If this is the case, heapify calls itself again using largest child node as the new root.
Heapify (A, i)
l ← left [i]
r ← right [i]
if l ≤ heap-size [A] and A[l] > A[i]
then largest ← l
else largest ← i
if r ≤ heap-size [A] and A[i] >
A[largest] then largest ← r
if largest ≠ i
then exchange A[i] ↔ A[largest]
Heapify (A, largest)

Analysis
If we put a value at root that is less than every value in the left and right subtree, then 'Heapify' will be called
recursively until leaf is reached. To make recursive calls traverse the longest path to a leaf, choose value that
make 'Heapify' always recurse on the left child. It follows the left branch when left child is greater than or equal
to the right child, so putting 0 at the root and 1 at all other nodes, for example, will accomplished this task. With
such values 'Heapify' will called h times, where h is the heap height so its running time will be θ(h) (since each
call does (1) work), which is (log n). Since we have a case in which Heapify's running time (log n), its
worst-case running time is Ω (log n).

Example of heapify
Suppose we have a complete binary tree somewhere whose sub trees are heaps. In the following complete binary
tree, the sub trees of 6 are heaps:

The Heapify procedure alters the heap, so that the tree rooted at 6's position is a heap. Here's how it works. First,
we look at the root of our tree and its two children.

We then determine which of the three nodes is the greatest. If it is the root, we are done, because we have a heap.
If not, we exchange the appropriate child with the root, and continue recursively down the tree. In this case, we
exchange 6 and 8, and continue.

37
Design and Analysis of Algorithms

Now, 7 is greater than 6, so we exchange them.

We are at the bottom of the tree, and can't continue, so we terminate.

Building a Heap
We can use the procedure 'Heapify' in a bottom-up fashion to convert an array A[1 . . n] into a heap. Since the
elements in the subarray A[n/2 +1 . . n] are all leaves, the procedure BUILD_HEAP goes through the
remaining nodes of the tree and runs 'Heapify' on each one. The bottom-up order of processing node guarantees
that the subtree rooted at children are heap before 'Heapify' is run at their parent.

BUILD_HEAP (A)
heap-size (A) ← length [A]
For i ← floor(length[A]/2) down to 1 do
Heapify (A, i)
We can build a heap from an unordered array in linear time.

Heap sort algorithm

The heap sort combines the best of both merge sort and insertion sort. Like merge sort, the worst case time of
heap sort is O (n log n) and like insertion sort, heap sort sorts in-place. The heap sort algorithm starts by using
procedure BUILD-HEAP to build a heap on the input array A[1 . . n]. Since the maximum element of the array
stored at the root A [1], it can be put into its correct final position by exchanging it with A[n] (the last element in
A). If we now discard node n from the heap than the remaining elements can be made into heap. Note that the
new element at the root may violate the heap property. All that is needed is to restore the heap property.

HEAPSORT (A)
BUILD_HEAP (A)
for i ← length (A) down to 2 do
exchange A[1] ↔ A[i]
heap-size [A] ← heap-size [A] - 1
Heapify (A, 1)
The HEAPSORT procedure takes time O (n log n), since the call to BUILD_HEAP takes time O(n) and each of
the n -1calls to Heapify takes time O(log n).

38
 Design and Analysis of Algorithms
Exercises 2
1. The mathematical model of a stack is .
a. FIFO
b. FILO
c. LIFO
d. LILO

2. The mathematical model of a queue is .

a. FIFO
b. FILO
c. LIFO
d. LILO

3. In a , each node contains, besides the next-node link, a second link field pointing to the previous
node in the sequence.
a. singly linked list
b. triple linked list
c. linear linked list
d. doubly-linked list

4. In computer science, consists of a collection of elements (values or variables), each identified

by at least one index.
a. a linked list
b. an array
c. a stack
d. a queue

5. In a graph G = (V, E), if some of the edges are directed and some are undirected, then the graph is a
.
a. multigraph
b. directed graph
c. mixed graph
d. complete graph

6. A is a tree where each node has exactly zero, one or two children.
a. ordered tree
b. binary tree
c. rooted tree
d. free tree

7. is the unique node in the tree to which further sub trees are attached.
a. Root
b. Leaves
c. Parent node
d. Edge

40
8. Multiprogramming is one of the direct applications of .
a. stack
b. array
c. linked list
d. queue

9. What is the function of the standard operation REAR (Q)?

a. Views the last data entered on queue 'Q'.
b. Views the next available data on queue 'Q'.
c. Put 'Data' in the rear path of queue 'Q'.
d. Clear queue 'Q' of all data.

10. Undo sequence in a text editor is one of the indirect applications of .

a. array
b. linked list
c. stack
d. queue

41
 Design and Analysis of Algorithms

Chapter III
Divide–And–Conquer Algorithms

Aim

The aim of this chapter is to:

• explain the divide-and-conquer method

• explain the various algorithms following divide-and-conquer technique

• explicate the steps involved in divide and conquer algorithms

Objectives
The objectives of this chapter are to:

• explain the concept of binary search

• explicate merge sort and quick sort

• elucidate Strassen’s Matrix Multiplication

Learning outcome
At the end of this chapter, you will be able to:

• understand divide-and-conquer method

• differentiate between binary search, finding minimum and maximum, merge sort, quick sort, selection sort and

Strassen's matrix multiplication

• identify the steps involved in binary search

42
 3.1 Introduction to Divide-and-Conquer Method
In computer science, divide and conquer is an important algorithm design paradigm. It works by recursively
breaking down a problem into two or more sub-problems of the same type, until these become simple enough to
be solved directly. The solutions to the sub-problems are then combined to give a solution to the original
problem. A divide and conquer algorithm is closely tied to a type of recurrence relation between functions of the
data in question, data is "divided" into smaller portions and the result calculated hence. The divide and conquer
algorithms consist of three steps:
• Breaking the problem into several sub-problems that are similar to the original problem but smaller in size,
• Solve the sub-problem recursively (successively and independently), and then
• Combine these solutions to subproblems to create a solution to the original problem.

The technique is named "divide and conquer" because a problem is conquered by dividing it into several smaller
problems. This technique yields elegant, simple and quite often very efficient algorithms. This technique is the basis
of efficient algorithms for all kinds of problems such as sorting (quick sort, merge sort), binary search, powering
a number, Fibonacci numbers, matrix multiplication and so on.

3.2 Binary Search

A binary search algorithm is a technique for finding a particular value in a sorted list. It makes progressively better
guesses and closes in on the sought value by selecting the median element in a list, comparing its value to the
target value (key) and determining if the selected value is greater than, less than or equal to the target value. A
guess that turns out to be too high becomes the new top of the list and a guess that is too low becomes the new
bottom of the list. Pursuing this approach iteratively, it narrows the search by a factor of two each time and finds
the target value. The binary search consists of the following steps:
• Search a sorted array by repeatedly dividing the search interval in half.
• Begin with an interval covering the whole array.
• If the value of the search key is less than the item in the middle of the interval, narrow the interval to the
lower half. Otherwise narrow it to the upper half.
• Repeatedly check until the value is found or the interval is empty.

The most straightforward implementation is recursion which recursively searches the sub-array dictated by the
comparison as given in algorithm below:

Algorithm: Binary Search(arr[1.. .n], value, low, high)

1. If (high < low)
2. return – 1 // not found
3. Endif
4. mid = (low + high) / 2
5. if (arr[mid] > value)
6. return BinarySearch(arr, value, low, mid – 1)
7. Else If (arr[mid] < value)
8. return BinarySerach(arr, value, mid + 1, high)
9. Else
10. return mid // found
11. Endif
12. Endif

The algorithm is invoked with initial low and high values of 1 and n. We can eliminate the recursion above and
convert this to an iterative implementation as given in algorithm below:

43
Design and Analysis of Algorithms

Algorithm: BinarySearch(a[1...n], n, x)
1. low = 1
2. high = n
3. while (low ≤ high)
4. mid = (low + high) / 2
5. If (a[mid] > x)
6. high = mid – 1
7. else If (a[mid] < x)
8. Low = mid + 1
9. Else
10. Return mid // found
11. Endif
12. endwhile
13. return – 1 // not found

Fig. 3.1 illustrates trace of the algorithm to find the target value of 65.

Binary search is a logarithmic algorithm and runs in O(log2n) time. Specifically, 1 + log2n iterations are needed to
return an answer. In most cases it is considerably faster than a linear search. It can be implemented using
recursion or iteration, as shown above.
[1] [2] [3] [4] [5] [6] [7] [8] [9]
10 15 40 50 55 65 75 90 95
mid = (low + high) / 2 = (1 + 9) / 2 = 5
arr[mid] < value (55 < 65)
low = mid + 1 = 5 + 1 = 6
high = 9
low mid high
[1] [2] [3] [4] [5] [6] [7] [8] [9]
10 15 40 50 55 65 75 90 95
mid = (low + high) / 2 = (6 + 9) / 2 = 7
arr[7] > value (75 > 65)
high = mid – 1 = 7 – 1 = 6

[1] [2] [3] [4] [5] l[6] m

[7] [8] hi[9]
mid = (low + high) / 2 = (6 + 6) / 2 = 6
arr[6] > value (65 > 65) → false 10 15 40 50 55 65 75 90 95
arr[6] < value (65 < 65) → false
arr[6] = value (65 = 65) → true
Found at mid = 6

low
mid
high

Fig. 3.1 Trace of binary search

44
 3.3 Minimum and Maximum
Finding the minimum and maximum is an example of the divide and conquer algorithmic paradigm. To illustrate
this approach, consider the problem of finding both the minimum and maximum in an array of integers A [1... n] and
assume for simplicity that n is a power of 2. A straightforward algorithm might look like the one below. It returns
a pair (x, y) where x is the minimum and y is the maximum.

Clearly, the number of element comparisons performed by this method is 2n-2. However, using the divide and
conquer strategy, we can find both the minimum and maximum in only (3n/2) – 2 element comparisons. The idea
is very simple:

Divide the input array into two halves A[1..n/2] and A[(n/2) + 1..n], find the minimum and maximum in each
half and return the minimum of the two minima and the maximum of the two maxima. The divide-and-conquer
algorithm is given in Algorithm MINMAX as given below:

3.4 Merge Sort

Merge sort is an O(n log n) comparison-based sorting algorithm. In most implementations it is stable, meaning
that it preserves the input order of equal elements in the sorted output. Sorting by merging is a recursive, divide-
and-conquer strategy. In the base case, we have a sequence with exactly one element in it. Since such a sequence
is already sorted, there is nothing to be done. The steps to sort a sequence of elements (n > 1) are as follows:

i. divide the sequence into two sequences of length n / 2 and n / 2

ii. recursively sort each of the two subsequences
iii. merge the sorted subsequences to obtain the final result

Fig. 3.2 given below shows the idea of merge sort

45
Design and Analysis of Algorithms

Fig. 3.2 Merge sort procedure

Algorithm: To sort the entire sequence A [1 ... n], make the initial call to the procedure MERGE-SORT (A, 1, n).

Fig. 3.3 shows the bottom-up view of the above procedure for n = 8.

Fig. 3.3 The bottom-up view

46
 The pseudo code of the MERGE procedure is as follows:

3.5 Quick Sort

The basic version of quick sort algorithm was invented by C. A. R. Hoare in 1960. It is used on the principle of
divide-and-conquer. Quick sort is an algorithm of choice in many situations because it is not difficult to
implement, it is a good "general purpose" sort and it consumes relatively fewer resources during execution.
• It is in-place since it uses only a small auxiliary stack.
• It requires only n log(n) time to sort n items.
• It has an extremely short inner loop
• This algorithm has been subjected to a thorough mathematical analysis, a very precise statement can be made
about performance issues.

Quick sort works by partitioning a given array A[p . . r] into two non-empty sub array A[p .... q] and A[q+1 r] such
that every key in A[p .... q] is less than or equal to every key in A[q+1......r]. Then the two subarrays are sorted by
recursive calls to Quick sort. The exact position of the partition depends on the given array and index q is
computed as a part of the partitioning procedure.

QUICKSORT
14. If p < r then
15. q Partition (A, p, r)
16. Recursive call to Quick Sort (A, p, q)
17. Recursive call to Quick Sort (A, q + r, r)

47
 Design and Analysis of Algorithms

Note that to sort the entire array, the initial call Quick Sort (A, 1, length[A]) is made. As a first step, Quick Sort
chooses as pivot one of the items in the array to be sorted. Then the array is partitioned on either side of the pivot.
Elements that are less than or equal to pivot will move toward the left and elements that are greater than or equal
to pivot will move toward the right.
Partitioning the array
Partitioning procedure rearranges the subarrays in-place as given below:

PARTITION (A, p, r)
1. x ← A[p]
2. i ← p-1
3. j ← r+1
4. while TRUE do
5. Repeat j ← j-1
6. until A[j] ≤ x
7. Repeat i ← i+1
8. until A[i] ≥ x
9. if i < j
10. then exchange A[i] ↔ A[j]
11. else return j
Partition selects the first key, A[p] as a pivot key about which the array will
partitioned: Keys ≤ A[p] will be moved towards the left .
Keys ≥ A[p] will be moved towards the right.

3.6 Selection Sort

This type of sorting is called "selection sort" because it works by repeatedly element. It works as follows: first
find the smallest in the array and exchange it with the element in the first position, then find the second smallest
element and exchange it with the element in the second position, and continue in this way until the entire array is
sorted. The algorithm is as given below:

SELECTION_SORT (A)
for i ← 1 to n-1 do
min j ← i;
min x ← A[i]
for j ← i + 1 to n do
If A[j] < min x then
min j ← j
min x ← A[j]
A[min j] ← A [i]
A[i] ← min x

Selection sort is among the simplest of sorting techniques and it works very well for small files. Furthermore,
despite its evident "naïve approach ", selection sort has a quite important application because each item is
actually moved at most once, selection sort is a method of choice for sorting files with very large objects
(records) and small keys.

3.7 Strassen’s Matrix Multiplication

The core of many equation solvers is a matrix multiplication routine. The time complexity of calculating the
matrix product C = AB where A, B and C are n × n matrices, using traditional matrix multiplication is O(n3).
Strassen's matrix multiplication algorithm is able to perform this calculation in time O(n2.81). Thus, one might be
able to speed up the code by using Strassen's algorithm instead of the traditional algorithm. The traditional
algorithm follows directly from the definition of matrix multiplication. To compute Cij, we compute the dot
product of the ith row in A with the jth column in B.

48
Strassen's matrix multiplication is based on a recursive divide and conquer scheme. Given n × n matrices A and
B we wish to calculate C = AB. To see how this algorithm works, we first divide the matrices as follows
(decomposing C = AB) into four blocks):

If the matrices A and B are not of type 2n × 2n, we fill the missing rows and columns with zeroes. The elements
of
C11 = A11 B11+ A12 B21
C12 = A11 B12+ A12 B22
C21 = A21 B11+ A22 B21
C22 = A21 B12+ A22 B22

C are given by:

As an example, to perform the multiplication of A and B

We define the following eight n/2 by n/2 matrices:

Strassen showed how the matrix C can be computed using only 7 block multiplications and 18 block additions or
subtractions (12 additions and 6 subtractions):

The correctness of the above equations is easily verified by substitution.

The elements of matrix C can be verified with the traditional algorithm.

The algorithm given below gives the Strassen's matrix multiplication after dividing matrices into sub-matrices
and

49
Design and Analysis of Algorithms

then recursively multiplying sub-matrices.

We perform seven n/2 by n/2 matrix multiplications and eighteen n/2 by n/2 matrix additions. The matrix
additions take O(n2) time. If the matrix multiplications are done recursively, then the running time satisfies
T(n) = 7T(n/2) + O(n2)
The solution of this recurrence is T(n) = .

50
 Design and Analysis of Algorithms

Exercises 3
1. Divide-and-conquer algorithms consist of steps.
a. two
b. three
c. four
d. one

2. The complexity of divide-and-conquer algorithm is .

a. (n log n)
b. (log n)
c. (log n2)
d. (n log n2)

3. Merge sort is an O (n log n) sorting algorithm.

a. iteration based
b. linear
c. dynamic
d. comparison based

4. is the fastest known sorting algorithm in practice.

a. Merge sort
b. Selection sort
c. Quick sort
d. Bubble sort

5. is among the simplest of sorting techniques and it works very well for small files.
a. Merge sort
b. Quick sort
c. Selection sort
d. Bubble sort

6. is based on a recursive divide-and-conquer scheme.

a. Strassen's matrix multiplication algorithm
b. Binary search algorithm
c. Bubble sort algorithm
d. Radix algorithm

7. The time complexity of calculating the matrix product C = AB where A, B and C are n × n matrices, using
traditional matrix multiplication is .
a. O (n2)
b. O (n3)
c. O (n log n3)
d. O (n log n)

52
8. works by recursively breaking down a problem into two or more sub-problems of the same
type, until these become simple enough to be solved directly.
a. Dynamic programming
b. Greedy algorithms
c. Backtracking algorithms
d. Divide-and-conquer technique

9. A is a technique for finding a particular value in a sorted list.

a. binary search algorithm
b. merge sort algorithm
c. quick sort algorithm
d. selection sort algorithm

10. Finding the minimum and maximum is an example of the algorithmic paradigm.
a. greedy
b. dynamic programming
c. divide and conquer
d. backtracking

53
 Design and Analysis of Algorithms

Chapter IV
Greedy Algorithms

Aim
The aim of this chapter is to:

• explain greedy algorithms

• define feasibility

• explicate various greedy algorithms

Objectives
The objectives of this chapter are to:

• describe the general structure of greedy algorithms

• explain the minimum spanning trees with the help of Prim's algorithm and Kruskal's algorithm

• explicate single source shortest path using Dijkstra's algorithm

Learning outcome
At the end of this chapter, you will be able to:

• differentiate between the various greedy algorithms

• identify the ways in which algorithms are expressed

• understand the minimum spanning trees and derive single source shortest path

54
4.1 Introduction
Greedy algorithms are simple and straightforward. They are short-sighted in their approach in the sense that they
take decisions on the basis of information at hand without worrying about the effect these decisions may have in
the future. They are easy to invent, easy to implement and most of the time quite efficient. Many problems cannot
be solved correctly by greedy approach. Greedy algorithms are used to solve optimisation problems.
Greedy algorithm is a technique for solving problems with the following properties:
• The problem is an optimisation problem; to find the solutions that minimises or maximises some value (cost/
profit).
• The solution can be constructed in a sequence of steps/choices.
• For each choice point:
 the choice must be feasible
 the choice looks as good as or better than alternatives
 the choice cannot be revoked

Example of making change

• Suppose we want to give change of a certain amount (say 24 cents).
• We would like to use fewer coins rather than more.
• We can make a solution by repeatedly choosing a coin  to the current amount, resulting in a new amount.
• The greedy solution always chooses the largest coin value possible (for 24 cents: 10. 10, 1, 1, 1, 1).
• If there were an 8-cent coin, the greedy algorithm would not be optimal (but not bad).

"The one with maximum benefit from multiple choices is selected" is the basic idea of greedy method. A greedy
method arrives at a solution by making a sequence of choices, each of which simply looks the best at the
moment. The below given algorithm describes the details of greedy method:

Algorithm: greedy (partial solution S, sub-problem P)

1. Generate all candidate choices as list L for current sub-problem P.
2. While (L is not empty or other finish condition is not met)
3. Compute the feasible value of each choice in L;
4. Modify S and P by taking choice with the highest feasible value;
5. Update L according to S and P;
6. Endwhile
7. Return the resulting complete solution

For an optimisation problem, what remains is called a sub-problem after making one or several steps of greedy
choice. For problem or sub-problem P, let S be the partial solution and L be the list of candidate choices at the
current moment. To order or prioritise the choices, some evaluation criteria are used to express the feasible value.
According to the above algorithm, the candidate choice with the highest feasible value is selected and the partial
solution is updated accordingly. This procedure is repeated step by step until a resulting complete solution is
obtained.

The representation of the above algorithm can be illustrated by a search tree as shown in the figure below. Each
node in the search tree corresponds to a partial solution and a line between two nodes represents the decision to
add a candidate choice to the existing partial solution. Consequently, leaf nodes at the end of tree correspond to
complete solutions. The black circle at level 1 denotes an initial partial solution. At level 2, there are five candidate
choices for current partial solution which denotes by five nodes. In order to select the best node, promise of each
node should be determined. After some evaluation function has been employed, the second node with highest
benefit (the circle in gray at level 2) is selected. Then, the partial solution and sub-problem are updated
accordingly.

55
Design and Analysis of Algorithms

Fig. 4.1 Representation of greedy algorithm

Structure of greedy algorithm

• Initially, the set of chosen items is empty, i.e., solution set.
• At each step,
i. Item will be added in a solution set by using selection function.
ii. IF the set would no longer be feasible
 reject items under consideration (and is never consider again)
iii. ELSE IF set is still feasible THEN
 add the current item

The greedy algorithm consists of four functions as given below:

• A function that checks whether chosen set of items provide a solution.
• A function that checks the feasibility of a set.
• The selection function tells which of the candidates is the most promising.
• An objective function, which does not appear explicitly, gives the value of a solution.

Definitions of feasibility
• A feasible set (of candidates) is promising if it can be extended to produce not merely a solution, but an
optimal solution to the problem. In particular, the empty set is always promising because an optimal solution
always exists.
• A greedy strategy usually progresses in a top-down fashion, making one greedy choice after another,
reducing each problem to a smaller one.
• The "greedy-choice property" and "optimal substructure" are two ingredients in the problem that lend to a
greedy strategy.
• It says that a globally optimal solution can be arrived at by making a locally optimal choice.

56
4.2 Fractional Knapsack Problem
In this version of a problem, the items can be broken into smaller piece so that we pack only a fraction xi of item
i, where 0  x  1.Item i contributes x w to the total weight in the knapsack, and x p to the total profit. Knapsack
i i i i i
capacity is c.
The fraction knapsack problem can be stated as follows:
Maximise

subject to constraint

It is clear that an optimal solution must fill the knapsack exactly, for otherwise we could add a fraction of one of
the remaining items and increase the total profit. Thus, in an optimal solution.

The fractional knapsack problem has the greedy-choice property and its algorithm is as given below. One way to
prove the correctness of the below algorithm is to prove the greedy choice property and optimal substructure
property. It consists of two steps. First, prove that there exists an optimal solution that begins with the greedy
choice. Secondly, prove that if A is an optimal solution to the original problem S, then A-a is also an optimal
solution to the problem S-s where a is the item included as in the greedy choice and S-s is the sub-problem after
the first greedy choice has been made. The second part is easy to prove since the more profitable items have less
weight. Note that if p`/w`, is not it can replace any other because w` < w, but it increases the profit because p` >
p.

Let the ratio p`/w` is maximal. This supposition implies that p`/w`  p/w for any pair (p, w), so p`p/w > p for any
(p, w). Now, suppose a solution does not contain the full w` weight of the best ratio. Then by replacing an amount
of any other w with more w` will improve the value.

Time complexity: If the items are already sorted into decreasing order of pi/wi, then the while-loop takes a time in
O(n). Therefore, the total time including the sort is in O(n log n).

57
 Design and Analysis of Algorithms

4.3 Minimum Spanning Trees (MST)

The MST problem is to find a free tree T of a given graph G that contains all the vertices of G and has the minimum
total weight of the edges of G over all such trees.

Problem formulation
Let G = (V, E, W) be a weighted connected undirected graph. Find a tree T that contains all the vertices in G and
minimise the sum of the weights of the edges (u, v) of T that is,

• Tree that contains every vertex of a connected graph is called spanning tree. The problem of constructing a
minimum spanning tree is computing a spanning tree T with smallest total weight.
• A tree is a connected graph with no cycles. A spanning tree is a subgraph of G which has the same set of
vertices of G and is a tree.
• A minimum spanning tree of a weighted graph G is the spanning tree of G whose edges sum to minimum
weight.
• A graph may have many spanning trees, for instance the complete graph on four vertices.

The above graph has sixteen spanning trees as shown in the figure below:

Fig. 4.2 Various forms of spanning trees

58
Here, we discuss Kruskal's algorithm and Prim's algorithm which are classic applications of the greedy strategy.
Kruskal's algorithm grows the MST in clusters by considering (greedily) edges in order of their weights and
Prim's algorithm on the other hand, grows the MST from single vertex (root).

4.3.1 Prim's Algorithm

• This algorithm repeatedly chooses the smallest-weight edge from the tree so far to the other vertices.
• If a spanning tree has a weightier edge between VT and V – VT, it can be improved by replacing it with e.
• We can put VT edges into a priority queue, and then dequeue edges until one goes between VT and V – VT.
• Prim's algorithm using a binary heap to implement a priority queue is O(E log E) = O(E log V).

The algorithm is as given below:

Example:

Fig. 4.3 An example of Prim's algorithm

59
Design and Analysis of Algorithms

Consider the graph shown in fig.4.3 (a). The vertices to the left of the dashed line belong to X and those to its
right belong to Y. First, as shown in fig. 4.3(a), X = {1} and Y = {2, 3... 6}. In fig. 4.3(b), vertex 2 is moved from Y to
X since edge (1, 2) has the least cost among all the edges incident to vertex 1. This is indicated by moving the
dashed line so that 1 and 2 are now to its left. As shown in fig. 4.3(b), the candidate vertices to be moved from Y
to X are 3 and 4. Since edge (1, 3) is of least cost among all edges with one end in X and one end in Y, 3 is
moved from Y to X. Next, from the two candidate vertices 4 and 5 in fig. 4.3(c), 4 is moved since the edge (3, 4)
has the least cost. Finally, vertices 6 and then 5 are moved from Y to X as shown in fig. 4.3(e). Each time a
vertex y is moved from Y to X, its corresponding edge is included in T, the set of edges of the minimum spanning
tree. The resulting minimum spanning tree is shown in fig. 4.3(f).

4.3.2 Kruskal's Algorithm

• This algorithm repeatedly chooses the smallest-weight edge that does not form a cycle.
• Kruskal's algorithm is O(E log V) using efficient cycle detection.
• Disjoint set implementation for detecting cycles:
 put each vertex into a singleton set
 e is chosen if its vertices are in different sets
 when e is chosen, the two sets are unioned

The algorithm is as given below:

Example:
Fig. 4.4 An example of Kruskal's algorithm

60
 Consider the weighted graph shown in fig. 4.4(a). As shown in fig. 4.4(b), the first edge that is added is (1, 2) since
it is of minimum cost. Next, as shown in fig. 4.4 (c)-(e), edges(1, 3), (4, 6) and then (5, 6) are included in T in
this order. Next, as shown in fig. 4.4(f), the edge (2, 3) creates a cycle and hence is discarded. For the same
reason, as shown in fig. 4.4(g), edge (4, 5) is also discarded. Finally, edge (3, 4) is included, which results in the
minimum spanning tree (V, T) as shown in fig. 4.4(h).

4.4 Single Source Shortest Path

Suppose G is a weighted directed graph where a minimum labelled (u, v) associated with each edge (u, v) in E,
called weight of edge (u, v). These weights represent the cost to traverse the edge. A path from vertex u to vertex v
is a sequence of one or more edges.

{(V1, V2), (V2, V3), ..., (Vn-1, Vn)} in E[G]

where

u = V1 and v = Vn.

The cost (or length or weight) of the path P is the sum of the weights of edges in the sequence. The shortest-path
weight from a vertex u  V to a vertex v  V in the weighted graph is the minimum cost of all paths from u to V.
If there exists no such path from vertex u to vertex v then the weight of the shortest path is . We can also define
this as:

61
Design and Analysis of Algorithms

4.4.1 Dijkstra's Algorithm

Dijkstra's algorithm solves the single source shortest path problem when all edges have non negative weights. It
is a greedy algorithm and similar to Prim's algorithm. Algorithm starts at the source vertex S it grows a tree T
that ultimately spans all vertices reachable from S. Vertices are added to T in order of distance i.e., first S, then the
vertex closest to S, then the next closest and so on. The algorithm is as given below:

In the above algorithm, we will assume that the input graph is represented by adjacency lists and the length of
edge (x, y) is stored in the vertex for y in the adjacency list for x. For instance, the directed graph is represented as
shown in fig. 4.5. We will also assume that the length of each edge in E is nonnegative. The two sets X and Y
will be implemented as boolean vectors X[1..n] and Y[1..n]. Initially, X[1] = 1 and Y[1] = 0 and for all i, 2  i 
n, X[i] = 0 and Y[i] = 1.Thus, the operation X  X  {y} is implemented by setting X[y] to 1 and the operation
Y  Y  {y} is implemented by setting Y[y] to 0.

Fig. 4.5 Directed graph representation for the shortest path algorithm
Example:

Fig. 4.6 An example of Dijkstra's algorithm

To see how the algorithm works, consider the directed graph shown in fig. 4.6(a). The first step is to label each
vertex v with [v] = length[1, v]. As shown in the figure, vertex 1 is labelled with 0 and vertices 2 and 3 are
labelled with 1 and 12 since length[1, 2] = 1 and length[1, 3] = 12. All other vertices are labelled with  since
there are no edges from the source vertex to these vertices. Initially X = {1} and Y = {2, 3, 4, 5, 6}. In the figure,
those vertices to the left of the dashed line belong to X and the others belong to Y. In fig. 4.6(a), we note that [2]
is the smallest

62
 among all vertices' labels in Y and hence it is moved to X indicating that the distance to vertex 2 has been found.
To finish processing vertex 2, the labels of its neighbours 3 and 4 are inspected to see if there are paths that pass
through 2 and are shorter than their old paths. In this case, we say that we update the labels of the vertices
adjacent to 2. As shown in the figure, the path from 1 to 2 to 3 is shorter than the path from 1 to 3 and thus [3] is
changed to 10, which is the length of the path that passes through 2. Similarly, [4] is changed to 4 since now
there is a finite path of length 4 from 1 to 4 that passes through vertex 2. These updates are shown in fig. 4.6(b).
The next step is to move that vertex with minimum label, namely 4, to X and update the labels of its neighbours
in Y as shown in fig. 4.6(c). In this figure, we notice that the labels of vertices 5 and 6 became finite and [3] is
lowered to 8. Now, vertex 3 has a minimum label, so it is moved to X and [5] is updated accordingly as shown in
fig. 4.6(d). Continuing in this way, the distance to vertex 5 is found and thus it is moved to X as shown in fig. 4.6(e).
As shown in fig. 4.6(f), vertex 6 is the only vertex remaining in Y and hence its label coincides with the length of its
distance from 1. In fig. 4.6(f), the label of each vertex represents its distance from the source vertex.

4.5 Optimal Storage on Tapes

There are 'n' programs that are to be stored on a computer tape of length 'l'. Associated with each other, i is the
length l , 1  i  n. All the programs can only be written on the tape if the sum of all the lengths of the program is
at most l.i

Assumption: Whenever a program is to be retrieved from the tape, the tape is positioned at the front. Now if
the programs are stored in the order as I = i1, i2, i3, i4..............., in, then the time tj needed to retrieve program (i, j) is
proportional to ∑1 ≤ k ≤ j lik. So, the problem is that we have to store them in the tape in such an order that the
M.R.T (mean retrieval time) is minimum.

A greedy approach to build such an algorithm requires such a permutation that chooses the next program on the
basis of some optimisation measure. In this we take the optimisation measure to be 'd ' (which is the current
length of the tape that is written with the program). So now every time when we write onto the disk, we keep in
mind that the increment in the length of 'd ' is minimum.

So, this greedy method requires us to just sort the lengths of the programs or to assign them in a non-decreasing
order, so that they can be directly written into disk on their length basis. So it in turns takes the complexity equal
to O (n log n) just to sort the length of the programs. Here's a sample pseudo code for the program if we have
multiple disks on which we have to write the data.

Pseudo code

tapes (n, m) // here n is the numbers of programs and m is the numbers of tapes.

j = 0;

for (i = 1 to n do)

write ("append", i "to the permutation of the tape", j)

j = (j + 1) mod m

63
Design and Analysis of Algorithms

Exercises 4
1. Greedy algorithms are used to solve problems.
a. optimisation
b. divide and conquer
c. theoretical
d. implementation

2. A set (of candidates) is promising if it can be extended to produce not merely a solution, but an
optimal solution to the problem.
a. optimal
b. empty
c. feasible
d. greedy solution

3. The problem is to find a free tree T of a given graph G that contains all the vertices of G and has
the minimum total weight of the edges of G over all such trees.
a. optimal
b. greedy
c. feasible
d. MST

4. Tree that contains every vertex of a connected graph is called a tree.

a. undirected
b. spanning
c. binary
d. rooted

5. A tree is a graph with no cycles.

a. biconnected
b. connected
c. digraph
d. mixed graph

6. algorithm repeatedly chooses the smallest-weight edge that does not form a cycle.
a. Kruskal's
b. Prim's
c. Bellman-Ford's
d. Dijkstra's

7. If the input of the Prim's algorithm is a weighted connected graph G = (V, E) then it's output is given by
a. set of vertices comprising a MST
b. set of edges comprising a binary tree
c. set of edges comprising a MST
d. set of edges comprising a connected graph

64
Design and Analysis of Algorithms

8. Kruskal's algorithm sorts the edges E by their .

a. vertices
b. depth
c. cycles
d. weights

9. If there exists no path from vertex u to vertex v, then the weight of the shortest path is .
 
b. 1
c. 0
d. -1

10. Dijkstra's algorithm solves the single source shortest path problem when all edges have ___________
weights.
a. zero
b. non negative
c. infinite
d. more than one

66
Chapter V
Graph Algorithms

Aim

The aim of this chapter is to:

• explain tree traversal techniques,

• explicate code optimisation techniques

• elucidate backtracking methods

Objectives
The objectives of this chapter are to:

• explain preorder traversal, inorder transversal and postorder transversal

• explain the process of code optimisation technique

• explicate the application on BFS technique

Learning outcome
At the end of this chapter, you will be able to:

• understand BFS and DFS techniques

• identify AND/OR graphs

• describe game trees

67
 Design and Analysis of Algorithms

5.1 Basic Tree Traversal Techniques

One of the most common operations performed on tree structures is that of traversal. This is a procedure by
which each node in the tree is processed exactly once in a systematic manner. The meaning of "processed"
depends on the nature of the application. For example, a tree could represent an arithmetic expression. In this
context the processing of a node which represents an arithmetic operation would probably mean performing or
executing that operation. There are three main ways of traversing a binary tree which are preorder, inorder and
postorder. We now examine each traversal order. The easiest way to define each order is by using recursion.

While traversing, if a particular sub tree is empty (i.e., a node has no left or right descendant), the traversal is
performed by doing nothing. In other words, a null sub tree is considered to be fully traversed when it is
encountered.

Preorder traversal
The preorder traversal of a binary tree is defined as follows:
 process the root node
 traverse the left sub tree in preorder
 traverse the right sub tree in preorder

The algorithm is given as follows:

Preorder (tree)
If tree is not NULL
Visit Info (tree)
Preorder (Left (tree))
Preorder (Right (tree))

Inorder traversal
The inorder traversal of a binary tree is given by the following steps:
 traverse the left sub tree in inorder
 process the root node
 traverse the right sub tree in inorder

The algorithm is given as follows:

Inorder (tree)
If tree is not NULL
Inorder (Left (tree))
Visit Info (tree)
Inorder (Right (tree))

Postorder traversal
The postorder traversal of a binary tree is defined as follows:
 traverse the left sub tree in postorder
 traverse the right sub tree in postorder
 process the root node

The algorithm is given as follows:

Postorder (tree)
If tree is not NULL
Postorder (Left (tree))
Postorder (Right (tree))
Visit Info (tree)

68
 Example:

The preorder traversal of the tree as given above gives the following processing order:
ABDEHCFGI
The inorder traversal of the tree as given above gives the following processing order:
DBHEAFCGI
The postorder traversal of the tree as given above gives the following processing order:
DHEBFIGCA

5.2 The Techniques of Code Optimisation

Computers transfer data in a number of different ways. Whether through a serial port, a parallel port, over a
modem, over an ethernet cable, or internally from a hard disk to memory, some data will be lost. To compensate
for that loss, numerous error detection and correction algorithms have been developed. One of the most common
error correction codes is the Reed-Solomon code, which is a special subset of BCH (Bose-Chaudhuri-
Hocquenghem) linear cyclic block codes. To counter possible data corruption during transmission, the data is
encoded using a multi-block Reed- Solomon implementation with a possibly shortened final block. In order to
maximise the amount of data transmitted, it was necessary to reduce the computation time of a Reed-Solomon
encoding to three percent of the processor’s time. To achieve such a reduction, many code optimisation
techniques were employed.

Process
The first task is to research code optimisation and get a feel for the general consensus on optimisation do’s and
don’ts. Optimisation techniques have been around for years, and not all of the long held beliefs are still
applicable today. Because of the boom in hardware speeds and the drop in hardware prices, many developers
have let code optimisation slip to the back of their minds. As a result, the rigorously developed techniques from
years ago have not been updated to account for modern compiler optimisation or hardware features. Synthesising
a sizable volume of data from opposing viewpoints led to the development of a general outline to follow when
optimising code. This is the process that was followed during the optimisation of the Reed-Solomon code.

Before beginning any project, it is imperative to choose a programming language. Many programmers will
choose a language they are familiar with, even if it is not the best language for the project. Speed, flexibility, and
ease of coding are a few of the major factors in deciding which language to use. Whatever be the language,
knowing it well will help reduce number of awkward constructs and also improve the quality of the code. When
inheriting code, the programming language is already chosen, but it may be more efficient to rewrite the code in
another language than try to optimise the existing code. With all of the choices available, choosing the right
language can be difficult yet is an important part of the optimisation process. The Reed-Solomon implementation
was written in C. This was a good choice because the GNU compiler collection (GCC) has a very good
optimising C compiler, allowing the compiler to do much of work. The availability of a good optimising
compiler (or fast command interpreter for an interpreted language) should always be considered when deciding
which language to use.

Assuming the programming language is already chosen and there is little need to choose a new one, the first step
towards optimisation is to look at algorithm choice. Choosing a good algorithm can be a difficult task and there is no
definitive process for choosing the right one. The gains of a good algorithm, however, include a major speed
increase and improved code readability and stability. Reducing an O(N2) algorithm to an O(N) algorithm will
speed up the code (especially for large amounts of data) and enable later optimisation to work with more efficient
code to produce even greater returns. Choosing an algorithm early in the process prevents optimisations from
being performed, and then being performed again after an algorithm change. Any changes to the algorithm
69
Design and Analysis of Algorithms

should be performed as early in the optimisation process as possible.

70
 Design and Analysis of Algorithms

After settling on an algorithm, the compiler, optimisation options should be enabled. This provides an idea about
the final speed and size of the code. The compiler will also perform many optimisations faster and just as well as,
if not better than, the human programmer will. Optimisation like moving constant expressions outside of loops,
storing variables in registers, moving functions inline, and unrolling loops should be performed by the compiler
in most cases. Occasionally the programmer can perform an optimisation better than the compiler because he has
additional knowledge about the code that the compiler lacks. For most code, however, the compiler has enough
information to make good decisions and perform the proper optimisation. There are some cases where certain
optimisation will hinder performance or unacceptably enlarge the code. To prevent that hindrance the
programmer can specify which optimisation to include or omit by using compiler flags. There is little point in
performing an optimisation by hand when a compiler can perform the same optimisation faster and more
accurately.

If the code is still not fast enough after the compiler optimisations, there are a number of hand optimisation that
can be performed. Before optimising all the code, it is a good idea to profile the code and get a sense of where the
bottlenecks are. In general, most of the code in a program will only run once, and most of the processing time is
spent in an inner loop. Optimising just that loop will reap the greatest benefits, as a single optimisation will save
on each run through the loop. Any good optimisation book will outline basic optimisation techniques, but it is
good to keep in mind the capabilities of the compiler. The programmer knows many aspects of the code better
than the compiler and can therefore perform some optimisation the compiler cannot. Like any other tools,
compilers are not perfect so it is important to understand the specific compiler being used. As good as the
compiler may be, it is foolish to rely on it to do all of the work. When done properly, utilising a compiler’s
features is quicker, easier, and more effective than doing all the work by hand.

For code that needs to be extremely streamlined, assembly language is a good choice. Some programming
languages, like C, allow assembly statements to be inserted directly into the code. It is also possible to write an
entire section of code in assembly. For many programmers, modifying compiler-generated assembly will produce
the best results in the least amount of time. Skilled assembly programmers, however, may be able to write entire
blocks of assembly that will outperform compiler generated assembly. Even so, using the compiler-generated
assembly is a good way to start out and it is always possible to write the assembly from scratch if modifying the
compiler-generated assembly does not yield great enough gains. It is not always a good idea to write an entire
program in assembly. For code that only runs once, or for which the compiler produces good assembly, it will
often be faster to use a high-level language than to hand-code assembly. The loss in code performance may not
offset the time saved by using a high- level language.

If all optimisation fail to make the code run fast enough it may be necessary to explore hardware options.
Implementing the code in hardware allows faster processing than that attainable by software. Because there are a
minimum number of cycles required to perform any given task, it may be necessary to use faster hardware.
Ultimately there will be some project constraint imposing a limit on the speed of the code and the solution may
be difficult to find or accept.

5.3 AND/OR Graphs

It is a form of graph or tree used in problem solving and problem decomposition. The nodes of the graph
represent states or goals and their successors are labelled as either AND or OR branches. The AND successors
are sub goals that must all be achieved to satisfy the parent goal while OR branches indicate alternative sub
goals, any one of which could satisfy the parent goal.

5.4 Game Trees

In combinatorial game theory, a game tree is a directed graph whose nodes are positions in a game and whose
edges are moves. The complete game tree for a game is the game tree starting at the initial position and
containing all possible moves from each position.

70
 Fig. 5.1 The first two ply of the game tree for tic-tac-toe

The above figure shows the first two levels, or ply, in the game tree for tic-tac-toe. We consider all the rotations and
reflections of positions as being equivalent, so the first player has three choices of move: in the centre, at the
edge, or in the corner. The second player has two choices for the reply if the first player played in the centre,
otherwise five choices and so on.

The number of leaf nodes in the complete game tree is the number of possible different ways the game can be
played. For example, the game tree for tic-tac-toe has 26,830 leaf nodes.

The game tree for tic-tac-toe is easily searchable, but the complete game trees for larger games like chess are
much too large to search. Instead, a chess-playing program searches a partial game tree: typically as many ply
from the current position as it can search in the time available. Two-person games can also be represented as
AND-OR trees. For the first player to win a game, there must exist a winning move for all moves of the second
player. This is represented in the AND-OR tree by using disjunction to represent the first player's alternative
moves and using conjunction to represent all of the second player's moves.

5.5 Graph Traversal Techniques

Graph traversal refers to the problem of visiting all the nodes in a graph in a particular manner. Tree traversal is a
special case of graph traversal. In contrast to tree traversal, in general graph traversal, each node may have to be
visited more than once, and a root-like node that connects to all other nodes might not exist. In this chapter, we
will discuss two methods of graph traversal: depth-first search and breadth-first search.

5.5.1 Breadth-First Search (BFS)

Breadth-first search is a way to find all the vertices reachable from a given source vertex, s. BFS traverse a connected
component of a given graph and defines a spanning tree. Intuitively, the basic idea of the breath-first search is
this: send a wave out from source s. The wave hits all vertices 1 edge from s. From there, the wave hits all
vertices 2 edges from s. etc. We use FIFO queue Q to maintain the wavefront: v is in Q if and only if wave has hit
v but has not come out of v yet.

71
Design and Analysis of Algorithms

Breadth-first search starts at a given vertex s, which is at level 0. In the first stage, we visit all the vertices that
are at the distance of one edge away. When we visit there, we paint as "visited," the vertices adjacent to the start
vertex s - these vertices are placed into level 1. In the second stage, we visit all the new vertices we can reach at
the distance of two edges away from the source vertex s. These new vertices, which are adjacent to level 1 vertex
and not previously assigned to a level, are placed into level 2, and so on. The BFS traversal terminates when
every vertex has been visited.

To keep track of progress, breadth-first-search colours each vertex. Each vertex of the graph is in one of three
states:
• undiscovered
• discovered but not fully explored and
• fully explored

The state of a vertex u, is stored in a colour variable as follows:

• colour[u] = White - for the "undiscovered" state
• colour [u] = Gray - for the "discovered but not fully explored" state
• colour [u] = Black - for the "fully explored" state

The BFS(G, s) algorithm develops a breadth-first search tree with the source vertex s, as its root. The parent or
predecessor of any other vertex in the tree is the vertex from which it was first discovered. For each vertex, v, the
parent of v is placed in the variable π[v]. Another variable, d[v], computed by BFS contains the number of tree
edges on the path from s to v. The breadth-first search uses a FIFO queue, Q, to store gray vertices.

Algorithm: breadth-first search traversal

Example:
The following diagram illustrates the progress of breadth-first search on the undirected sample graph.

After initialisation (paint every vertex white, set d[u] to infinity for each vertex u and set the parent of every
vertex to be NIL), the source vertex is discovered in line 5. Lines 8-9 initialise Q to contain just the source vertex
s.

72
 r s t u
∞ 0 ∞ ∞

Q s

∞ ∞ ∞ ∞ 0

v w x y
The algorithm discovers all vertices 1 edge from s, i.e., discovered all vertices (w and r) at level 1.

r s t u
1 0 ∞ ∞

Q w r

∞ 1 ∞ ∞ 1 1

v w x y

r s t u
1 0 2 ∞

Q r t x
∞ 1 2 ∞ 1 2 2

v w x y

The algorithm discovers all vertices 2 edges from s i.e., discovered all vertices (t, x and v) at level 2.

r s t u
1 0 2 ∞

Q t x v
2 1 2 ∞ 2 2 2

v w x y

r s t u
1 0 2 3

Q x v u
2 1 2 ∞ 2 2 3

v w x
y

73
Design and Analysis of Algorithms

r s t u
1 0 2 3

Q v u y
2 1 2 3 2 3 3

v w x y
The algorithm discovers all vertices 3 edges from s i.e., discovered all vertices (u and y) at level 3.

r s t u
1 0 2 3

Q u y

2 1 2 3 3 3

v w x y

r s t u
1 0 2 3

Q y

2 1 2 3 3

v w x y

The algorithm terminates when every vertex has been fully explored.

r s t u
1 0 2 3

Q 

2 1 2 3
v w x y

The while-loop in breadth-first search is executed at most V times. The reason is that every vertex enqueued atmost
once. So, we have O(V).

The for-loop inside the while-loop is executed atmost E times if G is a directed graph or 2E times if G is
undirected. The reason is that every vertex dequeued atmost once and we examine (u, v) only when u is
dequeued. Therefore, every edge examined atmost once if directed atmost twice if undirected. So, we have O(E).

Therefore the total running time for breadth-first search traversal is O(V + E).

Applications of BFS
BFS is used to solve the following problems:
 Testing whether graph is connected.
 Computing a spanning forest of graph.
 Computing a cycle in graph or reporting that no such cycle exists.

74
  Computing, for every vertex in graph, a path with the minimum number of edges between start vertex
and current vertex or reporting that no such path exists.

5.5.2 Depth-First Search (DFS)

Depth-first search is a systematic way to find all the vertices reachable from a source vertex, s. Like breadth-first
search, DFS traverse a connected component of a given graph and defines a spanning tree. The basic idea of
depth- first search is this: It methodically explores every edge. We start over from different vertices as necessary.
As soon as we discover a vertex, DFS starts exploring from it (unlike BFS, which puts a vertex on a queue so that
it explores from it later).

Depth-first search selects a source vertex s in the graph and paint it as "visited." Now the vertex s becomes our
current vertex. Then, we traverse the graph by considering an arbitrary edge (u, v) from the current vertex u. If
the edge (u, v) takes us to a painted vertex v, then we back down to the vertex u. On the other hand, if edge (u, v)
takes us to an unpainted vertex, then we paint the vertex v and make it our current vertex, and repeat the above
computation. Sooner or later, we will get to a “dead end,” meaning all the edges from our current vertex u takes
us to painted vertices. This is a deadlock. To get out of this, we back down along the edge that brought us here to
vertex u and go back to a previously painted vertex v. We again make the vertex v our current vertex and start
repeating the above computation for any edge that we missed earlier. If all of v's edges take us to painted vertices,
then we again back down to the vertex we came from to get to vertex v, and repeat the computation at that vertex.
Thus, we continue to back down the path that we have traced so far until we find a vertex that has yet unexplored
edges, at which point we take one such edge and continue the traversal. When the depth-first search has
backtracked all the way back to the original source vertex, s, it has built a DFS tree of all vertices reachable from
that source. If there still undiscovered vertices in the graph then it selects one of them as the source for another
DFS tree. The result is a forest of DFS-trees. Note that the edges lead to new vertices are called discovery or tree
edges and the edges lead to already visited (painted) vertices are called back edges.

Like BFS, to keep track of progress depth-first-search colours each vertex. Each vertex of the graph is in one of
three states:
• undiscovered
• discovered but not finished (not done exploring from it)
• finished (have found everything reachable from it) i.e., fully explored

The state of a vertex u, is stored in a colour variable as follows:

• colour[u] = White - for the "undiscovered" state
• colour[u] = Gray - for the "discovered but not finished" state,
• colour[u] = Black - for the "finished" state

Like BFS, depth-first search uses π[v] to record the parent of vertex v. We have π[v] = NIL if and only if vertex v is
the root of a depth-first tree.
• DFS time-stamps each vertex when its colour is changed.
• When vertex v is changed from white to gray the time is recorded in d[v].
• When vertex v is changed from gray to black the time is recorded in f[v].

The discovery and the finish times are unique integers, where for each vertex the finish time is always after the
discovery time. That is, each time-stamp is an unique integer in the range of 1 to 2|V| and for each vertex v, d[v]
< f[v]. In other words, the following inequalities hold:

1 ≤ d[v] < f[v] ≤ 2|V|

75
Design and Analysis of Algorithms

The algorithm for such a traversal can be written using recursion as given in the algorithm below:

The algorithm starts by marking all vertices unvisited. The algorithm then calls Procedure dfs for each unvisited
vertex in V. This is because not all the vertices may be reachable from the start vertex. Starting from some vertex
v  V, Procedure dfs performs the search on G by visiting v, marking v visited and then recursively visiting its
adjacent vertices. When the search is complete, if all vertices are reachable from the start vertex, a spanning tree
called the depth-first search spanning tree is constructed whose edges are those inspected in the forward direction
i.e. when exploring unvisited vertices. In other words, let (v, w) be an edge such that w is marked unvisited and
suppose the procedure was invoked by the call dfs(v). Then, in this case, that edge will be part of the depth-first
search spanning tree.

If not all the vertices are reachable from the start vertex then the search results in a forest of spanning trees
instead. After the search is complete, each vertex is labelled predfn and postdfn numbers. These two labels
impose preorder and postorder numbering on the vertices in the spanning tree (or forest) generated by the depth-first
search traversal. They give the order in which visiting a vertex starts and ends. In the following, we say that edge
(v, w) is being explored to mean that within the call dfs(v), the procedure is inspecting the edge (v, w) to test
whether w has been visited before or not. The edges of the graph are classified differently according to whether
the graph is directed or undirected.

The case of undirected graphs

Let G = (V, E) be an undirected graph. As a result of the traversal, the edges of G are classified into the following
two types:
• Tree edges: edges in the depth-first search tree. An edge (v, w) is a tree edge if w was first visited when exploring
the edge (v, w).
• Back edges: All other edges.

76
 Fig. 5.2 An example of depth-first search traversal of an undirected graph

Fig. 5.2 (b) illustrates the action of depth-first search traversal on the undirected graph shown in fig 5.2(a).
Vertex a has been selected as the start vertex. The depth-first search tree is shown in fig 5.2 (b) with solid lines.
Dotted lines represent back edges. Each vertex in the depth-first search tree is labelled with two numbers: predfn
and postdfn. Note that since vertex e has postdfn = 1, it is the first vertex whose depth-first search is complete.
Note also that since the graph is connected, the start vertex is labelled with predfn = 1 and postdfn = 10, the
number of vertices in the graph.

The case of directed graphs

Depth-first search in directed graphs results in one or more (directed) spanning trees whose number depends on
the start vertex. If v is the start vertex, depth-first search generates a tree consisting of all vertices reachable from
v. If not all vertices are included in that tree, the search resumes from another unvisited vertex, say w and a tree
consisting of all unvisited vertices that are reachable from w is constructed. This process continues until all
vertices have been visited. In depth-first search traversal of directed graphs, however, the edges of G are
classified into four types:

Tree edges: Edges in the depth-first search tree. An edge (v, w) is a tree edge if w was first visited when exploring
the edge (v, w).

Fig. 5.3 Tree edge

77
Design and Analysis of Algorithms

Back edges: Edges of the form (v, w) such that w is an ancestor of v in the depth-first search tree (constructed so
far) and vertex w was marked visited when (v, w) was explored.

Fig. 5.4 Back edge

Forward edges: Edges of the form (v, w) such that w is a descendant of v in the depth-first search tree (constructed
so far) and vertex w was marked visited when (v, w) was explored.

Fig. 5.5 Forward edge

Cross edges: All other edges.

Fig. 5.6 Cross edges

78
Applications of DFS
DFS is used to solve the following problems:
• Testing whether graph is connected.
• Computing a spanning forest of G.
• Computing the connected components of G.
• Computing a path between two vertices of G or reporting that no such path exists.
• Computing a cycle in G or reporting that no such cycle exists.

5.5.2.1 Biconnected Components and DFS

Articulation point: A vertex v in a connected graph G is an articulation point if the deletion of v from G, along
with the deletion of all edges incident to v, disconnects the graph into two or more nonempty components.

For the below Graph G = (V, E),

• vertex 2 is an articulation point
• vertices 5 and 3 are also articulation points

Biconnected graph: A graph G is biconnected if and only if it contains no articulation points.

• Presence of an articulation point may be an undesirable feature in many cases.
• Consider a communications network with nodes as communication stations and edges as communication
lines.
• Failure of a communication station may result in loss of communication between other stations as well, if
graph is not biconnected.
• Algorithm to determine if a connected graph is biconnected:
 Identify all the articulation points in a connected graph.
 If graph is not biconnected, determine a set of edges whose inclusion makes the graph biconnected.
 Find the maximal subgraphs of G that are biconnected.

Biconnected component: G' = (V', E') is a maximal biconnected subgraph of G if and only if G has no
biconnected subgraph G'' = (V'', E'') such that V' ⊆ V'' and E' ⊆ E''. A maximal biconnected subgraph is a
biconnected component.
• Two biconnected components can have at most one vertex in common and this vertex is an articulation point.

79
 Design and Analysis of Algorithms

• No edge can be in two different biconnected components; this will require two common vertices
• Graph G can be transformed into a biconnected graph by using the edge addition scheme in the following
algorithm:

• Biconnected components of the above given graph are: {1, 2, 3, 4}, {2, 5, 7, 8}, {5, 6}, {3, 10}, {3, 9}
 Add edge (4, 10) and (10, 9) corresponding to articulation point 3, edge (1, 5) corresponding to
articulation point 2, and edge (6, 7) corresponding to articulation point 5.
 In the algorithm mk_biconnected, once the edge (vi, vi+1) is added, vertex a is no longer an articulation
point.
 If G has p articulation points and b biconnected components, the above algorithm introduces exactly b − p
new edges into G.

5.6 Backtracking
A backtracking algorithm tries to build a solution to a computational problem incrementally. Whenever the
algorithm needs to decide between two alternatives to the next component of the solution, it simply tries both
options recursively.

For many real-world problems, the solution process consists of working your way through a sequence of decision
points in which each choice leads you further along some path. If you make the correct set of choices, you end
up at the solution. On the other hand, if you reach a dead end or otherwise discover that you have made an
incorrect choice somewhere along the way, you have to backtrack to a previous decision point and try a different
path. Algorithms that use this approach are called backtracking algorithms.

If you think about a backtracking algorithm as the process of repeatedly exploring paths until you encounter the
solution, the process appears to have an iterative character. As it happens, however, most problems of this form
are easier to solve recursively. The fundamental recursive insight is simply this: a backtracking problem has a
solution if and only if at least one of the smaller backtracking problems that results from making each possible
initial choice has a solution.

Back tracking is a systematic way to go through all the possible configuration of a search space. In general case, we
assume our solution is a vector v = (a1, a2, ..., an) where each element a is selected from a finite ordered set Si.

We build from a partial solution of length Kv = (a1, a2,...,ak) and try to extend it by adding another element. After
extending it, we will test whether what we have so far is still possible a partial solution. If not, we delete ak and
try the next element from Sk:

80
Recursive Backtracking
• Recursion can be used for elegant and easy implementation of backtracking.
• Backtracking can be easily be used to iterate through all subsets or permutations of a set.
• Backtracking ensures correctness by enumerating all possibilities.
• For backtracking to be efficient, we must prune the search space.

5.6.1 Sum of Subsets Problem

The sum of subsets problem consists of finding a subset of a given set X = {x1, x2...xn} of n distinct positive
integers and a positive integer S. Find all subsets of {x1, x2...xn} that sum to S.

For example, if X = {3, 5, 6, 7, 8, 9, 10} and S = 15, there will be more than one subset whose sum is 15. The subsets
are {7, 8}, {3, 5, 7}, {6, 9} and {5, 10}. On the other hand, if X = {1, 5, 6, 7, 11, 12, 13} and S = 15, there will
be no subset that adds up to 15.

We will assume a binary state space tree. The nodes at depth 1 are for including (yes = 1, no = 0) item 1, the
nodes at depth 2 are for item 2, etc. The left branch includes xi and the right branch excludes xi. The nodes contain
the sum of the numbers included so far.

Backtracking consists of doing a DFS of the state space tree, checking whether each node is promising and if the
node is non-promising backtracking to the node's parent. We call a node non-promising if it cannot lead to a feasible
(or optimal) solution, otherwise it is promising. The state space tree consisting of expanded nodes only is called
the pruned state space tree. The below example will show the pruned state space tree for the sum of subsets
problem. Consider a node at depth i,
sumSoFar = sum of node – that is, sum of numbers included in partial solution node.
sumLeft = sum of the remaining items i + 1 to n (for a node at depth i).

A node at depth i is non-promising:

If ((sumSoFar + sumLeft < S) or (sumSofar + x[i+1] > S))

To be able to use this "promising function" the xi must be sorted in increasing order. The include [1...n] is a boolean
array. If its value is true, then the node is included in the partial tree, else not included.

The below algorithm (a): sumOfSubsets (i, sumSofar, sumLeft) is invoked with:
i = 0, sumSoFar = 0 and sumLeft = x1 + x2 + ... + xn. The algorithm is called with sumOfSubsets (0, 0, 21) for the
below example.

81
Design and Analysis of Algorithms

Example:
X = {3, 5, 6, 7} and S = 15. There are only 15 nodes in the pruned state space tree as shown in the figure below. The
full state space tree has 31 nodes (24+1 – 1). Trace of the above algorithm is given in below Table 5.1. Nodes of
the tree are shown by circled numbers. Notice that the x1 is included at level 1 of the tree, x2 at level 2 and so on.
We have only one solution with subset {3, 5, 7}. This occurs at node 6 in the below figure.

Fig. 5.7 Pruned state space tree

82
 i node sumSoFar sumLeft Comment
0 1 0 21 Start
1 2 3 18 include 3
2 3 8 13 include 5
3 4 14 7 include 6
3 5 8 7 include 6
4 6 15 0 include 7
357 ← Solution
4 7 8 0 exclude 7
2 8 3 13 exclude 5
3 9 9 7 include 6
3 10 3 7 exclude 6
1 11 0 18 exclude 3
2 12 5 13 include 5
3 13 11 7 include 6
3 14 5 7 exclude 6
2 15 0 13 exclude 5

Table 5.1 Trace of sum of subsets

5.6.2 Graph Colouring

In graph theory, graph colouring is a special case of graph labelling; it is an assignment of labels traditionally
called "colours" to elements of a graph subject to certain constraints. In its simplest form, it is a way of colouring
the vertices of a graph such that no two adjacent vertices share the same colour; this is called a vertex colouring.
Similarly, an edge colouring assigns a colour to each edge so that no two adjacent edges share the same colour,
and a face colouring of a planar graph assigns a colour to each face or region so that no two faces that share a
boundary have the same colour.

Graph colouring is defined as colouring the nodes of a graph with the minimum number of colours without any
two adjacent nodes having the same colour. For example, the linked list needs two colours and so does the binary
search tree. Graph colouring has wide applications such as, estimation of sparse Jacobins, scheduling and
registering allocation.

The colouring of a graph G = (V, E) is a mapping c: v  s, where s is a finite set of colours, such that if vw  E
then c(v) ≠ c(w). In other words, adjacent vertices are not assigned the same colour. The problem that arises is
the colouring of a graph provided that no adjacent vertices have the same colour. The chromatic number X (G)
is the minimum number of colours needed for a colouring of G. A graph G is k_chromatic, if X (G) = k, and G is
k_colourable, if X(G) ≤ k.

Graph colouring is one of the most useful models in graph theory. It has been used to solve problems in school
timetabling, computer register allocation, electronic bandwidth allocation, and many other applications.

Graph Colouring Algorithms

There are many heuristic sequential techniques for colouring a graph. One of them is the Greedy Graph
Colouring. This technique focuses on carefully picking the next vertex to be coloured. In this heuristic algorithm,
once a vertex is coloured, its colour never changes. The first fit and degree based ordering techniques are
explained below.

a. First fit: First Fit algorithm is the easiest and fastest technique of all greedy colouring heuristics. The algorithm
sequentially assigns each vertex the lowest legal colour. This algorithm has the advantage of being very simple
and fast and can be implemented to run in O(n) .

83
Design and Analysis of Algorithms

b. Degree based ordering: It provides a better strategy for colouring a graph. It uses a certain selection criterion
for choosing the vertex to be coloured. This strategy is better than the First Fit which simply picks a vertex from
an arbitrary order. Some strategies for selecting the next vertex to be coloured have been proposed such as:

Largest degree ordering (LDO): It chooses a vertex with the highest number of neighbours. Intuitively, LDO
provides a better colouring than the First Fit. This heuristic can be implemented to run in O(n2).

Saturation degree ordering (SDO): The saturation degree of a vertex is defined as the number of its adjacent
differently coloured vertices. Intuitively, this heuristic provides a better colouring than LDO as it can be
implemented to run in O(n3).

Incidence degree ordering (IDO): A modification of the SDO heuristic is the incidence degree ordering. The
incidence degree of a vertex is defined as the number of its adjacent coloured vertices. This heuristic can be
implemented to run in O(n2).

Fig. 5.8 Example of graph colouring

84
The algorithm for graph colouring is given as follows:

5.6.3 Hamiltonian Cycles

In the mathematical field of graph theory, a Hamiltonian cycle (or Hamiltonian circuit) is a cycle in an undirected
graph which visits each vertex exactly once and also returns to the starting vertex. A Hamiltonian path (or
traceable path) is a path in an undirected graph which visits each vertex exactly once.

A Hamiltonian cycle, Hamiltonian circuit, vertex tour or graph cycle is a cycle that visits each vertex exactly once
(except the vertex which is both the start and end, and so is visited twice). A graph that contains a Hamiltonian
cycle is called a Hamiltonian graph.

A Hamiltonian path or traceable path is a path that visits each vertex exactly once. A graph that contains a
Hamiltonian path is called a traceable graph. A graph is Hamilton-connected if for every pair of vertices there is a
Hamiltonian path between the two vertices.

85
Design and Analysis of Algorithms

(a) Input

(b) Output

Fig. 5.9 An example of Hamiltonian cycle

Some of the examples are:

• a complete graph with more than two vertices is Hamiltonian
• every cycle graph is Hamiltonian
• every tournament has an odd number of Hamiltonian paths
• every platonic solid, considered as a graph, is Hamiltonian

Some of the properties are:

• Any Hamiltonian cycle can be converted to a Hamiltonian path by removing one of its edges, but a
Hamiltonian path can be extended to Hamiltonian cycle only if its endpoints are adjacent.
• The line graph of a Hamiltonian graph is Hamiltonian. The line graph of an Eulerian graph is Hamiltonian.
• A tournament (with more than 2 vertices) is Hamiltonian if and only if it is strongly connected.
• A Hamiltonian cycle may be used as the basis of a zero-knowledge proof.
• Number of different Hamiltonian cycles for a complete graph = (n-1)! / 2
• Number of different Hamiltonian cycles for a complete directed graph = (n-1)!

86
5.6.4 The Eight Queens Problem
The problem of the eight queens is a well-known example of the use of trial-and-error methods and of
backtracking algorithms. It was investigated by C .F. Gauss in 1850, but he did not completely solve it. The
characteristic property of these problems is that they defy analytic solution. Instead, they require large amounts of
exacting labour, patience, and accuracy. Such algorithms have therefore gained relevance almost exclusively
through the automatic computer, which possesses these properties to a much higher degree than people, and even
geniuses, do.

Eight queens are to be placed on a chess board in such a way that no queen checks against any other queen. There
remains the question of representing the eight queens on the board. An obvious choice would again be a square
matrix to represent the board, but a little inspection reveals that such a representation would lead to fairly
cumbersome operations for checking the availability of positions. This is highly undesirable since it is the most
frequently executed operation. We should therefore choose a data representation which makes checking as simple
as possible. The best recipe is to represent as directly as possible that information which is truly relevant and
most often used.

• The problem is to place eight queens on an 8 x 8 chess board so that no two queens attack i.e. no two of them
are on the same row, column or diagonal.
• Strategy: The rows and columns are numbered through 1 to 8.
• The queens are also numbered through 1 to 8.
• Since each queen is to be on a different row without loss of generality, we assume queen i is to be placed on
row i.
• The solution is an 8 tuple (x1,x2,.. . .,x8) where xi is the column on which queen i is placed.
• The explicit constraints are : S = {1,2,3,4,5,6,7,8} 1  i  n or 1  x  8
i i
where i = 1,........8.
• The solution space consists of 88 8- tuples.
• The implicit constraints are :
 no two xis can be the same that is, all queens must be on different columns
 no two queens can be on the same diagonal
 reduces the size of solution space from 88 to 8! 8 – tuples
 Two solutions are (4,6,8,2,7,1,3,5) and (3,8,4,7,1,6,2,5)

Fig 5.10 Example of 8-Queens problem

87
Design and Analysis of Algorithms

Basic idea of solution:

• Start with one queen in the first column, first row.
• Start with another queen in the second column, first row.
• Go down with the second queen until you reach a permissible situation.
• Advance to the next column, first row, and do the same thing.
• If you cannot find a permissible situation in one column and reach the bottom of it, then you have to go back
to the previous column and move one position down there. (This is the backtracking step.)
• If you reach a permissible situation in the last column of the board, then the problem is solved.
• If you have to backtrack BEFORE the first column, then the problem is not solvable.

The general algorithm for N-Queens problem is as given below:

88
 Design and Analysis of Algorithms

Exercises 5
1. For the below given graph, determine the preorder traversal.

2. For the graph given in Q.1, determine the inorder traversal.

3. For the graph given in Q.1, determine the postorder traversal.

4. is a procedure by which each node in the tree is processed exactly once in a systematic manner.
a. Backtracking
b. Recursion
c. Iteration
d. Traversal

5. How many ways are there of traversing a binary tree?

a. One
b. Two
c. Three
d. Four

6. A is considered to be fully traversed when it is encountered.

a. null sub tree
b. binary tree
c. connected tree
d. free tree

7. Which traversal technique processes the root node first?

a. preorder traversal
b. inorder traversal
c. postorder traversal
d. level order traversal

8. What is the long form of BCH?

a. Binary Council Hexadecimal
b. Bose-Chaudhuri-Hocquenghem
c. Binary Characteristic Homogeneous
d. Bureau of Correction History

90
9. In AND/OR graphs, the successors are sub goals that must all be achieved to satisfy the parent goal.
a. OR
b. AND
c. vertex
d. edge

10. A game tree is a graph whose nodes are positions in a game and whose edges are moves.
a. undirected
b. mixed
c. directed
d. multi

91
 Design and Analysis of Algorithms

Chapter VI
Complexity

Aim

The aim of this chapter is to:

• explore the complexity of the problem

• elucidate the computation theory

• explain the algorithm trouble

Objectives
The objectives of this chapter are to:

• explain the finite set of symbols

• explicate the notations of various terms

• elucidate computation with resource bounds

Learning outcome
At the end of this chapter, you will be able to:

• understand the polynomial time

• identify the discrete square roots

• recognise the time constructible functions

92
 6.1 Introduction
The need to be able to measure the complexity of a problem, algorithm or structure and to obtain bounds and
quantitive relations for complexity arises in more and more sciences: besides computer science, the traditional
branches of mathematics, statistical physics, biology, medicine, social sciences and engineering are also
confronted more and more frequently with this problem. In the approach taken by computer science, complexity
is measured by the quantity of computational resources (time, storage, program, communication) used up by a
particular task. These notes deal with the foundations of this theory.

Computation theory can basically be divided into three parts of different character. First, the exact notions of
algorithm, time, storage capacity, etc. must be introduced. For this, different mathematical machine models must
be defined, and the time and storage needs of the computations performed on these need to be clarified (this is
generally measured as a function of the size of input). By limiting the available resources, the range of solvable
problems gets narrower; this is how we arrive at different complexity classes. The most fundamental complexity
classes provide an important classification of problems arising in practice, but (perhaps more surprisingly) even
for those arising in classical areas of mathematics; this classification reflects the practical and theoretical
difficulty of problems quite well. The relationship between different machine models also belongs to this first
part of computation theory.

Second, one must determine the resource need of the most important algorithms in various areas of mathematics,
and give efficient algorithms to prove that certain important problems belong to certain complexity classes. In
these notes, we do not strive for completeness in the investigation of concrete algorithms and problems; this is
the task of the corresponding fields of mathematics (combinatorics, operations research, numerical analysis,
number theory). Nevertheless, a large number of concrete algorithms will be described and analyzed to illustrate
certain notions and methods, and to establish the complexity of certain problems.

Third, one must find methods to prove \negative results”, i.e. for the proof that some problems are actually
unsolvable under certain resource restrictions. Often, these questions can be formulated by asking whether certain
complexity classes are different or empty. This problem area includes the question whether a problem is
algorithmically solvable at all; this question can today be considered classical, and there are many important results
concerning it; in particular, the decidability or undecidablity of most concrete problems of interest is known.

The majority of algorithmic problems occurring in practice is, however, such that algorithmic solvability itself is
not in question, the question is only what resources must be used for the solution. Such investigations, addressed
to lower bounds, are very difficult and are still in their infancy. In these notes, we can only give a taste of this
sort of results. In particular, we discuss complexity notions like communication complexity or decision tree
complexity, where by focusing only on one type of rather special resource, we can give a more complete analysis
of basic complexity classes.

It is, finally, worth noting that if a problem turns out to be difficult to solve, this is not necessarily a negative
result. More and more areas (random number generation, communication protocols, cryptography and data
protection) need problems and structures that are guaranteed to be complex. These are important areas for the
application of complexity theory; from among them, we will deal with random number generation and
cryptography, the theory of secret communication.

6.2 Some Notation and Definitions

A finite set of symbols will sometimes be called an alphabet. A finite sequence formed from some elements of an
alphabet is called a word. The empty word will also be considered a word, and will be denoted by ; The set of
words of length n over is denoted by n, the set of all words (including the empty word) over is denoted by
*. A subset of *, i.e., an arbitrary set of words, is called a language. Note that the empty language is also
denoted by ; but it is different, from the language { } containing only the empty word.

Let us define some orderings of the set of words. Suppose that an ordering of the elements of is given. In the
lexicographic ordering of the elements of Σ*, a word proceeds a word , if either is a prefix (beginning

93
Design and Analysis of Algorithms

segment) of or the first letter which is different in the two words is smaller in . (E.g., 35244 precede 35344 which
precede

94
 Design and Analysis of Algorithms

353447). The lexicographic ordering does not order all words in a single sequence: for example, every word
beginning with 0 precedes the word 1 over the alphabet {0, 1}. The increasing order is therefore often preferred:
here, shorter words precede longer ones and words of the same length are ordered lexicographically. This is the
ordering of {0, 1}* we get when we write up the natural numbers in the binary number system.

The set of real numbers will be denoted by R, the set of integers by Z and the set of rational numbers (fractions) by
Q. The sign of the set of non-negative real (integer, rational) numbers is R+ (Z+, Q+). When the base of a
logarithm will not be indicated it will be understood to be 2.

Let f and g be two real (or even complex) functions defined over the natural numbers. We write

f = O(g)

if there is a constant c > 0 such that for all n large enough we have |f (n)| ≤ c|g(n)|. We write

f = o(g)

if f is 0 only at a finite number of places and f (n)/g(n) → 0 if n → ∞. We will also use sometimes an inverse of the
big O notation: we write

f = Ω(g)

if g = O(f ). The notation

f = Θ(g)

means that both f = O(g) and g = O(f ) hold, i.e. there are constants c1 , c2 > 0 such that for all n large
enough we have c1 g(n) ≤ f (n) ≤ c2 g(n). We will also use this notation within formulas. Thus,

(n + 1)2 = n2 + O(n)

means that (n + 1)2 can be written in the form n 2 + R(n) where R(n) = O(n2). Keep in mind that in this kind of
formula, the equality sign is not symmetrical. Thus, O(n) = O(nn ) but O(n2 ) = O(n). When such formulas
become too complex it is better to go back to some more explicit notation.

6.3 Computation with Resource Bounds

The algorithmic solvability of some problems can be very far from their practical solvability. There are
algorithmically solvable problems that cannot be solved, for an input of a given size, in fewer than exponentially
or doubly exponentially many steps. Complexity theory, a major branch of the theory of algorithms, investigates
the solvability of individual problems under certain resource restrictions. The most important resource are time
and space (storage).

We define these notions in terms of the Turing machine model of computation. This definition is suitable for
theoretical study; in describing algorithms, using the RAM is more convenient, and it also approximates reality
better. It follows, however, from our constructions, that from the point of view of the most important type of
resource restrictions (e.g. polynomial time and space) it does not matter, which machine model is used in the
definition.

This leads to the definition of various complexity classes: classes of problems solvable within given time bounds,
depending on the size of the input. Every positive function of the input size defines such a class, but some of
them are particularly important. The most central complexity class is polynomial time. Many algorithms
important in practice run in polynomial time (in short, are polynomial). Polynomial algorithms are often very
interesting mathematically, since they are built on deeper insight into the mathematical structure of the problems,
and often use strong mathematical tools.
94
 We restrict the computational tasks to yes-or-no problems; this is not too much of a restriction, and pays off in
what we gain simplicity of presentation. Note that the task of computing any output can be broken down to
computing its bits in any reasonable binary representation.

Most of this chapter is spent on illustrating how certain computational tasks can be solved within given resource
contraints. We start with the most important case, and show that most of the basic everyday computational tasks
can be solved in polynomial time. These basic tasks include tasks in number theory (arithmetic operations,
greatest common divisor and modular arithmetic) linear algebra (Gaussian elimination) and graph theory. (We
cannot in any sense survey all the basic algorithms, especially in graph theory; we’ll restrict ourselves to a few
that will be needed later.

Polynomial space is a much more general class than polynomial time (i.e., a much less restrictive resource
constraint). The most important computational problems solvable in polynomial space (but most probably not in
polynomial time) are games like chess or GO. We give a detailed description of this connection.

We end with a briefer discussion of other typical complexity classes.

6.4 Time and Space

Let us fix some finite alphabet Σ, including the blank symbol ∗ and let Σ0 = Σ \ {∗}. In this chapter, when a
Turing machine is used for computation, we assume that it has an input tape and output tape and k ≥ 1 work
tapes. At start, there is a word in Σ∗ written on the input tape.

The time demand of a Turing machine T is a function time T (n) defined as the maximum of the number of steps
taken by T over all possible inputs of length n. We assume time T (n) ≥ n (the machine must read the input; this
is not necessarily so but we exclude only trivial cases with this assumption). It may happen that time T (n) = ∞.

Similarly, the function space T (n) is defined as the maximum number, over all inputs of length n, of all cells on
all tapes to which the machine writes. (This way, the cells occupied by the input are not counted in the space
requirement.) We assume that space T (n) ≥ 1 (the machine has some output).

A Turing machine T is called polynomial , if there is a polynomial f (n) such that time T (n) = O(f (n)). This is
equivalent to saying that there is a constant c such that the time demand of T is O(n c ). We can define exponential
Turing machines similarly (for which the time demand is O( ) for some c > 0), and also Turing machines
working in polynomial and exponential space.

Now we consider a yes-or-no problem. This can be formalised as the task of deciding whether the input word x
belongs to a fixed language L ∈ Σ∗.

We say that a language L ∈ Σ∗ has time complexity at most f (n), if it can be decided by a Turing machine with
time demand at most f (n). We denote by DTIME(f (n)) the class of languages whose time complexity is at most f
(n). (The letter “D” indicates that we consider here only deterministic algorithms; later, we will also consider
algorithms that are “nondeterministic” or use randomness). We denote by PTIME, or simply by P, the class of all
languages decidable by a polynomial Turing machine. We define similarly when a language has space
complexity at most f (n), and also the language classes DSPACE(f (n)) and PSPACE (polynomial space).

Remark 6.4.1 It would be tempting to define the time complexity of a language L as the optimum time of a
Turing machine that decides the language. Note that we were more careful above, and only defined when the time
complexity is at most f (n). The reason is that there may not be a best algorithm (Turing machine) solving a given
problem: some algorithms may work better for smaller instances, some others on larger, some others on even
larger etc. Section
3.3 contains a theorem that provides such examples.

95
 Design and Analysis of Algorithms

Remark 6.4.2 When we say that the multiplication of two numbers of size n can be per- formed in time n2 then
we actually find an upper bound on the complexity of a function (multiplication of two numbers represented by
the input strings) rather than a language. The classes DTIME(f (n)), DSPACE(f (n)), etc. are defined as classes of
languages; corresponding classes of functions can also be defined.

Sometimes, it is easy to give a trivial lower bound on the complexity of a function. Consider e.g. the function is x
• y where x and y are numbers in binary notation. Its computation requires at least |x| + |y| steps, since this is the
length of the output. Lower bounds on the complexity of languages are never this trivial, since the output of the
computation deciding the language is a single bit.

How to define time on the RAM machine? The number of steps of the Random Access Machine is not the best
measure of the “time it takes to work”. One could (mis)use the fact that the instructions operate on natural
numbers of arbitrary size, and develop computational tricks that work in this model but use such huge integers
that to turn them into practical computations would be impossible. For example, we can simulate vector addition
by the addition of two very large natural numbers.

Therefore, we prefer to characterise the running time of RAM algorithms by two numbers, and say that “the
machine makes at most n steps on numbers with at most k bits”. Similarly, the space requirement is best
characterised by saying that “the machine stores most n numbers with at most k bits”.

If we want a single number to characterise the running time of a RAM computation, we can count as the time of a
step not one unit but the number of bits of the integers occurring in it (both register addresses and their contents).
Since the number of bits of an integer is essentially base two logarithm of its absolute value, it is also usual to
call this model logarithmic cost RAM.)

In arithmetical and algebraic algorithms, it is sometimes convenient to count the arith- metical operations; on a
Random Access Machine, this corresponds to extending the set of basic operations of the programming language
to include the subtraction, multiplication, division (with remainder) and comparison of integers, and counting the
number of steps in- stead of the running time. If we perform only a polynomial number of operations (in terms of
the length of the input) on numbers with at most a polynomial number of digits, then our algorithm will be
polynomial in the logarithmic cost model.

6.5 Polynomial Time I: Algorithms in Arithmetic

All basic arithmetic operations are polynomial: addition, subtraction, multiplication and division of integers with
remainder. (Recall that the length of an integer n as input is the number of its bits, i.e., log2 n + O(1)). We learn
polynomial time algorithms for all these operations in elementary school (linear time algorithms in the case of
addition and subtraction, quadratic time algorithms in the case of multiplication and division). We also count the
comparison of two numbers as a trivial but basic arithmetic operation, and this can also be done in polynomial
(linear) time.

A less trivial polynomial time arithmetic algorithm the Euclidean algorithm, computing the greatest common
divisor of two numbers.

6.5.1 Euclidean Algorithm

We are given two natural numbers, a and b. Select one that is not larger than the other, let this be a (say). If a = 0
then the greatest common divisor of a and b is gcd(a, b) = b. If a > 0 then let us divide b by a, with remainder,
and let r be the remainder.

Then gcd(a, b) = gcd(a, r), and it is enough therefore to determine the greatest common divisor of a and r. Since r
< a, this recurrence will terminate in a finite number of iterations and we get the greatest common divisor of a
and b.

Notice that strictly speaking, the algorithm given above is not a program for the Random Access Machine. It is a
recursive program, and even as such it is given somewhat informally. But we know that such an informal
program can be translated into a formal one, and a recursive program can be translated into a machine-language

96
program (most compilers can do that).

97
Design and Analysis of Algorithms

Lemma 6.5.1 The Euclidean algorithm takes polynomial time. More exactly, it carries out of O(log a + log b)
arithmetical operations carried out on input (a, b).

Proof: Since 0 ≤ r < a ≤ b, the Euclidean algorithm will terminate sooner or later. Let us see that it terminates in
polynomial time. Notice that b ≥ a + r > 2r and thus r < b/2. Hence ar < ab/2. Therefore after plog(ab)I iterations,
the product of the two numbers will be smaller than 1, hence one of them will be 0, i.e. the algorithm terminates.
Each iteration consists of elementary arithmetic operations, and can be carried out in polynomial time. D

It is an important feature of the Euclidean algorithm not only gives the value of the greatest common divisor, but
also delivers integers p, q such that gcd(a, b) = pa + qb. For this, we simply maintain such a form for all numbers
computed during the algorithm.

If a’ = p1 a + q1b and b’= p2 a + q2 b and we divide, say, bt by at with remainder: b’ = ha’+ r’ then
R’ = (p2 − hp1 )a + (q2 − hp2 )b,

and thus we obtain the representation of the new number r’ in the form p’a + q’b.

Remark 6.5.1 The Euclidean algorithm is sometimes given by the following iteration: if a = 0 then we are done. If a
> b then let us switch the numbers. If 0 < a ≤ b then let b:= b − a. Mathematically, essentially the same thing
happens (Euclid’s original algorithm was closer to this), this algorithm is not polynomial: even the computation
of gcd(1, b) requires b iterations, which is exponentially large in terms of the number log b + O(1) of digits of the
input.

The operations of addition, subtraction, multiplication can be carried out in polynomial times also in the ring of
remainder classes modulo an integer m. We represent the remainder classes by the smallest nonnegative remainder.
We carry out the operation on these as on integers; at the end, another division by m, with remainder, is
necessary.

If m is a prime number then we can also carry out the division in the field of the residue classes modulo m, in
polynomial time. This is different from division with remainder! It means that given integers a, b and m, where 0
≤ a, b ≤ m − 1 and b = 0, we can compute an integer x with 0 ≤ x < m such that

bx ≡ a (mod m).

(Such an x is sometimes denoted by a/b (mod m)).

The solution is to apply the Euclidean algorithm to compute the greatest common divisor of the numbers b, m. Of
course, we know in advance that the result is 1. But as remarked, we also obtain integers p and q such that bp +
mq = 1. In other words, bp ≡ 1 (mod m), and thus b(ap) ≡ a (mod m). So the quotient x we are looking for is the
remainder of the product ap after dividing by m.

We mention yet another application of the Euclidean algorithm. Suppose that a certain integer x is unknown to us
but we know its remainders x1 , . . . , xk with respect to the moduli m1 , . . . , mk which are all relatively prime to
each other. The Chinese Remainder Theorem says that these remainders uniquely determine the remainder of x
modulo the product m = m1 mk . But how can we compute this remainder?

It suffices to deal with the case k = 2 since for general k, the algorithm follows from this by mathematical
induction. We are looking for an integer x such that x ≡ x 1 (mod m1 ) and x ≡ x2 (mod m2 ) (we also want that 0 ≤
x ≤ m1 m2 − 1, but this we can achieve by dividing with remainder at the end).

In other words, we are looking for integers x, q1 and q2 such that x = x1 + q1 m1 and x = x2 + q2 m2. Subtracting, we
get x2 −x1 = q1 m1 −q2 m2 . This equation does not determine the numbers q1 and q2 uniquely, but this is not
important.
We can find, using the Euclidean algorithm, numbers q1 and q2 such that
x2 − x1 = q1 m1 − q2 m2 ,
98
and compute x = x1 + q1 m1 = x2 + q2 m2 . Then x ≡ x1 (mod m1 ) and x ≡ x2 (mod m2 ), as desired.

99
Design and Analysis of Algorithms

Next, we discuss the operation of exponentiation. Since even to write down the number 2n , we need an
exponential number of digits (in terms of the length of the input as the number of binary digits of n), so of course,
this number is not computable in polynomial time. The situation changes, however, if we want to carry out the
exponentiation modulo m: then ab is also a residue class modulo m, and hence it can be represented by log m +
O(1) bits. We will show that it can be not only represented polynomially but also computed in polynomial time.

6.5.2 Gaussian elimination

The basic operations of linear algebra are polynomial: addition and inner product of vectors, multiplication and
inversion of matrices, the computation of determinants. However, these facts are non-trivial in the last two cases,
so we will deal with them in detail.

Let A = (aij ) be an arbitrary n × n matrix consisting of integers.

Let us verify, first of all, that the polynomial computation of det(A) is not inherently impossible, in the sense that
the result can be written down with polynomially many bits.

Let K = max |aij |, then to write down the matrix A we need obviously at least L = n2 +log K bits. On the other hand,
the definition of determinants gives

| det(A)| ≤ n!Kn ,

hence det(A) can be written down using

log(n!Kn ) + O(1) ≤ n(log n + log K ) + O(1)

bits. This is polynomial in L.

Linear algebra gives a formula for each element of det(A−1 ) as the quotient of two sub- determinants of A. This
shows that A−1 can also be written down with polynomially many bits.

The usual procedure to compute the determinant is Gaussian elimination. We can view this as the transformation
of the matrix into a lower triangular matrix with column operations. These transformations do not change the
determinant, and in the final triangular matrix, the computation of the determinant is trivial: we just multiply the
diagonal elements to obtain it. It is also easy to obtain the inverse matrix from this form; we will not deal with
this issue separately.

Gaussian elimination: Suppose that for all i such that 1 ≤ i ≤ t, we have achieved already that in the i’th row, only
the first i entries hold a nonzero element. Pick a nonzero element from the last n − t columns (stop if there is no
such element). Call this element the pivot element of this stage. Rearrange the rows and columns so that this
element gets into position (t +1, t +1). Subtract column t +1, multiplied by at+1,i /at+1,t+1 , from column i column for
all i = t + 2, .
. . , n, in order to get 0’s in the elements (t + 1, t + 2), . . . , (t + 1, n). These subtractions do not change value of the
determinant and the rearrangement changes at most the sign, which is easy to keep track of.

Since one iteration of the Gaussian elimination uses O(n 2 ) arithmetic operations and n iterations must be performed,
this procedure uses O(n3 ) arithmetic operations. But the problem is that we must also divide, and not with
remainder. This does not cause a problem over a finite field, but it does in the case of the rational field. We
assumed that the elements of the original matrix are integers; but during the run of the algorithm, matrices also
occur that consist of rational numbers. In what form should these matrix elements be stored? The natural answer
is that as pairs of integers (whose quotient is the rational number).

Do we require that the fractions be in simplified form, i.e., that their numerator and denominator be relatively
prime to each other? We could do so; then we have to simplify each matrix element after each iteration, for which
we would have to perform the Euclidean algorithm. This can be performed in polynomial time, but it is a lot of
extra work, and it is desirable to avoid it. (Of course, we also have to show that in the simplified form, the

98
occurring numerators

99
Design and Analysis of Algorithms

and denominators have only polynomially many digits. This will follow from the discussions below.)
We could also choose not to require that the matrix elements be in simplified form. Then we define the sum and
product of two rational numbers a/b and c/d by the following formulas: (ad + bc)/(bd) and (ac)/(bd). With this
convention, the problem is that the numerators and denominators occurring in the course of the algorithm can
become very large (have a non-polynomial number of digits)!

Fortunately, we can give a procedure that stores the fractions in partially simplified form, and avoids both the
simplification and the excessive growth of the number of digits. For this, let us analyze a little the matrices occurring
during Gaussian elimination. We can assume that the pivot elements are, as they come, in positions (1, 1), . . . ,
(n, n), i.e., we do not have to permute the rows and columns. Let (a (k) ) (1 ≤ i, j ≤ n) be the matrix obtained after k
iterations. Let us denote the elements in the main diagonal of the final
i
matrix, for simplicity, by d 1 , . . . , dn (thus,
di = aii ). Let D denote the submatrix determined by the first k rows and columns of matrix A, and let D ij(k) , for
(n) (k)

k + 1 ≤ i, j ≤ n, denote the submatrix determined by the first k rows and the ith row and the first k columns and the
jth column. Let d(k) = det(D (k) ). Obviously, det(D(k) ) = d (k−1).
ij kk

6.5.3 Discrete square roots

In this section we discuss the number theoretic algorithm to extract square roots. We call the integers 0, 1, . . . , p − 1
residues (modulo p). Let p be an odd prime. We say that y is a square root of x (modulo p),

if y2 ≡ x (mod p).

If x has a square root then it is called a quadratic residue.

Obviously, 0 has only one square root modulo p: if y2 ≡ 0 (mod p), then p|y2 , and since p is a prime, this implies
that p|y. For every other integer x, if y is a square root of x, then so is p − y = −y (mod p). There are no further
square roots: indeed, if z2 ≡ x for some residue z, then p|y 2 − z2 = (y − z)(y + z) and so either p|y − z or p|y + z.
Thus z ≡ y or z ≡ −y as claimed.

This implies that not every integer has a square root modulo p: squaring maps the non- zero residues onto a
subset of size (p − 1)/2, and the other (p − 1)/2 have no square root. The following lemma provides an easy way
to decide if a residue has a square root.

Lemma 6.5.3 A residue x has a square root if and only

if x(p−1)/2 ≡ 1 (mod p). (4.1)

Proof. The “only if ” part is easy: if x has a square root y,

then x(p−1)/2 ≡ yp−1 ≡ 1 (mod p)

by Fermat’s “Little” Theorem. Conversely, the polynomial x(p−1)/2 − 1 has degree (p − 1)/2, and hence it has at
most (p − 1)/2 “roots” modulo p (this can be proved just like the well- know theorem that a polynomial of degree
n has at most n real roots). Since all quadratic residues are roots of x(p−1)/2 − 1, none of the quadratic non-
residues can be. D

6.6 General Theorems on Space and Time Complexity

If for a language L, there is a Turing machine deciding L for which for all large enough n the relation time T (n)
≤ f (n) holds then there is also a Turing machine recognising L for which this inequality holds for all n. Indeed,
for small values of n we assign the task of deciding the language to the control unit.

It can be expected that for the price of further complicating the machine, the time demands can be decreased. The
next theorem shows the machine can indeed be accelerated by an arbitrary constant factor, at least if its time need
is large enough (the time spent on reading the input cannot be saved).

10
Design and Analysis of Algorithms

Theorem 6.6.1(Linear Speedup Theorem) For every Turing machine and c > 0 there is a Turing machine S over the
same alphabet which decides the same language an for which time S (n) ≤ c • timeT (n) + n.

Proof. For simplicity, let us also assume that T has a single work tape (the proof would be similar for k tapes).
We can assume that c = 1/p where p is an integer.

Let the Turing machine S have an input-tape, 2p − 1 “starting” tapes and 2p − 1 further work tapes. Let us
number these each from 1 − p to p − 1. Let the index of cell j of (start- or work) tape i be the number j(2p − 1) +
i. The start- or work cell with index t will correspond to cell t on the input resp. Work tape of machine T. Let S
also have an output tape.

Machine S begins its work by copying every letter of input x from its input tape to the cell with the
corresponding index on its starting tapes, then moves every head back to cell 0. From then on, it ignores the
“real” input tape.

Every further step of machine S will correspond p consecutive steps of machine T. After pk steps of machine T,
let the scanning head of the input tape and the work tape rest on cells t and s respectively. We will plan machine
S in such a way that in this case, each cell of each start- resp. Work tape of S holds the same symbol as the
corresponding cell of the corresponding tape of T , and the heads rest on the starting-tape cells with indices t − p
+ 1, . . . , t + p − 1 and the work-tape cells with indices s − p + 1, . . . , s + p − 1. We assume that the control unit
of machine S “knows” also which head scans the cell corresponding to t resp. s. It knows further what is the state
of the control unit of T.

Since the control unit of S sees not only what is read by T ’s control unit at the present moment on its input- and
work tape but also the cells at a distance at most p −1 from these, it can compute where T ’s heads will step and
what they will write in the next p steps. Say, after p steps, the heads of T will be in positions t + i and s + j
(where, say, i, j > 0). Obviously, i, j < p. Notice that in the meanwhile, the “work head” could change the
symbols written on the work tape only in the interval [s − p + 1, s + p − 1].

Let now the control unit of S do the following: compute and remember what will be the state of T’s control unit p
steps later. Remember which heads rest on the cells corresponding to the positions (t + i) and (s + j). Let it
rewrite the symbols on the work tape according to the configuration p steps later (this is possible since there is a
head on each work cell with indices in the interval [s − p + 1, s + p − 1]). Finally, move the start heads with
indices in the interval [t − p + 1, t − p + i] and the work heads with indices in the interval [s − p + 1, s − p + j] one
step right; in this way, the indices occupied by them will fill the interval [t + p, t + p + i − 1] resp. [s + p, s + p + i
− 1] which, together with the heads that stayed in their place, gives interval [t + i − p + 1, t + i + p − 1] resp. [s + j
− p + 1, s + j + p − 1].

If during the p steps under consideration, T writes on the output tape (either 0 or 1) and stops, then let S do this,
too. Thus, we constructed a machine S that (apart from the initial copying) makes only a pth of the number of
steps of T and decides the same language.

Theorem 6.6.2 For every recursive function f (n) there is a recursive language L that is not an element of
DTIME(f (n)).

Proof: The proof is similar to the proof of the fact that the halting problem is undecidable. We can assume f (n) >
n. Let T be the 2-tape universal Turing machine constructed in Chapter 1, and let L consist of all words x for
which it is true that having x as input on both of its tape, T halts in at most f (|x|)4 steps. L is obviously recursive.

Let us now assume that ∈ DTIME(f (n)). Then there is a Turing machine (with some k > 0 tapes) deciding
in time f (n). From this we can construct a 1-tape Turing machine deciding in time cf (n)2 (e.g. in such a way
that it stops and writes 0 or 1 as its decision on a certain cell). Since for large enough n we have cf (n) 2 < f (n)3 ,
and the words shorter than this can be recognised by the control unit directly, we can also make a 1-tape Turing
machine that always stops in time f (n)3 . Let us modify this machine in such a way that if a word x is in then
it runs forever, while if x ∈ Σ∗ \ then it stops. This machine be S can be simulated on T by some program p in
such a way that T halts with input (x, p) if and only if S halts with input x; moreover, it halts in these cases within
100
|p|f (|x|)3 steps.

101
Design and Analysis of Algorithms

There are two cases. If p ∈ then—according to the definition of starting with input p on both tapes,
machine T will stop. Since the program simulates S it follows that S halts with input p. This is, however,
impossible, since S does not halt at all for inputs from . On the other hand, if p then—according to the
construction of S—starting with p on its first tape, this machine halts in time |p|f (|p|)3 < f (|p|)4 . Thus, T also
halts in time f (|p|)4
. But then p ∈ L by the definition of the language

. This contradiction shows that /∈ DTIME(f (n)).

There is also a different way to look at the above result. For some fixed universal two- tape Turing machine U
and an arbitrary function t(n) > 0, the t-bounded halting problem asks, for n and all inputs p, x of maximum
length n, whether the above machine U halts in t(n) steps. (Similar questions can be asked about storage.) This
problem seems decidable in t(n) steps, though this is true only with some qualification: for this, the function t(n)
must itself be computable in t(n) steps (see the definition of “fully time-constructible” below). We can also
expect a result similar to the undecidability of the halting problem, saying that the t-bounded halting problem
cannot be decided in time “much less” than t(n). How much less is “much less” here depends on some results on
the complexity of simulation between Turing machines.

6.6.1 Time-Constructible and Well-Computable Functions

We call a function f : Z+ → Z+ fully time-constructible if there is a multitape Turing machine that for each input
of length n using exactly f (n) time steps. The meaning of this strange definition is that with fully time-
constructable functions, it is easy to bound the running time of Turing machines: If there is a Turing machine
making exactly f (n) steps on each input of length n then we can build this into any other Turing machine as a
clock: their tapes, except the work tapes, are different, and the combined Turing machine carries out in each step
the work of both machines.

Obviously, every fully time-constructible function is recursive. On the other hands, it is easy to see that n2 , 2n , n!
and every “reasonable” function is fully time-constructible. The lemma below guarantees the existence of many
completely time-construct able functions.

Let us call a function f : Z+ → Z+ well-computable if there is a Turing machine computing

f (n) in time O(f (n)). (Here, we write n and f (n) in unary notation: the number n is given by a sequence 1 . . . 1 of
length n and we want as output a sequence 1 . . . 1 of length f (n). The results would not be changed, however, if
n and f (n) were represented e.g. in binary notation.) Now the following lemma is easy to prove:

Lemma 6.6.1
• To every well-computable function f (n), there is a fully time-constructible function g(n) such that f (n) ≤ g(n)
≤ const f (n).
• For every fully time-constructible function g(n) there is a well-computable function f (n) with g(n) ≤ f (n) ≤
const • g(n).
• For every recursive function f there is a fully time-constructible function g with f ≤ g.

This lemma allows us to use, in most cases, fully time-constructible and well-computable functions
interchangeably. Following the custom, we will use the former.

6.6.2 Space Versus Time

Above, some general theorems were stated with respect to complexity measures. It was shown that there are
languages requiring a large amount of time to decide them. Analogous theorems can be proved for the storage
complexity. It is natural to ask about the relation of these two complexity measures. There are some very simple
relations mentioned in the text before Theorem 6.6.2.

There is a variety of natural and interesting questions about the trade-off between storage and time. Let us first
102
mention the well-know practical problem that the work of most computers can be speeded up significantly by
adding

103
Design and Analysis of Algorithms

memory. The relation here is not really between the storage and time complexity of computations, only between
slower and faster memory. Possibly, between random-access memory versus the memory on disks, which is
closer to the serial-access model of Turing machines.

There are some examples of real storage-time trade-off in practice. Suppose that during a computation, the values
of a small but complex Boolean function will be used repeatedly. Then, on a random-access machine, it is worth
computing these values once for all inputs and use table look-up later. Similarly, if a certain field of our records
in a data base is often used for lookup then it is worth computing a table facilitating this kind of search
(inverting). All these examples fall into the following category. We know some problem P and an algorithm A
that solves it. Another algorithm at is also known that solves P in less time and more storage than A. But
generally, we don’t have any proof that with the smaller amount of time really more storage is needed to solve P.
Moreover, when a lower bound is known on the time complexity of some function, we have generally no better
estimate of the storage complexity than the trivial one mentioned above (and vice versa).

102
 Design and Analysis of Algorithms

Exercises 6
1. A finite sequence formed from some elements of an alphabet is called a word.
a.
b.
c. Θ
d. ∞

2. How will you denote the set of words of length n over ?

a. 0
b. *
c. 2
d. n

3. A subset of *, i.e., an arbitrary set of words, is called a .

a. alphabet
b. language
c. element
d. word

4. Match the following

1. Set of real numbers A. R+ (Z+, Q+)
2. Set of integers B. R
3. Set of rational numbers C. Z
4. The sign of the set of non-negative real numbers D. Q
a. 1-C, 2-B, 3-A, 4-D
b. 1-B, 2-C, 3-D, 4-A
c. 1-D, 2-A, 3-C, 4-B
d. 1-A, 2-C, 3-B, 4-D

5. When the base of a logarithm will not be indicated it will be understood to be .

a. one
b. zero
c. two
d. infinity

6. A Turing machine T is called , if there is a polynomial f (n) such that time T (n) = O(f (n)).
a. equivalent
b. monomial
c. polynomial
d. exponential

7. If there is a function x • y where x and y are numbers in binary notation then how many steps are required for
its computation?
a. |x| + |y|
b. x*y
c. x2 + y2
d. log2 n + O(1)

104
8. To every well-computable function f (n), there is a fully time-constructible function g(n) such that
.
a. g(n) ≤ f (n) ≤ const • g(n)
b. f (n) ≤ g(n) ≤ const f (n)
c. f ≤ g
d. f : Z+ → Z+

9. For every fully time-constructible function g(n) there is a well-computable function f (n) with g(n) ≤ f (n) ≤
const • g(n).
a. g(n) ≤ f (n) ≤ const • g(n)
b. f (n) ≤ g(n) ≤ const f (n)
c. f ≤ g
d. f : Z+ → Z+

10. Analogous theorems can be proved for the complexity.

a. space
b. storage
c. time
d. domain

105
 Design and Analysis of Algorithms

Chapter VII
Graph Theory

Aim
The aim of this chapter is to:

• explore the various terminologies used in graph theory

• elucidate the graph operations

• explain the labeled graphs

Objectives
The objectives of this chapter are to:

• explain the isomorphism

• explicate the trees and forests

• elucidate the circuits and cut sets

Learning outcome
At the end of this chapter, you will be able to:

• understand the directed graphs

• identify the directed trees

• recognise the use of different graph theories

106
7.1 Introduction
Conceptually, a graph is formed by vertices and edges connecting the vertices.

Fig. 7.1 Graph

Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, formed by pairs
of vertices. E is a multiset, in other words, its elements can occur more than once so that every element has a
multiplicity. Often, we label the vertices with letters (for example: a, b, c, . . . or v1, v2, . . . ) or numbers 1, 2, . . .
Throughout this chapter, we will label the elements of V in this way.

We have V = {v1, . . . , v5} for the vertices and E = {(v1, v2), (v2, v5), (v5, v5), (v5, v4), (v5, v4)} for the edges.
Similarly, we often label the edges with letters (for example: a, b, c, . . . or e1, e2, . . . ) or numbers 1, 2, . . . for
simplicity.

Remark: The two edges (u, v) and (v, u) are the same. In other words, the pair is not ordered. Example: We label
the edges as follows:

So E = {e1, . . . , e5}.
We have the following terminologies:
• The two vertices u and v are end vertices of the edge (u, v).
• Edges that have the same end vertices are parallel.
• An edge of the form (v, v) is a loop.
• A graph is simple if it has no parallel edges or loops.
• A graph with no edges (i.e. E is empty) is empty.
• A graph with no vertices (i.e. V and E are empty) is a null graph.
• A graph with only one vertex is trivial.
• Edges are adjacent if they share a common end vertex.
• Two vertices u and v are adjacent if they are connected by an edge, in other words, (u, v) is an edge.
• The degree of the vertex v, written as d(v), is the number of edges with v as an end ertex.
• By convention, we count a loop twice and parallel edges contribute separately.
• A pendant vertex is a vertex whose degree is 1.

107
Design and Analysis of Algorithms

• An edge that has a pendant vertex as an end vertex is a pendant edge.

• An isolated vertex is a vertex whose degree is 0.

Example:
• v4 and v5 are end vertices of e5.
• e4 and e5 are parallel.
• e3 is a loop.
• The graph is not simple.
• e1 and e2 are adjacent.
• v1 and v2 are adjacent.
• The degree of v1 is 1 so it is a pendant vertex.
• e1 is a pendant edge.
• The degree of v5 is 5.
• The degree of v4 is 2.
• The degree of v3 is 0 so it is an isolated vertex.

In the future, we will label graphs with letters, for example:

G = (V, E).

The minimum degree of the vertices in a graph G is denoted δ(G) (= 0 if there is an isolated vertex in G).
Similarly, we write ∆(G) as the maximum degree of vertices in G.

Theorem 1.1. The graphG = (V, E), where V = {v1, . . . , vn} and E = {e1, . . . , em}, satisfies

Corollary. Every graph has an even number of vertices of odd degree.

Proof. If the vertices v1, . . . , vk have odd degrees and the vertices vk+1, . . . , vn have even degrees, then (Theorem
1.1)

d(v1) + · · · + d(vk) = 2m − d(vk+1) − · · · − d(vn) is even. Therefore, k is even.

A simple graph that contains every possible edge between all the vertices is called a complete graph. A complete
graph with n vertices is denoted as Kn. The first four complete graphs are given as examples:

The graph G1 = (V1,E1) is a subgraph of G2 = (V2,E2) if

1. V1 ⊆ V2 and
2. Every edge of G1 is also an edge of G2.

108
7.2 Walks, Trails, Paths, Circuits, Connectivity, Components
Remark. There are many different variations of the following terminologies. We will adhere to the definitions given
here.

A walk in the graph G = (V,E) is a finite sequence of the form

vi0 , ej1 , vi1, ej2, . . . , ejk , vik ,

which consists of alternating vertices and edges of G. The walk starts at a vertex. Vertices and vit are end
vertices of ejt (t = 1, . . . , k). vi0 is the initial vertex and vik is the terminal vertex. k is the length of the walk. A
zero length walk is just a single vertex vi 0. It is allowed to visit a vertex or go through an edge more than once. A
walk is open if vi0 6= vik . Otherwise it is closed.

Example. In the graph

The walk v2, e7, v5, e8, v1, e8, v5, e6, v4, e5, v4, e5, v4 is open. On the other hand, the walk v4, e5, v4, e3, v3, e2, v2,
e7, v5, e6, v4 is closed.

A walk is a trail if any edge is traversed at most once. Then, the number of times that the vertex pair u, v can
appear as consecutive vertices in a trail is at most the number of parallel edges connecting u and v.

A trail is a path if any vertex is visited at most once except possibly the initial and terminal vertices when they
are the same. A closed path is a circuit. For simplicity, we will assume in the future that a circuit is not empty, i.e.
its length ≥ 1. We identify the paths and circuits with the subgraphs induced by their edges.

The walk starting at u and ending at v is called a u–v walk. u and v are connected if there is a u–v walk in the graph
(then there is also a u–v path!). If u and v are connected and v and w are connected, then u and w are also connected,
i.e. if there is a u–v walk and a v–w walk, then there is also a u–w walk. A graph is connected if all the vertices
are connected to each other.
(A trivial graph is connected by convention.)

Theorem 1.2 If the graph G has a vertex v that is connected to a vertex of the component G1 of G, then v is also a
vertex of G1.

Proof. If v is connected to vertex v′ of G1, then there is a walk in G

v = vi0 , ej1, vi1 , . . . , vik−1, ejk , vik = v′.

Since v′ is a vertex of G1, then (condition #2 above) ejk is an edge of G1 and vik−1 is a vertex of G1. We continue
this process and see that v is a vertex of G1.

109
 Design and Analysis of Algorithms

7.3 Graph Operations

The complement of the simple graph G = (V, E) is the simple graph G = (Ē V), where the edges in Ē are exactly
the edges not in G.

Example. The complement of the complete graph Kn is the empty graph with n vertices.

Obviously, = G. If the graphs G = (V,E) and G′ = (V′,E′) are simple and V′ ⊆ V , then the difference graph is G
− G′ = (V,E′′), where E′′ contains those edges from G that are not in G′ (simple graph).

7.4 Cuts
A vertex v of a graph G is a cut vertex or an articulation vertex of G if the graph G−v consists of a greater number
of components than G.

Example. v is a cut vertex of the graph below:

( Note! Generally, the only vertex of a trivial graph is not a cut vertex, neither is an isolated vertex.)

A graph is separable if it is not connected or if there exists at least one cut vertex in the graph. Otherwise, the
graph is non separable.

Theorem 1.3 The vertex v is a cut vertex of the connected graph G if and only if there exist two vertices u and w

11
 in the graph G such that:
(i) v 6= u, v 6= w and u 6= w, but
(ii) v is on every u–w path.

Proof: First, let us consider the case that v is a cut-vertex of G. Then, G − v is not connected and there are at
least two components G1 = (V1,E1) and G2 = (V2,E2). We choose u ∈ V1 and w ∈ V2. The u–w path is in G because
it is connected. If v is not on this path, then the path is also in G − v ( ). The same reasoning can be used for all
the u–w paths in G.

If v is in every u–w path, then the vertices u and w are not connected in G − v.

Theorem 1.8. A nontrivial simple graph has at least two vertices which are not cut vertices.

Theorem 1.9. If F is a cut set of the connected graph G, then G − F has two components.

7.5 Labeled Graphs and Isomorphism

By a labeling of the vertices of the graph G = (V,E), we mean a mapping α : V → A, where A is called the label
set. Similarly, a labeling of the edges is a mapping β: E → B, where B is the label set. Often, these labels are
numbers. Then, we call them weights of vertices and edges.

In a weighted graph, the weight of a path is the sum of the weights of the edges traversed. The labeling of the
vertices (respectively edges) is injective if distinct vertices (respectively edges) have distinct labels. An injective
labeling is bijective if there are as many labels in A (respectively in B) as the number of vertices (respectively
edges).

Example. If A = {0, 1} and B = ℝ, then in the graph, the labeling of the edges (weights) is injective but not the
labeling of the vertices.

The two graphs G1 = (V1,E1) and G2 = (V2,E2) are isomorphic if labeling the vertices of G 1 bijectively with the
elements of V2 gives G2. (Note! We have to maintain the multiplicity of the edges.)

7.6 Trees and Forests

A forest is a circuitless graph. A tree is a connected forest. A subforest is a subgraph of a forest. A connected
subgraph of a tree is a subtree. Generally speaking, a subforest (respectively subtree) of a graph is its subgraph,
which is also a forest (respectively tree).

11
Design and Analysis of Algorithms

Example. Four trees which together form a forest:

A spanning tree of a connected graph is a subtree that includes all the vertices of that graph. If T is a spanning
tree of the graph G, then
G − T =def.T∗

is the cospanning tree.

The edges of a spanning tree are called branches and the edges of the corresponding cospanning tree are called
links or chords.

Theorem 1.4. If the graph G has n vertices and m edges, then the following statements are equivalent:
(i) G is a tree.
(ii) There is exactly one path between any two vertices in G and G has no loops.
(iii) G is connected and m = n − 1.
(iv) G is circuitless and m = n − 1.
(v) G is circuitless and if we add any new edge to G, then we will get one and only one circuit.

Proof. (i)⇒(ii): If G is a tree, then it is connected and circuitless. Thus, there are no loops in G. There exists a
path between any two vertices of G. By Theorem 1.6, we know that there is only one such path.

(ii) ⇒(iii): G is connected. Let us use induction on m.

Induction Basis: m = 0, G is trivial and the statement is obvious.
Induction Hypothesis: m = n − 1 when m ≤ ℓ. (ℓ ≥ 0)
Induction Statement: m = n − 1 when m = ℓ + 1.
Induction Statement Proof: Let e be an edge in G. Then G − e has ℓ edges. If G − e is connected, then there exist
two different paths between the end vertices of e so (ii) is false. Therefore, G− e has two components G1 and G2.
Let there be n1 vertices and m1 edges in G1.

Similarly, let there be n2 vertices and m2 vertices in G2. Then,

n = n1 + n2 and m = m1 + m2 + 1.

The Induction Hypothesis states

that
m1 = n1 − 1 and m2 = n2 − 1,
so m = n1 + n2 − 1 = n − 1.

(iii) ⇒(iv): Consider the counter hypothesis: There is a circuit in G. Let e be some edge in that circuit. Thus, there
are n vertices and n − 2 edges in the connected graph G − e.

(iv) ⇒(v): If G is circuitless, then there is at most one path between any two vertices (Theorem 1.6). If G has more
than one component, then we will not get a circuit when we draw an edge between two different components. By
adding edges, we can connect components without creating circuits:

If we add k(≥ 1) edges, then (because (i)⇒(iii))

11
 m + k = n − 1 ( because m = n − 1).
So G is connected. When we add an edge between vertices that are not adjacent, we get only one circuit. Otherwise,
we can remove an edge from one circuit so that other circuits will not be affected and the graph stays connected,
in contradiction to (iii)⇒(iv). Similarly, if we add a parallel edge or a loop, we get exactly one circuit.

(v) ⇒(i): Consider the counter hypothesis: G is not a tree, i.e. it is not connected. When we
add edges as we did previously, we do not create any circuits (see figure).

Since spanning trees are trees, Theorem 2.1 is also true for spanning trees.

7.7 (Fundamental) Circuits and (Fundamental) Cut Sets

If the branches of the spanning tree T of a connected graph G are b 1, . . . , bn−1 and the corresponding links of the
cospanning tree T∗ are c1, . . . , cm−n+1, then there exists one and only one circuit Ci in T + ci (which is the subgraph
of G induced by the branches of T and ci) (Theorem 2.1). We call this circuit a fundamental circuit. Every
spanning tree defines m − n + 1 fundamental circuits C1, . . . ,Cm−n+1, which together form a fundamental set of
circuits. Every fundamental circuit has exactly one link which is not in any other fundamental circuit in the
fundamental set of circuits. Therefore, we can not write any fundamental circuit as a ring sum of other
fundamental circuits in the same set. In other words, the fundamental set of circuits is linearly independent under
the ring sum operation.

The graph T − bi has two components T1 and T2. The corresponding vertex sets are V 1 and V2. Then, is a
cut of G. It is also a cut set of G if we treat it as an edge set because G − has two components. Thus,
every branch bi of T has a corresponding cut set Ii. The cut sets Ii. The cut set I1, ,In−1 are also known as
fundamental
cut sets and they form a fundamental set of cut sets. Every fundamental cut set includes exactly one branch of T
and every branch of T belongs to exactly one fundamental cut set. Therefore, every spanning tree defines a unique
fundamental set of cut sets for G.

11
 Design and Analysis of Algorithms

7.8 Directed Graphs

Intuitively, a directed graph or digraph is formed by vertices connected by directed edges or arcs.

Formally, a digraph is a pair (V,E), where V is the vertex set and E is the set of vertex pairs as in ”usual” graphs.
The difference is that now the elements of E are ordered pairs: the arc from vertex u to vertex v is written as (u,
v) and the other pair (v, u) is the opposite direction arc. We also have to keep track of the multiplicity of the arc
(direction of a loop is irrelevant). We can pretty much use the same notions and results for digraphs. However:
• Vertex u is the initial vertex and vertex v is the terminal vertex of the arc (u, v). We also say that the arc is
incident out of u and incident into v.
• The out-degree of the vertex v is the number of arcs out of it (denoted d+(v)) and the in-degree of v is the number
of arcs going into it (denoted d−(v)).
• In the directed walk (trail, path or circuit),
vi0 , ej1, vi1 , ej2, . . . , ejk, vik

viℓ is the initial vertex and viℓ−1 is the terminal vertex of the arc ejℓ

• When we treat the graph (V,E) as a usual undirected graph, it is the underlying undirected graph of the
digraph G = (V,E), denoted Gu.
• Digraph G is connected if Gu is connected. The components of G are the directed subgraphs of G that
correspond to the components of Gu. The vertices of G are connected if they are connected in Gu. Other
notions for undirected graphs can be used for digraphs as well by dealing with the underlying undirected
graph.
• Vertices u and v are strongly connected if there is a directed u–v path and also a directed v–u path in G.
• Digraph G is strongly connected if every pair of vertices is strongly connected. By convention, the trivial
graph is strongly connected.
• A strongly connected component H of the digraph G is a directed subgraph of G (not a null graph) such that
H is strongly connected, but if we add any vertices or arcs to it, then it is not strongly connected anymore.

Every vertex of the digraph G belongs to one strongly connected component of G. However, an arc does not
necessarily belong to any strongly connected component of G.

7.9 Directed Trees

A directed graph is quasi-strongly connected if one of the following conditions holds for every pair of vertices u
and v:
(i) u = v or
(ii) there is a directed u–v path in the digraph or
(iii) there is a directed v–u path in the digraph or
(iv) there is a vertex w so that there is a directed w–u path and a directed w–v path.

11
Example. The digraph G is quasi-strongly connected.
Quasi-strongly connected digraphs are connected but not necessarily strongly connected. The vertex v of the
digraph G is a root if there is a directed path from v to every other vertex of G.

Example. The digraph G only has one root, v1.

Theorem 3.1. A digraph has at least one root if and only if it is quasi-strongly connected.

Proof. If there is a root in the digraph, it follows from the definition that the digraph is quasi-strongly connected.

Let us consider a quasi-strongly connected digraph G and show that it must have at least one root. If G is trivial,
then it is obvious. Otherwise, consider the vertex set V = {v 1, . . . , vn} of G where n ≥ 2. The following process
shows that there must be a root:
• Set P ← V .
• If there is a directed u–v path between two distinct vertices u and v in P, then we remove v from P. Equivalently,
we set P ← P − {v}. We repeat this step as many times as possible.
• If there is only one vertex left in P, then it is the root. For other cases, there are at least two distinct vertices u
and v in P and there is no directed path between them in either direction. Since G is quasi-strongly connected,
from condition (iv) it follows that there is a vertex w and a directed w–u path as well as a directed w–v path.
Since u is in P, w can not be in P. We remove u and v from P and add w, i.e. we set P ← P − {u, v} and P ←
P
𝖴 {w}. Go back to step #2.
• Repeat as many times as possible.

Every time we do this, there are fewer and fewer vertices in P. Eventually, we will get a root because there is a
directed path from some vertex in P to every vertex we removed from P. The digraph G is a tree if Gu is a tree. It
is a directed tree if Gu is a tree and G is quasistrongly connected, i.e. it has a root. A leaf of a directed tree is a
vertex whose out-degree is zero.

11
 Design and Analysis of Algorithms

7.10 Acyclic Directed Graphs

A directed graph with at least one directed circuit is said to be cyclic. A directed graph is acyclic otherwise.
Obviously, directed trees are acyclic but the reverse implication is not true.

Example. The digraph

is acyclic but it is not a directed tree.

Theorem 1.5 In an acyclic digraph, there exist at least one source (a vertex whose in-degree is zero) and at least
one sink (a vertex whose out-degree is zero).

Proof. Let G be an acyclic digraph. If G has no arcs, then it is obvious. Otherwise, let us consider the directed
path

vi0 , ej1 , vi1, ej2, . . . , ejk , vik ,

which has the maximum path length k. Since G is acyclic, vi0 vik. If (v, vi0) is an arc, then one of the following
is true:

• v vit for every value of t = 0, . . . , k. Then,

 v, (v, vi0), vi0 , ej1, vi1 , ej2, . . . , ejk , vik
is a directed path with length k + 1

• v = vit for some value of t. We choose the smallest such t. Then, t > 0 because there are no loops in G and
 vi0 , ej1, vi1, ej2, . . . , ejt , vit , (v, vi0), vi0
is a directed circuit

Hence, d−(v ) = 0. Using a similar technique, we can show that d+(v ) = 0 as well.
i0 ik

If G = (V,E) is a digraph with n vertices, then a labeling of the vertices with an injectivefunction α : V → {1, . . . ,
n} which satisfies the condition α(u) < α(v) whenever (u, v) is an arc in G is known as topological sorting.

11
 Design and Analysis of Algorithms

Exercises 7
1. A graph is a pair of sets (V, E), where V is the set of and E is the set of , formed by
pairs of vertices.
a. variants, end-points
b. vertices, edges
c. edges, multiset
d. labels, numbers

2. A simple graph that contains every possible edge between all the vertices is called a .
a. sub-graph
b. isolated graph
c. complete graph
d. pendant graph

3. Match the following

1. Simple graph A. Empty graph

2. A graph with no edges B. Null graph

3. A graph with no vertices C. Trivial

4. A graph with only one vertex D. No parallel edges or loops

a. 1-A, 2-C, 3-D, 4-B
b. 1-B, 2-D, 3-A, 4-C
c. 1-C, 2-B, 3-C, 4-A
d. 1-D, 2-A, 3-B, 4-C

4. In which condition in a graph we can say the edges are adjacent?

a. Edges are adjacent if they share a common end vertex.
b. Edges are adjacent if a graph has only one vertex.
c. Edges are adjacent if it has a loop.
d. Edges are adjacent if it has a degree one.

5. An isolated vertex is a vertex whose degree is .

a. one
b. zero
c. two
d. null

6. The minimum degree of the vertices in a graph G is denoted .

a. V1 ⊆ V2
b. G = (V, E)
c. δ(G)
d. ∆(G)

11
7. A complete graph with n vertices is denoted as .
a. G = (V, E)
b. Kn
c. ∆(G)
d. Gn

8. A trail is a if any vertex is visited at most once except possibly the initial and terminal vertices
when they are the same.
a. walk
b. path
c. edge
d. circuit

9. The walk starting at u and ending at v is called a walk.

a. edge path
b. u*v
c. v-u
d. u–v

10. A vertex v of a graph G is a or an articulation vertex of G if the graph G−v consists of a greater
number of components than G.
a. connected vertex
b. equivalent vertex
c. cut vertex
d. labeled vertex

11
 Design and Analysis of Algorithms

Chapter VIII
Brute Force

Aim

The aim of this chapter is to:

• explore the algorithm design strategy

• elucidate the brute force

• explain the terms used in brute force

Objectives
The objectives of this chapter are to:

• explain the brute force approach

• explicate the selection sort operation

• elucidate the algorithm’s basic operations

Learning outcome
At the end of this chapter, you will be able to:

• understand the bubble sort

• identify the brute force approach

• recognise the Brute-Force String Matching

120
8.1 Introduction
Brute force is a straightforward approach to problem solving, usually directly based on the problem’s statement
and definitions of the concepts involved. Though rarely a source of clever or efficient algorithms, the brute-force
approach should not be overlooked as an important algorithm design strategy. Unlike some of the other
strategies, brute force is applicable to a very wide variety of problems.

For some important problems (e.g., sorting, searching, string matching), the brute-force approach yields
reasonable algorithms of at least some practical value with no limitation on instance size Even if too inefficient in
general, a brute-force algorithm can still be useful for solving small-size instances of a problem. A brute-force
algorithm can serve an important theoretical or educational purpose.

Sorting Problem: Brute force approach to sorting Problem: Given a list of n orderable items (e.g., numbers,
characters from some alphabet, character strings), rearrange them in non-decreasing order.

Selection Sort
ALGORITHM Selection Sort(A[0..n - 1])

//The algorithm sorts a given array by selection sort

//Input: An array A[0..n - 1] of orderable elements

//Output: Array A[0..n - 1] sorted in ascending order

for i 0 to n - 2 do

min i

for j i + 1 to n - 1 do
if A[j ]<A[min] min j
swap A[i] and A[min]

Example:

| 89 45 68 90 29 34 17
17 | 45 68 90 29 34 89
17 29 | 68 90 45 34 89
17 29 34 | 90 45 68 89
17 29 34 45 | 90 68 89
17 29 34 45 68 | 90 89
17 29 34 45 68 89 | 90

Selection sort operation on the list 89, 45, 68, 90, 29, 34, 17. Each line correspond to one iteration of the
algorithm, i.e., a pass through the list trail to the right of the vertical bar; an element in bold indicates the smallest
element found. Elements to the left of the vertical bar are in their final positions and are not considered in this or
subsequent iterations.

Performance Analysis of the selection sort algorithm: The input’s size is given by the number of elements n.

The algorithm’s basic operation is the key comparison A[j]<A[min]. The number of times it is executed depends
only on the array’s size and is given by

121
 Design and Analysis of Algorithms

Thus, selection sort is a O(n2) algorithm on all inputs. The number of key swaps is only O(n) or, more precisely,
n-1 (one for each repetition of the i loop).This property distinguishes selection sort positively from many other
sorting algorithms.

8.2 Bubble Sort

Compare adjacent elements of the list and exchange them if they are out of order. Then we repeat the process. By
doing it repeatedly, we end up ‘bubbling up’ the largest element to the last position on the list.

ALGORITHM BubbleSort(A[0..n - 1])

//The algorithm sorts array A[0..n - 1] by bubble sort

//Input: An array A[0..n - 1] of orderable elements

//Output: Array A[0..n - 1] sorted in ascending order

for i 0 to n - 2 do

for j 0 to n - 2 - i do

if A[j + 1]<A[j ] swap A[j ] and A[j + 1

?
89 45 68 90 29 34 17
?
45 89 68 90 29 34 17
? ?
45 68 89 90 29 34 17
?
45 68 89 29 90 34 17
?
45 68 89 29 34 90 17
45 68 89 29 34 17 90

45 68 89 29 34 17 | 90
45 68 29 89 34 17 | 90
45 68 29 34 89 17 | 90
45 68 29 34 17 | 89 90
etc.

The first 2 passes of bubble sort on the list 89, 45, 68, 90, 29, 34, 17. A new line is shown after a swap of two
elements is done. The elements to the right of the vertical bar are in their final positions and are not considered in
subsequent iterations of the algorithm.

122
8.3 Bubble Sort- The Analysis
Clearly, the outer loop runs n times. The only complexity in this analysis in the inner loop. If we think about a
single time the inner loop runs, we can get a simple bound by noting that it can never loop more than n times.
Since the outer loop will make the inner loop complete n times, the comparison can’t happen more than O(n2)
times.

The number of key comparisons for the bubble sort version given above is the same for all arrays of size n.

The number of key swaps depends on the input. For the worst case of decreasing arrays, it is the same as the
number of key comparisons.

Observation: if a pass through the list makes no exchanges, the list has been sorted and we can stop the algorithm
Though the new version runs faster on some inputs, it is still in O(n 2) in the worst and average cases. Bubble sort
is not very good for big set of input. How ever bubble sort is very simple to code.

8.3.1 General Lesson from Brute Force Approach

A first application of the brute-force approach often results in an algorithm that can be improved with a modest
amount of effort. Compares successive elements of a given list with a given search key until either a match is
encountered (successful search) or the list is exhausted without finding a match (unsuccessful search).

Sequential Search
ALGORITHM SequentialSearch2(A[0..n], K)

//The algorithm implements sequential search with a search key as a // sentinel

//Input: An array A of n elements and a search key K

//Output: The position of the first element in A[0..n - 1] whose value is

// equal to K or -1 if no such element is found

A[n] K
i 0
while A[i] = K do

i i+1

if i < n return i

else return

123
 Design and Analysis of Algorithms

8.3.2 Brute-Force String Matching

Given a string of n characters called the text and a string of m characters (m = n) called the pattern, find a
substring of the text that matches the pattern. To put it more precisely, we want to find i—the index of the
leftmost character of the first matching substring in the text—such that:

ti= p0, . . . , ti+j = pj , . . . , ti+m-1 = pm-1:

t0 . . . ti . . . ti+j . . . ti+m-1 . . . tn-1 text T

p0 . . . pj . . . pm-1 pattern P

1. Pattern: 001011
Text: 10010101101001100101111010

2. Pattern: happy
Text: It is never too late to have a happy Childhood

The algorithm shifts the pattern almost always after a single character b comparison. in the worst case, the
algorithm may have to make all m comparisons before shifting the pattern, and this can happen for each of the n -
m + 1 tries. Thus, in the worst case, the algorithm is in θ(nm).

8.4 Closest-Pair Problem

Find the two closest points in a set of n points (in the two-dimensional Cartesian plane). Brute-force algorithm
compute the distance between every pair of distinct points and return the indexes of the points for which the
distance is the smallest.

Algorithm Brute Force Closet Points (P)

//Input: A List P of n (n ) points P1 = (x1, y1), , Pn = (xn, yn)

//Output: Indices index 1 and index2 of the closet pair of points

Dmin

for i 1 to n-1 do

124
for j i+1 to n do

d sqrt ((x -x )2 //sqrt is the square root function

i

if d< dmin

dmin d; index 1 ; index 2 j

return index1, index2

125
Design and Analysis of Algorithms

Exercises 8
1. The number of key swaps depends on the .
a. a. input
b. b. output
c. c. string
d. d. pattern

2. Which of the following compares the adjacent elements of the list and exchange them if they are out of
order?
a. a. Brute force algorithm
b. b. Quick sort
c. c. Bubble sort
d. d. Knapsack algorithm

3. The complexity of Bubble sort algorithm is .

a. a. O(n)
b. b. O(n2 )
c. c. nlogn
d. d. n

4. The number of key swaps in the selection sort algorithm is given as .

a. O(n)
b. O(n2 )
c. nlogn
d. n2

5. A algorithm can serve an important theoretical or educational purpose.

a. Knapsack
b. Prism’s
c. Brute force
d. Dijkstra’s

6. Brute force is a approach to problem solving, usually directly based on the problem’s statement
and definitions of the concepts involved.
a. Dynamic
b. Static
c. Straight forward
d. Recursive

7. Which of the following sorting is not very good for big set of input?
a. Quick sort
b. Selection sort
c. Merge sort
d. Bubble sort

126
Design and Analysis of Algorithms

8. Which of the following is the only complexity in the bubble sort anlaysis?
a. Inner loop
b. Outer loop
c. Number of elements in array
d. None of the above

9. Which of the following statement is false?

a. A brute-force algorithm can serve an important theoretical or educational purpose.
b. Brute-force algorithm compute the distance between every pair of distinct points and return the indexes
of the points for which the distance is the smallest.
c. A first application of the brute-force approach often results in an algorithm that can be improved with a
modest amount of effort.
d. The number of key swaps depends on the output.

10. Bubble sort algorithm is to code.

a. Simple
b. Difficult
c. Complex
d. Moderate

128
Application 129
Using Quicksort Algorithm, sort the given numbers step by step:

314592687
Solution:

The basic concept is to pick one of the elements in the array as a pivot value around which the other elements
will be rearranged. Everything less than the pivot is moved left of the pivot (into the left partition). Similarly,
everything greater than the pivot goes into the right partition. At this point, each partition is recursively quick
sorted.

The Quicksort algorithm is fastest when the median of the array is chosen as the pivot value. That is because the
resulting partitions are of very similar size. Each partition splits itself in two and thus the base case is reached
very quickly.

In practice, the Quicksort algorithm becomes very slow when the array passed to it is already close to being
sorted. Because there is no efficient way for the computer to find the median element to use as the pivot, the first
element of the array is used as the pivot. So when the array is almost sorted, Quicksort doesn't partition it equally.
Instead, the partitions are lopsided as given in figure above. This means that one of the recursion branches is
much deeper than the other, and causes execution time to go up. Thus, it is said that the more random the
arrangement of the array, the faster the Quicksort Algorithm finishes.

129
 Design and Analysis of Algorithms

Application II
For the given graph, the source vertex is 1 and the destination vertex is 7. Find the shortest path for this graph
from 1 to 7 and also determine the path length using Dijkstra's algorithm.

130
Application 131

Traverse a graph shown below, using DFS. And start from a vertex with number 1.

131
Design and Analysis of Algorithms

132