Design & Analysis

of Algorithms

For

Computer Science
&
Information Technology
By

[Link]
✆080-40611000
 Syllabus

Syllabus for Design & Analysis of Algorithms

Searching, Sorting, Hashing, Asymptotic Worst Case Time and Space Complexity, Algorithm Design
Techniques, Greedy, Dynamic Programming and Divide‐and‐Conquer, Graph Search, Minimum
Spanning Trees, Shortest Paths.

Previous Year GATE Papers and Analysis

GATE Papers with answer key

[Link]/gate-papers

Subject wise Weightage Analysis

[Link]/gate-syllabus

info@[Link] ©Copyright reserved. Web:[Link]

 Contents

Contents

Chapters Page No.

#1. Algorithm Analysis 1 – 12
 Introduction 1
 Definition of Algorithm 1–2
 Need for Analysis 2
 Algorithm Analysis 2–7
 Asymptotic Notation 7 – 11
 Recurrence 11 – 12

#2. Divide and Conquer 13 – 28

 The General Method 13 – 14
 Finding MaxMin 14 – 15
 Binary Search 15 – 17
 Sorting 17
 Bubble sort 17 – 18
 Merge Sort 18 – 22
 Quick Sort 22 – 24
 Insertion Sort 25
 Selection Sort 26
 Heap Sort 26 – 27
 Straseen’s Matrix Multiplications 27 – 28

#3. Greedy Techniques 29 – 47

 General Method 29 – 34
 Minimum Spanning Tree 34
 Prim’s Algorithm 34 – 37
 Kruskal’s Algorithm 37 – 40
 Single Source Shortest Path Algorithm 40 – 47

#4. Dynamic Programming 48 – 65

 Introduction 48
 Idea of Dynamic Programming 49
 Traveling Salesperson Problem (TSP) 49 – 50
 Matrix Chain Multiplication Algorithm 50 – 52
 0/1 Knapsack 52 – 54
 Optimal Binary Search Trees (OBST) 54 – 58
 Longest Common Subsequences 58 – 60
 Knapsack with Repetition 60 – 61
 Memoization 61 – 63
 All-Pairs Shortest Paths 63 – 65

info@[Link] ©Copyright reserved. Web:[Link] i

 Contents

#5. Hashing 66 – 70
 Hashing 66 – 67
 Floading 67
 Conflict Resolution Techniques 67 – 68
 Double Hashing 68 – 69
 Separate Chaining 69
 Coalesced Chaining 70

Reference Books 71

info@[Link] ©Copyright reserved. Web:[Link] ii

 "Dream no small dreams for they have
no power to move the hearts of men."

11
…Goethe
CHAPTER

Algorithm Analysis

Learning Objectives
After reading this chapter, you will know:
1. Definition of Algorithm
2. Need for Analysis
3. Algorithm Analysis
4. Asymptotic Notation
5. Recurrence

Introduction
Once an algorithm is given for a problem and decided to be correct, then an important step is to
determine how much in the way of resources, such as time or space, the algorithm will be required.
The analysis required to estimate use of these resources of an algorithm is generally a theoretical
issue and therefore a formal framework is required. In this framework, we shall consider a normal
computer as a model of computation that will have the standard repertoire of simple instructions
like addition, multiplication, comparison and assignment, but unlike the case with real computer, it
takes exactly one unit time to do anything (simple) and there are no fancy operations such as matrix
inversion or sorting, that clearly cannot be done in one unit time. We always assume infinite
memory also.

Definition of Algorithm
An Algorithm is a finite sequence of instructions that, if followed, accomplishes a particular task. In
addition, all algorithms must satisfy the following criteria:
1. Input: Zero or more quantities are externally supplied.
2. Output: At least one quantity is produced.
3. Definiteness: Each instruction is clear and unambiguous.
4. Finiteness: If trace out the instructions of an algorithm, then for all cases, the algorithm
terminates after a finite number of steps.
5. Effectiveness: Every instruction must be very basic so that it can be carried out, in principle, by
a person using only pencil and paper. It is not enough that each operation be definite as in
criteria 3; it also must be feasible.

Algorithm Development Stages

There are five phases of Algorithm Development Stages:
(i) Requirements: Make sure you that we understand the information that is given (the input) and
what results that are produce (the output)
info@[Link] ©Copyright reserved. Web:[Link] 1
 Algorithm Analysis

(ii) Design: For each object there will be some basic operations to perform on it. These operations
already exist in the form of procedures and write an algorithm which solves the problem
according to the requirements.
(iii) Analysis: Can we think of another algorithm? If so, write it down. Next, try to compare these two
methods. It may already be possible to tell if one will be more desirable than the other. If you
can’t distinguish between the two, choose one to work on for now and we will return to the
second version later.
(iv) Refinement and Coding: Modern approach suggests that all processing which is independent of
the data representation be written out first.
(v) Verification: Verification consists of three distinct aspects;
(1) Program Proving, (2) Testing and (3) Debugging

Need for Analysis

Analysis is the study we perform in order to figure out what to do. It uses a high-level description of
the algorithm instead of an implementation and it characterizes running time as function of the
input size, n. it takes into account all possible inputs and allows us to evaluate the speed of an
algorithm independent of the hardware/software environment.
The “Analysis” deals with performance evaluation (Complexity Analysis). One of the goals of
analysis is to compare algorithm mainly in terms of running time but also in terms of other factors
(e.g., memory requirements, programmer’s effort etc.)

Algorithm Analysis
Types of Analysis/Behavior of Algorithm
Worst Case
 Provides an upper bound on running time
 An absolute guarantee that the algorithm would not run longer, no matter what the inputs are
Best Case
 Provides a lower bound on running time
 Input is the one for which the algorithm runs the fastest
Average Case
 Provides a prediction about running time
 Assumes that the input is random
 ower ound unning Time pper ound

The following two components need to be analyzed for determining algorithm efficiency. If we have
more than one algorithms for solving a problem then we really need to consider these two before
utilizing one of them.

Time Complexity
The time complexity of an algorithm is to find the time taken by an Algorithm to complete its
execution. There two methods
1. A Priori Analysis: It is based on determining the order of the magnitude of the statement,
construct or data structure. This method is independent of machine, programming language

info@[Link] ©Copyright reserved. Web:[Link] 2

 Algorithm Analysis

and operating system. If algorithm has to be analyzed further in detail then each operation
(Arithmetic, Relational and Logical) is considered to take 1 unit of time.
2. Posteriori Testing: In this method an algorithm is converted into a program using any
programming language, executed on a particular machine. Algorithm’s execution time is taken
with the systems watch time. Result of this analysis will be dependent on the machine and
language used. It will be real time.
Running Time Complexity: The time required for running an algorithm.

Space Complexity
The amount of space required at run-time by an algorithm for solving a given problem.
In general these measurements are expressed in terms of asymptotic notations, like Big-Oh, Theta,
Omega etc.

General Rules for Space Complexity Calculation

While computing space complexity we need to analyze whether the memory requirement is
dependent on input size. Three things mainly need to be considered;
1) Maximum width of system stack which holds the activation records during the run time of the
function.
2) Whether the size of activation record is dependent on input size.
3) And in each invocation how much memory is being used from heap.
Then space complexity is as follows:
Max-system-stack-width*((Size of the memory allocated on activation record which is
dependent on n )+ (Size of the memory allocated from heap which is dependent on n ))

Example: Consider the simple program fragment for analyzing space complexity.
int sum(int n)
{
int partialSum = 0;
for(int i = 0; i<n; i++)
partialSum = partialSum i i i;
return partialSum;
}
Notice that the memory used by this program is absolutely independent of input size
because this is non-recursive program and has only one activation record to be pushed on
the system stack whose size is not going to change with n and also each invocation
doesn’t have any heap space requirement which is dependent on n. So whether n = 10,
20, 100, etc, the number of records to be pushed is O (1). Therefore Space Complexity is O
(1).

Example: Consider the recursive C program which prints the null terminated string in the reverse
order.
void printRev(char *str)
{
if( *str == ‘\0’) return;

info@[Link] ©Copyright reserved. Web:[Link] 3

 Algorithm Analysis

printRev(str+1);
printf(“%c”,*str);
}
Maximum width of the system stack is O(L) where L is string length. And the size of
activation record is constant w.r.t length L. Therefore, space complexity is O(L).

General Rules for Running Time Calculations

Rule 1-for/While Loops
The running time of a for/while loop is = (The number of iteration perform)
(the running time of statements inside the loop).

Example: Consider the simple program fragment whose running time cost is O(n) where n is a
positive integer.
int sum(int n)
{
int partialSum = 0;
for (int i = 1; i<= n; i++)
partialSum = partialSum i i i;
return partialSum;
}
Lines 1 and 4 count one unit each. Line 3 counts for four units per time executed
(two multiplications, one addition, and one assignment) and is executed n times, for a
total of 4n units. Line 2 has hidden costs of initializing i, testing i <= n and incrementing i.
The total cost of all these is 1 to initialize, n+1 for all the tests, and n for all the
increments, which 2n+[Link], total cost of 6n+4, which is O(n).

Rule 2 –Nested loops

The total running time of a statement inside a group of nested loops is the running time of
the statement multiplied by the product of the sizes of all loops.
As an example following program fragment is O(n2).
for( i = 0; i< n ; i++)
for( j = 0; j<n; j++)
k++;

Rule 3 - Consecutive Statements

Just add running time of all these statements.

As an example, the following program fragment, which has O(n) work followed by O(n2)
work, is also O(n2).
for( i = 0; i< n ; i++)
k++;
for( i = 0; i< n ; i++)
for( j = 0; j<n; j++)
k++;

info@[Link] ©Copyright reserved. Web:[Link] 4

 Algorithm Analysis

Rule 4 – if/else
For the fragment
if (condition )
S1
else
S2
Running time of an if/else statement is never more than the running time of test plus the
larger of the running times of S1 and S2.

Rule 5 – Recursive function

Deriving the recurrence relation and then solving it for getting the running time is always
the better way than any other solution.

Example: Consider the code given below for printing null terminated string in reverse order.
Let T (n) be the running time of printRev ( ) for which string length is n. Then, T(n )
would represent running time of the same function which is given string of length n – 1.
Thus
T(n) = T(n 1) + O(1)

Logarithm Time Complexity

There are several algorithms, which require logn cost in worst case. Binary Search, Heap ADT
operations, etc are examples of that.
Typically, an algorithm is O (logn) if it takes constant time to cut the problem size by a half. That’s
what exactly happens in binary search algorithm.
int binarySearch(int a[ ], int len, int x)
{
int low = 0 , high = len – 1;
while(low < = high)
{
int mid = (low + high)/2;
if( a[mid] < x)
low = mid + 1;
else if(a[mid] > x)
high = mid – 1;
else
return mid;
}
return NOT_FOUND;
}

At first look this algorithm gives the illusion of O (n) cost as we might think that since it has a while
loop and that will always run for the entire length of the given array. A careful examination would
expose that the loop will not run more than O (logn) times since in each iteration high or low getting
adjusted such that the problem size decreases by half of the current size. The following recurrence

info@[Link] ©Copyright reserved. Web:[Link] 5

 Algorithm Analysis

relation can best represent the running time of binary search algorithm. T (n) = T (n/2) + 1, where
T (n) be the running time for n input elements.
Look at another interesting code given below.
sum = 0;
for( i = 1; i< n ; i)
sum++;
The i variable values getting incremented in each iteration such that its becoming double of current
hence certainly would not take much longer than logn to reach its value as n or more.

Amortized Analysis
An amortized analysis is any strategy for analyzing a sequence of operations to show that the
average cost per operation is small, even though a single operation within the sequence might be
expensive. Even though we take averages, however, probability is not involved. An amortized
analysis guarantees the average performance of each operation in the worst case.

Types of Amortize Analysis

There are three common amortization arguments:
 The Aggregate method.
 The Accounting method and
 The Potential method.

Online Algorithm
Definition: An algorithm that must process each input in turn, without detailed knowledge of future
inputs. In computer science, an online algorithm is one that can process its input piece-by-piece in a
serial fashion, i.e., in the order that the input is fed to the algorithm without having the entire input
available from the start. In contrast, an offline algorithm is given the whole problem data from the
beginning and is required to output an answer which solves the problem at hand (for example,
selection sort requires that the entire list be given before if can sort it, while insertion sort doesn’t).
Since it does not know the whole input, an online algorithm is forced to make decisions that may
later turn out not be optimal, and the study of online algorithms has focused on the quality of
decision-making that is possible in this setting. Competitive analysis formalizes this idea by
comparing the relative performance of an online and offline algorithm for the same problem
instance.

A problem exemplifying the concepts of online algorithms is the Canadian Traveler Problem, The
goal of this problem is to minimize the cost reaching a target in weighted graph where some of the
edges are unreliable and may have been removed from the graph. However, that an edge has been
removed (failed) is only revealed to the traveler when she/he reaches one of the edges endpoints.

The worst case for this problem is simply that all of the unreliable edges fail and the problem
reduces to the usual shortest path problem. An alternative analysis of the problem can be made with
the help of competitive analysis, for this method of analysis. The offline algorithm known in advance
which edges will fail and the goal is to minimize the ratio between the online and offline algorithm
performance. This problem is PSPACE-complete.

info@[Link] ©Copyright reserved. Web:[Link] 6

 Algorithm Analysis

Randomized Algorithm
In order to use probabilistic analysis, we need to know something about the distribution on the
inputs. In many cases, we know very little about the input distribution. Even if we do know
something about the distribution, we may not be able to model this knowledge computationally. Yet
we often can use probability and randomness as a tool for algorithms.

Consider the hiring problem. In the hiring problem, it may seem as if the candidates are being
presented to use in a random order, but we have no way of knowing whether or not they really are.
Thus, in order to develop a randomized algorithm for the hiring problem, we must have greater
control over the order in which we interview the candidates. We will, therefore, change the model
slightly. We will say that the employment agency has n candidates, and they send us a list of the
candidates in advance. On each day, we choose, randomly, which candidate to interviews. Although
we know nothing about the candidates (beside their names), we have made a significant change.
Instead of relying on a guess that the candidates will come to us in a random order, we have instead
of relying on a guess that the candidates enforced a random order. More generally, we call an
algorithm randomized if its behavior is determined not only by its input but also by values produced
by a random-number generator. We shall assume that we have at our disposal a random-number
generator RANDOM.

A call to RANDOM (a, b) returns an integer between a and b, inclusive, with each such integer being
equally likely.
For example, RANDOM (0, 1) produces 0 with probability 1/2, and it produces 1 with probability
1/2. A call to RANDOM (3, 7) retunes either3, 4, 5, 6 or 7, each with probability 1/5. Each integer
returned by RANDOM is independent of the integers returned on previous calls. You may imagine
RANDOM as rolling a (b a )-sided die to obtain its output.

Asymptotic Notation
 Asymptotic analysis is based on two simplifying assumptions which hold in most (but not all
cases). But it is important to understand these assumptions and limitations of asymptotic
analysis.
 Large input sizes: We are most interested in how the running time grows for large values of n
 Ignore constant factors: The actual running time of the program depends on various constant
factors in the implantations (coding tricks, optimizations in compilations speed of the
underlying hardware etc.) Therefore we will ignore constant factors.

The asymptotic notations are used to represent the relative growth rate between functions.

Big Oh (‘O’)
Represent upper bound on the running time and the memory being consumed by the algorithms.
O (n) essentially conveys that the growth rate of running time/memory consumption rate will not
be more than “n” for all inputs of size n for a given algorithm. However, it may be less than this.
More formally Big-Oh is defined as follows:
The function f(n) = Og(n) if and only if f(n) c. g(n) for all n, n n where c, n are positive
constants.

info@[Link] ©Copyright reserved. Web:[Link] 7

 Algorithm Analysis

Thus, if f(n) = O g(n) statement is said to be true then the growth rate of function g(n) is surely
higher than/equal to f(n).
We use O-notation to denote an upper bound that is not asymptotically tight
O (g (n)) = {f(n) : for any positive constant c > 0
There exists constant n0 > 0 0 f(n) cg(n) such that for all n n0+

Big-Oh Properties
1. If f (n) is O (g (n)) then a. f (n) is also O (g (n))
2. If f (n) is O (g (n)) and h (n) is O(p(n)) then f (n) + h(n) =O (max (g (n), P (n)))
3. If f (n) is O (g (n)) and h (n) is O (p (n)) then f (n) h (n) is O (g (n). p (n))
4. If f (n) is O (g (n)) and g (n) is O (h (n)) then f (n) is also O (h (n))
5. logn is O (logn) k
6. If f(n) is any polynomial of degree m, F(n) = a . n a n a n a , then f(n) is
O(n )

Θ Notation
C g(n)

f (n)

C g(n)

n
n0
f(n) = (g(n))
 For a given function g(n), we denote by Θ(g(n)), the set of functions:
Θ (g(n)) = {f(n): there exists positive constants c1, c2
And n0 such that 0 c g(n) f(n) c (g(n))
For all n n0
 Used when asymptotic lower bound is needed
Ω (g (n)) ={f(n): there exists positive constants c and
n such that 0 cg (n) f(n)
 Theorem
For any two functions f (n) and g (n) we have f (n) = Θ (g(n)) if and only
if f(n) = O(g(n)) and f (n) = Ω (g(n))

Remarks
 If f (x) = (g(x)) then g( x) is also (f(x))
 If f (x) = (g(x)) we can say that f (x) is O (g(x)) and f (x) is Ω (g(x)) and also g(x) is
O (f(x)) and g(x) is Ω (f(x))

info@[Link] ©Copyright reserved. Web:[Link] 8

 Algorithm Analysis

Small Oh (o)
The function f (n) = o (g(n)) iff
im f(n)
=o
n g(n)

Big Omega ( )
Big Omega represents lower bound on the running time and the memory being consumed by the
algorithms. Ω (n) essentially conveys that the growth rate of running time/memory consumption
rate will not be less than “n” for all inputs of size n for a given algorithm. However, it may be greater
than this.
More formally Big-Omega is defined as follows:
If f(x) and g (x) are any two functions and f (x) is Ω(g (x)),
If f (x) c. g(x) for x k where c and k are any two positive constants.
Thus, if f(x) is Ω(g (x)), statement is said to be true then the growth rate of function g(x) is surely
lower than/equal to f(x).

Small omega (ω) Notation

ω (g(n)) = *f(n) for any positive constant
c > 0 there exists a constant n > 0 such that
f (n) cg (n) ∀ n n }

Asymptotic form Relationship

f(n) ∈ (g(n)) f(n) = g(n)
f(n) ∈ Ο(g(n)) f(n) g(n)
f(n) ∈ Ω (g(n)) f(n) g(n)
f(n) ∈ ο(g(n)) f(n) < g(n)
f(n) ∈ ω(g(n)) f(n) > g(n)

Properties of Asymptotic Notations

1. Transitivity
f(n) = (g(n))and g(n) = (h(n))imply f(n) = (h(n)),
f(n) = O (g(n))and g(n) = O(h(n))imply f(n) = O(h(n)),
f(n) = Ω (g(n))and g(n) = Ω(h(n))imply f(n) = Ω(h(n)),
f(n) = o (g(n))and g(n) = o(h(n))imply f(n) = o(h(n)),
f(n) = ω (g(n))and g(n) = ω(h(n))imply f(n) = ω(h(n)),

2. Reflexivity
f(n) = (f(n)),
f(n) = O (f(n)),
f(n) = Ω (f(n)).

3. Symmetry
f(n) = (g(n))if and only if g(n) = (f(n)).

info@[Link] ©Copyright reserved. Web:[Link] 9

 Algorithm Analysis

4. Transpose Symmetry
f(n) = O (g(n)) if and only if g(n) = Ω(f(n)),
f(n) = O (g(n)) if and only if g(n) = ω(f(n)).
because these properties hold for asymptotic notations, one can draw an analogy between the
asymptotic comparison of two functions f and g the comparison of two real numbers a and b.
f(n) = O (g(n)) a b,
f(n) = Ω (g(n)) a b,
f(n) = (g(n)) a = b,
f(n) = o (g(n)) a b,
f(n) = w(g(n)) a b
We say that f (n) is asymptotically smaller than g (n) if f (n) = o (g(n)), and f (n) is
asymptotically larger than f (n) if f (n) = ω (g (n)).
One property of real numbers, however, does not carry over to asymptotic notation:

5. Trichotomy: For any two real numbers a and b, exactly one of the following must hold:
a < b, a = b, or a>b.

Some Examples
Example: f(n) = n
n n for all n
n = O (n)Here c = , n =

Example: f(n) = n n
n n n for n
n n = O (n )Here c = , n =

Example: f(n) = . n
. n
. n = O( ) for n

Example: n n O(n)
ecause here doesn’t exist any positive n and c so that Big-Oh equation gets satisfied.
Remarks - For the function 4n+3, 4n+3 is O(n)
4n+3 is also O(n ) and O(n )
Even though 4n+3 is O(n ) and O(n ) but the best answer for , 4n+3 is O(n) only, as
O(n) shows most tighter upper bound than the other in the question

Example: F (n) = n , h (n) = logn

n logn = O(n )
In general one should remember order of the following functions which will help while
solving the relative growth rate of more complicated functions.
O( )O(logn), O(n)O(nlogn), O(n ), O(n ) … . O(n ), O( )
All the functions are arranged in increasing order of growth rate.

info@[Link] ©Copyright reserved. Web:[Link] 10

 Algorithm Analysis

If an algorithm has the time complexity O(1), then the time complexity is said to be
constant, that means running time is independent of input size.

Example: f(n) = n
n n for n
n n for n
n is Ω (n) Here c = 2, k = 1
We can also say that n n for then c = 1, k = 1
Remarks:
If f(n) is O (g (n)), then g (n) is Ω(f (n)).

Example: f(n) = n2 + n + 1; g(n) = 5n2 + 1; h(n) = 2logn + n2

Then, f(n) = (g(n)) because both have same degree and hence will have same growth
rate.
f(n) = (h(n)) statement is also true because both have same degree and hence will have
same growth rates.
h(n) can be simplified as follows:
2logn is n only,
Let 2logn = n ---------> 1
By taking log on both sides in equation 1.
logn*loge2 = logen
Then, after simplifying the above equation
logn = logen/ loge2 = logn.
Therefore, h (n) = n + n2.

Recurrence
A recurrence is an equation or inequality that describes a function in terms of its value on smaller
inputs.

Three Methods of Recurrence

 Substitution method
The steps involved
1. Guess the form of solution
2. Use mathematical induction
 Recursion - tree method
This method converts the recurrence into a tree whose nodes represent the costs incurred at
various levels of recursion
 Master Method
n
T(n) = aT ( ) f(n)
b
Where a ,b and f(n) is a given function

info@[Link] ©Copyright reserved. Web:[Link] 11

 Algorithm Analysis

Master Theorem
T(n) = aT ( ) (n log n)
Where a ,b , k > 0 and p is a real number
1. If a>b , them T(n) = (n
k )
2. If a = b k

(a) If p > , then T(n) = (n log n)

(b) If p = , then T(n) = (n log log n)
(c) If p < , then T(n) = (n )
3. If a < b k

(a) If p 0, then T(n) = (n log n)

(b) If p < 0, then T(n) = Ο(n )

Example: T(n) = T(n ) n

Solution: T(n) = (n ) (Master Theorem case 3(a))

Example: T(n) = T(n ) n

Solution: T(n) = (n log n) (Master Theorem case 2(a))

Example: T(n) = 0. T(n )

Solution: Does not apply a

info@[Link] ©Copyright reserved. Web:[Link] 12

 "Always bear in mind that your own resolution
to succeed is more important than any other."

12
Abraham Lincoln….
CHAPTER

Divide and Conquer

Learning Objectives
After reading this chapter, you will know:
1. The General Method
2. Finding MaxMin
3. Binary Search
4. Sorting
5. Bubble sort
6. Merge Sort
7. Quick Sort
8. Insertion Sort
9. Selection Sort
10. Heap Sort
11. Straseen’s Matrix Multiplications

The General Method

Divided-and conquer is a general algorithm design paradigm consisting of the following parts:
 Divide: Divide the input data S in two or more disjoint subsets S1, S2, . . . Sn
 Recursion: Solve the sub problems recursively.
 Conquer: Combine the solutions for S1, S2,.., into a solution for S
(i) Given a function to compute on n inputs, the divide-and-conquer strategy suggest splitting
the inputs into k distinct subsets, 1 < k n yielding k sub problems.
(ii) These sub problems must be solve and then a method must be found to combine sub
solutions into a solution of the whole problem. If the sub-problems are relatively large, then
the divide-and-conquer strategy may possibly be reapplied.
(iii) Often the sub problems resulting from a divide-and-conquer design are of the same type as
the original problem.

The Control Abstraction of Divide-and-Conquer

A control abstraction means a procedure whose flow of control is clear, but whose primary
operations are specified by other procedures whose precise meaning is left undefined.
1. Algorithm D and C (P)
2. {
3. If small (P) then return S (P);
4. else
5. {

info@[Link] ©Copyright reserved. Web:[Link] 13

 Divide and Conquer

6. Divide P into smaller instances …… k

7. Apply D and C to each of these sub problems;
8. Return Combines (D and C ( ), D and C ( ), …..D and C ( ));
9. }
10. }
The complexity of divide-and-conquer algorithm is given by the recurrences of the form
T (n) = T (1) n=1
a T (n/b) + f (n) n>1
Where T (n) is the time for D and C on any input of size n and g (n) is the time to computer the
answer directly for small inputs.
The function f(n) is the time for dividing P and combining the solutions to sub-problems. For
divided-and-conquer-based algorithm that produce sub-problems of the same type as the original
problem. ‘a’ and ‘b’ are known constants. We assume that T(1) is known and n is a power of b
(i.e., n =b )

Finding MaxMin
The problem of finding Max Min is to find the maximum and minimum items in a set of ‘n’ elements.
The following Algorithm is a straightforward algorithm to accomplish the task.

Algorithm: Straight Forward Maximum and Minimum

1. Algorithm straight MaxMin (a, n, max, min)
2. // Set max to the maximum and min to the minimum of a [1: n]
3. {
4. Max = Min = a [1];
5. For i = 2 to n do
6. {
7. If (a [i] > max) then max = a [i],
8. If (a [i]<min) then min = a [i];
9. }
10. }
 The time complexity of this algorithm is given by the number of elements compared.
 If the elements in a [1: n] are polynomials, vectors, very large number, or strings of characters,
the cost of an element comparison is much higher than the cost of the other operations.
 Hence the time is determined mainly by the total cost of the elements compared.
 The comparison a [i] <min is necessary only when a [i] > max is false. Hence we can replace the
contents of the for loop by
If (a [i] > max) then max = a [i];
else if (a [i] < min) then min = a [i];
 Now the best case occurs when the elements are in increasing order. The number of element
comparisons is n
 The worst case occurs when the elements are in decreasing order. In this case the number of
element comparisons is 2 (n ).
 The average number of element comparisons is less than 2 (n ). On the average, a [i] is
greater than max half the time, and so the average number of comparisons is 3n/2 3/2.

The DAC Solution

info@[Link] ©Copyright reserved. Web:[Link] 14
 Divide and Conquer

A divide-and-conquer algorithm for this problem would proceed as follows:

Algorithm: Recursively Finding the Maximum and Minimum

1. Algorithm MaxMin (I, j, max, min)
2. // a [1: n] is a global array. Parameters I and j are integers
3. // 1 i j n. The effect is to set max and min to the largest and smallest values in a [i : j]
respectively
4. {
5. If (i j then max min a[i] Small
6. Else if (i = j 1) then // Another case of Small (P)
7. {
8. If (a[i] < a[j]) then
9. {
10. max = a [j]; min = a [i];
11. }
12. else
13. {
14. Max = a [i]; min = a [j];
15. }
16. }
17. else
18. {// if P is not small, divide P into sub-problems
19. // Find where to split the set
20. Mid = [(i + j)/2];
21. // Solve the sub-problems
22. MaxMin (i, mid, max, min);
23. MaxMin (mid + 1, j, max 1, min1);
24. // Combine the solutions
25. If (max < max 1) then max = max1;
26. If (min > min1) then min = min1;
27. }
28. }

Straightforward MaxMin Vs Recursive MaxMin

 Compared with the n comparisons for the straightforward method, this is saving of 25% in
comparisons. It can be shown that no algorithm base on comparisons uses less than n
comparisons.

Therefore Algorithm MaxMin is Optimal

In terms of storage, MaxMin is worse than the straightforward algorithm because it requires stack
space for i, j, max, min, max1, and min1.
 The comparative figure for straight MaxMin is n (including the comparison needed to
implement the for loop). This is larger than n .
 MaxMin is slower than straight MaxMin because of the overhead of using the additional Data
Structures Stack for the recursion.
Binary Search
Let a i n be a list of elements which are sorted in non-decreasing order.

info@[Link] ©Copyright reserved. Web:[Link] 15

 Divide and Conquer

Consider the problem of determining whether a given element x is present in the list. In case x is
present. We are to determine a value j such that a x if x is not in the list then j is to be set to zero.

Binary Search is a Divide-and-Conquer Strategy

Which suggests breaking up any instance I = n, a …a , x) of this search problem into sub instances.
One possibility is to pick and index k and obtain three instances: I1 = (k a ….a , x),
I2 = (1, a , x), and I3 = (n-k, a ….an x .
The search problem for two of these three instances is easily solved by comparing X with a .
If x = a then j = k and I1 and I3 need not be solved.
If x > a then for I2 and I3, j = 0 and only I1 remains to be solved.
If x > a then for I1 and I2, j = 0 and only I3remains to be solved.
After a comparison, with the instance remaining to be solver (if any) can be solved by using this
divide-and-conquer scheme again. If k is always chosen such that a is the middle element
(i.e., k = [(n+1)/2]) and the resulting search algorithm is known as binary search.

Algorithm: Recursive Binary Search

1. Algorithm BinSrch (a, i, j, x)
2. // Given an array a [i: 1] of elements in non-decreasing
3. // Order, 1 i determine whether 1 is present, and
4. // If so, return j such that i = a [j]; else return 0.
5. {
6. If (i = j) then // if Small (P)
7. {
8. If (i = a[i]) then return i;
9. Else return 0;
10. }
11. Else
12. {// reduce P into a smaller sub problem.
13. Mid; = [(i+1)/2];
14. If (x = = a[mid]) return mid;
15. Else if (i < a [mid]) then
16. Return BinSrch (a, i, mid , x);
17. Else return BinSrch (a, mid+1, i, x);
18. }
19. }

Example: Consider the following elements in their ascending Order (i.e., the pre-requisite for
Binary Search)

The working of Binary Search for x: 101, , and 82 for two successful searches and one
unsuccessful search is as follows.

X = 101 Low High Mid X= Low High Mid

1 9 5 1 9 5
6 9 7 1 4 2
8 9 8 1 1 1
info@[Link] ©Copyright reserved. Web:[Link] 16
 Divide and Conquer

9 9 9 2 1 Not found
X = 82 Low High Mid
1 9 5
6 9 7
8 9 8
found

Sorting
Sorting algorithms used in computer science are often classified by:
 Computational complexity (worst, average and best behaviour) of element comparisions in
terms of the size of the list. For typical sorting algorithms good behaviour is O(nlogn) and bad
behaviour is O(n2).
 Memory usage (and use of other computer resources): In particular, some sorting algorithms
are "in place". This means that they need only O(1) memory beyond the items being sorted and
they don't need to create auxiliary locations for data to be temporarily stored, as in other
sorting algorithms.
 Recursion: Some algorithms are either recursive or non-recursive, while others may be both
(e.g., Merge sort).
 Stability: Stable sorting algorithms maintain the relative order of records with equal keys
(i.e., values).
 Comparison: Whether or not they are a comparison sort. A comparision sort examines the data
only by comparing two elements with a comparison operator.
 Adaptability: Whether or not the presortedness of the input affects the running time.
Algorithms that take this into account are known to be adaptive.

Bubble Sort
Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be
sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order.
First pass bubbles out the largest element and places it in the last position and second pass places
the second largest in the second last position and so on. Thus, in the last pass smallest item is placed
in the first position. Because, it only uses comparisions to operate on elements, it is a comparision
sort.
E.g.: Let us take the array of numbers "5 1 4 2 9", and sort the array from lowest number to greatest
number using bubble sort algorithm. In each step, elements written in bold are being compared.

First Pass: Considering length n

(5 1 4 2 9) (1 5 4 2 9), Here, algorithm compares the first two elements, and swaps them.
(1 5 4 2 9) (1 4 5 2 9), Swap since 5 > 4
(1 4 5 2 9) (1 4 2 5 9), Swap since 5 > 2
(1 4 2 5 9) (1 4 2 5 9), Now, since these elements are already in order (9 > 5), algorithm does not
swap them.

Second Pass: Considering length n 1

(1 4 2 5 9) (1 4 2 5 9)
(1 4 2 5 9) (1 2 4 5 9), Swap since 4 > 2
(1 2 4 5 9) (1 2 4 5 9)

info@[Link] ©Copyright reserved. Web:[Link] 17

 Divide and Conquer

Third Pass: Considering length n 2

(1 2 4 5 9) (1 2 4 5 9)
(1 2 4 5 9) (1 2 4 5 9)

Fourth Pass: Considering length n 3

(1 2 4 5 9) (1 2 4 5 9)

Performance
The running time can be bound as the total number of comparisons being made in the entire
execution of this algorithm. Thus, in the worst case (input is descending order) numbers of
comparisons in the respective passes are as follows:
1st n–1
2nd n – 2
…
(n – 1)th pass 1
Therefore, total comparisons = n(n 1)/2;
Which implies O (n2) time complexity
Bubble sort has worst-case and average complexity both as О (n²), where n is the number of items
being sorted. Performance of bubble sort over an already-sorted list (best-case) is O(n). Remember
that using a flag it can easily be determined that if no swaps were performed in the current pass that
would mean the list is sorted and bubble sort can come out, rather than going through all the
remaining passes.
Remarks
 It is comparison based sorting method.
 It is in place sorting method.
 Worst case space complexity is of O (1)
 It is adaptive sorting method as presortedness affects the running time.
A stable sorting method.

Merge Sort
Merge Sort is a divide-and-conquer strategy that sorts the elements in non-decreasing order.
 Given a set of n-elements also called keys a [ ] ….. a [n] the concept is to split them into two
sets a[ ] …. a[[n ]] and a [[n ]+ ] …a[n]. Each set is individually sorted and the resulting
sorted sequences are merged to produce a single sorted sequence of n elements.
 Thus, Marge Sort splits the given set of elements into two equal-size sets and the combining
operation is the merging of two sorted sets into one.
 Merge Sort (Algorithm) describes this process using recursion an a function Merge (Algorithm)
which merge two sorted sets.

Algorithm: Merge Sort

1. Algorithm Mergesort (low, high)
2. // a [low: high] is a global array to be sorted
3. // Small (P) is true if there is only one element
4. // to sort. In this case the list is already sorted
5. {
info@[Link] ©Copyright reserved. Web:[Link] 18
 Divide and Conquer

6. If (low<high) then // if there are more than one element

7. {
8. // Divide P into sub problems
9. // Find where to split the set
10. Mid = [(low+high)/2];
11. // Solve the sub problems
12. Mergesort (low, mid);
13. Mergesort (mid + 1, high);
14. //Combine the solutions
15. Merge (low, mid, high);
16. }
17. }

Merge Sort is an O(n log n) comparison-based divide and conquer sorting algorithm.
Conceptually, a merge sort works as follows:
1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
2. Divide the unsorted list into two sub lists of about half the size.
3. Sort each sub list recursively by re-applying merge sort algorithm.
4. Merge the two sub lists back into one sorted list.

Example:
39 27 43 3 9 82 10

39 27 43 3 9 82 10

39 27 43 3 9 82 10

39 27 43 3 9 82 10

27 39 3 43 9 82 10

3 27 39 43 9 10 82

3 9 10 27 39 43 82

Algorithm: Merging two Sorted Sub-Arrays Using Auxiliary Array

1. Algorithm Merge (low, mid, high)
2. // a[low: high] is a global array containing two sorted
3. // subsets in a [low: mid] and in a [mid + 1: high]. The goal is to merge these two sets into a
single set residing
4. // in a [low: high]. b [] is an auxiliary global array.
5. {

info@[Link] ©Copyright reserved. Web:[Link] 19

 Divide and Conquer

6. h: low; i: = low; j; = mid + 1;

7. while (h mid) and (j high) do
8. {
9. If (a[h] a[j]) then
10. {
11. b [i] = a[h]; h = h + 1;
12. }
13. else
14. {
15. b [i] = a[j]; j = j + 1;
16. }
17. i; = i + 1;
18. }
19. if (h> mid) then
20. for k = j to high do
21. {
22. b[i] = a [k]; i = i +1;
23. }
24. else
25. For k = h to mid to
26. {
27. b[i] = a [k]; i = i + 1;
28. }
29. for k = low to high do a [k] = b[k];
30. }

Example: Consider the Array of ten elements

A [1: 10] = (310, 285, 179, 652, 351, 423, 861, 254, 450, 520).
 Marge Sort begins by splitting a [] into two sub-array each of size 5 (a [1: 5] and a
[6: 10]).
 The elements in a [1: 5] are then split into two sub-arrays of size 3 (a [1: 3]) and 2
(a [4: 5]).
 Then the items in a [1: 3] are split into sub-array of size 2 (a [1: 2]) and one (a [3: 3]).
 The two values in a [1: 2] are split a final time into one elements sub-arrays, and now
the merging process starts.
The recursive mechanism can be shown as follows:
(310! 285! 179! 652,351! 423, 861, 254, 450, 520)
(285! 310! 179! 652,351! 423, 861, 254, 450, 520)
Then a [3] is merged with a [1:2] and
(179, 285, 310! 652, 351! 423, 861, 254, 450, 520)
Is produced, Next, elements a [4] and a [5] are merged.
(179, 285, 310! 351, 652! 423, 861, 254, 450, 520)
And then a [1: 3] and a [4: 5]:
(179, 285, 310, 351, 652,! 423, 861, 254, 450, 520)
Merge sort is called first time and is about to process the second recursive call.
Repeated recursive calls are invoked producing the following sub-arrays:
(179, 285, 310, 351, 652! 423! 861! 254, 450, 520)

info@[Link] ©Copyright reserved. Web:[Link] 20

 Divide and Conquer

Elements a [6] and a [7] are merged. Then a [8] is merged with a [6: 7]:
(179, 285, 310, 351, 652,! 254, 423, 450, 861, 520,)
Next a [9] and a [10] are emerged and then a [6: 8] and a [9: 10]
(179, 285, 310, 351, 652! 254, 423, 450, 520, 861)
Now there are two sorted sub-arrays and the final merge produce the fully sorted
result (179, 254, 310, 285, 351, 423, 450, 520, 652, 861)

Performance
In sorting n objects, merge sort has an average and worst-case performance of O(n log n). If the
running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2) + O(n)
follows from the definition of the algorithm (apply the algorithm to two lists of half the size of the
original list, and add the n units taken to merge the resulting two sorted lists).
Thus, after simplifying the recurrence relation T(n) = O(nlogn).

Space Complexity
 The stack space is necessitated by the use of recursion of Merge Sort.
 Since merge sort splits each set into two approximately equal-sized subsets, the maximum depth
of the stack is proportional to log n.
 The need for stack space seems indicated by the top-down manner in which this algorithm was
devised.
 The need for stack space can be eliminated if we build an algorithm that works bottom-up

Limitations: One of the drawbacks of merge sort is its use of the auxiliary array (additional storage).

The Solution: An alternative to associate a new field of information with each key. (The elements in a
[ ] are called keys). This field is used to link the keys and any associated information together in a
sorted list (keys and related information are called records). Then the merging of the sorted list
proceeds by changing only a link values, and no records need be moved at all. A field that contains
only a link will generally be smaller than an entire record, so less space will be used.
Along with the original array a [], we define an auxiliary array ling (1: n) that contains integers in
the range [0, n]. These integers are interpreted as pointers to elements of a []. A list is a sequence of
pointers ending with a zero. Below is one set of values for ling that contains two lists: Q and R. The
integer Q = 2 denotes the start of one list and R = 5 the start of the other.
Link: [1] [2] [3] [4] [5] [6] [7] [8]
6 4 7 1 3 0 8 0
The two lists are Q = (2, 4, 1, 6) abd R = (5, 3, 7, 8). Interpreting these lists as describing sorted
subsets of a [1: 8], we conclude that a [2] a [4] a [1] a [5] a [3] a [7] a [8].
An Alternative to Merge Sort: (Insertion Sort)
Insertion sort works exceedingly fast on arrays of less than, say 16 elements, though for large n its
computing time is O (n ). Its basic idea for sorting the items in a [1: n] is as following:
For j = 2 to n do
{
Place a [j] in its correct position in the sorted set a [1: j 1];
 The Algorithm is initially invoked by placing the keys of the records to be sorted in a [1: n] and
setting link [1: n] to zero.

info@[Link] ©Copyright reserved. Web:[Link] 21

 Divide and Conquer

 A pointer to a list of indices that give the elements. Of a [] in sorted order is returned. Insertion
sort is used whenever the number of items to be sorted is less than 16.
The version of insertion sort need to be altered so that it sorts a [low: high] into a linked list.

Algorithm: Merge Sort Using Links

1. Algorithm Mergesort1 (Low, High)
2. // The global array a [Low: High] is sorted in non decreasing order using the auxiliary array
link [Low; High]. the values in link represent a list of the indices low through high giving a [ ] in
sorted order. A pointer to the beginning of the list is returned,
3. {
4. If (High-Low)<15) then
5. Return insertionsort1 (A, Link, Low, High);
6. Else
7. {
8. Mi0d = [(Low + High)/2];
9. Q = Mergesort1 (Low, Mid);
10. R = Mergesort1 (Mid+1, High);
11. Return Merge1 (q, r);
12. }
13. }
Remarks:
 Its not adaptive.
 Merge sort is a stable sort as long as the merge operation is implemented properly.
Not an in-place sorting method as it requires O (n) of additional memory space. The additional
n locations were needed because one couldn't reasonably merge two sorted sets in place.

Quick Sort
Quick Sort is a Divide-and-Conquer approach which is an efficient sorting method, different from
merge sort.
In quicksort, the division into two sub arrays is made so that the sorted sub arrays do not need to be
merged later. This is accomplished by rearranging the elements in a [1: n] such that a [i] a[j] for
all i between 1 and m and all j between m + 1 and n for some m, 1 m n.
Thus, the element in a [1: m] and a [m+1: n] can be independently sorted. No merge is needed.
The rearrangement of the elements is accomplished by picking some element of a [], say t = a [s],
and then reordering the other elements so that all elements appearing before t in a [1: n] are less
than or equal to and all elements appearing after t are greater than or equal to t. this rearranging is
referred to as partitioning.
Function Partition of Algorithm, partitions elements of a [m: p 1]. It is assumed that a [p] a [m]
and that a [m] is the partitioning element. If m = 1 and p = n, then a [n+1] must be define and
must be greater than or equal to all elements in a [1: n]. The assumption that a [m] is the partition
element is merely for convenience; other choices for the partitioning element than the first item in
the set are better in practice. The function interchange (a, I, j) exchanges a [i] with a [j].

Example: Consider the following set of element. The function is initially invoked as partitions (a, 1,
10). The element a [1] = 65 is the partitions elements and it eventually (in the sixth row)

info@[Link] ©Copyright reserved. Web:[Link] 22

 Divide and Conquer

determined to the fifth smallest element of the set. Notice that the remaining elements
are unsorted but partitioned about a [5] = 65.
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) i p
70 75 80 85 60 55 50 45 + 2 9
45 75 80 85 60 55 75 70 + 3 8
45 50 80 85 60 55 75 70 + 4 7
45 50 55 85 60 80 75 70 + 5 6
45 50 55 60 85 80 75 70 + 6 5
45 50 55 65 85 80 75 70 +
We can device a divide-and-conquer method for completely sorting n elements. Function
partition, creates two sets S and S . All elements is S are less than or equal to the
elements in S Hence S and S can be sorted independently. Each set is sorted by reusing
the function partition. The following Algorithm describes the complete process.

Algorithm: Quick sort (Sorting by Partitioning)

1. Algorithm QuickSort (p, q)
2. Sorts the elements a [p] ….. which reside in the global
3. // array a [1: n] into ascending order, a [n+1] is considered to be defined and must be all the
elements in a [1: n]
4. {
5. If (p<q) then // if there are more than one elements
6. {
7. // divide p in into two sub problems
8. J = Partition (a, p, q +1);
9. // j is the position of the partitioning element
10. // Solve the sub problems
11. QuickSort (p, j-1);
12. QuickSort (j+1, q);
13. // There is no need for combining solutions
14. }
15. }

Algorithm: Partition
1. Algorithm Partition (a, m, p)
2. Within a [m] a [m+ ] ….a [p 1] the elements are Rearranged in such a manner that if
initially t = a [m], Then after completion a [q] = t for some q between m and p 1, a [k] t for m
k < q, and a [k] t for q < k < p, q is returned. Set a [p] = .
3. {
4. v = a [m]; i = m; j = p;
5. Repeat
6. {
7. Repeat
8. i = i + 1;
9. Until (a [i] v);
10. Repeat
11. J = j ;

info@[Link] ©Copyright reserved. Web:[Link] 23

 Divide and Conquer

12. } until (a[i] v);

13. If (i<j) then interchange (a, i j ’
14. } until (i j);
15. a [m] = a [j]; a [j] = v; return j;
16. }

Quick sort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.
The simple steps to remember are:
1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements which are less than the pivot come before the pivot and so
that all elements greater than the pivot come after it (equal values can go either way). After this
partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
The base case of the recursion are lists of size zero or one, which are always sorted.

Performance
If the running time of quick sort for a list of length n is T(n), then the recurrence
T(n) = T(size of s1) + T(size of s2) + n follows from the definition of the algorithm (apply the
algorithm to two sets which are results of portioning, and add the n units taken by the portioning of
the given list).

Worst Case Time Complexity

The quick sort shows its worst case behavior when one of the subsets after portioning is always
empty for all subsequent recursive quick sort calls. This could have happened because of a bad
choice of pivot. Then the above recurrence relation can be written as follows to represent the worst
case behavior.
n + n + n n + n
herefore n n + n + n + … n

Best Case Time Complexity

The quick sort shows its best case behavior when the size of each subset after portioning is always
close to same for all subsequent recursive quick sort calls. This could have happened because of a
good choice of pivot. Then the above recurrence relation can be written as follows to represent the
best case behavior.
T (n) = 2T (n/2) + n
Therefore, T (n) = O (nlogn)
O (nlogn) is also the average case time complexity of quick sort.
Remarks:
 The known fastest in-place algorithm in practice.
 Each call finalizes the correct position of pivot element which can never be changed by any
number of subsequent calls.
 It is an adaptive sorting method.
Can be implemented as a stable sort depending on how the pivot is handled.

info@[Link] ©Copyright reserved. Web:[Link] 24

 Divide and Conquer

Insertion Sort
Insertion Sort: Is a simple comparison sorting algorithm. Every iteration of insertion sort removes
an element from the input data, inserting it into the correct position in the already-sorted list, until
no input element remains in wrong position. The choice of which element to remove from the input
is arbitrary, and can be made using almost any algorithm.
Example
Pass 1
54321 45321
Pass 2
45321 43521 34521
Pass 3
34521 34251 32451 23451
Pass 4
23451 23415 23145 21345 12345

Performance
The worst case input is an array sorted in reverse order. In this case every iteration of the inner loop
will scan and shift the entire sorted subsection of the array before inserting the next element. For
this case insertion sort has a quadratic running time (i.e., O (n2)). The running time can be bound as
the total number of comparisons being made in the entire execution of this algorithm. Thus, the
worst case comparisions in the respective passes are as follows:
1st 1
2nd 2
3rd 3
(n – 1)th pass n 1
Therefore, total comparisons = n (n 1)/2;
Which implies O (n2) time complexity.
The best case input is an array that is already sorted. In this case insertion sort has a linear running
time (i.e., O (n)). During each iteration, the first element of the input is only compared with the
right-most element of the sorted subsection of the array.
Insertion sort typically requires more writes because the inner loop can require shifting large
sections of the sorted portion of the array. In general, insertion sort will write to the array O (n2)
times, whereas selection sort will write only O (n) times. For this reason selection sort may be
preferable in cases where writing to memory is significantly more expensive than reading.

Remarks: It is much less efficient on large lists than more advanced algorithms such as quicksort,
heap sort, or merge sort. However, insertion sort provides several advantages
 Simple implementation
 efficient for (quite) small data sets
 Adaptive, i.e. efficient for data sets that are already substantially sorted the time complexity is
O (n)
 Stable, i.e. does not change the relative order of elements with equal keys
 In-place, i.e. only requires a constant amount O (1) of additional memory space
Most humans when ordering a deck of cards, for example—use a method that is similar to
insertion sort.

info@[Link] ©Copyright reserved. Web:[Link] 25

 Divide and Conquer

Selection Sort
Selection sort is also a simple comparison sorting algorithm. The algorithm works as follows:
1. Find the minimum value in the list
2. Swap it with the value in the first position
3. Repeat the steps above for the remainder of the list (starting at the second position and
advancing each time)
Effectively, the list is divided into two parts: the sublist of items already sorted, which is built
up from left to right and is found at the beginning, and the sublist of items remaining to be
sorted, occupying the remainder of the array.
Here is an example of this sort algorithm sorting five elements
66 25 12 22 11, 11 25 12 22 66, 11 12 25 22 66, 11 12 22 25 66, 11 12 22 25 66

Performance
All the inputs are worst case inputs for selection sort as each current element has to be compared
with the rest of unsorted array. The running time can be bound as the total number of comparisons
being made in the entire execution of this algorithm. Thus, the worst case comparisions in the
respective passes are as follows:
1st n–1
2 nd n–2
…
(n – 1)th pass 1
Therefore total comparisions = n(n 1) / 2;
Which implies O (n2) time complexity.
Remarks:
 It is much less efficient on large lists than more advanced algorithms such as quicksort,
heapsort, or merge sort.
 Simple implementation.
 Efficient for (quite) small data sets.
 Not adaptive.
 Its stability depends on the implementation of choosing minimum.
 In-place, i.e. only requires a constant amount O (1) of additional memory space.
 Insertion sort is very similar to selection sort as after the kth iteration; the first k elements in the
array are in sorted order. Insertion sort's advantage is that it only scans as many elements as it
needs in order to place the k + 1st element, while selection sort must scan all remaining
elements to find the k + 1st element.
 Selection sort always performs O (n) swaps.

Heap Sort
Heap Sort is a comparison-based sorting algorithm which is much more efficient version of selection
sort. It also works by determining the largest (or smallest) element of the list, placing that at the end
(or beginning) of the list, then continuing with the rest of the list, but accomplishes this task
efficiently by using a data structure called a heap. Once the data list has been made into a heap, the
root node is guaranteed to be the largest (or smallest) element. When it is removed (using
deleteMin/deleteMax) and placed at the end of the list, the heap is rearranged so that the largest
element of remaining moves to the root. Using the heap, finding the next largest element takes O

info@[Link] ©Copyright reserved. Web:[Link] 26

 Divide and Conquer

(log n) time, instead of O (n) for a linear scan as in simple selection sort. This allows Heapsort to run
in O (n log n) time.
Remarks:
 Its not adaptive.
 It is in-place sorting method as it utilized the same input array for placing the sorted sub array.
Not a stable sorting method as during deleteMin/deleteMax the order is not preserved for the
same key values. Consider an input that is having all the same key values. The deleteMin will
pick up the last heap element to place it in the root location. Thereby, the order is changed
because in the sorted output later values appear before.

Straseen’s Matrix Multiplications

Let A and B be two n x n matrices. The product matrix C =A B is also an n x n matrix whose j
element is formed by taking the elements in the ith row of A and the j column of n and
multiplying them to get
ij ∑ ik kj

For all i and j between 1 and n. To compute C (i, j) using this formula, we need n multiplication. As
the matrix C has n elements, the time for the resulting matrix multiplication algorithm, which we
refer to as the conventional method is n .

The Solution: The divide-and-conquer strategy suggests another way to computer the product of
two n x n matrices. For simplicity we assume that n is a power of 2, that is there exists a non-
negative integer k such that n = in case is not a power of two then enough rows and column of
zeros can be added to both A and B so that the resulting dimensions are a power of two.

Imagine that A and B are each partitioned into four square sub matrices, each sub matrix having
dimensions n/2 × n/2. Then the product AB can be computed by using the above formula for the
product of 2 × 2 matrices: if AB is
( ) ( ) ( )

Then
+
+
+
+

These elements are typically floating point numbers. For n >2, the elements of C can be computed
using matrix multiplication and addition operations applied to matrices of size n/2 × n/2. Since n is
a power of 2, these matrix products can be recursively computed by the same algorithm we are
using for the n × n case. This algorithm will continue applying itself to smaller-sized sub matrices
directly.
Since two n/2 × n/2 matrices can be added in time cn for some constant c, the overall computing
time T (n) of the resulting divide-and-conquer algorithm is given by the recurrence

info@[Link] ©Copyright reserved. Web:[Link] 27

 Divide and Conquer

n b n
n + cn n >2
Where b and c are constants.

This recurrence can be solved to obtain T (n) = O (n )

Hence no improvement over the conventional method has been made. Since matrix multiplications
are more expensive than matrix additions (O (n ) versus O (n ), we can attempt to reformulate the
equations for ij so as to have fewer multiplications and possibly more additions. Volker Straseen’s
has discovered a way to computer the ij’s of formula using only 7 multiplications and 18 additions
or subtractions. This method involves first computing the seven n/2 × n/2 matrix P, Q, R, S, T, U and
V. then the Cij are computed. As can be seen P, Q, R, S, T, U and V can be computed using 7 matrix
multiplication and matrix additions or subtractions. he ij’s require and additions additions
or subtractions.

info@[Link] ©Copyright reserved. Web:[Link] 28

 "The gem cannot be polished without
friction, nor man perfected without trials."

13
….Confucius
CHAPTER

Greedy Techniques

Learning Objectives
After reading this chapter, you will know:
1. General Method
2. Minimum Spanning Tree
3. Prim’s Algorithm
4. Kruskal’s Algorithm
5. Single Source Shortest Path Algorithm

General Method
 The greedy method is a design technique applied to those problems having n inputs and
requires us to obtain a subset that satisfies some constraints.
 Any subset that satisfies these constraints is called a feasible solution.
 We are required to find a feasible solution that either maximizes or minimizes a given objective
function.
 A feasible solution that does this is called an optimal solution.
 The greedy method suggests that one can design an algorithm which works in stages,
Considering one input at a time.
 Consider the inputs in an order determined by some selection procedure. If the inclusion of the
next input into the partially constructed optimal solution will result in an infeasible solution,
then this input is not added to the partial solution.
 The selection procedure is based on some optimization measure. This measure may or may not
be the objective function.

The Greedy Method Control Abstraction

1. Algorithm GREEDY (A, n)
2. {
3. // A (1: n) contains the n inputs//
4. Solution initialize the solution to empty//
5. For i to n do
6. x S T (A)
7. if AS (solution x)then
8. Solution UNION (solution, x);
9. End if
10. Repeat
11. Return (solution);
12. }

info@[Link] ©Copyright reserved. Web:[Link] 29

 Greedy Techniques

 The function SELECT selects an input from A, and assigns its value to x.
 FEASIBLE is a Boolean-valued function which determines if x can be included into the
solution vector.
 UNION combines x with solutions and updates the objective function.

Optimal Storage on Tapes

 Given ‘n’ programs that are to be stored on a computer tape of length .
 Associated with each program is a length i n.
 Programs can be stored on the tape if and only if the sum of the length of the programs is at most L
 Whenever a program is to be retrieved from this tape, the tape is initially positioned at the front.
 If the programs are stored in the order i i i2 …. in the time tj need to retrieve program ij is
proportional to .
 If all programs are retrieved equally often then the expected or mean retrieval time (MRT) is
(1/n) tj.
 In this problem, we are required to find a permutation for then programs so that when they are
stored on the tape in this order the MRT is minimized.
 Minimizing the MRT is equivalent to minimizing D (I) = .

Example: Consider three tapes with their lengths as (l l l ) = (5, 10, 3). There are n! = 6 possible
ordering. These orderings and their respective D values are:
Ordering 1 D(I)
A, 2, 3 5+5+10+5+10+3=38
1, 3, 2 5+5+3+5+3+10=31
2, 1, 3 10+10+5+10+5+3=43
2, 3, 1 10+10+3+10+3+5=41
3, 1, 2 3+3+5+3+5+10=29
3, 2, 1 3+3+10+3+10+5=34
The Optimal Ordering is 3, 1, 2
 A greedy approach of building the required permutation would choose the next
program based upon some optimization measure.
 One possible measure would be the D value of the permutation constructed so far.
 The next program to be stored on the tape would be one which minimized the
increase in D.
 If we have already constructed the permutation i i … . . i i i. This increases
the D value by .
 The greedy method suggests us to store the program in non-decreasing order of their
length. This ordering can be carried out in O (n log n) time using an efficient sorting
algorithm.

Knapsack Problem
 Given ‘n’ objects and a knapsack (a bag). Object have a weight w , and the knapsack has a
capacity m.
 If a fraction a , 0, < i, < 1, of object I is placed into the knapsack, then a profit of pi, is earned.
 The objective is to obtain a filling of the knapsack that maximizes the total profit earned.
 Since the knapsack capacity is m, we require the total weight of all chosen objects to be at most m.
The problem of knapsack can be stated as follows:
info@[Link] ©Copyright reserved. Web:[Link] 30
 Greedy Techniques

ax P X ( )
Subject to Wi Xi m (2)
And Xi, = 0 or 1, 1 i n ( )
The problem of knapsack are positive numbers.
 A feasible solution (or filling) is any set (xi ….Xn) satisfying (2) and ( ) above.
 An optimal solution is a feasible solution for which (1) is maximized.

Example: Consider the following instance of the knapsack problem:

n m 2 (p p2 p ) 2 2 , and (w w w ) = (18, 15, 10).
Few of the feasible solutions are:
( )
(1/2, 1/3, 1/4) 16.5 24.25
(1, 2/15, 0) 20 28.2
(0, 2/3, 1) 20 31
(0, 1, 1/2) 20 31.5
 Of these four feasible solutions, solution 4 yields the maximum profit
 Object one, has the largest profit value (pi=25). So it is place into the knapsack first.
Then, z i and a profit of 25 is earned.
 Only 2 units of knapsack capacity are left. Object two has the next largest profit
(p2 = 24). However, u and it doesn’t fit into the knapsack. Using x fills the
knapsack exactly with part of object 2 and the value of the resulting solution is 28.2.
 The time to initially sort the objects, each of the three strategies outline above requires
only O[n] time.

Algorithm for Greedy Strategy for the Knapsack Problem

1. Algorithm Greed Knapsack (m, n)
2. {
3. For (i; = 1 to n) do a: [t]:==0.0;
4. U: = m;
5. For (i: =1 to n) do
6. {
7. If (W[i]>U) then break;
8. X [i]:= 1.0; U: = U – w [i];
9. }
10. If (i n) then x [i]: = U/w [i];
11. }

Tree Vertex Splitting

 Trees with edge weights are called weighted trees.
 A weighted tree can be used, to model a distribution network in which electric signals
Or commodities such as oil are transmitted.
 Nodes in the tree correspond to receiving stations and edges correspond to transmission lines.
 Each edge in the tree is labeled with the loss that occurs in traversing that edge. The network
may not be able to tolerate losses beyond a certain level.
 In places where the loss exceeds the tolerance level, boosters has to be placed.
info@[Link] ©Copyright reserved. Web:[Link] 31
 Greedy Techniques

The “Tree Vertex Splitting Problem (TVSP) is to determine an optimal placement of boosters”.
The TVSP can be specified as follows:
 Let T = {V, E, w} be a weighted directed tree, where V is the vertex set, E is the edge set, and w is
the weight function for the edges.
 W (i, j) is the weight of the edge <i, j> in E. the weight w (i, j) is undefined for any {i, j} not in E.
 A source vertex is a vertex with in-degree zero, and sink vertex is a vertex with out-degree zero.
For any path P in the tree, its delay. D (P), is defined to be the sum of the weight on that path.
 The delay of the tree T, d (T), is the maximum of all the path delays.
 For the TVSP, the quantity that is optimized (minimized) is the number of nodes in X.
 A greedy approach to solving this problem is to compute for each node u ϵ V, the maximum delay
d (u) from u to any other node in its sub-tree.
 If u has parent v such that d (u) + w (v, u) > , then the node u gets split and d (u) is set to zero.
Computation proceeds from the leaves toward the root.
 The order in which TVS visits the nodes of the tree is called the post order.

Tree Vertex Splitting Algorithm

1. Algorithm TVS (T )
2. {
3. If (T 0) then
4. {
5. D [T] = 0;
6. for each child v of T do
7. {
8. TVS (v, );
9. d[T]: = max {d [T], d[v]+ w (T, v)};
10. }
11. if (T is not the root) and
12. (d[T]+ w (parent {T),T> }} then
13. {
14. Write (T); d [T]; = 0;
15. }
16. }
17. }

 Algorithm TVS Takes ( ) where n is the number of nodes in the tree. This can be seen as
follows;
 When TVS is called on any node T, only a constant number of operations are performed
(excluding the time taken for the recursive calls). Also, TVS is called only once on each node T in
the tree.

Job Sequencing with Deadlines

 Given ‘n’ jobs associated with each job is an integer deadline d > 0 and a profit p >0. For any
job i the profit p is earned if and only if the job is completed by its deadline.

info@[Link] ©Copyright reserved. Web:[Link] 32

 Greedy Techniques

 To complete a job, one has to process the job on a machine for one unit of time. Only one machine
is available for processing jobs.
 A feasible solution for this problem is subset j of job such that each job in this subset can be
completed by its deadlines. The value of a feasible solution j is the sum of the profits the jobs in j.
 An optimal solution is a feasible solution with maximum value. Since the problem involves the
identification of a subset, it fits the subset paradigm.

Example: Let n = 4, Penalties (p1, p2, p3, p4) = (100, 10, 15, 27) and Deadlines (d1, d2, d3, d4) =
(2, 1, 2, 1).
The feasible solution and their values are:
Feasible Processing Solution Sequence Value (Profit)
(1, 2) 2, 1 110
(1, 3) 1, 3 or 3, 1 115
(1, 4) 4, 1 127
(2, 3) 2, 3 25
(3, 4) 4,3 42
(1) 1 100
(2) 2 10
(3) 3 15
(4) 4 27
Solution 3 is Optimal: In this solution only jobs 1 and 4 are processed and the value is 127
These jobs must be processed in the order job 4 followed by job 1. Thus the processing of
job 4 begins at time zero and that of job 1 is completed at time 2.

A General Algorithm for Job Sequencing with Deadlines

1. Algorithm Greedy job (d, j, n)
2. {
3. j: = {1};
4. For i: = 2 to n do
5. {
6. If (all jobs in j U {i} can be completed by their deadlines) then j: = j U {i};
7. }
8. }

A Greedy Algorithm for job sequencing with Deadlines and Profits Algorithm JS (d, j, n)
1. {
2. b[0] = j [0] = 0;
3. j [1] = 1;
4. k: = 1;
5. For i = 2 to n do
6. {
7. r = k;
8. While (d [j[r]]> d [i]) and (d[j[r]] r+) do r = r ;
9. if (d[j[r]] d[z]) and (d[j[r]]>r)) then
10. {

info@[Link] ©Copyright reserved. Web:[Link] 33

 Greedy Techniques

11. For q = k to (r+1) step do j [g+1]= j[g];

12. j[r+1]: = 1; k: = k+1;
13. }
14. }
15. Return k;
16. }
 There are two possible parameters for JS Algorithm in terms of which its complexity can be
measured. These are n, the number of jobs, and s, the number of jobs include in the solution j.
 Each iteration takes O (1) time.
 The computing time of JS can be reduced from O(n ) to nearly O(n).

Minimum Spanning Tree

Let G(V ) be an undirected graph where V set of vertices & set of edges, then a spanning
tree T of graph can be defined as a sub graph of G. A spanning tree of a graph must include every
vertex and if the graph contains n vertices, spanning tree must contain exactly (n 1) edges.

Spanning Tree: A minimum cost spanning tree is a spanning tree such that the sum of all the weights
of edges in spanning tree is minimum.
Spanning tree is a connected sub-graph without any circuit, basically determine from a graph.

MST: Minimum spanning tree is a spanning tree with minimum weight.

We can find the minimal spanning tree of a graph by using two method.
Two greedy algorithms exist to solve this problem namely Prim’s and Kruskal’s algorithm.

Prim’s Algorithm
This algorithm computes the minimum spanning tree by including appropriate vertex and thus one
edge into existing partially constructed tree in successive stages.
At any point in the algorithm, we can observe that we have a set of vertices that have already been
included in the tree; the rest of the vertices have not. The algorithm then finds, at each stage, a new
vertex to add to the tree by choosing the edge (u, v) such that the cost of this edge is the smallest
among all edges where u is in the tree and v is not.
The Prim’s algorithm is essentially identical to Dijkstra’s only except the update rule.
The new update rule is as follows:
dw = min(dw, cw,v). Thus the RT analysis of Dijkstra’s algorithm will remain applicable here too.
Algorithm work as given below,
Algorithm:
The Prims algorithm is given below.
A *V ,v- V * *r+ Q++
MST – PRIM (G w r)
G Graph
[ w Weight ]
r Source Vertex
1. for each u ϵ V,G-
2. do key ,u-
3. ,u-
4. key,r-
info@[Link] ©Copyright reserved. Web:[Link] 34
 Greedy Techniques

5. Q V. ,G- [// Q is a priority Queue]

6. while Q
7. do u XTRA T (Q)
8. for each Vϵ Adj,u-
9. do if Vϵ Q and w(u v) key,v-
10. then ,v- u
11. key,v- w(u v)
Above Prims algorithm operates much like dijkstra‟s algorithm for finding shortest path from a
graph. Prims algorithm has the following property that the edge in set A always form a single tree. In
the Prims algorithm also the input states given unlike Kruskal’s algorithm.

Example: This example will walk through all stages of Prim’s algorithm for the following graph.
V V
2
1 3 10
4

2 2
V V V

4
5 8

V 1 6
V

V C=0 V C=2

V C=4 V C=1 V

V V
Left V1 is Declared Known;

V C=0 V C=2

V C=2 V V C=7

V C=8 V C=4
Right V4 is Declared Known

info@[Link] ©Copyright reserved. Web:[Link] 35

 Greedy Techniques

V C=0 C=2
V

V V C=1 V C=7
C=2

V C=5 V C=4
V2 and then V3 are Declared Known

C=0
V V C=2

V V C=1 V C=6
C=2

V C=1 V C=4
Left V7 Declared Known

C=0
V V C=2

V V C=1 V C=6
C=2

V V C=4
C=1
Right V6 is Declared Known

info@[Link] ©Copyright reserved. Web:[Link] 36

 Greedy Techniques

C=0 2
V V C=2

2 C=1
V V V C=6
C=2
4
6
V V C=4
1
C=1
V5 is Declared Known
Spanning tree weight 2 2

Kruskal’s Algorithm
Initially from the graph G, consider a forest of all the vertices without any edge.
1. Sort all the edges in ascending order according to their costs.
2. Include the edge with minimum cost into the forest if it does not form a cycle in the partially
constructed tree. Repeat step (2) until no edge can be added to the tree.
Algorithm work as given below,
Algorithm:
The Kruskal’s algorithm is given below.
MST – KRUSKAL (G, w)
1. A
2. For each vertex vϵV do MAKE-SET
3. Sort the edges of E into non-decreasing order according their weight W.
4. For each edge (u v) ϵ taken in non-decreasing order by weight.
5. Do if FIND-SET(u) FIND-SET (v)
6. Then A A *(u v)+
7. UNION (u v)
8. Return A
Above Kruskal algorithm takes two input the graph G and weight of each edge W.
Now we shows how this algorithm actually works using the following example.

E.g.: This example will walk through all stages of Kruskal’s algorithm for the following graph.

info@[Link] ©Copyright reserved. Web:[Link] 37

 Greedy Techniques

2
V V

4 3 10
1

2 7
V V V

8 4
5 6
V V
1
Let sort the edges based on their cost.
(V6, V7, 1) (V1, V4, 1) (V1, V2, 2) (V3, V4, 2) (V2, V4, 3) (V1, V3, 4) (V4, V7, 4) (V3, V6, 5) (V5, V7, 6)
(V4, V5, 7) (V4, V6, 8) (V2, V5, 10).

V V

V V V

V V

Left Empty Forest

V V

V V V

V V
1
Right V6V7 is Added

info@[Link] ©Copyright reserved. Web:[Link] 38

 Greedy Techniques

V V
1

V V V

V V
1
Left V1V4 is Added

2
V V
1

V V V

V V
1
Right V1V2 is Added
2
V V

2
V V V

V V
1
Left V3V4 is Added

2
V V

2
V V V
4

V V
1
Right V4V7 is Added

info@[Link] ©Copyright reserved. Web:[Link] 39

 Greedy Techniques

2
V V

2
V V V

4
6

V V
1
V5 and V7 is Added

Thus, the cost of minimum spanning tree is 16. The following three edges were rejected by the
algorithm though they were selected, (V2, V4, 3) (V1, V3, 4) (V3, V6, 5). That means, it is possible
for a minimum spanning tree to have greater cost edges included while not including the lower cost
edges(because these cause cycles).

Running Time Analysis

Total number of edges considered by this algorithm in worst case is |E|.
That means, the maximum number of stages is |E|. Now we need to compute the RT of each stage. In
each stage an edge with lowest cost is selected and being checked for not causing cycle. Thus, if
minHeap of edges is used then finding next edge takes up O(log|E|). Therefore, total RT is
O(|E|log|E|). Notice that if E=O (|V|2), then RT is O (|E|log|V|).

Remarks: If the weight of all the edges of a graph G is unique, then only one minimum spanning tree
exists for that graph.
If the weights of all the edges of a graph G are not unique, then the graph might have only one
minimum spanning tree or more than one also which are structurally different.

Single Source Shortest Path Algorithm

The problem is about to computing shortest path to every other vertex from a given starting vertex
in a directed graph.

Unweighted Shortest Path Algorithm

This is efficiently done using BFS algorithm.
dist[s] = 0;
enqueueQ(s);
while(!isEmptyQ())
{
Vertex v = dequeue (Q);
for each Vertex w adjacent to v
{
if(dist[w] = = INFINITY)
{

info@[Link] ©Copyright reserved. Web:[Link] 40

 Greedy Techniques

dist[w] = dist[v] + 1;
path [w] = v;
enqueueQ (w);
}
}
}

Running Time Analysis

Assume graph is represented using adjacency list.
As it can be clearly seen that the inner ‘for’ loop processes each adjacency vertex of vertex v, that
means the inner loop runs for number of adjacent vertices in worst case for each graph vertex.
Thus,
RT of processing v1 is = O(1) + |e1|, e1 is set of v ’s adjacent edges.
RT of processing v2 is = O (1) + |e2|, e2 is set of v2’s adjacent edges.
( ) ( ) ( ) ( ) ( ) ( ) e e2 en
V
Therefore, RT of the whole algorithm is = O(|V| + |E|).
If the graph were represented using adjacency matrix then the RT would be O(|V|2).
This is because ‘RT of processing each vertex’ now will take O( v ) (each array element of the
corresponding row has to be searched).

Weighted Shortest Path Algorithm (Dijkstra’s Algorithm)

Dijkstra’s algorithm proceeds in stages. At each stage this algorithm selects a vertex v, which has
the smallest dv among all the unknown vertices, and declares that the shortest path from s to v is
known. The remainder of a stage consists of updating the values of dw.
for (; ; )
{
Vertex v = smallest distance unknown vertex;
Known[v] = true;
for each Vertex w adjacent to v
{
if(!known[w])
{
{
//update w
Dist. [w] = dist. [v] + Cvw;
Path [w] = v;
}
}
}
}

Example: The following diagram illustrates state of graph just after declaring V1 as known vertex.
There is an update in cv of V2 and V4 vertices also.

info@[Link] ©Copyright reserved. Web:[Link] 41

 Greedy Techniques

0 2
V INF
V
1 3 10
4

2 2
INF V V V INF
INF
4
5 8
6

V 1 V
INF
INF

0 2
*V C=2
V
1 3 10
4 C=1

2 2
INF V V V INF
INF
4
5 8
6

V 1 V
INF
INF
V1 is Chosen Because it was the Unknown Vertex with Lowest Cost
0 2
*V V C=2
1 3 10
4
C =1

C=3 V 2 *V 2
V C=3

4
5 8 6

V 1 V
C=9 C=5
Left V4 is Made Known

0 2
V C=2
V
1 3 10
4
C=1
2 2
C=3 V V V C=3
INF
4
5 8
6

V 1 V
C=9 C=5
Right V2 is Made Known

info@[Link] ©Copyright reserved. Web:[Link] 42

 Greedy Techniques

0 2
V V C=2
1 3 10
4
C=1

C=3 V 2 2
V V C=3

4
5 8
6

V 1 V
C=9 C=5
Left V5 is Made Known
0 2
V V C=2

1 3 10
4
C=1
2 2
C=3 V V V C=3

4
5 8
6

V 1 V
C=8 C=5
Right V3 is Made Known

0 2
V V C=2

1 3 10
4
C=1

C=3 V 2 2
V V C=3

4
5 8
6
V 1 V
C=6 C=5
Left V7 is Made Known
0 2
V C=2
V
1 3 10
4
C=1
2 2
C=3 V V V C=3

4
5 8
6

V 1 V
C=6 C=5
Right V6 is Made Know

Running Time Analysis

info@[Link] ©Copyright reserved. Web:[Link] 43

 Greedy Techniques

Each stage of the algorithm considers exactly one vertex whose cost is lowest to be marked as
known. That means algorithm will consist of |V| stages. Now we need to analyze RT of each stage. In
general MinHeap is used for implementing this algorithm efficiently. Minheap is implemented for
vertex cost, and then surely root node will always be the next vertex to be picked up by algorithm.
DeleteMin will return the vertex having the lowest cost. And decrease key can be used for updating
the Cw. Thus, if graph is represented using adjacency list then;
The RT of for loop for processing vertex v1 is = log|V| + |e1|log|V|
The RT of for loop for processing vertex v2 is = log|V| + |e2|log|V|
Therefore, total RT is = |V|log|V| + |E|log|V| = (|E| + |V|)log|V|.
However, if graph is represented using adjacency matrix, then
RT is = |V|log|V| + |V|2log|V| = O (|V|2log|V|).

Bellman Ford Algorithm

Bellman Ford algorithm consider negative weight edge. The Bellman Ford algorithm returns a
Boolean value indicating whether or not there is a negative weight cycle that is reachable from the
source. If there is such a cycle, the algorithm indicates that no solution exists. The Bellman Ford
algorithm is as follows:
BELLMAN-FORD (G,W,S)
IHTTIALIZE_SINGLE_SOURCE(G,S)
for i to V G
do for each edge (u v)ϵ [G]
do RELAX (u,v,w)
do for each edge (u v)ϵ [G]
do if d[v] > d[u] + w(u,v)
the returns FALSE
return TRUE
Now we give an example of Bellman Ford algorithm as follows.

r r
(A) g ( ) g

2 2

s s
2 2

y z y z

info@[Link] ©Copyright reserved. Web:[Link] 44

 Greedy Techniques

r
( ) g r
(D) 2 g

2
2
s
s
2 2

2
y z 2
y z

r
( ) 2 g

s
2

2
2
y z

Running Time Analysis

The Bellman Ford algorithm runs in time O(VE), since the initialization in line 1 take O(V) time, each
of the |V| 1 pass over the edges in lines 2-4 takes O(E) time, and the for loop of line 5-7 takes O(E)
time.

Optimal Merge Patterns

 Given ‘n’ sorted files of some order are to be merged. The optimal merge pattern follows the
procedure.
 Let the given set of files x1, x2, x3, and x4 are to be merged, we first merge x1 and x2 to get a file
y1. Then we could merge y1 and x3 to get y2. Finally, we could merge y2 and x4 to get the desired
sorted file.
 Alternatively, we could first merge x1 and x2 to get y1, then merge x3 and x4 get y2. Finally
merge y1 and y2 get the desired sorted file.
 Given n sorted files, there are many ways in which to pair-wise merge them into a single sorted
file. Different pairings require differing amounts of computing time.
 The problem is that of determining an optimal way (one requiring the fewest comparisons) to
pair-wise merge n sorted files.
 Since this problem calls for an ordering among the pairs to be merged, it fits the ordering
paradigm.
 Merging an n-record file and an m-record file requires (n+m) record moves.
 At each step, merge the two smallest size files.

info@[Link] ©Copyright reserved. Web:[Link] 45

 Greedy Techniques

Example: onsider the following files (x ….x ) with size (2 ) the greedy method
generate the following merge pattern:
Merge x4 and x3 to get z1 (|z1|=15), merge z1 and x1 to get z2 (|z2|=35), merge x2 and
x5 to get z3 (|z3|=60), and merge z2 and z3 to get the answer z4.
The total number of record moves is 205.
 This type of merge pattern is called as a two-way merge pattern (each merge step
involves the merging of two files). The two-way merge pattern can be represented by
binary merge tress.
 The leaf nodes are drawn as squares and represent the given files. These nodes are
called external nodes. The remaining nodes are drawn as circles and are called
internal nodes.
 Each internal node has exactly two children, and it represents the file obtained by
merging the files represented by its two children. The number in each node is the
length (i.e., the number of records) of the file represented by that node.

Algorithm to Generate a Two-Way Merge Tree

Treenode = record {
Treenode* i child; Treenode* rchild;
Integer weight;
};
1. Algorithm Tree(n)
2. {
3. For(i = 1 to n) do
4. {
5. Pt: = new Treenode; // Get a new tree node
6. (pt ichild): = Least (list) i // Merge two trees with
7. (Pt rchild): = Least (list);// small lengths
8. (Pt-weigh): = ((Pt Lchild) weight)
9. + ((Pt rchild) weight))
10. Insert (list, Pt);
11. }
12. Return Least (list);// Tree left in fist is the merge tree
13. }

 The greedy method to generate merge trees also works for the case of k-ary merging.
 In this case the corresponding merge tree is a k-ary tree. Since all internal nodes must have
degree k, for certain values of n there is no corresponding k-ary merge tree.
 For example, when k = 3, there is no k-ary merge tree with n = 2 external nodes. Hence, it is
necessary to introduce a certain number of dummy external nodes. Each dummy node is
assigned a qi, of zero. This dummy value does not affect the weighted external path length of the
resulting k-ary tree.
 The greedy rule to generate optimal merge trees is: At each step choose k sub-trees with least
length for merging

Huffman Codes

info@[Link] ©Copyright reserved. Web:[Link] 46

 Greedy Techniques

 An application of binary tree with minimal weighted external path length is to obtain an optimal
set of codes for messages ….. n .
 Each code is a binary string that is used for transmission of the corresponding message. At the
receiving end the code is decoded using a decode tree. A decode tree is a binary tree in which
external node represent messages.
The Binary Merge Tree
T q q

q q

 The binary bits in the code word for a message determine the branching needed at each level of
the decode tree to reach the correct external node.
 If we interpret a zero as a left branch and a one as a right branch then the decode tree of the
above Diagram corresponds to codes 000, 001, 01, and 1 for messages M1, M2, M3, and M4
respectively. These codes Huffman codes.
 The cost of decoding a code word is proportional to the number of bits in the code. This number
is equal to the distance of the corresponding to the external node from the root node.
Huffman Code

info@[Link] ©Copyright reserved. Web:[Link] 47

 "Success is a lousy teacher. It seduces
smart people into thinking they can't lose."

4
….Bill Gates
CHAPTER

Dynamic Programming

Learning Objectives
After reading this chapter, you will know:
1. Idea of Dynamic Programming
2. Traveling Salesperson Problem (TSP)
3. Matrix Chain Multiplication Algorithm
4. 0/1 Knapsack
5. Optimal Binary Search Trees (OBST)
6. Longest Increasing Subsequences
7. Knapsack with Repetition
8. Memoization

Introduction
In the preceding chapters we have seen some elegant design principles. Such as divide-and conquer,
graph exploration, and greedy choice. That yield definitive algorithms for a variety of important
computational tasks. The drawback of these tools is that they can only be used on very specific types
of problems. We now turn to the two sledgehammers of the algorithms craft, dynamic programming
and linear programming, techniques of very broad applicability that can be invoked when more
specialized methods fail. Predictably, this generality often comes with a cost in efficiency.
 Dynamic programming is an algorithm design method that can be used when the solution to a
problem can be viewed as the result of a sequence of decisions
 For any problem, it is not possible to make stepwise decisions (based only on local information)
in such a manner that the sequence of decisions made is optional
 One way to solve problem for which it is not possible to make a sequence of stepwise decisions
leading to an optimal decision sequence is to try all possible decision sequences.
 In dynamic programming an optimal sequence of decisions is obtained by making explicit
appeal to three principle of optimality.
 Principle of optimally: The principle of optimality states that an optimal sequence of decision
has the property that whatever the initial state and decision are, the remaining decisions must
constitute an optimal decision sequence with regard to the sate resulting from the first decision.
 The difference between the greedy method and dynamic programming is that in the greedy
method only one decision sequence is ever generated. In dynamic programming many decision
sequences may be generated.

info@[Link] ©Copyright reserved. Web:[Link] 48

 Dynamic Programming

Idea of Dynamic Programming

In divide and conquer we break the whole problem into sub-problems. Then solve the individual
sub-problem and combine the result of the sub-problems to get the actual result. Sometimes we
have to recalculate the duplicate sub-problem. We do not consider the duplicate problem. Dynamic
programming is a strategy not programming. It calculates one time of same or common problem.
Divide and Conquer is a top down approach, because it divides the whole problem into small
sub-problems. Whereas dynamic programming is a bottom up approach. In dynamic programming
we usually start with the smallest, and hence simplest, sub-instances. By combining their solutions
we obtain the answers to the sub-instances by increasing size, until finally we arrive at the solution
of the original instances.
Now the following algorithm is used to calculate Fibonacci number using dynamic programming.
Fibonacci (n)
{
f is a local array
f[0] = 0
f[1] = 1
For i = 2 to
f[i] = f[i 1]+f[i 2]
return (f[n])
}
Dynamic programming is typically applied to optimization problems. The development of a dynamic
programming algorithm can be broken into a sequence of four steps.
(i) Characterize the structure of an optimal solution
(ii) Recursively define the value of an optimal solution
(iii) Compute the value of the optimal solution in a button up fashion
(iv) Construct an optimal solution from computed information.
Step (i) to (iii) form the basis of a dynamic programming solution to a problem. Step (iv) can be
omitted if only the value of an optimal solution is required.

Traveling Salesperson Problem (TSP)

 Let G = (V, E) be a directed graph with edge costs . The variable is (defined such that >0
for all i and j and t| | where n > 1)
 A tour of G is a directed simple cycle that includes every vertex in V
 The cost of a tour is the sum of the cost of the edges on the tour
 The traveling salesperson problem is to find a tour of minimum cost
2 2
A A B B
3 3
4 1 4
1
2 2 2 2 E E
3 3
2 2 4 4
C C2 D
2
D
For all (i, j) ϵ E
dist(i, j, 0) = l(i, j)
for k = 1 to n

info@[Link] ©Copyright reserved. Web:[Link] 49

 Dynamic Programming

for i = 1 to n
for j = 1 to n
dist (i, j, k) = min{dist (i, j, ) + dist(k, j, ), dist (i, j, )}

Some of the applications of Traveling sales Person problem are:

1. Suppose we have to route a postal van to pick up mail from mail boxes located at n different
sites.
 An n + 1 vertex graph can be used to represent the situation. One vertex represents the post
from which the postal van starts and to which it must return.
 Edge <i, j> is assigned a cost equal to the distance from site i to site j.
 The route taken by the postal van is a tour, and we are interested in finding tour of minimum
length.
2. Suppose we wish to use a robot arm to tighten the nuts on some piece of machinery on an
assembly line.
 The arm will start from is initial position, successively move to each of the remaining nuts,
and return to the initial position.
 A minimum-cost tour will minimize the time needed for the arm to completer its task (note
that only total arm movement time is variable; the nut tightening time is independent of the
tour).
3. Consider a production environment in which several commodities are manufactured on the
same set of machines.
 The manufacture proceeds in cycles. In each production cycle, n different commodities are
produced.
 When the machines are changed from production of commodity i to commodity j a
changeover cost r, is incurred.
 It is desired to find a sequence in which to manufacture these commodities. This sequence
should minimize the sum of change over costs (the remaining production costs are sequence
independent).

Matrix Chain Multiplication Algorithm

Matrix multiplication is associative
So,
(AB)C=A (BC)
Two matrices can be multiplied if the number of columns of the first matrix is equal to the number
of rows of the second matrix. Suppose two matrices A and then the resultant
matrix would be . We also know that the upper bound of matrix multiplication is and
lower bound is .
The main objective of the matrix chain multiplication is to optimize (minimize) the number of scalar
multiplications to obtain the result of the multiplication of the chain of the matrices
say … .
Now consider an example where we multiply a chain of three matrices. Say A, B, C
A B C
100 x 5 5 x 50 100 x 50
Case 1:

info@[Link] ©Copyright reserved. Web:[Link] 50

 Dynamic Programming

Case 2:

Thus computing the product as rather than A (BC) reduces the number of scalar
multiplications by ( ) - a significant improvement.

The matrix chain multiplication problem can be stated as follows

Given a chain〈 … 〉 of n matrices where for i=1, …. matrix Ai has dimension fully
parenthesize the product … in a way that minimizes the number of scalar multiplications.

Counting the number of parenthesizations

P(n) denotes the number of alternate parenthesis of a sequence of n matrices. Since we split a
sequence of n matrices between and atr s r a y …. and then
parenthesize the two sub-sequences independently, we obtain the recurrence.

{
∑

The solution of this recurrence is

r [ ] st ata u r.
The number of solutions are thus exponential in n, and the brute force method of exhaustive search
is therefore a poor strategy for determining the optimal parenthesization of a matrix chain.
Let be the minimum number of scalar multiplications needed to compute matrix the cost
of the cheapest way to compute ….. would be
We can define recursively as follows:
If i = j, then it contains just one matrix . So no scalar multiplication is necessary to compute the
product. Thus,
r ….. 3.
Now if i > j the is minimum if we place a parenthesis between and . So is
minimum if computing the sub-product …. a plus the cost of multiplying the matrices
together.
…. take number of scalar multiplications.
T ss va u s ar ….. – 1.
So the cost of parenthesizing the product … . becomes

If we use the recursive algorithm then it will take exponential time – no better than the brute force
method of checking each way of parenthesizing the product. So we use dynamic programming
approach.
We know has the dimension for … . . . . Let P[n]be an array of length n + 1 which
stores the dimension of the array, …. …. auxiliary table for storing m[i ,j] cost …. ..
auxiliary table that records which index of k achieved the optimal cost in computing .

info@[Link] ©Copyright reserved. Web:[Link] 51

 Dynamic Programming

MATRIX CHAIN_ORDERED (P)

n length [P] – 1
for l 1 to n
do m[I, j] 0
for l 2 to n
do
for i 1 to n –l+1
do

m[I, j]
for t
do
if
then

Return m and
The algorithm first computes for … . when length of the sequence is 1. It then
computes for … (the minimum cost for chains of length 2) during first execution
of the loop (for t . The second time through it computes for i …. -2 (the
minimum cost for chains of length 3). And so forth. At each step, the cost computed depends
only on table entries and already computed.

Time Complexity
A simple inspection of the nested loop structure of MATRIX_CHAIN_ORDER yields a running time of
for the algorithm. There is nested for loop of depth 3. The loop indices a take on at
most n values.

0/1 KNAPSACK
 Given: A set S of n items, associated with each item i having
wi = A positive weight
bi = A profit
 Goal: Choose items with maximum total profit but with weight at most W.
 If we are not allowed to take fractional amounts then this is the 0/1 knapsack problem
 r ‘ ’ at s t t ss t t t a sa a ‘ ’ at s t t ts t .
In this case, we let T denote the set of items we take

Objective:
ax z ∑

Constraint:
∑w

Example: v A set S of n items, with each item i having

info@[Link] ©Copyright reserved. Web:[Link] 52
 Dynamic Programming

bi- A s t v “ r t”
wi- A s t v “w t”
Goal: Choose items with maximum total benefit but with weight at most W
Given

Weight 4 kg 2 kg 2 kg 6 kg 2 kg
Profit $20 $3 $6 $25 $80
Solution: Item 5 ($80, 2 in)
Item 3 ($6, 2 in)
Item 1 ($20, 4 in)

Example: Consider another knapsack instance where n = 3(w1, w2, w3) = ( 2, 3, 4) and(P1, P2,
P3)=(1, 2, 5) and m = 6 for these data we have
} }
} 3 3 }
3 3 } }
3 }
Now the pair (3, 5) has to be eliminated from as a result of the purging rule
When generating the we can also purge all pairs (P, W) with W >m

Knapsack Algorithm
1. Algorithm DKP(p, w, n, m)
2. {
3. }
4. for i=1 to do
5. {
6. { | ϵ a }
7. r ur ( )
8. }
9. ast a r
10. (PY, WY) w w r st ar st
11. Any pair in su t at
12. t x
13. s x
14. Tra a r x ….x
15. }
Reliability Design
 The problem of Reliability Design is to design a system that is composed of several devices
connected in series.
 Let r, be the reliability of device Di (that is, r, is the probability that device I will function
properly).

info@[Link] ©Copyright reserved. Web:[Link] 53

 Dynamic Programming

 The reliability of the entire system is r . Even if the individual devices are very reliable i.e., the
ri’s ar v ry s t t r a ty t syst ay t v ry .
 For example, if n = 10 and r = 0.99, 1 < i < 10, then r, = 0.904.
 The solution is to duplicate copies of the devices. Multiple copies of the same device type are
connected in parallel as shown below.

Multiple Device Connected in Parallel in Each Stage

Stage 1 Stage 2 Stage 3 Stage n
D1 D2 D3 Dn
D1 D2 D3 Dn
D1 D2 D3 Dn

 If stage i contains m, copies of device D,, then the probability that all m, have a malfunction is
r . Hence the reliability of stage I becomes 1 – r
 Consider if r = 0.99 and m = 2 the stage reliability becomes 0.9999. In any practical situation, the
stage reliability is a little less than 1 r
 The problem is to use device duplication to maximize reliability.
 Let be the cost of each unit of device i and let c be the maximum allowable cost of the system
being designed. We wish to solve the following maximization
Problem:
Maximize
Where is the reliability and is the number of devices

Optimal Binary Search Trees (OBST)

 Given a fixed set of identifiers, a binary search tree can be organized in many ways
 The problem of OBST is to organize a BST with the given set of Identifiers such the cost of finding
an identifier is Minimum
 Let p(i) be the probability with which we search for a.
 Let q(i) be the probability that the identifier x being searched for is such that
a x a .
 In obtaining a cost function for binary search trees, it is useful to add a fictitious node in place of
every empty sub tree in the search tree. Such nodes, called External nodes which are denoted as
square
 All other nodes are internal nodes, which are denoted as circle
 If a binary search tree represents n identifiers , then there will be exactly n internal nodes and
n + 1 (fictitious) external node
 Every internal node represents a point where a successful search may terminate
 Every external node represents a point where an unsuccessful search may terminate

info@[Link] ©Copyright reserved. Web:[Link] 54

 Dynamic Programming

r r

w t

t
w

(a) (b)

Binary Search Trees with External Nodes Added

 A successful search terminates at an internal node
 Unsuccessful searches terminate with t = 0 (i.e., at an external node)
 Applying dynamic programming to the problem of optimal binary search tree, we view the
construction of such a tree as the result of a sequence of decisions and then observe that the
principle of optimality holds when applied to the problem state resulting from a decision
a

r
An optimal binary search tree with root a a as t a r as r t
Example
Consider the following set of identifier (do, if, while)
The Possible binary search trees can be formed as follows
w

a
w

info@[Link] ©Copyright reserved. Web:[Link] 55

 Dynamic Programming

The cost I unction for a Optimal Binary search Tree can be given as follows
} w
w r v w
a w r
Algorithm for OBST
1. Algorithm OBST(p, q, n)
2. {
3. For i = 0 to n – 1 do
4. {
5. w r
6. w
7. r
8.
9. }
10. w r
11. r t t a tr ss w t s
12. r t
13. {
14.
15. w[i, j]=w[i, ] +p[j]+q[j]
16. r
17. w
18. r
19. }
20. wr t w r
21. }

Sets and Disjoint Set Union

A set is a collection of ordered elements.
Consider n = 10, the elements are partitioned into three disjoint sets, }.
}a 3 }.

The Operations on these sets are

1. Disjoint set Union: If a are two disjoint sets, then their union S U All elements x such
that x is in r T us }.
2. Find (i): Given the elements I, find the set containing i. thus 4 is in set , and 9 is in set

info@[Link] ©Copyright reserved. Web:[Link] 56

 Dynamic Programming

1 5

8 9
7 5 1 2 10

2 10 7 9
8
r

1. Tree Representation of Sets

5 3
1

9 2 10 4 6
7 8

2. Data Representation for

3

3. Array Representation of
t [1] [2] [3] [4] [5] [d] [7] [8] [9] [10]
P 3 3 1 1 1 5

Simple Algorithm for Union

1. Algorithm Simple Union (i, j)
2. {
3. P [i] = j;
4. }

Simple Algorithm for Find

1. Algorithm Simple Find (i)
2. {
3. While (p [i] > 0) do i: = p [i];
4. Return i;
5. }

Union Algorithm with weighting rule

Algorithm weighted Union (i, j)
1. {
info@[Link] ©Copyright reserved. Web:[Link] 57
 Dynamic Programming

2. Temp: = p [i] + p [j];

3. If (p [i]> p [j]) then
4. {
5. P [i]: = j; p [j]: = temp;
6. }
7. Else
8. {
9. P [j] : = i; p [i] = temp;
10. }
11. }

Collapsing rule
If j is a node of the path from I to its root p [i] root [i], then set p [j] to root [i].
Find algorithm with collapsing rule
1. Algorithm collapsing find (i)
2. {
3. R: = i;
4. While (p [r]>0) do r = p [r];
5. While (i r) do
6. {
7. S = p [i] p [i] = r; i: = s;
8. {
9. Return r;
10. }

Longest Common Subsequences

In the longest increasing subsequence problem, the input is a sequence of numbers a … . . a . A
subsequence is any subset of these numbers taken in order, of the form a a … a where
, and an increasing subsequence is one in which the numbers are getting
strictly larger. The task is to find the increasing subsequence of greatest length. For instance, the
longest increasing subsequence of 5, 2, 8, 6, 3, 6, 9, 7 is 2, 3, 6, 9:
5 2 8 6 3 6 9 7

The dag of increasing subsequences

info@[Link] ©Copyright reserved. Web:[Link] 58

 Dynamic Programming

5 52 28 86 63 36 69 97 7

In this example, the arrows denote transitions between consecutive elements of the optimal
solution. More generally, to better understand the solution space, let's create a graph of all
permissible transitions: establish a node i for each element a , and add directed edges (i, j)
whenever it is possible for a and a to be consecutive elements in an increasing subsequence, that is,
whenever i < j and a < a .
Notice that (1) this graph G = (V, E) is a dag, since all edges (i, j) have i < j, and (2) there is a one-to-
one correspondence between increasing subsequences and paths in this dag. Therefore, our goal is
simply to find the longest path in the dag!
Here is the algorithm:
r …
L(j) = 1 + max {L(i): (i, j) ϵ E}
Return max L(j)

L(j) is the length of the longest path the longest increasing subsequence ending at j (plus 1, since
strictly speaking we need to count nodes on the path, not edges). By reasoning in the same way as
we did for shortest paths, we see that any path to node j must pass through one of its predecessors,
and therefore L(j) is 1 plus the maximum L(.) value of these predecessors. If there are no edges into
j, we take the maximum over the empty set, zero. And the final answer is the largest L(j), since any
ending position is allowed.
This is dynamic programming. In order to solve our original problem, we have defined a collection
of subproblems } with the following key property that allows them to be solved in a
single pass:
(*) There is an ordering on the subproblems, and a relation that shows how to solve a subproblem
given the answers to “smaller” subproblems, that is, subproblems that appear earlier in the
ordering.
In our case, each subproblem is solved using the relation
ax ϵ }

an expression which involves only smaller subproblems. How long does this step take? It requires
the predecessors of j to be known; for this the adjacency list of the reverse graph , constructible in
linear time, is handy. The computation of L(j) then takes time proportional to the indegree of j,
giving an overall running time linear in |E|. This is at most O( ), the maximum being when the
input array is sorted in increasing order. Thus the dynamic programming solution is both simple
and efficient.
There is one last issue to be cleared up: the L-values only tell us the length of the optimal
subsequence, so how do we recover the subsequence itself? This is easily managed with the same
bookkeeping device we used for shortest paths in Chapter 4. While computing L(j), we should also

info@[Link] ©Copyright reserved. Web:[Link] 59

 Dynamic Programming

note down prev(j), the next-to-last node on the longest path to j. The optimal subsequence can then
be reconstructed by following these backpointers.

Common Subproblems
Finding the right subproblem takes creativity and experimentation. But there are a few standard
choices that seem to arise repeatedly in dynamic programming
1. The input is … . . and a subproblem is ….
x x x x x x x x x x
The number of subproblem is therefore linear
2. The input is x … … x a y … . y . A subproblem is x … … x a y …. y .
x x x x x x x x x x
y y y y y y y y
The number of subproblem is O(mn)
3. The input is x … . . x a a su r sx x ……. x
x x x x x x x x x x
The number of subproblem is
4. The input is a rooted tree. A subproblem is a rooted subtree.

If the tree has n nodes, how many subproblem are there?

’v a r a y u t r t rst tw as s a t t r ar u s rt y

Knapsack with Repetition

Let's start with the version that allows repetition. As always, the main question in dynamic
programming is, what are the subproblems? In this case we can shrink the original problem in two
ways: we can either look at smaller knapsack capacities w W, or we can look at fewer items
(for instance, items … r ). It usually takes a little experimentation to figure out exactly
what works.
The first restriction calls for smaller capacities. Accordingly, define
K(w) = Maximum value achievable with a knapsack of capacity w.
Can we express this in terms of smaller subproblems? Well, if the optimal solution to K(w) includes
item i, then removing this item from the knapsack leaves an optimal solution to K(w w ). In other
words, K(w) is simply K(w w ) + v , for some i. We don't know which i, so we need to try all
possibilities.
w ax w w v}
r as usua ur v t s t at ax u v ra ty s t s . ’r !T a rt
now writes itself, and it is characteristically simple and elegant

info@[Link] ©Copyright reserved. Web:[Link] 60

 Dynamic Programming

K(0) = 0
For w = 1 to W:
K(w) = max {K( )+v w w}
Return K(W)
This algorithm fills in a one-dimensional table of length W + 1, in left-to-right order. Each entry can
take up to O(n) time to compute, so the overall running time is O(nW). As always, there is an
underlying dag. Try constructing it, and you will be rewarded with a starting insight: this particular
variant of knapsack boils down to finding the longest path in a dag!

Knapsack without repetition

On to the second variant: what if repetitions are not allowed? Our earlier subproblems now become
completely useless. For instance, knowing that the value K(w w ) is very high doesn't help us,
because we don't know whether or not item n already got used up in this partial solution. We must
therefore refine our concept of a subproblem to carry additional information about the items being
used. We add a second parameter, :
K(w, j) = maximum value achievable using a knapsack of capacity w and items … … . .
The answer we seek is K(W, n).
How can we express a subproblem K(w, j) in terms of smaller subproblems? Quite simple either
item j is needed to achieve the optimal value, or it isn't needed:
K(w, j) = max {K(w w ) +v w }.
(The first case is invoked only is w w.) In other words, we can express K(w, j) in terms of
subproblems K(., )
The algorithm then consists of filling out a two-dimensional table, with W + 1 rows and n + 1
columns. Each table entry takes just constant time, so even though the table is much larger than in
the previous case, the running time remains the same, O(nW). Here's the code.
Initialize all K(0, j) = 0 and all K(w, 0) = 0
for j = 1 to n:
for w = 1 to W:
if w > w: K(w, j) = K(w, j 1)
else: K(w, j) = max{K(w; j 1);K(w w ; j 1) + v }
return K(W, n)

Memoization
In dynamic programming, we write out a recursive formula that expresses large problems in terms
of smaller ones and then use it to fill out a table of solution values in a bottom-up manner, from
smallest subproblem to largest.
The formula also suggests a recursive algorithm, but we saw earlier that naive recursion can be
terribly inefficient, because it solves the same subproblems over and over again. What about a more
intelligent recursive implementation, one that remembers its previous invocations and thereby
avoids repeating them?
On the knapsack problem (with repetitions), such an algorithm would use a hash table (recall
Section 1.5) to store the values of K(.) that had already been computed. At each recursive call
requesting some K(w), the algorithm would first check if the answer was already in the table and
then would proceed to its calculation only if it wasn't. This trick is called memoization:
A hash table, initially empty, holds values of K(w) indexed by w

info@[Link] ©Copyright reserved. Web:[Link] 61

 Dynamic Programming

function knapsack(w)
if w is in hash table: return K(w)
K(w) = max{knapsack(w w v w w}
insert K(w) into hash table, with key w
return K(w)
Since this algorithm never repeats a subproblem, its running time is O(nW), just like the dynamic
program. However, the constant factor in this big-O notation is substantially larger because of the
overhead of recursion.
In some cases, though, memoization pays off. Here's why: dynamic programming automatically
solves every subproblem that could conceivably be needed, while memoization only ends up solving
the ones that are actually used. For instance, suppose that W and all the weights w are multiples of
100. Then a subproblem K(w) is useless if 100 does not divide w. The memoized recursive
algorithm will never look at these extraneous table entries.

Shortest Paths
2 2
A A B B
1 1 A 4
5
S S5 15 T1 T
5

2 2 1 1
C C D3 D
3

We started this chapter with a dynamic programming algorithm for the elementary task of finding
the shortest path in a dag. We now turn to more sophisticated shortest-path problems and see how
these too can be accommodated by our powerful algorithmic technique.

Shortest reliable paths

Life is complicated, and abstractions such as graphs, edge lengths, and shortest paths rarely capture
the whole truth. In a communications network, for example, even if edge lengths faithfully reflect
transmission delays, there may be other considerations involved in choosing a path. For instance,
each extra edge in the path might be an extra “hop” fraught with uncertainties and dangers of packet
loss. In such cases, we would like to avoid paths with too many edges. Illustrates this problem with a
graph in which the shortest path from S to T has four edges, while there is another path that is a
little longer but uses only two edges. If four edges translate to prohibitive unreliability, we may have
to choose the latter path.
Suppose then that we are given a graph G with lengths on the edges, along with two nodes s and t
and an integer k, and we want the shortest path from s to t that uses at most k edges.
Is there a quick way to adapt Dijkstra's algorithm to this new task? Not quite: that algorithm focuses
on the length of each shortest path without “remembering” the number of hops in the path, which is
now a crucial piece of information.
In dynamic programming, the trick is to choose subproblems so that all vital information is
remembered and carried forward. In this case, let us define, for each vertex v and each integer i k,
dist(v; i) to be the length of the shortest path from s to v that uses i edges. The starting values dist
(v; 0) are for all vertices except s, for which it is 0. And the general update equation is, naturally
enough,

info@[Link] ©Copyright reserved. Web:[Link] 62

 Dynamic Programming

st v st u uv }

All-Pairs Shortest Paths

What if we want to find the shortest path not just between s and t but between all pairs of vertices?
One approach would be to execute our general shortest-path algorithm (Since there may be
negative edges) |V| times, once for each starting node. The total running time would then be
| | | | . We'll now see a better alternative, the | | dynamic programming-based Floyd-
Warshall algorithm.
Is there is a good subproblem for computing distances between all pairs of vertices in a graph?
Simply solving the problem for more and more pairs or starting points is unhelpful, because it leads
right back to the | | | | algorithm.
One idea comes to mind: the shortest path u w w v between u and v uses some
number of intermediate nodes possibly none. Suppose we disallow intermediate nodes altogether.
Then we can solve all-pairs shortest paths at once the shortest path from u to v is simply the direct
edge (u, v), if it exists. What if we now gradually expand the set of permissible intermediate nodes?
We can do this one node at a time, updating the shortest path lengths at each stage. Eventually this
set grows to all of V, at which point all vertices are allowed to be on all paths, and we have found the
true shortest paths between vertices of the graph!
More concretely, number the vertices in V as … }, and let dist(i, j, k) denote the length of the
shortest path from i to j in which only nodes … } can be used as intermediates. Initially, dist
(i, j, 0) is the length of the direct edge between i and j, if it exists, and is otherwise.
What happens when we expand the intermediate set to include an extra node k? We must
reexamine all pairs i, j and check whether using k as an intermediate point gives us a shorter path
from i to j. But this is easy: a shortest path from i to j that uses k along with possibly other lower-
numbered intermediate nodes goes through k just once (why? because we assume that there are no
negative cycles). And we have already calculated the length of the shortest path from i to k and from
k to j using only lower-numbered vertices:

s
Thus, using k gives us a shorter path from i to j if and only if
dist(i, k, ) + dist(k, j, ) < dist(i, j, )
in which case dist(i, j, k) should be updated accordingly.
Here is the Floyd – Warshall algorithm and as you can see, it takes | | time.
For i = 1 to n
For j = 1 to n
dist (i, j, 0) =
Independent sets in Trees
A subset of nodes S ⊂ V is an independent set of graph G = (V, E) if there are no edges between
them. For instance, the nodes {1, 5} form an independent set, but nodes {1, 4, 5} do not, because of
the edge between 4 and 5. The largest independent set is {2, 3, 6}. Like several other problems we
have seen in this chapter (knapsack, traveling salesman), finding the largest independent set in a
graph is believed to be intractable. However, when the graph happens to be a tree, the problem can

info@[Link] ©Copyright reserved. Web:[Link] 63

 Dynamic Programming

be solved in linear time, using dynamic programming. And what are the appropriate subproblems?
Already in the chain matrix multiplication problem we noticed that the layered structure of a tree
provides a natural definition of a subproblem as long as one node of the tree has been identified as a
root.
So here's the algorithm: Start by rooting the tree at any node r. Now, each node defines a subtree the
one hanging from it. This immediately suggests subproblems:
I(u) = Size of largest independent set of subtree hanging from u:

On Time and Memory

The amount of time it takes to run a dynamic programming algorithm is easy to discern from the
dag of subproblems: in many cases it is just the total number of edges in the dag! All we are really
doing is visiting the nodes in linearized order, examining each node's inedges, and, most often, doing
a constant amount of work per edge. By the end, each edge of the dag has been examined once.
But how much computer memory is required? There is no simple parameter of the dag
characterizing this. It is certainly possible to do the job with an amount of memory proportional to
the number of vertices (subproblems), but we can usually get away with much less.
The reason is that the value of a particular subproblem only needs to be remembered until the
larger subproblems depending on it have been solved. Thereafter, the memory it takes up can be
released for reuse.
For example, in the Floyd-Warshall algorithm the value of dist(i, j, k) is not needed once the
dist(., ., k +1) values have been computed. Therefore, we only need two |V| × |V| arrays to store the
dist values, one for odd values of k and one for even values: when computing dist(i, j, k), we
overwrite dist(i, j, k 2).

Our final goal is I(r).

Dynamic programming proceeds as always from smaller subproblems to larger ones, that is to say,
bottom-up in the rooted tree. Suppose we know the largest independent sets for all subtrees below
a certain node u; in other words, suppose we know I(w) for all descendants w of u. How can we
compute I(u)? Let's split the computation into two cases: any independent set either includes u or it
doesn't.

u ax { ∑ w ∑ w }

If the independent set includes u, then we get one point for it, but we aren't allowed to include the
children of u therefore we move on to the grandchildren. This is the first case in the formula. On the
other hand, if we don't include u, then we don't get a point for it, but we can move on to its children.
The number of subproblems is exactly the number of vertices. With a little care, the running time
can be made linear, O(|V| + |E|).

1 1 2 2

5 5 6 6

3 3 4 4

info@[Link] ©Copyright reserved. Web:[Link] 64

 Dynamic Programming

r r

u u

info@[Link] ©Copyright reserved. Web:[Link] 65

 "I don't measure a man's success by how
high he climbs but how high he bounces

5
when he hits bottom."
CHAPTER
….George S. Patton

Hashing

Learning Objectives
After reading this chapter, you will know:
1. Hashing
2. Floading
3. Conflict Resolution Techniques
4. Double Hashing
5. Separate Chaining
6. Coalesced Chaining

Hashing
Hashing is a different kind of searching mechanism to search a table for a given key value: In
hashing, the record for a key value, “K”, is directly referred by calculating the address from the key
value.

Hash Function
Consider there are ‘n’ keys such that all key values are between ‘a’ and ‘b’. These ‘n’ element are to
be stored in a hash table of size ‘M’, where (M n) an elements with key value ‘K’ will be put in slot
‘j’ of the hash table, if j = h(k); ‘h’ is called the hash function. The domain of the hashing function
namely, the interval [a, b] is usually very wide. For example, h(K) may be defined as k mod M where
1 h(k) M for any integer ‘k’. Ideally, hash functions should result in a unique value when
applied to any key but such a hash function is not practically available.
An ideal hash function should distribute the keys uniformly over the range (0, M ). In other
words generating an address ‘x’ (where x M ) for a given key ‘k’ should be ( ). An hash
function may return same address for different keys, this situation is called Collision or Conflict.
There are many different hash functions and collision resolution techniques available, some of them
have been discussed in the next section.

The Division Method

In this method the key is divided by ‘M’ and the remainder is taken to be the address. Thus the hash
function ‘h’ is given by
h(k) k mod M
Generally M is chosen as non-prime odd integer having no divisor less than ‘ 9’ or another good
choice ‘M’ is a prime number.

info@[Link] ©Copyright reserved. Web:[Link] 66

 Hashing

The Mid Square Method

In this method, the key is squared and a portion of the squared value is selected from the middle
which is chosen as the address. Suppose that if digit address is to be generated from a p digit key. To
do so, the p-digit key is first squared to yield a 2p digit value. The q digit address then is selected
from the middle of this 2p-digit result. For example, let p 4, q 3 and the key be ‘327 ’. Square of
the 327 is ‘ 69944 ’. We chose 994 is the middle as the address.

Floading
Suppose we have p-digits key from which q digits address are to be generated. In this method, the
digits of a key are partitioned into groups of ‘q’ digits from the right. These groups are then added to
the right most ‘q’ digits and the sum is selected as the address. For example suppose from a ‘8’ digit
number, 39427829 and we have to generate a 3 digit number by partitioning this number into three
groups. 39 427 829
Adding 39, 427, 829 we get 1295. Selecting the last three digits, we get the desired address as 295.

Conflict Resolution Techniques

Conflict or collision occurs when the hash function returns the same address for different key
values. We must know how to cope up with such situations. There are two board classes called open
addressing and chaining used to handle conflicts.

Linear and Quadratic Probing

In this open addressing method, if the hash address is found to be already occupied by an element
then the indices following the hash index are sequentially examined to locate the first empty
position. The algorithm of inserting element into a hash table, and searching an element from hash
table is given below. Here we assume an array ‘A’ to be of size m storing the key field. Another array
‘T’ is used to indicate whether an element of ‘A’ is empty or not. It is assumed that if the i element
of ‘T’ is false then the i element of ‘A’ is empty.

Algorithm
Insert element into hash table using linear probe.
int insert Linear Probe (int k)
{
int i = 0, j;
j = hash (k);
do
{
if (T[j] = false)
{
A[j] = k;
T[j] = true;
return j;
}
i++

info@[Link] ©Copyright reserved. Web:[Link] 67

 Hashing

j = (j + i) %m
}
while (i < m)
return ( 1)

Algorithm
Searching an element from hash table using linear probe.
int search Linear Probe(int k)
{
int i = 0, j;
j = hash(k)
do
{
if (A[j] ==k)
{
return j;
}
i++;
j = (j+i)%m;
}
while ((T[j] = = True) && (i < m))
return ;
}
In quadratic probing let k is to be inserted in the hash table and h[k = j]. If A[j] is already occupied
then k has to be inserted at some other locations. In a quadratic probing, the location ‘j’, (j + 1),
(j + 4), (j + 9)& are examined to find out the first empty slot where ‘k’ may be inserted. Thus the
increment in this case i.e., i for i = 1, 2, 3, &

Double Hashing
This method requires two hashing functions f (k) and f (k). The function f (k) is used as a primary
hash function. If the address generated by primary hash function is already occupied by a key, the
function f (k) is evaluated. The second hash function is used to compute the increment to be added
to the address obtained by the first hash function in case of collision. Algorithm to store key in the
hash table using double hashing is shown below.
int store Double Hashing (int k)
{
int j, k, u, i = 0;
j = hash1(k);
u = hash2(k);
do
{
if (T[j] == false)
{
A[j] = k;
T[j] = true;
return j;

info@[Link] ©Copyright reserved. Web:[Link] 68

 Hashing

}
i++
j = ( j + i * u)%m;
}
while (i < m)
return – 1;
}
The search for an element in the array should follow the same path used to store the element.

Separate Chaining
In this method, linked list is maintained to store all elements that hash to the same address. Let the
hash table ‘A’ contain mentries or slots. Each slot contains a pointer to a link list and the list stores
the elements that hash to this slot. Each node in such a list is a self-referential structure containing a
key value and a pointer to the same structure. A typical ‘c’ declaration for a node may be done in the
following manner.
typed of struct node
{
int key;
struct node * next;
}
node;
Then the hash table ‘A’ containing m pointers may be defined as follows node * A [5 ]
while inserting a key ‘k’ using a hash function ‘h’ first h(k)is computed. Let h(k)be ‘i’, i m
then ‘k’ is inserted to the list pointed to by A[i] Therefore each slot in the hash table maintains a
separate chain (i.e. a linked list) to store all elements hashed to that slot. This is why this method is
known as ‘separate chaining’ method.

Example: Let us consider the list given below

(35 ,493,25 ,7 ,7 6, 46)
Suppose A[0, 6] is used as hash table. Let the hash function used be defined as
h(k) mod 7. the hashed addresses generated for the element in ‘ ’, are , 3, 6, , 6, 6,
respectively. So after the insertion into the hash table is looking like as follows:
0 351 71

2
3 493

4
5

6 251 706 146

info@[Link] ©Copyright reserved. Web:[Link] 69

 Hashing

Coalesced Chaining
This technique is similar to linear probe method except that all keys that hash to the same address
are linked together. Each node in the hash table should have an additional field that will either
contain the address of the node holding a synonym or a null link. The node of the home element will
contain the address of the first synonym and this node in-turn will contain the address of the second
synonym and so on. A null link indicates the end of the chain.

Example: Consider a hash table with n buckets, where external (overflow) chaining is used to
resolve collisions. The hash function is such that the probability that a key value is hashed
to a particular bucket is . The hash table is initially empty and K distinct values are
inserted in the table.
(a) What is the probability that bucket number 1 is empty after the K insertion?
(b) What is the probability that no collision has occurred in any of the K insertion?
(c) What is the probability that the first collision occurs at the k insertion?
(A) 2 (C) 4
(B) 3 (D) 6
Solution: Given that all buckets are equally likely. Hash function distributes keys ideally.
(A) Probability that a key goes to a bucket ( )
Probability that a key does not go to a bucket ( )

Probability that bucket number 1 is empty ( )( )...... K times( )

. favourable
(B) Probability ( )
( )
(C) Probability that the first collision occurs at the Kth insertion = * +

info@[Link] ©Copyright reserved. Web:[Link] 70

 Reference Books

Reference Books

1. Data Structure & Algorithm in C

By Mark Allen Weiss

2. Programming Languages
By Ravi Sethi

3. Introduction to Algorithms
By Corman, Rivest

4. Fundamentals of computer Algorithms

By Horowitz

5. ‘C’
By Kernighen and Ritchie

info@[Link] ©Copyright reserved. Web:[Link] 71