Vivekananda: Lecture Notes On

Vivekananda
College
e of Engineering & Technolog
ogy
N
Nehru nagar post, Puttur, D.K. 5742013
Lecture Notes on
15CS43
Design and Analysis
lysis of
Algorithms
(CBCS Scheme)
Prepared by
Mr. Harivinod N
Dept. of Computer
C Science and Engineering,
VCET Puttur
Jan 2017
Module--1 : Introduction to Algorithms

ms
Contents
1. Introduction 4. Important Proroblem Types

1.1. What is an Algo
gorithm? 4.1. Sorting
1.2. Algorithm Speci
ecification 4.2. Searching
ing
1.3. Analysis Framewo
work 4.3. String pro
processing
2. Performance Analysiysis 4.4. Graph Problems
Pro
2.1. Space complexit
xity 4.5. Combinat
natorial Problems
2.2. Time complexityity 5. Fundamental al Data
D Structures
3. Asymptotic Notation ons 5.1. Linear
near Data Structures
3.1. Big-Oh notation
on 5.2. Graphs
3.2. Omega notationon 5.3. Trees
3.3. Theta notation 5.4. Sets andd Dictionaries.
D
3.4. Little-oh notatio
tion
3.5. Mathematical ana
nalysis
Cours
ourse website: www.techjourney.in
Lecture Notes | 15CS43
CS43 – Design & Analysis of Algorithms | Module 1: Introdu
troduction
1. Introduction
1.1. What is an Algorithm??
An algorithm is a finite setet of instructions to solve a particular proble lem. In addition, all
algorithms must satisfy the following
fol criteria:
a. Input. Zero or morore quantities are externally supplied.
b. Output. At least one
on quantity is produced.
c. Definiteness. Eachch instruction is clear and unambiguous. It mus ust be perfectly clear
what should be donone.
d. Finiteness. If wee trace
t out the instruction of an algorithm, the hen for all cases, the
algorithm terminate
ates after a finite number of steps.
e. Effectiveness. Ever
very instruction must be very basic so that it ca can be carried out, in
principle, by a person
per using only pencil and paper. It is not ot enough that each
operation be defini
inite as in criterion c; it also must be feasible.
Algorithm design and analy lysis process - We now briefly discuss a seq
equence of steps one
typically goes through in desig
signing and analyzing an algorithm
• Understanding the Prob oblem - From a practical perspective, the firstrst thing you need to
do before designing an algorithm
al is to understand completely the pr problem given. An
input to an algorithm spec
ecifies an instance of the problem the algorithm
thm solves. It is very
important to specify exactl
ctly the set of instances the algorithm needs to handle.
• Ascertaining the Capab bilities of the Computational Device - Onc nce you completely
understand a problem, you
ou need to ascertain the capabilities of the com
computational device
the algorithm is intended
ded for. Select appropriate model from seq equential or parallel
programming model.
Prerpared by Harivinod N www.techjourney.in Page|1.2

troduction
• Choosing between Exac act and Approximate Problem Solving - The T next principal
decision is to choose betw
tween solving the problem exactly and solving
ing it approximately.
Because, there are importa
rtant problems that simply cannot be solvedd exactly
e for most of
their instances and somee of
o the available algorithms for solving a prob
oblem exactly can be
unacceptably slow because
use of the problem’s intrinsic complexity.
• Algorithm Design Tech chniques - An algorithm design techniquee (or “strategy” or
“paradigm”) is a generall approach
a to solving problems algorithmically
lly that is applicable
to a variety of problemss from
f different areas of computing. They provide
pro guidance for
designing algorithms foror new problems, i.e., problems for which tthere is no known
satisfactory algorithm.
• Designing an Algorithm m and Data Structures - One should pay ay close attention to
choosing data structuress appropriate
a for the operations performed byy the algorithm. For
example, the sieve of Erat
ratosthenes would run longer if we used a linke
ked list instead of an
ion. Algorithms + Data Structures = Program
array in its implementation ams
• Methods of Specifying an Algorithm- Once you have designed an algorithm;
al you need
to specify it in some fashion.
fas These are the two options that are re most widely used
nowadays for specifyingg algorithms.
a Using a natural language hass an a obvious appeal;
however, the inherent ambiguity
am of any natural language makes a concise and clear
description of algorithmss surprisingly difficult. Pseudocode is a mi mixture of a natural
language and programmin ing language like constructs. Pseudocode is usually
us more precise
than natural language, and
nd its usage often yields more succinct algorithm
thm descriptions.
• Proving an Algorithm’s ’s Correctness - Once an algorithm has beenn sspecified, you have
to prove its correctness.. That
T is, you have to prove that the algorithm
hm yields a required
result for every legitimate
te input in a finite amount of time. For some algorithms, a proof
of correctness is quite easy
asy; for others, it can be quite complex. A com
ommon technique for
proving correctness is to use mathematical induction because an alg lgorithm’s iterations
provide a natural sequencece of steps needed for such proofs.
• Analyzing an Algorithm m - After correctness, by far the most importartant is efficiency. In
o algorithm efficiency: time efficiency, indic
fact, there are two kindss of dicating how fast the
algorithm runs, and space
ce efficiency, indicating how much extra memo mory it uses. Another
desirable characteristic of an algorithm is simplicity. Unlike efficieniency, which can be
precisely defined and inve
vestigated with mathematical rigor, simplicity,
ty, like beauty, is to a
considerable degree in the
he eye of the beholder.
• Coding an Algorithm - Most algorithms are destined to be ultimate ately implemented as
computer programs. Impleplementing an algorithm correctly is necessary ry but not sufficient:
you would not like to dim
iminish your algorithm’s power by an inefficie ient implementation.
Modern compilers do provrovide a certain safety net in this regard, especi
ecially when they are
used in their code optimiza
ization mode.

troduction
1.2. Algorithm Specification

tion
An algorithm can be specified
ed in
1) Simple English
2) Graphical representatio
tion like flow chart
3) Programming language
age like c++ / java
4) Combination of above
ve methods.
Using the combination of simple
si English and C++, the algorithm for selection sort is
specified as follows.
In C++ the same algorithm can be specified as follows
Here Type is a basic or user defined

de data type.
Recursive algorithms
An algorithm is said to be recursive
re if the same algorithm is invokedd iin the body (direct
recursive). Algorithm A is said
aid to be indirect recursive if it calls another
er algorithm which in
turn calls A.
Example 1: Factorial computa
tation n! = n * (n-1)!
Example 2: Binomial coefficie
cient computation
Example 3: Tower of Hanoii problem

pr
Example 4: Permutation Gene
nerator

troduction
1.3. Analysis Framework

General framework for analy lyzing the efficiency of algorithms is discuss
ssed here. There are
two kinds of efficiency: timee efficiency and space efficiency. Time efficie
iciency indicates how
fast an algorithm in questionn runs; space efficiency deals with the extra space
s the algorithm
requires.
In the early days of electronic
ic computing, both resources time and space were w at a premium.
Now the amount of extra spac ace required by an algorithm is typically nott oof as much concern,
In addition, the research exper
perience has shown that for most problems, we can achieve much
more spectacular progress in speed than in space. Therefore, followingg a well-established
tradition of algorithm textbook
oks, we primarily concentrate on time efficienc
ency.
Measuring an Input’s Size

It is observed that almost all
ll algorithms
a run longer on larger inputs. For
Fo example, it takes
longer to sort larger arrays,, multiply
m larger matrices, and so on. Therefo
efore, it is logical to
investigate an algorithm's efficiency
ef as a function of some parameterter n indicating the
algorithm's input size.
There are situations, where the choice of a parameter indicating an input ut size does matter.
The choice of an appropriatete size metric can be influenced by operationss of the algorithm in
question. For example, how ow should we measure an input's size for a spell-checking
algorithm? If the algorithm examines individual characters of its inpu put, then we should
measure the size by the numb mber of characters; if it works by processing
ng words, we should
count their number in the inpu
put.
We should make a special note
no about measuring the size of inputs for algorithms
alg involving
properties of numbers (e.g e.g., checking whether a given integer n is prime). For such
ists prefer measuring size by the number b off bits
algorithms, computer scientist b in the n's binary
representation: log n 1. This metric usually gives a better ideaa aabout the efficiency
of algorithms in question.
Units for Measuring Runnin

ing lime
To measure an algorithm's efficiency,
eff we would like to have a metric thahat does not depend
on these extraneous factors.. One possible approach is to count the numbber of times each of
the algorithm's operations iss executed.
e This approach is both excessivelyy difficult
d and, as we
shall see, usually unnecessaryry. The thing to do is to identify the most impportant operation of
the algorithm, called the basasic operation, the operation contributing the most to the total
running time, and compute the number of times the basic operation is execu ecuted.
For example, most sorting algorithms
al work by comparing elements (keys)(ke of a list being
sorted with each other; for suc
uch algorithms, the basic operation is a key com
omparison.
As another example, algorith
rithms for matrix multiplication and polyn
lynomial evaluation
require two arithmetic operatio
tions: multiplication and addition.

troduction
Let cop be the execution timee of an algorithm's basic operation on a partic

ticular computer, and
let C(n) be the number of tim
imes this operation needs to be executed for this
th algorithm. Then
we can estimate the runningg time T(n) of a program implementing this is algorithm on that
computer by the formula:
unless n is extremely large or very small, the formula can give a reasona
nable estimate of the
algorithm's running time.
It is for these reasons that the
he efficiency analysis framework ignores multi
ltiplicative constants
and concentrates on the count nt's order of growth to within a constant mul
ultiple for large-size
inputs.
Orders of Growth
Why this emphasis on the count's
co order of growth for large input sizes?
s? Because for large
values of n, it is the function's
n's order of growth that counts: just look at ta
table which contains
values of a few functions parti
rticularly important for analysis of algorithms.
Table: Values
of several
functions
important for
analysis of
algorithms
Algorithms that require an exponential

ex number of operations are practica
tical for solving only
problems of very small sizes.
Worst-Case, Best-Case, and

d Average-Case Efficiencies
Definition: The worst-casee efficiency
e of an algorithm is its efficiencyy for the worst-case
input of size n, for which thee algorithm
a runs the longest among all possible
le inputs of that size.
Consider the algorithm for seq
equential search.

troduction
The running time of above algorithm

al can be quite different for the same
me list size n. In the
worst case, when there are no matching elements or the first matching element
el happens to
be the last one on the list,, the algorithm makes the largest number of key comparisons
si n: Cworst(n) = n.
among all possible inputs off size
In general, we analyze the algorithm
alg to see what kind of inputs yield thee llargest value of the
basic operation's count C(n) among
a all possible inputs of size n and then compute
c this worst-
case value Cworst (n). The wors orst-case analysis provides algorithm's efficien
ency by bounding its
running time from above. Thu hus it guarantees that for any instance of size n,n the running time
will not exceed Cworst (n), itss running
ru time on the worst-case inputs.
Definition: The best-case efficiency
eff of an algorithm is its efficiency for
or the best-case input
of size n, for which the algorit
rithm runs the fastest among all possible inputs
uts of that size.
We determine the kind of inputs
inp for which the count C(n) will be thee ssmallest among all
possible inputs of size n. Forr example, for sequential search, best-case inp
nputs are lists of size
n with their first elements equ
qual to a search key; Cbest(n) = 1.
The analysis of the best-case
se efficiency is not nearly as important as tha
hat of the worst-case
efficiency. Also, neither the
he worst-case analysis nor its best-case coun unterpart yields the
necessary information about an
a algorithm's behavior on a "typical" or "random"
"ra input. This
information is provided by ave
verage-case efficiency.
Definition: the average-casese complexity of an algorithm is the amountt oof time used by the
algorithm, averaged over alll possible
p inputs.
Let us consider again sequenti
ntial search. The standard assumptions are that at (a) the probability
of a successful search is equ
qual top (0 ≤ p ≤ 1) and (b) the probability ty of the first match
th
occurring in the i position of the list is the same for every i. We can findd tthe average number
of key comparisons Cavg (n) as follows.
In the case of a successfull search,
s the probability of the first match ooccurring in the ith
position of the list is p/n for every
e i, and the number of comparisons mad ade by the algorithm
in such a situation is obviouiously i. In the case of an unsuccessful searc arch, the number of
robability of such a search being (1- p). Therefo
comparisons is n with the prob efore,
Investigation of the average-ccase efficiency is considerably more difficult

ult than investigation
of the worst-case and best-cacase efficiencies. But there are many importortant algorithms for
which the average case efficficiency is much better than the overly pess essimistic worst-case
efficiency would lead us to believe.
be Note that average-case efficiency can
annot be obtained by
taking the average of the wors
rst-case and the best-case efficiencies.

troduction
Summary of analysis framew

ework
• Both time and space efficie
iciencies are measured as functions of the algororithm's input size.
• Time efficiency is measuasured by counting the number of times the algorithm's basic
operation is executed. Space
Sp efficiency is measured by counting the th number of extra
memory units consumed by b the algorithm.
• The efficiencies of somee algorithms
a may differ significantly for input
uts of the same size.
For such algorithms, wee need
n to distinguish between the worst-case,se, average-case, and
best-case efficiencies.
• The framework's primary ry interest lies in the order of growth of thee algorithm's
a running
time (or extra memory uninits consumed) as its input size goes to infinity
ity.
2. Performance Analysis
lysis
2.1 Space complexity

Total amount of computer memory
m required by an algorithm to comple
plete its execution is
called as space complexity of that algorithm. The Space required by an algorithm
al is the sum
of following components
• A fixed part that is independent
ind of the input and output. This inclu
cludes memory space
for codes, variables, constants
co and so on.
• A variable part that depends
de on the input, output and recursion sta
stack. ( We call these
parameters as instance
ce characteristics)
Space requirement S(P) of an algorithm P, S(P) = c + Sp where c is a constant depends
on the fixed part, Sp is the inst
nstance characteristics
Example-1: Consider followin
wing algorithm abc()
Here fixed component depend aracteristics Sp=0

nds on the size of a, b and c. Also instance char
Example-2: Let us considerr the
th algorithm to find sum of array.
re the problem instances are characterized by n, the number of
For the algorithm given here
elements to be summed. Thee space
s needed by a[ ] depends on n. So the spa space complexity can
be written as; Ssum(n) ≥ (n+3)
(n+ n for a[ ], One each for n, i and s.

troduction
2.2 Time complexity

Usually, the execution time oro run-time of the program is refereed as its
it time complexity
denoted by tp (instance chara
aracteristics). This is the sum of the time ta
taken to execute all
instructions in the program.
Exact estimation runtime iss a complex task, as the number of instru truction executed is
dependent on the input data. Also
A different instructions will take differentt ttime to execute. So
for the estimation of the timee complexity
c we count only the number of program
pr steps.
A program step is loosely defined
de as syntactically or semantically meani
aning segment of the
program that has and execut
cution time that is independent of instance characteristics.
c For
example comment has zero steps;
ste assignment statement has one step and so on.
We can determine the stepss needed
n by a program to solve a particularr pproblem instance in
two ways.
oduce a new variable count to the program whhich is initialized to
In the first method we introd
atements to increment count by an appropriat
zero. We also introduce state iate amount into the
program. So when each timee original program executes, the count alsoo incremented
i by the
step count.
lgorithm sum( ). After the introduction of the
Example-1: Consider the algo he count the program
will be as follows.
timate that invocation of sum( ) executes tota

From the above we can estim otal number of 2n+3
steps.
The second method to determ rmine the step count of an algorithm is to bui
uild a table in which
we list the total number of step
teps contributed by each statement. An example
ple is shown below.

troduction
Example-2: matrix addition
The above thod is both exces essively difficult and, usually unnecessary. Th
The thing to do is to
identify the most important operation of the algorithm, called the bas asic operation, the
operation contributing the moost to the total running time, and compute ththe number of times
the basic operation is executed
ted.
Trade-off
There is often a time-space-tr
tradeoff involved in a problem, that is, it can
annot be solved with
few computing time and loww memory consumption. One has to make a compromise
c and to
exchange computing time forfo memory consumption or vice versa, dependingdep on which
algorithm one chooses and how one parameterizes it.
3. Asymptotic Notations
ions
The efficiency analysis frame
mework concentrates on the order of growth th of an algorithm’s
basic operation count as the principal
pr indicator of the algorithm’s efficienc
ncy. To compare and
rank such orders of growth, th, computer scientists use three notations: O(bigO oh), Ω(big
omega), Θ (big theta) and o(lit
(little oh)
3.1. Big-Oh notation

Definition: A function t(n) is said to be in O(g(n)), denoted t(n)∈O(g(n)),)), if t (n) is bounded
above by some constant mul ultiple of g(n) for all large n, i.e., if there eexist some positive
constant c and some nonnegati
ative integer n0 such that
t(n) ≤ c g(n) for all n ≥ n0.

troduction
Informally, O(g(n)) is the sett of

o all functions with a lower or same order of growth as g(n)
Examples:
ormally prove 100n + 5 ∈ O(n2)

As another example, let us for
100n + 5 ≤ 100nn + n (for all n ≥ 5) = 101n ≤ 101n2. (c=101,, n0=5)
Note that the definition gives alues for constants c
es us a lot of freedom in choosing specific val
and n0.
Example: To prove n2 + n = O(n3)
Strategies for Big-O Someti

etimes the easiest way to prove that f(n) = O(g
(g(n)) is to take c to
be the sum of the positive
ve coefficients of f(n). We can usually ig ignore the negative
coefficients.

troduction
3.2. Omega notation

Definition: A function t(n) is said to be in Ω(g(n)), denoted t(n)∈ Ω(g(n)) )), if t(n) is bounded
below by some positive cons nstant multiple of g(n) for all large n, i.e.,, iif there exist some
positive constant c and somee nonnegative
n integer n0 such that
t(n) ≥ c g(n) for all n ≥ n0.
Here is an example of the formrmal proof that n3 ∈ Ω(n2):

n3 ≥ n2 for all n ≥ 0,
i.e., we can select c = 1 and n0 = 0.
Example:
Example: To prove n3 + 4n2 = Ω(n2)
3.3. Theta notation

A function t(n) is said to bee in Θ(g(n)), denoted t(n) ∈ Θ(g(n)), if t (n (n) is bounded both
above and below by some pos ositive constant multiples of g(n) for all largee n,
n i.e., if there exist
some positive constants c1 and
nd c2 and some nonnegative integer n0 such thattha
c2 g(n)
g t(n) c1g(n) for all n n0 .

troduction
Example: n2 + 5n + 7 = Θ(n2)
Strategies for Ω and Θ

• Proving that a f(n) = Ω(g(n
g(n)) often requires more thought.
– Quite often, we have
hav to pick c < 1.
– A good strategy is to pick a value of c which you think will w work, and determine
which value of n0 is
i needed.
– Being able to do a little algebra helps.
– We can sometim imes simplify by ignoring terms of f(n)) with the positive
coefficients.
• The following theorem shows
sho us that proving f(n) = Θ(g(n)) is nothingg new:
Theorem: f(n) = Θ(g(n))
Θ if and only if f(n) = O(g(n)) and f(n)) = Ω(g(n)).
Thus, we just apply the previous
pre two strategies.

troduction

troduction
3.4. Little Oh The function f(n)

f = o(g(n)) [ i.e f of n is a little oh of g off n ] if and only if
lim 0
→
Example:
For comparing the order of growth

gro limit is used
If the case-1 holds good in the

he above limit, we represent it by little-oh.

troduction
3.5. Basic asymptotic Efficien

ficiency Classes
Class Name Comments

troduction
3.6. Mathematical Analysis

sis of Non-recursive & Recursive Algorithms
ithms
Analysis of Non-recursive Algorithms
Al
General Plan for Analyzing the
th Time Efficiency of Nonrecursive Algorithm
hms
1. Decide on a parameterter (or parameters) indicating an input’s size.
2. Identify the algorithm’’s basic operation. (As a rule, it is located inn iinnermost loop.)
3. Check whether the number
num of times the basic operation is execute ted depends only on
the size of an input.. If
I it also depends on some additional proper erty, the worst-case,
average-case, and, if necessary, best-case efficiencies have to t be investigated
separately.
4. Set up a sum express essing the number of times the algorithm’s ’s basic operation is
executed.
5. Using standard formuulas and rules of sum manipulation, either er find a closedform
formula for the countt or,
o at the very least, establish its order of growowth.
Example-1: To find maximu
um element in the given array
Algorithm
Here comparison is the basic

ic operation.
Note that number of comparisrisions will be same for all arrays of size n. Therefore,
Th no need to
distinguish worst, best and ave
verage cases.
Total number of basic operatio
tions (comparison) are,
Example-2: To check whethe

ther all the elements in the given array are distinct
d
Algorithm

troduction
Here basic operation is compa parison. The maximum no. of comparisons hhappen in the worst
th array are distinct and algorithms return tru
case. (i.e. all the elements in the rue).
Total number of basic operatio
tions (comparison) in the worst case are,
Other than the worst case, the

he total comparisons are less than . ( Forr example if the first
two elements of the array are
re equal, only one comparison is computed).
). So
S in general C(n)
2
=O(n )
Example-3: To perform mat
atrix multiplication
Algorithm
Number of basic opera

erations
(multiplications) is
Total running time:

Suppose if we take into accoun
ount of addition; Algoritham also have same nu
number of additions
3
A(n) = n
Total running time:

troduction
Example-4: To count the bit

its in the binary representation
Algorithm
The basic operation is count=c

t=count + 1 repeats no. of times
es
Analysis of Recursive Algori
rithms
General plan for analyzing the time efficiency of recursive algorithms
1. Decide on a parameterter (or parameters) indicating an input’s size.
2. Identify the algorithm’
m’s basic operation.
3. Check whether the number
nu of times the basic operation is exec xecuted can vary on
different inputs of thee same size; if it can, the worst-case, average--case, and best-case
efficiencies must bee investigated
i separately. Set up a recurrence ce relation, with an
appropriate initial cond
ndition, for the number of times the basic operaeration is executed.
4. Solve the recurrence or,
or at least, ascertain the order of growth of its solution.
Example-1
Algorithm
Since the function F(n) is com

mputed according to the formula
ns M(n) needed to compute it must satisfy thee eequality

The number of multiplications

troduction
Such equations are called recu

currence Relations
Condition that makes the alg lgorithm stop if n = 0 return 1. Thus recur urrence relation and
initial condition for the algorit
rithm’s number of multiplications M(n) can be stated as
We can use backward substitu

itutions method to solve this
….
Example-2: Tower of Hanoi oi puzzle. In this puzzle, There are n disks of different sizes that
can slide onto any of three peg
egs. Initially, all the disks are on the first pegg iin order of size, the
largest on the bottom and thehe smallest on top. The goal is to move all the disks to the third
peg, using the second one ass ana auxiliary, if necessary. We can move only ly one disk at a time,
and it is forbidden to place a larger
la disk on top of a smaller one.
The problem has an elegant recursive
re solution, which is illustrated in Figur
ure.
• To move n>1 disks from pegp 1 to peg 3 (with peg 2 as auxiliary),
o we first move recur
cursively n-1 disks from peg 1 to peg 2 (with pe
peg 3 as auxiliary),
o then move the large
rgest disk directly from peg 1 to peg 3, and,
o finally, move recurursively n-1 disks from peg 2 to peg 3 (using peg
p 1 as auxiliary).
• If n = 1, we move the singl
ngle disk directly from the source peg to the des
destination peg.
Figure: Rec
ecursive solution to the Tower of Hanoi puzzle
zle
The number of moves M(n) depends
de only on n. The recurrence equationn is
i
We have the following recurre

rrence relation for the number of moves M(n):

troduction
We solve this recurrence by the

th same method of backward substitutions:
The pattern of the first three sums

su on the left suggests that the next one will
ill be
24 M(n − 4) + 23 + 22 + 2 + 1, and generally, after i substitutions, we get
Since the initial condition iss specified

s for n = 1, which is achieved for i = n - 1, we get the
following formula for the solulution to recurrence,
Alternatively, by counting the

th number of nodes in the tree obtained byy recursive calls, we
can get the total number of calls
cal made by the Tower of Hanoi algorithm:
Figure: Tree of recursivee calls

c made by the recursive algorithm for thee T
Tower of Hanoi
puzzle.
Example-3
The recurrence relation can be written as

.
Also note that A(1) = 0.

troduction
The standard approach to solv fo n = 2k and then

olving such a recurrence is to solve it only for
take advantage of the theore rem called the smoothness rule which claim ims that under very
k
broad assumptions the orderr ofo growth observed for n = 2 gives a correcrect answer about the
order of growth for all valuess of
o n.

troduction
4. Important Problem
m Types
Ty
In this section, we are goin
oing to introduce the most important proble blem types: Sorting,
Searching, String processing,, Graph problems, Combinatorial problems.
4.1. Sorting
The sorting problem is to rear
earrange the items of a given list in non-decre
creasing order. As a
practical matter, we usuallyy need
n to sort lists of numbers, characters from
fro an alphabet or
character strings.
Although some algorithms are indeed better than others, there is no algori orithm that would be
the best solution in all situatio
tions. Some of the algorithms are simple but relrelatively slow, while
others are faster but more complex;
co some work better on randomly ord rdered inputs, while
others do better on almost-so sorted lists; some are suitable only for listss rresiding in the fast
memory, while others can bee adapted
a for sorting large files stored on a disk
isk; and so on.
Two properties of sorting alglgorithms deserve special mention. A sortingg algorithm is called
stable if it preserves the relat
lative order of any two equal elements in its input. The second
notable feature of a sorting algorithm
alg is the amount of extra memory thee algorithm requires.
An algorithm is said to be in-pplace if it does not require extra memory, exc
xcept, possibly, for a
few memory units.
4.2. Searching
The searching problem deals ls with finding a given value, called a searchh key,
k in a given set.
(or a multiset, which permits
its several elements to have the same value). There
T are plenty of
searching algorithms to choosose from. They range from the straightforward rd sequential search
to a spectacularly efficient but
bu limited binary search and algorithms bassed on representing
the underlying set in a differe
rent form more conducive to searching. The latter
la algorithms are
of particular importance for real-world
re applications because they are indisp
ispensable for storing
and retrieving information from
rom large databases.
4.3. String Processing
In recent decades, the rapid proliferation
pr of applications dealing with non--numerical data has
intensified the interest off researchers and computing practitionerss in string-handling
algorithms. A string is a sequence
s of characters from an alphabet. et. String-processing
algorithms have been impo portant for computer science in conjunctio tion with computer
languages and compiling issueues.
4.4. Graph Problems
One of the oldest and most interesting
int areas in algorithmics is graph algorit
rithms. Informally, a
graph can be thought of as a collection
co of points called vertices, some of which
w are connected
by line segments called edges.
ed Graphs can be used for modeling a wide variety of
applications, including transpo
sportation, communication, social and economi mic networks, project
scheduling, and games. Stud udying different technical and social aspects ts of the Internet in

troduction
particular is one of the acti

ctive areas of current research involving co
computer scientists,
economists, and social scientis
tists.
4.5. Combinatorial Problems
lems
Generally speaking, combinat
natorial problems are the most difficult proble
blems in computing,
from both a theoretical and practical
p standpoint. Their difficulty stemss ffrom the following
facts. First, the number off combinatorial
c objects typically grows extr tremely fast with a
problem’s size, reaching unimaginable
un magnitudes even for modera rate-sized instances.
Second, there are no known wn algorithms for solving most such proble blems exactly in an
acceptable amount of time.
5. Fundamental Data
a Structures
Stru
Since the vast majority off algorithms of interest operate on data, particular
p ways of
organizing data play a critical
al role in the design and analysis of algorithmss. A data structure
can be defined as a particularr scheme
s of organizing related data items.
5.1. Linear Data Structures
res
The two most important eleme
mentary data structures are the array and the linked
lin list.
A (one-dimensional) array is a sequence of n items of the same data ty
type that are stored
contiguously in computer mem
emory and made accessible by specifying a value
v of the array’s
index.
A linked list is a sequence of zero or more elements called nodes, each containing
co two kinds
of information: some data and nd one or more links called pointers to otherr nnodes of the linked
list. In a singly linked list, each
eac node except the last one contains a single le pointer to the next
element. Another extension is i the structure called the doubly linked list,li in which every
node, except the first and thee last,
l contains pointers to both its successor and
an its predecessor.
A list is a finite sequence off data

d items, i.e., a collection of data items ar
arranged in a certain
linear order. The basic ope perations performed on this data structuree are searching for,

troduction
inserting, and deleting an element.

e Two special types of lists, stacks
cks and queues, are
particularly important.
A stack is a list in which insertions
ins and deletions can be done only at the
th end. This end is
called the top because a stack
ck is usually visualized not horizontally but ve
vertically—akin to a
stack of plates whose “operatio
ations” it mimics very closely.
A queue, on the other hand, d, is a list from which elements are deleted from
fr one end of the
structure, called the front (thi
this operation is called dequeue), and new elem
lements are added to
the other end, called the rear
rea (this operation is called enqueue). Cons nsequently, a queue
operates in a “first-in–first-ou
out” (FIFO) fashion—akin to a queue of cust stomers served by a
single teller in a bank. Queu eues also have many important applications,ns, including several
algorithms for graph problemsms.
Many important applications ns require selection of an item of the highest est priority among a
dynamically changing set off candidates. A data structure that seeks to sa satisfy the needs of
such applications is called a priority queue. A priority queue is a collec lection of data items
from a totally ordered univ niverse (most often, integer or real numbe bers). The principal
operations on a priority queue
ue are finding its largest element, deleting itss la
largest element, and
adding a new element.
5.2. Graphs
A graph is informally thoughght of as a collection of points in the plane ccalled “vertices” or
nodes,” some of them connecnected by line segments called “edges” or “arcs.”
“ar A graph G is
called undirected if every edge
ed in it is undirected. A graph whose every ry edge is directed is
called directed. Directed grap
aphs are also called digraphs.
The graph depicted in Figuree (a)
( has six vertices and seven undirected edge
ges:
V = {a, b, c, d, e, f },
} E = {(a, c), (a, d), (b, c), (b, f ), (c, e), (d, e)
e), (e, f )}.
The digraph depicted in Figure
ure 1.6b has six vertices and eight directed edge
ges:
V = {a, b, c, d, e, f },, E = {(a, c), (b, c), (b, f ), (c, e), (d, a), (d, e), (e
(e, c), (e, f )}.
Graph Representations - Graphs

Gr for computer algorithms are usually represented
rep in one of
two ways: the adjacency matr
trix and adjacency lists.
The adjacency matrix of a graph
g with n vertices is an n x n boolean matrix
m with one row
and one column for each of the the i row and the jth
th graph’s vertices, in which the element in th th

troduction
i an edge from the ith vertex to the jth vertex

column is equal to 1 if theree is tex, and equal to 0 if
there is no such edge.
The adjacency lists of a graph
aph or a digraph is a collection of linked lists,, oone for each vertex,
that contain all the vertices adjacent
ad to the list’s vertex (i.e., all the vertices
ces connected to it by
an edge).
Weighted Graphs: A weigh ghted graph (or weighted digraph) is a graphph (or digraph) with
numbers assigned to its edges.
es. These numbers are called weights or costs.
Among the many propertiess of o graphs, two are important for a great numb
mber of applications:
connectivity and acyclicity. Both
B are based on the notion of a path. A path
pat from vertex u to
vertex v of a graph G can be b defined as a sequence of adjacent (conn nnected by an edge)
vertices that starts with u andd ends
e with v.
A graph is said to be connecte

cted if for every pair of its vertices u and v there
the is a path from u
to v. Graphs with several cononnected components do happen in real-world rld applications. It is
important to know for many ny applications whether or not a graph under er consideration has
cycles. A cycle is a path of a positive length that starts and ends at the sam
same vertex and does
not traverse the same edge moore than once.
5.3. Trees
A tree (more accurately, a free
fre tree) is a connected acyclic graph. A graphph that has no cycles
but is not necessarily connecte
cted is called a forest: each of its connected co
components is a tree.
Trees have several importantt properties
p other graphs do not have. In particu
ticular, the number of
edges in a tree is always onee less
le than the number of its vertices: |E| = |V| - 1

troduction
Rooted Trees: Another veryy important

i property of trees is the fact that for
or every two vertices
in a tree, there always existss exactly
e one simple path from one of these vertices
ve to the other.
This property makes it possib
sible to select an arbitrary vertex in a free treeee and consider it as
the root of the so-called roote
oted tree. A rooted tree is usually depicted byy placing its root on
the top (level 0 of the tree),, the
t vertices adjacent to the root below it (le (level 1), the vertices
two edges apart from the root still below (level 2), and so on.
The depth of a vertex v is the length of the simple path from the root to v. The height of a
tree is the length of the longes
est simple path from the root to a leaf.
Ordered Trees- An orderedd treet is a rooted tree in which all the childrenen of each vertex are
ordered. It is convenient to assume
as that in a tree’s diagram, all the children
ren are ordered left to
right. A binary tree can be defined
de as an ordered tree in which every vertertex has no more than
two children and each child is designated as either a left child or a rightt child
ch of its parent; a
binary tree may also be emptyty.
If a number assigned to eachh parental vertex is larger than all the number
ers in its left subtree
and smaller than all the nummbers in its right subtree. Such trees are cal
alled binary search
trees. Binary trees and binary
ry search
trees have a wide varie riety of
applications in computer scien
ience.

troduction
5.4. Sets and Dictionaries

A set can be described as an unordered collection (possibly empty) of distinct di items called
elements of the set. A specificific set is defined either by an explicit listing of its elements (e.g.,
S = {2, 3, 5, 7}) or by specif cifying a property that all the set’s elementss anda only they must
satisfy (e.g., S = {n: n is a prim
rime number smaller than 10}).
The most important set opera rations are: checking membership of a givenn iitem in a given set;
finding the union of two sets,
s, which comprises all the elements in either or both of them; and
finding the intersection of twoo sets, which comprises all the common eleme
ments in the sets.
Sets can be implemented inn computer
c applications in two ways. The first considers only sets
that are subsets of some large
ge set U, called the universal set. If set U has n elements, then any
subset S of U can be represen ctor, in which the ith
ented by a bit string of size n, called a bit vect
element is 1 if and only if thee ith element of U is included in set S.
The second and more common on way to represent a set for computing purpos oses is to use the list
structure to indicate the set’s
’s elements. This is feasible only for finite sets
ets. The requirement
for uniqueness is sometimes es circumvented by the introduction of a m multiset, or bag, an
unordered collection of itemss that are not necessarily distinct. Note that if a set is represented
by a list, depending on the application
ap at hand, it might be worth maint intaining the list in a
sorted order.
Dictionary: In computing, theth operations we need to perform for a set et or a multiset most
often are searching for a given
giv item, adding a new item, and deleting ng an item from the
collection. A data structure that
th implements these three operations is call alled the dictionary.
An efficient implementation on of a dictionary has to strike a compro romise between the
efficiency of searching and the
th efficiencies of the other two operations.. They
T range from an
unsophisticated use of arrays
ys (sorted or not) to much more sophisticatedd techniques such as
hashing and balanced search trees.
tr
A number of applications in computing require a dynamic partition off ssome n-element set
into a collection of disjoint subsets.
su After being initialized as a collection
ion of n one-element
subsets, the collection is subje
bjected to a sequence of intermixed union and nd search operations.
This problem is called the set
et union problem.
*****

Vivekananda
College
gy
Lecture Notes
on
15CS43
Design and Analysis
lysis of
Algorithms
(CBCS Scheme)
Prepared by
Mr. Harivinod N
Assistant Professor,
Dept. of Computer
VCET Puttur
Feb 2017
Module
odule-2 : Divide and Conquer
Contents
1. General methodod
2. Recurrence equ
quation
3. Algorithm: Bin
inary search
4. Algorithm: Fin
inding the maximum and minimum
5. Algorithm: Meerge sort
6. Algorithm: Quiuick sort
7. Algorithm: Stra
trassen’s matrix multiplication
8. Advantages and Disadvantages
9. Decrease and Conquer
C Approach
10. Algorithm: Top
opological Sort
Course
ourse website: www.techjourney.in
Lecture Notess || 10CS43 – DAA || Module 2: Divide and Conque
nquer
1. General method:
Divide and Conquer is one of the best-known general algorithm designn technique.
t It works
according to the following geneneral plan:
• Given a function to compute
co on ‘n’ inputs the divide-and-conqueuer strategy suggests
splitting the inputs into
nto ‘k’ distinct subsets, 1<k<=n, yielding ‘k’ su
sub problems.
• These sub problems must m be solved, and then a method must be fou found to combine sub
solutions into a solutio
tion of the whole.
• If the sub problems are still relatively large, then the divide-and-co conquer strategy can
possibly be reapplied.
• Often the sub problem ems resulting from a divide-and-conquer desig sign are of the same
type as the originall problem.
p For those cases the reapplicationn of the divide-and-
conquer principle is naturally
na expressed by a recursive algorithm.
A typical case with k=2 is diag

iagrammatically shown below.
Problem of size n
Sub Problem
lem of size n/2 Sub Problem
m of
o size n/2
Solution to sub
ub problem
p 1 Solution to sub
su problem 2
Solution to the original problem
Control Abstraction for divide

de and conquer:
In the above specification,

• Initially DAndC(P) is invoked,
i where ‘P’ is the problem to be solve
lved.
• Small (P) is a Boolean an-valued function that determines whether the input size is small
enough that the answeer can be computed without splitting. If thiss sso, the function ‘S’
is invoked. Otherwise,
se, the problem P is divided into smaller sub problems.
pr These sub
a solved by recursive application of DAndC
problems P1, P2 …Pk are C.
• Combine is a function on that determines the solution to P using thee ssolutions to the ‘k’
sub problems.
Prepared by Harivinod N www.techjourney.in Page| 2.2
nquer
2. Recurrence equation
n for
f Divide and Conquer:
If the size of problem ‘p’ is n and the sizes of the ‘k’ sub problems ms are n1, n2 ….nk,
respectively, then the comput
uting time of divide and conquer is described
ed by the recurrence
relation
Where,
• T(n) is the time for div
ivide and conquer method on any input of size
ze n and
• g(n) is the time to com
mpute answer directly for small inputs.
• The function f(n) is the time for dividing the problem ‘p’ and comb
mbining the solutions
to sub problems.
For divide and conquer based ed algorithms that produce sub problems of the th same type as the
original problem, it is very natural
nat to first describe them by using recursion
on.
More generally, an instance of o size n can be divided into b instances off size n/b, with a of
them needing to be solved. (Here,
(H a and b are constants; a>=1 and b > 1.). Assuming that
k
size n is a power of b (i.e. n = b ), to simplify our analysis, we get the fo
following recurrence
for the running time T(n):
..... (1)
where f(n) is a function that accounts

ac for the time spent on dividing the pro
roblem into smaller
ones and on combining theirr solutions.
s
Substitution Method - Onee of the methods for solving the recurrence relation
re is called the
substitution method. This meethod repeatedly makes substitution for each
ch occurrence of the
function T in the right hand side
sid until all such occurrences disappear.
Master Theorem - The efficie
iciency analysis of many divide-and-conquer algorithms
alg is greatly
simplified by the master theore
orem.
quation T(n) = aT(n/b) + f (n), If f (n)∈Θ (nd ) where d ≥ 0 then
It states that, in recurrence equ
Analogous results hold for the

he Ο and Ω notations, too.
For example, the recurrence for

fo the number of additions A(n) made by the divide-and-
lgorithm (see above) on inputs of size n = 2k is
conquer sum-computation algo
Thus, for this example, a = 2, b = 2, and d = 0; hence, since a >bd,

nquer
Problems on Substitutio
ion method & Master theorem to solv
olve the
recurrence relation

nquer

nquer

nquer

nquer

nquer

nquer
3. Binary Search
Problem definition: Let ai, 1 ≤ i ≤ n be a list of elements that are sorted
ed in non-decreasing
order. The problem is to findnd whether a given element x is present in the list or not. If x is
present we have to determine ne a value j (element’s position) such that aj=x.
=x If x is not in the
list, then j is set to zero.
Solution: Let P = (n, ai…al , x) oblem where n is the
x denote an arbitrary instance of search prob
number of elements in the list,
lis ai…al is the list of elements and x is thehe key element to be
searched for in the given list. Binary
B search on the list is done as follows:
Step 1: Pick an index q in the
th middle range [i, l] i.e. q= 1 /2 andd compare
c x with aq.
Step 2: if x = aq i.e key elem
ement is equal to mid element, the problem is im
immediately solved.
Step 3: if x < aq in this case
se x has to be searched for only in the sub-listt ai, ai+1, ……, aq-1.
Therefore problem reduces
re to (q-i, ai…aq-1, x).
Step 4: if x > aq , x has to be searched for only in the sub-list aq+1, ...,., al . Therefore
T problem
reduces to (l-i, aq+1…a
… l, x).
For the above solution proced
cedure, the Algorithm can be implemented as recursive or non-
recursive algorithm.
Recursive binary search algo

lgorithm
Iterative binary search:

nquer
Analysis
In binary search the basic operation
ope is key comparison. Binary Search can
ca be analyzed with
the best, worst, and averagee case
c number of comparisons. The numberss of o comparisons for
the recursive and iterative ver
ersions of Binary Search are the same, if comp
mparison counting is
relaxed slightly. For Recursive
ive Binary Search, count each pass through the if-then-else block
as one comparison. For Iterati
rative Binary Search, count each pass throughh the while block as
one comparison. Let us find out
o how many such key comparison does thee algorithm make on
an array of n elements.
Best case – Θ(1) In the best
est case, the key is the middle in the array. A cconstant number of
comparisons (actually just 1)) are
a required.
nquer
Worst case - Θ(log2 n) In theth worst case, the key does not exist in the ar
array at all. Through
each recursion or iteration of Binary Search, the size of the admissible ran
range is halved. This
(lo 2 n ) times. Thus, log n comparisons are
halving can be done ceiling (log ar required.
Sometimes, in case of the sucuccessful search, it may take maximum numbber of comparisons.
log n . So worst case com
mplexity of successful binary search is Θ (log2 n).
Average case - Θ (log2 n) Too find the average case, take the sum of the product
pro of number of
comparisons required to findd each element and the probability of searchin ing for that element.
To simplify the analysis, assusume that no item which is not in array will be searched for, and
that the probabilities of search
ching for each element are uniform.
How to compute Average case

ase complexity?
Space Complexity - The spac ace requirements for the recursive and iterative
ive versions of binary
search are different. Iterativee Binary Search requires only a constant amouount of space, while
Recursive Binary Search requires
req space proportional to the numberr oof comparisons to
maintain the recursion stack.
Advantages: Efficient on very
ery big list, Can be implemented iteratively/rec
ecursively.
Limitations:
• Interacts poorly with the
th memory hierarchy
• Requires sorted list as an input
• Due to random access ss of list element, needs arrays instead of linked
ed list.

nquer
4. Finding the maximum

um and minimum
Problem statement: Given a list of n elements, the problem is to findd the maximum and
minimum items.
StraightMaxMin: A simplee and
a straight forward algorithm to achieve this
is is given below.
Explanation:
StraightMaxMin requi
quires 2(n-1) comparisons in the best, averagee & worst cases.
By realizing the compparison of a[i]>max is false, improvement in a algorithm can be
done. Hence we can replace
re the contents of the for loop by,
If(a[i]>Max) then Max = a[i]; Else if (a[i]< min)
) min=a[i]
On the average a[i] is > max half the time. So, the avg. no. of compparison is 3n/2-1.
Algorithm based on Dividee and

a Conquer strategy
Let P = (n, a [i],……,a [j]) denote
den an arbitrary instance of the problem. Here H ‘n’ is the no. of
elements in the list (a[i],….,a[
,a[j]) and we are interested in finding the maxim
ximum and minimum
of the list. If the list has more
re than 2 elements, P has to be divided into smaaller instances.
For example, we might divide
de ‘P’ into the 2 instances,
P1=( [n/2],a[1],……..a
..a[n/2])
P2= ( n-[n/2], a[[n/2]+
]+1],….., a[n])
After having divided ‘P’ intoo 2 smaller sub problems, we can solve them by recursively
invoking the same divide-and--conquer algorithm.
Algorithm:

nquer
Example:
of recursive calls of MaxMin

in is
i as follows
Analysis - Time Complexity

nquer
Compared with the straight forward

for method (2n-2) this method saves 25%
% in comparisons.
Space Complexity
Compared to the straight forw
rward method, the MaxMin method requires extra ex stack space for
i, j, max, min, max1 and min1.
mi Given n elements there will be 1 levels of
recursion and we need to save
ve seven values for each recursive call. (6 + 1 for
f return address).
5. Merge Sort
Merge sort is a perfect exa xample of a successful application of the divide-and
d conquer
technique. It sorts a given arra alves A [0 .. /2 -1]
rray A [O ... n - 1] by dividing it into two halv
and A [ /2 .. n-1], sorting ing each of them recursively, and then mergin ging the two smaller
sorted arrays into a single sort
rted one.
The merging of two sorted arr

rrays can be done as follows.
Two pointers (array indices)
in are initialized to point to the first elem
lements of the arrays
being merged.
The elements pointeded to are compared, and the smaller of them
m is added to a new
array being constructed
ted

nquer
After that, the index of

o the smaller element is incremented to poin
oint to its immediate
successor in the arrayy it was copied from. This operation is repeat
ated until one of the
two given arrays is exhausted,
exh and then the remaining elements of the other array are
copied to the end of the new array.
Example:
The operation of the algorithm hm on the
list 8, 3, 2, 9, 7, 1, 5, 4 is illust
ustrated in
the figure
Analysis
Here the basic operation is key

ey comparison. As merge sort execution doess not
n depend on the
order of the data, best case and
nd average case runtime are the same as worst
st case runtime.
Worst case: During key com omparison, neither of the two arrays becomes
es empty before the
other one contains just onee element
e leads to the worst case of mergee sort.
s Assuming for

nquer
simplicity that total numberr of

o elements n is a power of 2, the recurren
ence relation for the
number of key comparisons C(n)
C is
where, Cmerge(n) is the number

n of key comparison made during the merging
m stage.
Let us analyze Cmerge(n), the number
n of key comparisons performed duringng the merging stage.
At each step, exactly one commparison is made, after which the total number
ber of elements in the
two arrays still needing to bee processed is reduced by 1. In the worst case,
se, neither of the two
arrays becomes empty before re the other one contains just one element (e.g
.g., smaller elements
ing arrays). Therefore, for the worst case, Cmergge(n) = n – 1.
may come from the alternating
Now,
Solving the recurrence equatio

tion using master theorem:
Here a = 2, b = 2, f (n) = n, d = 1. Therefore 2 = 21, case 2 holds in the m
master theorem
d 1
Cworst (n) = Θ (n log n) = Θ (n log n) = Θ (n log n) Therefore Cworst(n) = Θ (n log n)
Advantages:
• Number of comparison sons performed is nearly optimal.
• For large n, the numbber of comparisons made by this algorithm in i the average case
turns out to be aboutt 0.25n
0 less and hence is also in Θ(n log n).
• Mergesort will neverr degrade
d to O (n2)
• Another advantage of o mergesort over quicksort and heapsortt is i its stability. (A
sorting algorithm is said
sa to be stable if two objects with equal keys
ys appear in the same
order in sorted output
ut as they appear in the input array to be sorted.
d. )
Limitations:
• The principal shortcom oming of mergesort is the linear amount [ O(n (n) ] of extra storage
the algorithm requires
es. Though merging can be done in-place, thee resulting algorithm
is quite complicated and
an of theoretical interest only.
Variations of merge sort

1. The algorithm can be b implemented bottom up by merging pa pairs of the array’s
elements, then mergin
ging the sorted pairs, and so on. (If n is nott a power of 2, only
slight bookkeeping complications
co arise.) This avoids the time and
nd space overhead of
using a stack to handle
dle recursive calls.
2. We can divide a listt to
t be sorted in more than two parts, sort eac
each recursively, and
then merge them togegether. This scheme, which is particularly usef
seful for sorting files
residing on secondary
ry memory devices, is called multiway mergesoesort.

nquer
6. Quick sort
Quicksort is the other import
ortant sorting algorithm that is based on thee ddivide-and-conquer
approach. Unlike mergesort, t, which
w divides its input elements accordingg to their position in
the array, quicksort divides ( or
o partitions) them according to their value.
A partition is an arrangementent of the array’s elements so that all the elem
lements to the left of
some element A[s] are less than
tha or equal to A[s], and all the elements to th
the right of A[s] are
greater than or equal to it:
Obviously, after a partition is achieved, A[s] will be in its final positionn iin the sorted array,
and we can continue sortin ting the two subarrays to the left and too the right of A[s]
independently (e.g., by the sam
ame method).
In quick sort, the entire work happens
h in the division stage, with no work re
required to combine
the solutions to the sub proble
lems.
Partitioning
We start by selecting a pivot—
—an element with respect to whose value wee are going to divide
the subarray. There are sev everal different strategies for selecting a ppivot. We use the
sophisticated method suggeste
sted by C.A.R. Hoare, the prominent Britishsh computer scientist
who invented quicksort.
Select the subarray’s first element:
e p = A[l]. Now scan the subarray
ray from both ends,
comparing the subarray’s elem
ements to the pivot.
The left-to-right scan
an, denoted below by index pointer i, starts rts with the second
element. Since we waant elements smaller than the pivot to be in the left part of the
subarray, this scan skip
kips over elements that are smaller than the pipivot and stops upon
encountering the firstt element
e greater than or equal to the pivot.
The right-to-left scan,
n, denoted below by index pointer j, starts with
ith the last element of
the subarray. Since wee want elements larger than the pivot to be inn tthe right part of the

nquer
subarray, this scan skips

sk over elements that are larger than thee ppivot and stops on
encountering the firstt element
e smaller than or equal to the pivot.
After both scans stop, three situations
s may arise, depending on whetherr oor not the scanning
indices have crossed.
1. If scanning indices i and
a j have not crossed, i.e., i < j, we simply
ly exchange A[i] and
A[j ] and resume thee scans
s by incrementing I and decrementing j,, re
respectively:
2. If the scanning indice

ices have crossed over, i.e., i > j, we will ha
have partitioned the
subarray after exchang
nging the pivot with A[j]:
3. If the scanning indiceces stop while pointing to the same element,

t, ii.e., i = j, the value
they are pointing to must
m be equal to p. Thus, we have the subarrarray partitioned, with
the split position s = i = j :
We can combine this with

w the case-2 by exchanging the pivot with
th A[j] whenever i j
ALGORITHM HoarePartitio tion(A[l..r])

//Partitions a subarray by Hoar
oare’s algorithm, using the first element as a piv
pivot
//Input: Subarray of array A[0...n − 1], defined by its left and right indices l and r (l<r)
//Output: Partition of A[l..r],, with
w the split position returned as this function
ion’s value
Note that index i can go out of the subarray’s bounds in this pseudocode.

nquer
Example: Example of quicks ksort operation. (a) Array’s transformations with

wi pivots shown in
bold. (b) Tree of recursive call
alls to Quicksort with input values l and r of subarray
su bounds and
split position s of a partition obtained.
ob
Analysis
Best Case - Here the basic operation
op is key comparison. Number of keyy comparisons made
before a partition is achievedd is
i n + 1 if the scanning indices cross over andnd n if they coincide.
If all the splits happen in the middle of corresponding subarrays, we will ll have the best case.
The number of key compariso sons in the best case satisfies the recurrence,
ctly for n = 2k yields

eorem, Cbest(n) ∈ Θ(n log2 n); solving it exact
According to the Master Theo
Cbest(n) = n log2 n.
Worst Case – In the worst case,
ca all the splits will be skewed to the extrem
reme: one of the two
subarrays will be empty, and
nd the size of the other will be just 1 less th
than the size of the
subarray being partitioned.. This unfortunate situation will happen,, in particular, for
increasing arrays.

nquer
Indeed, if A[0..n − 1] is a stri

trictly increasing array and we use A[0] as the pivot, the left-to-
right scan will stop on A[1]] while the right-to-left scan will go all thee wway to reach A[0],
indicating the split at position
ion 0: So, after making n + 1 comparisons too gget to this partition
and exchanging the pivot A[0] A with itself, the algorithm will be left with the strictly
increasing array A[1..n − 1]] to
t sort. This sorting of strictly increasing arr
arrays of diminishing
sizes will continue until the last
la one A[n−2 .. n−1] has been processed. The T total number of
key comparisons made will be equal to
Average Case - Let Cavg(n) be the average number of key comparisons made ma by quicksort on
a randomly ordered array off size
s n. A partition can happen in any positi ition s (0 s n−1)
after n+1comparisons are mad
ade to achieve the partition. After the partition
ion, the left and right
subarrays will have s and n − 1− s elements, respectively. Assuming tha hat the partition split
can happen in each position s with the same probability 1/n, we get the fofollowing recurrence
relation:
Its solution, which is much trickier

tric than the worst- and best-case analyses,
s, turns out to be
Thus, on the average, quicks

ksort makes only 39% more comparisons tha han in the best case.
Moreover, its innermost loop
op is so efficient that it usually runs fasterr than mergesort on
randomly ordered arrays off nontrivial
n sizes. This certainly justifies thee name given to the
algorithm by its inventor.
Variations
Because of quicksort’s import
ortance, there have been persistent efforts over
er the years to refine
the basic algorithm. Among several
se improvements discovered by researche hers are:
Better pivot selection
on methods such as randomized quicksort that
th uses a random
element or the mediedian-of-three method that uses the median
ian of the leftmost,
rightmost, and the mid
iddle element of the array
Switching to insertion
ion sort on very small subarrays (between 5 and an 15 elements for
most computer systemtems) or not sorting small subarrays at all ll and finishing the
algorithm with insertio
rtion sort applied to the entire nearly sorted arra
rray
Modifications of the
he partitioning algorithm such as the three--way partition into
segments smaller than
an, equal to, and larger than the pivot

nquer
Limitations
It is not stable.
It requires a stack to store
st parameters of subarrays that are yet to be sorted.
While Performance on randomly ordered arrays is known to be sensitivese not only to
implementation details ils of the algorithm but also to both compute uter architecture and
data type.
7. Stassen’s Matrix multip

ultiplication
Direct Method: Suppose wee want to multiply two n x n matrices, A and nd B. Their product,
2
C=AB, will be an n by n matrixm and will therefore have n elementsnts. The number of
3
multiplications involved in producing
pro the product in this way is Θ(n )
Divide and Conquer method

od
Multiplication of 2 × 2 matrices:
ma By using divide-and-conquer appro roach we can reduce
the number of multiplications.
ns. Such an algorithm was published by V. Str trassen in 1969. The
principal insight of the algorith
rithm lies in the discovery that we can find thee product C of two 2
× 2 matrices A and B with just j seven multiplications as opposed to the eight required by
the brute-force algorithm. This
his is accomplished by using the following form rmulas:
where
Thus, to multiply two 2×2 matrices,

m Strassen’s algorithm makes sevenn multiplications
m and
18 additions/subtractions, whhereas the brute-force algorithm requires eight
eig multiplications
and four additions.

nquer
Multiplication of n × n mat atrices – Let A and B be two n × n matrices where n is a power

of 2. (If n is not a power of 2, matrices can be padded with rows and colulumns of zeros.) We
roduct C into four n/2 × n/2 submatrices eachh as
can divide A, B, and their prod a follows:
It is not difficult to verify tha

hat one can treat these submatrices as number
ers to get the correct
product. For example, C00 can ca be computed either as A00 * B00 + A01 * B10 or as M1 + M4 –
M5 + M7 where M1, M4, M5, and M7 are found by Strassen’s formulas, as, with the numbers
replaced by the corresponding ing submatrices. If the seven products of n/2
/2 × n/2 matrices are
computed recursively by the th same method, we have Strassen’s algo lgorithm for matrix
multiplication.
Analysis
Here the basic operation is muultiplication. If M(n) is the number of multipl
iplications made by
Strassen’s algorithm in multip
tiplying two n × n matrices (where n is a powerer of 2), we get the
following recurrence relationn for
f it:
This implies M(n) = Θ(n2.807) which is smaller than n3 required by the brute
ute-force algorithm.
8. Advantages and Disadv

isadvantages of Divide & Conquer
Advantages
Parallelism: Divide and
an conquer algorithms tend to have a lot of in
inherent parallelism.
Once the division pha
hase is complete, the sub-problems are usuall
ally independent and
can therefore be solve
lved in parallel. This approach typically gene
nerates more enough
concurrency to keep the
t machine busy and can be adapted forr execution
e in multi-
processor machines.
Cache Performance: e: divide and conquer algorithms also tend to have good cache
performance. Once a sub-problem fits in the cache, the standard rd recursive solution
reuses the cached data
ta until the sub-problem has been completely so
solved.

nquer
It allows solving diffi

fficult and often impossible looking problemss like the Tower of
Hanoi. It reduces the
he degree of difficulty since it divides thee problem into sub
problems that are easil
sily solvable, and usually runs faster than other
er algorithms would.
Another advantage to this paradigm is that it often plays a part art in finding other
efficient algorithms,, and
a in fact it was the central role in finding
ng the quick sort and
merge sort algorithms.
s.
Disadvantages
One of the most comommon issues with this sort of algorithm is the fact that the
recursion is slow, whhich in some cases outweighs any advantages
es of this divide and
conquer process.
Another concern with th it is the fact that sometimes it can becomee more complicated
ve approach, especially in cases with a largee nn. In other words, if
than a basic iterative
someone wanted to add ad a large amount of numbers together, if they just create a
simple loop to add them
the together, it would turn out to be a much ch simpler approach
than it would be too divide the numbers up into two groups, s, add these groups
recursively, and then add
a the sums of the two groups together.
Another downfall iss that sometimes once the problem is broke oken down into sub
problems, the same subsu problem can occur many times. It is solv lved again. In cases
like these, it can often
en be easier to identify and save the solutionn tto the repeated sub
problem, which is com mmonly referred to as memorization.
9. Decrease and Conquer

quer Approach
Decrease-and-conquer is a general
g algorithm design technique, based
sed on exploiting a
relationship between a solutio
tion to a given instance of a problem and a solution
so to a smaller
instance of the same problemem. Once such a relationship is established,, it
i can be exploited
either top down (usually recur
ursively) or bottom up.
There are three major variation
ions of decrease-and-conquer:
decrease-by-a-constant
ant, most often by one (e.g., insertion sort)
decrease-by-a-constant
ant-factor, most often by the factor of two (e.g.,
g., binary search)
variable-size-decrease
se (e.g., Euclid’s algorithm)
In the decrease-by-a-constantant variation, the size of an instance is red
educed by the same
constant on each iteration off the
t algorithm. Typically, this constant is equ
qual to one although
other constant size reductions
ns do happen occasionally.

nquer
Figure: Decrease-(by one)-and

nd-conquer technique
n n-1
Example: a = a × a Problem of size
ize n
Sub Problem
of size n-1
Solution to sub
problem
Solution to the originall problem

pro
The decrease-by-a-constant--factor technique suggests reducing a proble

blem instance by the
same constant factor on each
ch iteration of the algorithm. In most applicat
cations, this constant
factor is equal to two.
Figure: Decrease-(by half)-and
and-conquer technique. Problem of size n
Sub Problem
of size n/2
Solution to sub
problem
Example: Solution to the original

nal problem
p
Finally, in the variable-size--decrease variety of decrease-and-conquer,

r, the size-reduction
pattern varies from one iteratio
tion of an algorithm to another.
Example: Euclid’s algorithm
m for computing the greatest common divisor.
or. It is based on the
formula. gcd
cd(m, n) = gcd(n, m mod n).
Though the value of the seconond argument is always smaller on the right-han
hand side than on the
left-hand side, it decreases nei
either by a constant nor by a constant factor.

nquer
10. Topological Sort

Background
A directed graph, or digraphh for short, is a graph with directions specifie
fied for all its edges.
The adjacency matrix and adjacency
ad lists are the two principal meansns of representing a
digraph.
There are only two notabl ble differences between undirected and directed
d graphs in
representing them: (1) the adjacency
a matrix of a directed graph doe oes not have to be
symmetric; (2) an edge in a directed
di graph has just one (not two) correspo
ponding nodes in the
digraph’s adjacency lists.
Depth-first search and breadt dth-first search are principal traversal algorit
rithms for traversing
digraphs as well, but the strutructure of corresponding forests can be more re complex than for
undirected graphs. Thus, even en for the simple example of Figure, the depth
pth-first search forest
(Figure b) exhibits all four typ
ypes of edges possible in a DFS forest of a dire
irected graph:
• tree edges (ab, bc, de),,
• back edges (ba) from vertices
v to their ancestors,
• forward edges (ac) from fr vertices to their descendants in the tree
tre other than their
children, and
• cross edges (dc), which ich are none of the aforementioned types.
Note that a back edge in a DFS

DF forest of a directed graph can connect a vertex
v to its parent.
Whether or not it is the case,
se, the presence of a back edge indicates thatat the digraph has a
directed cycle. A directed cycl
ycle in a digraph is a sequence of three or more
ore of its vertices that
starts and ends with the samee vertex and in which every vertex is connecte
cted to its immediate
predecessor by an edge directe or example, a, b, a is
cted from the predecessor to the successor. For
a directed cycle in the digraraph in Figure given above. Conversely, if a DFS forest of a
digraph has no back edges, the digraph is a dag, an acronym for directed acyclic
ac graph.

nquer
Motivation for topological sorting

so
Consider a set of five required
red courses {C1, C2, C3, C4, C5} a part-timee student has to take
in some degree program. The he courses can be taken in any order as lon
ong as the following
course prerequisites are met:
t: C1 and C2 have no prerequisites, C3 requir
uires C1 and C2, C4
requires C3, and C5 requires C3 and C4. The student can take only onee ccourse per term. In
which order should the studen
ent take the courses?
The situation can be modeled
ed by a digraph in which vertices represent
courses and directed edges indicate
ind prerequisite requirements.
In terms of this digraph, the question
qu is whether we can list its vertices
in such an order that for every
ery edge in the graph, the vertex where the
edge starts is listed before the
he vertex where the edge ends. In other words,ds, can you find such
an ordering of this digraph’ss vertices?
v This problem is called topologicall sorting.
so
Topological Sort
For topological sorting to bee possible,
p a digraph in question must be a dadag. i.e., if a digraph
has no directed cycles, the top
opological sorting problem for it has a solution.
n.
There are two efficient algori
orithms that both verify whether a digraph is a dag and, if it is,
produce an ordering of vertic
tices that solves the topological sorting proble
lem. The first one is
based on depth-first search; the
th second is based on a direct application off th
the decrease-by-one
technique.
Topological Sorting based on DFS

Method
1. Perform a DFS travers
ersal and note the order in which vertices becomome dead-ends
2. Reversing this orderr yields
y a solution to the topological sorting pro
roblem, provided, of
course, no back edge
ge has been encountered during the traversal. l. If a back edge has
been encountered, the
he digraph is not a dag, and topological sortin ting of its vertices is
impossible.
Illustration
a) Digraph for which thee topological sorting problem needs to be solve
lved.
b) DFS traversal stack with
wi the subscript numbers indicating the poppi ping off order.
c) Solution to the problem
lem. Here we have drawn the edges of the dig digraph, and they all
point from left to right
ght as the problem’s statement requires. It is a convenient way to
check visually the cororrectness of a solution to an instance of the topological sorting
problem.

nquer
Topological Sorting using decrease-and-conquer

d technique:
Method: The algorithm is based
ba on a direct implementation of the decr
crease-(by one)-and-
conquer technique:
1. Repeatedly, identifyy in
i a remaining digraph a source, which is a vertex with no
incoming edges, andd delete
d it along with all the edges outgoing frfrom it. (If there are
several sources, break
ak the tie arbitrarily. If there are none, stop be
because the problem
cannot be solved.)
2. The order in which the vertices are deleted yields a solution to thee topological sorting
problem.
Illustration - Illustration of the
th source-removal algorithm for the topologic
gical sorting problem
is given here. On each iteration
tion, a vertex with no incoming edges is deleted
ed from the digraph.
Note: The solution obtained

ed by the source-removal algorithm is diffe ferent from the one
obtained by the DFS-based algorithm.
a Both of them are correct, of cour
urse; the topological
sorting problem may have sev
everal alternative solutions.
Applications of Topologicall Sorting
S
• Instruction schedulingg in program compilation
• Cell evaluation orderin
ring in spreadsheet formulas,
• Resolving symbol depe
ependencies in linkers.
***

Vivekananda
College
ogy
N
Nehru Nagar Post, Puttur, D.K. 574203
Lecture Notes on
15CS43
Design and Analysis
lysis of
Algorithms
(CBCS Scheme)
Prepared by
Mr. Harivinod N
Dept. of Computer
VCET Puttur
Mar 2017
Modu
Module-3 : Greedy Method
Contents
1. Introduction to Greedy meethod 3. Single source shortes

test paths
1.1. General method, 3.1. Dijkstra's Algor
orithm
1.2. Coin Change Problem
em 4. Optimal Tree problelem:
1.3. Knapsack Problem 4.1. Huffman Treess and
a Codes
1.4. Job sequencing withh deadlines
d 5. Transform and Conq nquer Approach:
2. Minimum cost spanning trees:
tr 5.1. Heaps
2.1. Prim’s Algorithm, 5.2. Heap Sort
2.2. Kruskal’s Algorithm
S43 – Design & Analysis of Algorithms | Module 3: Greedy
eedy Method
M
1. Introduction to Greedy
reedy method
1.1 General method
The greedy method is thee straight forward design technique applica
icable to variety of
applications.
The greedy approach sugges ests constructing a solution through a sequen
uence of steps, each
expanding a partially constru
tructed solution obtained so far, until a compl
plete solution to the
problem is reached. On each step
s the choice made must be:
• feasible, i.e., it has too satisfy
s the problem’s constraints
• locally optimal, i.e.,., iti has to be the best local choice among aall feasible choices
available on that step
• irrevocable, i.e., once nce made, it cannot be changed on subseq equent steps of the
algorithm
As a rule, greedy algorithmss are
a both intuitively appealing and simple. Giv
iven an optimization
problem, it is usually easy to figure out how to proceed in a greedy man anner, possibly after
considering a few small instan
tances of the problem. What is usually moree difficult
d is to prove
that a greedy algorithm yields
ds an optimal solution (when it does).
1.2. Coin Change Problem

Problem Statement: Given coins
coi of several denominations find out a wayy to give a customer
an amount with fewest numbe
ber of coins.
Example: if denominations are
a 1, 5, 10, 25 and 100 and the change required
r is 30, the
solutions are,
Amount : 30
Solutions : 3 x 100 ( 3 coins ), 6 x 5 ( 6 coins )
1 x 255 + 5 x 1 ( 6 coins ) 1 x 25 + 1 x 5 ( 2 coin
ins )
The last solution is the optima
mal one as it gives us change only with 2 coins
ns.
Prerpared by Harivinod N www.techjourney.in Page| 3.2

eedy Method
M
Solution for coin change proroblem using greedy algorithm is very intui
tuitive and called as
cashier’s algorithm. Basic principle
pri is: At every iteration for search of
o a coin, take the
largest coin which can fit into
in remain amount to be changed at thatt particular
p time. At
the end you will have optimal
al solution.
1.3. Knapsack Problem
There are several greedy meth

thods to obtain the feasible solutions.
a) At each step fill the knaps
apsack with the object with largest profit - If I the object under
consideration does not fit, then
hen the fraction of it is included to fill the knap
apsack. This method
does not result optimal solutio
tion. As per this method the solution to the ab above problem is as
follows;
Select Item-1 with prof
rofit p1=25, here w1=18, x1=1. Remaining cap apacity = 20-18 = 2
Select Item-2 with prof
rofit p1=24, here w2=15, x1=2/15. Remaining ing capacity = 0
nd
Total profit earned = 28.2.
2 This results 2 solution in the exampple 4.1

eedy Method
M
b) At each step fill the objectt with

w smallest weight
rd
This results 3 solution
ion in the example 4.1
c) At each step include the objbject with maximum profit/weight ratio
th
This results 4 solution
ion in the example 4.1
This greedy approachh always
a results optimal solution.
Algorithm: The algori
orithm given below assumes that the objects are sorted in non-
increasing order of pro
rofit/weight ratio
Analysis:
Disregarding the time to initia
tially sort the object, each of the above strategie
gies use O(n) time,
0/1 Knapsack problem
Note: The greedy approachh to solve this problem does not necessarily
ily yield an optimal
solution

eedy Method
M
1.4. Job sequencing with deadlines

dead
The greedy strategy to solvee job

jo sequencing problem is, “At each time sele elect the job that that
satisfies the constraints and
nd gives maximum profit. i.e consider the jobs in the non
decreasing order of the pi’s”
w get the 3rd solution in the example 4.3. Itt can
By following this procedure,, we c be proved that,
this greedy strategy always results
res optimal solution
High lev
evel description of job sequencing algorithm

eedy Method
M
Algorithm/Program 4.6: Greed

eedy algorithm for sequencing unit time jobs wi
with deadlines and
profits
Analysis:

eedy Method
M
Fast Job Scheduling Algorith

ithm

eedy Method
M
Algorithm: Fast Job Sheduli

uling
Analysis

eedy Method
M
2. Minimum cost spannin

anning trees
Definition: A spanning tree ee of a connected graph is its connected acycl
clic subgraph (i.e., a
tree) that contains all the ver
ertices of the graph. A minimum spanningg tree t of a weighted
connected graph is its spanni ning tree of the smallest weight, where thee w
weight of a tree is
defined as the sum of the weig
eights on all its edges. The minimum spannin
ning tree problem is
the problem of finding a minim
nimum spanning tree for a given weighted conn
nnected graph.
2.1. Prim’s Algorithm

Prim's algorithm constructs a minimum spanning tree through a sequence ce of expanding sub-
trees. The initial subtree in such
s a sequence consists of a single vertexx selected arbitrarily
from the set V of the graph'sh's vertices. On each iteration it expands thee current tree in the
greedy manner by simply atta ttaching to it the nearest vertex not in that tre
tree. (By the nearest
vertex, we mean a vertex not ot in the tree connected to a vertex in the tree
ee by an edge of the
smallest weight. Ties can be broken arbitrarily.) The algorithm stops after af all the graph's
vertices have been included in the tree being constructed. Since the algori rithm expands a tree
by exactly one vertex on eachach of its iterations, the total number of such
ch iterations is n - 1,
where n is the number of vertices
v in the graph. The tree generated by b the algorithm is
obtained as the set of edges.

eedy Method
M
Correctness
Prim’s algorithm always yield
lds a minimum spanning tree.
Example: An example of pri rim’s algorithm is shown below.

The parenthesized labels off a vertex in the middle column
indicate the nearest tree vert
ertex and edge weight; selected
vertices and edges are shownn in
i bold.
Tree vertices Remaining vertices Illustratio

tion

eedy Method
M
Analysis of Efficiency
The efficiency of Prim’s algor
orithm depends on the data structures chosenn for
f the graph itself
and for the priority queue of the set V − VT whose vertex priorities aree the
t distances to the
nearest tree vertices.
1. If a graph is represente
nted by its weight matrix and the priority queueue is implemented
as an unordered arra Θ 2). Indeed, on
ray, the algorithm’s running time will be in Θ(|V|
each of the |V| − 1itera
erations, the array implementing the priority qu
queue is traversed to
find and delete the minimum
m and then to update, if necessary,, the
th priorities of the
remaining vertices.
We can implement the priorit
rity queue as a min-heap. (A min-heap is a co complete binary tree
in which every element is less
ess than or equal to its children.) Deletion of the
th smallest element
from and insertion of a new element
el into a min-heap of size n are O(log n) operations.
2. If a graph is represente
nted by its adjacency lists and the priority que
ueue is implemented
as a min-heap, the run
unning time of the algorithm is in O(|E| log |V
V |).
This is because the algorithmm performs |V| − 1 deletions of the smallestt eelement and makes
|E| verifications and, possibly
bly, changes of an element’s priority in a mi min-heap of size not
exceeding |V|. Each of thesee operations,
o as noted earlier, is a O(log |V|) operation.
op Hence, the
running time of this implemenentation of Prim’s algorithm is in
(|V| − 1+ |E|) O (log |V |) = O(|E| log |V |) because, in a connected grap
aph, |V| − 1≤ |E|.
2.2. Kruskal’s Algorithm

Background
Kruskal's algorithm is another
er greedy algorithm for the minimum spanning ing tree problem that
also always yields an optimal
al solution. It is named Kruskal's algorithm, afte
fter Joseph Kruskal.
Kruskal's algorithm looks att a minimum spanning tree for a weighted con
connected graph G =
(V, E) as an acyclic sub graph
aph with |V | - 1 edges for which the sum of the
th edge weights is
the smallest. Consequently, y, the algorithm constructs a minimum spa spanning tree as an
expanding sequence of subb graphs, which are always acyclic but aare not necessarily
connected on the intermediate
te stages of the algorithm.
Working
The algorithm begins by sortirting the graph's edges in non decreasing orde rder of their weights.
Then, starting with the empty ty sub graph, it scans this sorted list adding the
th next edge on the
list to the current sub graph if such an inclusion does not create a cycle and
an simply skipping
the edge otherwise.

eedy Method
M
The fact that ET ,the set of edges

edg composing a minimum spanning tree of graph G actually a
tree in Prim's algorithm but generally
ge just an acyclic sub graph in Kruskal's
l's algorithm.
Kruskal’s algorithm is not simpler

sim because it has to check whether the aaddition of the next
edge to the edges already selec
lected would create a cycle.
We can consider the algorith rithm's operations as a progression through a series of forests
containing all the vertices off a given graph and some of its edges. The initia
itial forest consists of
|V| trivial trees, each comprisi
ising a single vertex of the graph. The finall forest
f consists of a
single tree, which is a min inimum spanning tree of the graph. On eeach iteration, the
algorithm takes the next edge ge (u, v) from the sorted list of the graph's edges,
ed finds the trees
containing the vertices u andd v, and, if these trees are not the same, uniteites them in a larger
tree by adding the edge (u, v).).
Analysis of Efficiency
The crucial check whether two
wo vertices belong to the same tree can be foun
und out using union-
find algorithms.
Efficiency of Kruskal’s algori
orithm is based on the time needed for sorting ng the edge weights
of a given graph. Hence, withith an efficient sorting algorithm, the time effic
fficiency of Kruskal's
algorithm will be in O (|E| log
og |E|).

eedy Method
M
Illustration
An example of Kruskal’s alg lgorithm is shown below. The
selected edges are shown in bold.
bo

eedy Method
M
3. Single source shortest

rtest paths
Single-source shortest-pathss problem is defined as follows. For a givenen vertex called the
source in a weighted connect
ected graph, the problem is to find shortest paths
pa to all its other
vertices. The single-source shortest-paths
sh problem asks for a family off ppaths, each leading
from the source to a different
ent vertex in the graph, though some paths may,
ma of course, have
edges in common.
3.1. Dijkstra's Algorithm
Dijkstra's Algorithm is the
he best-known algorithm for the single-sou ource shortest-paths
problem. This algorithm is applicable
ap to undirected and directed graphs
hs with nonnegative
weights only.
Working - Dijkstra's algorithm
ithm finds the shortest paths to a graph's vertic
tices in order of their
distance from a given source.
e.
First, it finds the shor
ortest path from the source to a vertex neare
arest to it, then to a
second nearest, and so on.
In general, before its i ith iteration commences, the
algorithm has alreadyy identified the shortest paths to i-1
other vertices nearest
st to the source. These vertices, the
source, and the edgess of
o the shortest paths leading to them
from the source form rm a subtree Ti of the given graph
shown in the figure.
Since all the edge wei
eights are nonnegative, the next vertex nearesrest to the source can
be found among the vertices
ve adjacent to the vertices of Ti. The sett of
o vertices adjacent
to the vertices in Ti can
c be referred to as "fringe vertices"; theyy are the candidates
from which Dijkstra's
's algorithm
a selects the next vertex nearest to the
th source.
To identify the ith nea
earest vertex, the algorithm computes, for eve very fringe vertex u,
ce to the nearest tree vertex v (given by the we
the sum of the distance weight of the edge (v,
u)) and the length d., of
o the shortest path from the source to v (prev
reviously determined
by the algorithm) andd then
t selects the vertex with the smallest such
ch sum. The fact that
it suffices to compare
are the lengths of such special paths is the he central insight of
Dijkstra's algorithm.
To facilitate the algorit
rithm's operations, we label each vertex with tw
two labels.
o The numeric labebel d indicates the length of the shortest pathth from the source to
this vertex foundd by the algorithm so far; when a vertex is added
a to the tree, d
indicates the lengt
gth of the shortest path from the source to that
at vertex.
o The other label indicates
in the name of the next-to-last vertex oon such a path, i.e.,
the parent of thee vertex
v in the tree being constructed. (It cann be left unspecified
for the source s and
an vertices that are adjacent to none of the cur
current tree vertices.)

eedy Method
M
With such labeling,, finding

f the next nearest vertex u* becomes es a simple task of
finding a fringe vertex
ex with the smallest d value. Ties can be broken
en arbitrarily.
After we have identifie
ified a vertex u* to be added to the tree, we ne
need to perform two
operations:
o Move u* from m the fringe to the set of tree vertices.
o For each remaaining fringe vertex u that is connected to u* by an edge of
weight w (u*,, u)
u such that d u*+ w(u*, u) <d u, update the labels of u by u*
and du* + w(u*
u*, u), respectively.
o
Illustration: An example of Dijkstra's algorithm is shown
below. The next closest vertex
tex is shown in bold.
The shortest paths (identified

ed by following nonnumeric labels backward rd from a destination
vertex in the left column to the
th source) and their lengths (given by numeri
eric labels of the tree
vertices) are as follows:

eedy Method
M
The pseudocode of Dijkstra tra’s algorithm is given below. Note that at in the following
pseudocode, VT contains a giv iven source vertex and the fringe contains thee vvertices adjacent to
it after iteration 0 is completed
ted.
Analysis:
The time efficiency of Dijk ijkstra’s algorithm depends on the data structures
st used for
implementing the priority queue
qu and for representing an input graphh itself. For graphs
represented by their adjacency
cy lists and the priority queue implemented as a min-heap, it is in
O ( |E| log |V| )
Applications
Transportation plannin
ing and packet routing in communication netwtworks, including the
Internet
Finding shortest paths
hs in social networks, speech recognition, doc
ocument formatting,
robotics, compilers, and
an airline crew scheduling.

eedy Method
M
4. Optimal Tree problem

blem
Background
Suppose we have to encode a text
t that comprises characters from some n-ccharacter alphabet
by assigning to each of the text's th codeword.There
tex characters some sequence of bits called the
are two types of encoding: Fix
ixed-length encoding, Variable-length encodin
ing
Fixed-length encoding: This
is method assigns to each character a bit string
ng of the same length
m (m >= log2 n). This is exac
actly what the standard ASCII code does. Onne way of getting a
coding scheme that yields a shorter bit string on the average is basedd on the old idea of
assigning shorter code-words
rds to more frequent characters and longerr code-words
c to less
frequent characters.
Variable-length encoding: This Th method assigns code-words of differentt lengths
l to different
characters, introduces a proble
blem that fixed-length encoding does not have
ve. Namely, how can
we tell how many bits of an encoded text represent the first (or, more re generally, the ith)
character? To avoid this compplication, we can limit ourselves to prefix-free
ee (or simply prefix)
codes. In a prefix code, no codeword
co is a prefix of a codeword of anothe
her character. Hence,
with such an encoding, we can simply scan a bit string until we get the firs
irst group of bits that
is a codeword for some character,
cha replace these bits by this characte
cter, and repeat this
operation until the bit string's
's end
e is reached.
If we want to create a binaryary prefix code for some alphabet, it is natur tural to associate the
alphabet's characters with leav
eaves of a binary tree in which all the left edge
ges are labelled by 0
and all the right edges are labe
abelled by 1 (or vice versa). The codeword off a character can then
be obtained by recording thee labels on the simple path from the root too tthe character's leaf.
Since there is no simple path th to a leaf that continues to another leaf, noo ccodeword can be a
prefix of another codeword; hence,
he any such tree yields a prefix code.
Among the many trees thatt can c be constructed in this manner for a givgiven alphabet with
known frequencies of the character
ch occurrences, construction of such
ch a tree that would
assign shorter bit strings too high-frequency characters and longer ones es to low-frequency
characters can be done by thee following greedy algorithm, invented by Dav
avid Huffman.
4.1 Huffman Trees and Codes
Huffman's Algorithm
Step 1: Initialize n one-nodee trees
t and label them with the characters of th the alphabet. Record
cter in its tree's root to indicate the tree's weigh
the frequency of each characte ght. (More generally,
the weight of a tree will be equal
equ to the sum of the frequencies in the tree's 's leaves.)
Step 2: Repeat the followingg operation
o until a single tree is obtained. Find
nd two trees with the
smallest weight. Make them the t left and right subtree of a new tree and nd record the sum of
their weights in the root of the
he new tree as its weight.
ove algorithm is called a Huffman tree. It def
A tree constructed by the abov efines-in the manner
described-a Huffman code.

eedy Method
M
Example: Consider the five-ssymbol alphabet {A, B, C, D, _} with the fol

following occurrence
frequencies in a text made upp of
o these symbols:
The Huffman tree construction

ion for the above problem is shown below:
The resulting codewords are as

a follows:
Hence, DAD is encoded as 011101,

01 and 10011011011101 is decoded as BAD_AD.
BA
With the occurrence frequen
encies given and the codeword lengths obta
btained, the average
number of bits per symboll in this code is
2 * 0.35 + 3 * 0.1+ 2 * 0.2 + 2 * 0.2 + 3 * 0.15 = 2.25.

eedy Method
M
Had we used a fixed-length encoding

en for the same alphabet, we would ha
have to use at least 3
bits per each symbol. Thus, for he compression ratio
fo this example, Huffman’s code achieves the
(a standard measure of a comp
mpression algorithm’s effectiveness) of (3−2.225)/3*100%= 25%.
In other words, Huffman’s encoding
en of the above text will use 25% les
less memory than its
fixed-length encoding.
5. Transform and Conque

nquer Approach
5.1. Heaps
Heap is a partially ordered data
da structure that is especially suitable for imp
mplementing priority
queues. Priority queue is a multiset
m of items with an orderable characteris
ristic called an item’s
priority, with the following operations:
op
• finding an itemm with the highest (i.e., largest) priority
• deleting an item
tem with the highest priority
• adding a new item
it to the multiset
Notion of the Heap
Definition:
A heap can be defined as a binary
b tree with keys assigned to its nodes,
s, one key per node,
provided the following two conditions
co are met:
1. The shape property— —the binary tree is essentially complete (or
or simply complete),
i.e., all its levels aree full
f except possibly the last level, where on
only some rightmost
leaves may be missing ng.
2. The parental dominan ance or heap property—the key in each nod ode is greater than or
equal to the keys in its children.
Illustration:
The illustration of the definiti
ition of heap is shown bellow: only the left moost tree is heap. The
second one is not a heap, bec ecause the tree’s shape property is violated. The
Th left child of last
subtree cannot be empty. And nd the third one is not a heap, because the pparental dominance
fails for the node with key 5.
Properties of Heap
o essentially complete binary tree with n nodes.
1. There exists exactly one n Its height is
equal to
2. The root of a heap alw
lways contains its largest element.

eedy Method
M
3. A node of a heap consinsidered with all its descendants is also a heap.

4. A heap can be implem emented as an array by recording its element nts in the top down,
left-to-right fashion.. ItI is convenient to store the heap’s elemeents in positions 1
through n of such an array, leaving H[0] either unused or puttin tting there a sentinel
whose value is greaterer than every element in the heap. In such a representation,
rep
no keys will be in the first n/2 . positionss of the array, while
a. the parental node
w occupy the last n/2 positions;
the leaf keys will
b. the children of a key in the array’s parental position i (1≤ ≤ /2 ) will be in
≤ i ≤
positions 2i and 2i + 1, and, correspondingly, the parent of a key in position i
ill be in position /2 .
(2 ≤ i ≤ n) will
Heap and its array representation
Thus, we could also define a heap

h as an array H[1..n] in which every elem
ement in position i in
the first half of the array is greater
gr than or equal to the elements in posit
sitions 2i and 2i + 1,
i.e.,
H[i] ≥ max {H [2i], H [22i + 1]} for i = 1. . . /2
Constructions of Heap - Ther

here are two principal alternatives for construct
cting Heap.
1) Bottom-up heap constructio
tion 2) Top-down heap construction
Bottom-up heap construction

ion:
The bottom-up heap construct
uction algorithm is illustrated bellow. It initial
ializes the essentially
complete binary tree with n nodes
no by placing keys in the order given and then
th “heapifies” the
tree as follows.
• Starting with the last
ast parental node, the algorithm checks whhether the parental
dominance holds forr the
th key in this node. If it does not, the algori
orithm exchanges the
node’s key K with theth larger key of its children and checks whether
wh the parental
dominance holds forr K in its new position. This process continues ues until the parental
dominance for K is satisfied.
sat (Eventually, it has to because it hold
lds automatically for
any key in a leaf.)
• After completing thee “heapification” of the subtree rooted at the th current parental
node, the algorithm proceeds
pro to do the same for the node’s immediadiate predecessor.
• The algorithm stops after
af this is done for the root of the tree.

eedy Method
M
Illustration
Bottom-up construction of a heap
h for the list 2, 9, 7, 6, 5, 8. The double headed
he arrows show
key comparisons verifying the
he parental dominance.
Analysis of efficiency - botto

tom up heap construction algorithm:
Assume, for simplicity, that n = 2k − 1 so that a heap’s tree is full, i.e.,., tthe largest possible
eac level. Let h be the height of the tree.
number of nodes occurs on each
rty of heaps in the list at the beginning of thee ssection, h=
According to the first property
or just 1 = k − 1 forf the specific values of n we are consideringing.
Each key on level i of the tree
tre will travel to the leaf level h in the wors
orst case of the heap
construction algorithm. Sincece moving to the next level down requires twoo comparisons—one
to find the larger child and the other to determine whether the exchange is required—the total
number of key comparisons involving
in a key on level i will be 2(h − i).
Therefore, the total number of key comparisons in the worst case will be

eedy Method
M
where the validity of the last

st equality
e can be proved either by using the closed-form
cl formula
for the sum or by mathematical induction on h.

lgorithm, a heap of size n can be constructedd with
Thus, with this bottom-up alg w fewer than 2n
comparisons.
Top-down heap construction

on algorithm:
It constructs a heap by success
essive insertions of a new key into a previously
ly constructed heap.
ode with key K in it after the last leaf of the exi
1. First, attach a new nod xisting heap.
2. Then shift K up to itss appropriate
a place in the new heap as follows. s.
a. Compare K with its ts parent’s
p equal to K, stop (the
key: if the latter is greater than or eq
structure is a heap);); otherwise, swap these two keys and compa pare K with its new
parent.
b. This swapping contin tinues until K is not greater than its last parent
nt or it reaches root.
Obviously, this insertion opeperation cannot require more key comparison sons than the heap’s
height. Since the height of a heap
h with n nodes is about log2 n, the time effi
fficiency of insertion
is in O (log n).
Illustration of inserting a new ne key: Inserting a new key (10) into the
heap is constructed bellow. The T new key is shifted up via a swap with
its parents until it is not larger
er than its parents (or is in the root).
ap: Deleting the root’s key from a heap can

Delete an item from a heap an be done with the
following algorithm:
Maximum Key Deletion from om a heap
ke with the last key K of the heap.
1. Exchange the root’s key
2. Decrease the heap’s size
siz by 1.
er tree by sifting K down the tree exactly in the same way we did
3. “Heapify” the smaller
it in the bottom-upp heap construction algorithm. That is, vverify the parental
dominance for K: if it holds,
h we are done; if not, swap K with the la
larger of its children
and repeat this operatio holds for K in its new
tion until the parental dominance condition hol
position.

eedy Method
M
Illustration
The efficiency of deletion is i determined by the number of key compmparisons needed to

“heapify” the tree after the swap
sw has been made and the size of the tree
ee is decreased by 1.
Since this cannot require moremo key comparisons than twice the heap’p’s height, the time
efficiency of deletion is in O (log
( n) as well.
5.2. Heap Sort

Heapsort - an interesting sort
rting algorithm is discovered by J. W. J. Willi
lliams. This is a two-
stage algorithm that works ass follows.
f
tion): Construct a heap for a given array.
Stage 1 (heap constructio
Stage 2 (maximum deletietions): Apply the root-deletion operation n−11 times
t to the
remaining heap.
As a result, the array element
nts are eliminated in decreasing order. But sin
since under the array
implementation of heaps an element
e being deleted is placed last, the resu
esulting array will be
exactly the original array sorte
rted in increasing order.
Heap sort is traced on a specif

cific input is shown below:

eedy Method
M
Analysis of efficiency:
Since we already know thatt the i in O(n), we have
th heap construction stage of the algorithm is
to investigate just the timee efficiency of the second stage. For the number of key
comparisons, C(n), needed for eliminating the root keys from the heaps of
o diminishing sizes
from n to 2, we get the followi
wing inequality:
This means that C(n) ∈ O(n log

lo n) for the second stage of heapsort.
For both stages, we get O(n)) + O(n log n) = O(n log n).
A more detailed analysis show
ows that the time efficiency of heapsort is, in fact, in Θ(n log n)
in both the worst and average
age cases. Thus, heapsort’s time efficiency fall
alls in the same class
as that of mergesort.
Unlike the latter, heapsort is in-place, i.e., it does not require any extr
xtra storage. Timing
experiments on random filess show
s that heapsort runs more slowly than quicksort
qu but can be
competitive with mergesort.
*****

Vivekananda
College of Engineering & Technology
Nehru Nagar Post,
P Puttur, D.K. 574203
Lecture Notes on
15CS43
Design and Analysis of
Algorithms
(CBCS Scheme)
Prepared by
Harivinod N
Dept. of Computer Science and Engineering,
VCET Puttur
April 2017
Module : Dynamic Programming

Module-4
Contents
1. Introduction to Dynamic Programming 4. Optimal Binary Search Trees

1.1. General method with Examples 5. Knapsack problem
1.2. Multistage Graphs 6. Bellman-Ford
Ford Algorithm
2. Transitive Closure: 7. Travelling Sales Person problem
2.1. Warshall’s Algorithm, 8. Reliability design
3. All Pairs Shortest Paths:
3.1. Floyd's Algorithm,
Course Website
www.TechJourney.in
Lecture Notes | 10CS43 – Design & Analysis
A of Algorithms | Module 4: Dynamic Programming
1. Introduction to Dynamic Programming

Dynamic programming is a technique for solving problems with overlapping subproblems.
subproblems
Typically, these subproblems arise from a recurrence relating a given problem’s solution to
solutions of its smaller subproblems. Rather than solving overlapping subproblems again and
again, dynamic programming suggests solving each of the smaller subproblems only once
and recording the results in a table from which a solution to the original
al problem can then
t be
obtained. [From T1]
The Dynamic programming can also be used when the solution to a problem can be viewed
as the result of sequence of decisions.
decisions [ From T2]. Here are some examples.
Example 1
Example 2
Example 3
Example 4
Prerpared by Harivinod N, Dept of CSE, VCET Puttur Techjourney.in Page| 2


1.2 Multistage Graphs

Figure: Five stage graph


Backward Approach

2. Transitive Closure using Warshall’s Algorithm,

Definition: The transitive closure of a directed graph with n vertices can be defined as the n
× n boolean matrix T = {tij }, in which the element in the ith row and the jth column is 1 if
there exists a nontrivial path (i.e., directed path of a positive length) from the ith vertex to the
jth vertex; otherwise, tij is 0.
Example: An example of a digraph, its adjacency matrix, and its transitive closure is given
below.
(a) Digraph. (b) Its adjacency matrix. (c) Its transitive closure.
We can generate the transitive closure of a digraph with the help of depthfirst search or
first search. Performing either traversal starting at the ith vertex gives the information
breadth-first
about the vertices reachable from it and hence the columns that contain 1’s in the ith row of
the transitive closure. Thus, doing such a traversal for every vertex as a starting point yields
the transitive closure in its entirety.
Since this method traverses the same digraph several times, we can use a better algorithm
called Warshall’s algorithm.. Warshall’s algorithm constructs the transitive closure through
a series of n × n boolean matrices:
Each of these matrices provides certain information about directed paths in the digraph.
Specifically, the element in the ith row and jth column of matrix R(k) (i, j = 1, 2, . . . , n, k
= 0, 1, . . . , n) is equal to 1 if and only if there exists a directed path of a positive length from
the ith vertex to the jth vertex with each intermediate vertex, if any, numbered not higher than
k.
Thus, the series starts with R(0) , which does not allow any intermediate vertices in its paths;
hence, R(0) is nothing other than the adjacency matrix of the digraph.
digraph R(1) contains the
information about paths thatat can use the first vertex as intermediate. The last matrix in the
(n)
series, R , reflects paths that can use all n vertices of the digraph as intermediate and hence
is nothing other than the digraph’s transitive closure.
This means that there exists a path from the ith vertex vi to the jth vertex vj with each
intermediate vertex numbered not higher than k:
vi, a list of intermediate vertices each numbered not higher than k, vj . --- (*)
Two situations regarding this path are possible.

1. In the first, the list of its intermediate vertices does not contain the kth vertex. Then this
−1. i.e. r
path from vi to vj has intermediate vertices numbered not higher than k− 1
2. The secondd possibility is that path (*)(* does contain the kth vertex vk among the
intermediate vertices. Then path (*) can be rewritten as;
vi, vertices numbered ≤ k − 1, vk, vertices numbered ≤ k − 1, vj .
i.e r 1 and r 1
Thus, we have the following formula for generating the elements of matrix R(k) from the
elements of matrix R(k−1)
The Warshall’ss algorithm works based on the above formula.
As an example, the application of Warshall’s algorithm to the digraph is shown below. New
1’s are in bold.

Analysis
Its time efficiency is Θ(n3). We can make the algorithm to run faster by treating matrix rows
as bit strings and employ the bitwise or operation available in most modern computer
languages.
Space efficiency: Although separate matrices for recording intermediate results of the
algorithm are used, that can be avoided.
3. All Pairs Shortest Paths using Floyd's Algorithm,

Problem definition: Given a weighted connected graph (undirected or directed), the all-pairs
all
shortest paths problem asks to find the distances—i.e.,
distances the lengths of the shortest paths - from
each vertex to all other vertices.
Applications: Solution to this problem finds applications in communications, transportation
networks,
tworks, and operations research. Among recent applications of the all--pairs shortest-path
problem is pre-computing
computing distances for motion planning in computer games.
We store the lengths of shortest paths in an n x n matrix D called the distance matrix: the
element dij in the ith row and the jth column of this matrix indicates the length of the shortest
path from the ith vertex to the jth vertex.
(a) Digraph. (b) Its weight matrix. (c) Its distance matrix
We can generate the distance matrix with an algorithm that is very similar to Warshall’s
algorithm. It is called Floyd’s algorithm.
Floyd’s algorithm computes the distance matrix of a weighted graph with n vertices through a
series of n × n matrices:

The element in the ith row and the jth column of matrix D(k) (i, j = 1, 2, . . . , n, k = 0, 1,
he length of the shortest path among all paths from the i vertex to the jth
. . . , n) is equal to the th
vertex with each intermediate vertex, if any, numbered not higher than k.
As in Warshall’s algorithm, we can compute all the elements of each matrix D(k) from its
immediate predecessor D(k−1)
If 1,, then it means that there is a path;
vi, a list of intermediate vertices each numbered not higher than k, vj .

We can partition all such paths into two disjoint subsets: those that do not use the kth vertex vk
as intermediate and those that do.
i. Since the paths of the first subset have their intermediate vertices numbered not higher
than k − 1, the shortest of them is, by definition of our matrices, of length
ii. In the second subset the paths are of the form
vi, vertices numbered ≤ k − 1, vk, vertices numbered ≤ k − 1, vj .
The situation is depicted symbolically in Figure,

Figure which shows
the underlying
nderlying idea of Floyd’s algorithm.
Taking into account the lengths of the shortest paths in both subsets leads to the following
recurrence:
Analysis: Its time efficiency is Θ(n3), similar to the warshall’s algorithm.

Application of Floyd’s algorithm to the digraph is shown below.. Updated elements are shown
in bold.
4. Optimal Binary Search Trees

A binary search tree is one of the most important data structures in computer science. One of
its principal applications is to implement a dictionary, a set of elements with the operations of
searching, insertion, and deletion.
If probabilities of searching for elements of a set are known e.g., from accumulated data
about past searches it is natural to pose a question about an optimal binary search tree for
which the average number of comparisons in a search is the smallest possible.
As an example, consider four keys A, B, C, and D
to be searched for with probabilities 0.1, 0.2, 0.4,
and 0.3, respectively. The figure depicts two out of
14 possible binary search trees containing these
keys.

The average number of comparisons in a successful search in the first of these trees is 0.1 *
1+ 0.2 * 2 + 0.4 * 3+ 0.3 * 4 = 2.9, and
and for the second one it is 0.1 * 2 + 0.2 * 1+ 0.4 * 2 +
0.3 * 3= 2.1. Neither of these two trees is, in fact, optimal.
For our tiny example, we could find the optimal tree byb generating all 14 binary search trees
with these keys. As a general algorithm, this exhaustive-search
exhaustive approach is unrealistic: the
total number of binary search trees with n keys is equal to the nth Catalan number,
which grows to infinity as fast as 4n / n1.5

So let a1, . . . , an be distinct keys ordered from the smallest to the largest and let p1, . . . , pn be
the probabilities of searching for them. Let C(i, j) be the smallest average number of
comparisons made in a successful search in a binary searchse tree Tij made up of keys ai, . . , aj,
where i, j are some integer indices, 1≤ 1 i ≤ j ≤ n.
Following the classic dynamic programming approach, we will find values of C(i, j) for all
smaller instances of the problem, although we are interested just in C(1, n). To derive a
recurrence underlying a dynamic programming algorithm, we will consider all possible ways
to choose a root ak among the keys ai, . . . , aj . For such a binary search tree (Figure 8.8), the
root contains key ak, the left subtree Tik−1 contains keys ai, . . . , ak−1 optimally arranged, and
the right subtree Tjk+1contains keys ak+1, . . . , aj also optimally arranged. (Note how we are
taking advantage of the principle of optimality here.)
If we count tree levels starting with 1 to make the comparison numbers equal the keys’ levels,
the following recurrence relation is obtained:

The two-dimensional
dimensional table in Figure 8.9 shows the values needed for computing C(i, j) by
formula (8.8): they are in row i and the columns to the left of column j and in column j and
the rows below row i. The arrows point to the pairs of entries whose sums are computed in
order to find the smallest one to be recorded as the value of C(i, j). This suggests filling the
table along its diagonals, starting with all zeros on the main diagonal and given probabilities
pi, 1≤ i ≤ n, right above it and moving toward the upper right corner.
The algorithm we just sketched computes C(1, n)—the n) the average number of comparisons for
successful searches in the optimal binary tree.
tree. If we also want to get the optimal tree itself,
we need to maintain another two-dimensional
two dimensional table to record the value of k for which the
minimum in (8.8) is achieved. The table has the same shape as the table in Figure 8.9 and is
filled in the same manner,
nner, starting with entries R(i, i) = i for 1≤
1 i ≤ n. When the table is filled,
its entries indicate indices of the roots of the optimal subtrees, which makes it possible to
reconstruct an optimal tree for the entire set given.

Example: Let us illustrate the algorithm by applying it to the four-key

four key set we used at the
beginning of this section:
The initial tables look like this:
Let us compute C(1, 2):
Thus, out of two possible binary trees containing the first two keys, A and B, the root of the
optimal tree has index 2 (i.e., it contains B), and the average number of comparisons in a
successful search in this tree is 0.4. On finishing the computations we get the following final
tables:
Thus, the average number of key comparisons

comparisons in the optimal tree is equal to 1.7. Since R(1,
4) = 3, the root of the optimal tree contains the third key, i.e., C. Its left subtree is made up of
keys A and B, and its right subtree contains just key D. To find the specific structure of these
subtrees,, we find first their roots by consulting the root table again as follows. Since R(1, 2) =
2, the root of the optimal tree containing A and B is B, with A being its left child (and the
root of the one-node tree: R(1, 1) = 1). Since R(4, 4) = 4, the root of this one-node
one optimal
tree is its only key D. Figure given below presents the optimal tree in its entirety.
Here is Pseudocode of the dynamic programming algorithm.

5. Knapsack problem
We start this section with designing a dynamic programming algorithm for the knapsack
problem: given n items of known weights w1, . . . , wn and values v1, . . . , vn and a knapsack
of capacity W, find the most valuable subset of the items that fit into the knapsack.
To design a dynamic programming algorithm, we need to derive a recurrence relation that
expresses a solution to an instance of the knapsack problem in terms of solutions to its
smaller subinstances.
Let us consider an instance defined by the first i items, 1≤1 i ≤ n, with weights w1, . . . , wi,
values v1, . . . , vi , and knapsack capacity j, 1 ≤ j ≤ W. Let F(i, j) be the value of an optimal
solution to this instance. We can divide all the subsets of the first i items that fit the knapsack
th ith item and those that do. Note
of capacity j into two categories: those that do not include the
the following:
i. Among the subsets that do not include the ith item, the value of an optimal subset is,
by definition, F(i − 1, j).
ii. Among the subsets that do include the ith item (hence, j − wi ≥ 0), an optimal subset is
made
de up of this item and an optimal subset of the first i−1
i−1 items that fits into the
knapsack of capacity j − wi . The value of such an optimal subset is vi + F(i − 1, j −
wi).

Thus, the value of an optimal solution among all feasible subsets of the first I items is the
maximum of these two values.
It is convenient to define the initial conditions as follows:

F(0, j) = 0 for j ≥ 0 and F(i, 0) = 0 for i ≥ 0.
Our goal is to find F(n, W), the maximal value of a subset of the n given items that fit into
the knapsack
psack of capacity W, and an optimal subset itself.
Example-1: Let us consider the instance given by the following data:
The dynamic programming table, filled by applying formulas is given below
Thus, the maximal value is F(4, 5) = $37.
We can find the composition of an optimal subset by backtracing the computations of this
entry in the table. Since F(4, 5) > F(3, 5), item 4 has to be included in an optimal solution
along with an optimal subset for filling 5 − 2 = 3 remaining units of the knapsack capacity.
ca
The value of the latter is F(3, 3). Since F(3, 3) = F(2, 3), item 3 need not be in an optimal
subset. Since F(2, 3) > F(1, 3), item 2 is a part of an optimal selection, which leaves element
F(1, 3 − 1) to specify its remaining composition. Similarly,
Similarly, since F(1, 2) > F(0, 2), item 1 is
the final part of the optimal solution {item 1, item 2, item 4}.

Analysis
The time efficiency and space efficiency of this algorithm are both in Θ(nW). The time
needed to find the composition of an optimal solution is
i in O(n).
Memory Functions
The direct top-down
down approach to finding a solution to such a recurrence leads to an algorithm
that solves common subproblems more than once and hence is very inefficient.
inefficient
The classic dynamic programming approach, on the other hand, works bottom up: it fills a
table with solutions to all smaller subproblems, but each of them is solved only once. An
unsatisfying aspect of this approach is that solutions to some of these smaller subproblems
are often not necessary for getting a solution
so to the problem given. Since this drawback is not
present in the top-down
down approach, it is natural to try to combine the strengths of the top-down
top
and bottom-up approaches. The goal is to get a method that solves only subproblems that are
necessary andnd does so only once. Such a method exists; it is based on using memory
functions.
This method solves a given problem in the top-down top down manner but, in addition, maintains a
table of the kind that would have been used by a bottom-up
bottom up dynamic programming algorithm.
algori
Initially, all the table’s entries are initialized with a special “null” symbol to indicate that they
have not yet been calculated. Thereafter, whenever a new value needs to be calculated, the
method checks the corresponding entry in the table first: if this entry is not “null,” it is simply
retrieved from the table; otherwise, it is computed by the recursive call whose result is then
recorded in the table.
The following algorithm implements this idea for the knapsack problem. After initializing the
table,
ble, the recursive function needs to be called with i = n (the number of items) and j = W
(the knapsack capacity).
Algorithm MFKnapsack(i, j )
//Implements the memory function method for the knapsack problem
//Input: A nonnegative integer i indicating the number of the first items being
considered and a nonnegative integer j indicating the knapsack capacity
//Output: The value of an optimal feasible subset of the first i items
//Note: Uses as global variables input arrays
arrays Weights[1..n], V alues[1..n], and
table F[0..n, 0..W ] whose entries are initialized with −1’s except for
row 0 and column 0 initialized with 0’s

Example-2 Let us apply the memory function method to the instance considered in Example
1. The table in Figure given below gives the results. Only 11 out of 20 nontrivial values (i.e.,
not those in row 0 or in column 0) have been computed. Just one nontrivial entry, V (1, 2), is
retrieved rather than being recomputed. For larger instances,
stances, the proportion of such entries
can be significantly larger.
Figure: Example of solving an instance of the knapsack problem by the memory function algorithm
In general, we cannot expect more than a constant-factor

constant factor gain in using the memory function
method for the knapsack problem, because its time efficiency class is the same as that of the
bottom-up algorithm
6. Bellman-Ford
Ford Algorithm (Single source shortest path with –ve
ve weights)
Problem definition
Single source shortest path - Given a graph
gra and a source vertex s in graph, find shortest paths
from s to all vertices in the given graph. The graph may contain negative weight edges.
Note that wee have discussed Dijkstra’s algorithm for single source shortest path problem.
Dijksra’s algorithm is a Greedy algorithm and time
ti complexity is O(VlogV)
ogV). But Dijkstra
doesn’t work for graphs
raphs with negative weight edges.
edges
Bellman-Ford
Ford works for such graphs. Bellman
Bellman-Ford
Ford is also simpler than Dijkstra and suites
well for distributed systems. But time complexity of Bellman
Bellman-Ford
Ford is O(VE), which is more
than Dijkstra.
How it works?
Like other Dynamic Programming Problems, the algorithm calculates shortest paths in
bottom-up
up manner. It first calculates the shortest distances for the shortest paths which have
at-most
most one edge in the path. Then, it calculates
cal shortest paths with at-most
ost 2 edges, and so
th
on. After the i iteration of outer loop, the shortest paths with at most i edges are calculated.
There can be maximum |V| – 1 edges in any simple path, that is why the outer loop runs |v| –
1 times. The idea is, assuming that there is no negative weight cycle, if we have calculated
shortest paths with
th at most i edges, then an iteration over all edges guarantees to give shortest
path with at-most (i+1) edges

Bellman-Ford
Ford algorithm to compute shortest path

7. Travelling Sales Person problem (T2:5.9),



8. Reliability design



Vivekananda
College of Engineering & Technology
Nehru Nagar Post,
P Puttur, D.K. 574203
Lecture Notes on
15CS43
Design and Analysis of
Algorithms
(CBCS Scheme)
Prepared by
Harivinod N
Dept. of Computer Science and Engineering,
VCET Puttur
May 2017
Module : Backtracking
Module-5
Contents
1. Backtracking: 3. 0/1 Knapsack problem

1.1. General method 3.1. LC Branch and Bound solution
1.2. N-Queens problem 3.2. FIFO Branch and Bound solution
1.3. Sum of subsets problem 4. NP-Complete
Complete and NP-Hard
NP problems
1.4. Graph coloring 4.1. Basic concepts
1.5. Hamiltonian cycles 4.2. Non-deterministic
deterministic algorithms
alg
2. Branch and Bound: 4.3. P, NP, NP-Complete,
Complete, and NP-Hard
NP
2.1. Assignment Problem, classes
2.2. Travelling Sales Person problem
Course Website
www.TechJourney.in
1. Backtracking
Some problems can be solved,
solved by exhaustive search. The exhaustive-search
exhaustive technique
suggests generating all candidate solutions and then identifying the one (or the ones) with a
desired property.
Backtracking is a more intelligent variation of this approach. The principal idea is to
construct solutions one component at a time and evaluate such partially constructed
candidates as follows. If a partially constructed solution can be developed further without
violating the problem’s constraints, it is done by taking the first remaining legitimate option
for the next component. If there is no legitimate option for the next component, no
alternatives for any remaining component need to be considered. In this case, the algorithm
backtracks to replace the last component of the partially constructed solution with its next
option.
It is convenient to implement this kind of processing by constructing a tree of choices being
made, called the state-space tree Its root represents an initial state before the search for a
space tree.
solution begins. The nodes of the first level in the tree represent the choices made for the first
component of a solution; the nodes of the second level represent the choices for the second
component, and so on. A node in a state-space
state space tree is said to be promising if it corresponds to
a partially constructed solution that may still lead to a complete solution; otherwise,
o it is
called non-promising.. Leaves represent either non-promising
non promising dead ends or complete
solutions found by the algorithm.
In the majority of cases, a statespace tree for a backtracking algorithm is constructed in the
manner of depth-first search.. If the current node is promising, its child is generated by adding
the first remaining legitimate option for the next component of a solution, and the processing
moves to this child. If the current node turns out to be non-promising,
non promising, the algorithm
backtracks
racks to the node’s parent to consider the next possible option for its last component; if
there is no such option, it backtracks one more level up the tree, and so on. Finally, if the
algorithm reaches a complete solution to the problem, it either stops (if just one solution is
required) or continues searching for other possible solutions.
1.1 General method (Textbook

Textbook T2:7.1)

General Algorithm (Recursive)
General Algorithm (Iterative)

General Algorithm for backtracking (From textbook T1)
1.2 N-Queens problem (Textbook

Textbook T1:12.1),
The problem is to place n queens on an n × n chessboard so that no two queens attack each
other by being in the same row or in the same column or on the same diagonal.
So let us consider the four-queens
queens problem and solve it by the backtracking technique.
Since each of the four queens has to be placed in its own row, all we need to do is to assign a
column for each queen
ueen on the board presented in figure.
f

We start with the empty board and then place queen 1 in the first possible position of its row,
which is in column 1 of row 1. Then we place queen 2, after trying unsuccessfully columns 1
and 2, in the first acceptable position for it, which is square (2, 3), the square in row 2 and
column 3. This proves to be a dead end because there is no acceptable position for queen 3.
So, the algorithm backtracks and puts queen 2 in the next possible position at (2, 4). Then
queen 3 is placed at (3, 2), which proves to be another dead end. The algorithm algorith then
backtracks all the way to queen 1 and moves it to (1, 2). Queen 2 then goes to (2, 4), queen 3
to (3, 1), and queen 4 to (4, 3), which is a solution to the problem. The state-space
state tree of this
search is shown in figure.
Figure: State-space
space tree of solving the four-queens
queens problem by backtracking.
× denotes an unsuccessful attempt to place a queen in the indicated column. The
numbers above the nodes indicate the order in which the nodes are generated.
If other solutions need to be found, the algorithm can simply resume its operations at the leaf
at which it stopped. Alternatively, we can use the board’s symmetry for this purpose.
Finally, it should be pointed out that a single solution to the n-queens
n problem for any n ≥ 4
can be found in linear time.
Note: The algorithm NQueens() is not in the syllabus. It is given here for interested learners.
The algorithm is referred from textbook T2.
T2

1.3 Sum
um of subsets problem
Problem definition: Find a subset of a given set A = {a1, . . . , an } of n positive integers
whose sum is equal to a given positive integer d.
For example, for A = {1, 2, 5, 6, 8} and d = 9, there are two solutions: {1, 2, 6} and {1, 8}.
Of course, some instances of this problem may have no solutions.
It is convenient to sort the set’s elements in increasing order. So, we will assume that
a1< a2 < . . . < an.
The state-space
space tree can be constructed as a binary tree like that in Figure shown below for
the instance A = {3, 5, 6, 7} and d = 15.
The number inside a node is the sum of the elements already included in the subsets
represented by the node. The inequality below a leaf indicates the reason for its termination.

The root of the tree represents

ents the starting point, with no decisions about the given elements
made as yet. Its left and right children represent, respectively, inclusion and exclusion of a1 in
a set being sought.
Similarly, going to the left from a node of the first level corresponds to inclusion of a2 while
going to the right corresponds to its exclusion, and so on. Thus, a path from the root to a node
on the ith level of the tree indicates which of the first i numbers have been included in the
subsets represented by that node.
We record the value of s, the sum of these numbers, in the node. If s is equal to d, we have a
solution to the problem. We can either report this result and stop or, if all the solutions need
parent. If s is not equal to d, we can
to be found, continue by backtracking to the node’s parent.
terminate the node as non-promising
promising if either of the following two inequalities holds:
Example: Apply backtracking to solve the following instance of the subset sum problem: A
= {1, 3, 4, 5} and d = 11.
1.4 Graph coloring



Analysis

1.5 Hamiltonian cycles


2. Branch and Bound

Recall that the central idea of backtracking, discussed in the previous section, is to cut off a
branch of the problem’s state-space
state space tree as soon as we can deduce that it cannot lead to a
solution. This idea can be strengthened further if we deal with an optimization problem.
An optimization problem seeks to minimize or maximize some objective function f (a tour
length, the value of items selected, the cost of an assignment, and the like), usually subject to
some constraints. Ann optimal solution is a feasible solution with the best value of the
objective function (e.g., the shortest Hamiltonian circuit
circuit or the most valuable subset of items
that fit the knapsack).
Compared to backtracking, branch-and-bound
branch bound requires two additional items:
1. a way to provide, for every node of a state-space
state tree, a bound on the best value of
the objective function on any solution
olution that can be obtained by adding further
components
omponents to the partially constructed solution represented by the node
2. the value of the best solution seen so far
In general, we terminate a search path at the current node in a state-space
state space tree of a branch-
and-bound
bound algorithm for any one of the following three reasons:
1. The value of the node’s bound is not better than the value of the best solution seen so
far.
2. The node represents no feasible solutions because the constraints of the problem are
already violated.
3. The subset of feasible solutions represented by the node consists of a single point (and
hence no further choices can be made)—in
made) in this case, we compare the value of the
objective function for this feasible solution with that of the best solution seen so far
and update the latter with the former if the new solution is better.
2.1 Assignment Problem

Let us illustrate the branch-and
and-bound
bound approach by applying it to the problem of assigning n
people to n jobs so that the total cost of the assignment is as small as possible.
Ann instance of the assignment problem is specified by an n × n cost matrix C so that we can
state the problem as follows: select one element in each row of the matrix so that no two
selected elements are in the same column and their
their sum is the smallest possible. We will
demonstrate how this problem can be solved using the branch-and-bound
branch bound technique by
considering the small instance of the problem.
problem Consider the data given below.

How can we find a lower bound on the cost of an optimal selection without actually solving
the problem?
We can do this by several methods. For example, it is clear that the cost of any solution,
solution
including an optimal one, cannot be smaller than the sum of the smallest elements in each
of the matrix’s rows.. For the instance here, this sum is 2 + 3+ 1+ 4 = 10. We can and will
apply the same thinking to partially constructed solutions. For example, for any legitimate
selection that selects 9 from the first row, the lower bound will be 9 + 3 + 1+ 4 = 17.
Rather
ather than generating a single child of the last promising node as we did in backtracking, we
will generate all the children of the most promising node among non-terminated
terminated leaves in the
current tree. (Nonterminated, i.e., still promising, leaves are also called live.) How can we tell
which of the nodes is most promising? We can do this by comparing the lower bounds of the
live nodes. It is sensible to consider a node with the best bound as most promising, although
this does not, of course, preclude the possibility
possibility that an optimal solution will ultimately
belong to a different branch of the state-space
state tree. This variation of the strategy is called the
best-first branch-and-bound
bound.
We start with the root that corresponds to no elements selected from the cost matrix. The
lower-bound
bound value for the root, denoted lb, is 10. The nodes on the first level of the tree
correspond to selections of an element in the first row of the matrix, i.e., a job for person a.
a
See the figure given below.
Figure: Levels 0 and 1 of the state-space

state space tree for the instance of the assignment
problem being solved with the best-first
best branch-and-bound
bound algorithm. The number
above a node shows the order in which the node was generated. A node’s fields
indicate the job number assigned to person a and the lower bound value, lb, for this
node.
So we have four live leaves— —nodes 1 through 4—that

that may contain an optimal solution. The
most promising of them is node 2 because it has the smallest lowerbound value. Following
our best-first
irst search strategy, we branch out from that node first by considering the three
different ways of selecting an element from the second row
row and not in the second column -
the three different jobs that can be assigned to person b.
b See the figure given below
belo (Fig
12.7).

Of the six live leaves—nodes

nodes 1, 3, 4, 5, 6, and 7—that
7 that may contain an optimal solution, we
again choose the one with the smallest lower bound, node 5. First, we consider selecting the
third column’s element from c’s row (i.e., assigning person
pers c to job 3); this leaves us with no
choice but to select the element from the fourth column of d’s row (assigning person d to job
4). This yields leaf 8 (Figure 12.7), which corresponds to the feasible solution {a→2,{a b→1,
c→3, d →4} with the total cost of 13. Its sibling, node 9, corresponds to the feasible solution
{a→2, b→1, c→4, d →3} 3} with the total cost of 25. Since its cost is larger than the cost of the
solution represented by leaf 8, node 9 is simply terminated. (Of course, if its cost were
smallerr than 13, we would have to replace the information about the best solution seen so far
with the data provided by this node.)
Now, as we inspect each of the live leaves of the last state-space

state tree—nodes
nodes 1, 3, 4, 6, and 7
in Figure 12.7—we discover that their lower-bound
lower values are not smaller than 13, the value
of the best selection seen so far (leaf 8). Hence, we terminate all of them and recognize the
solution represented by leaf 8 as the optimal solution to the problem.
2.2 Travelling Sales Person problem

We will be able to apply the branch-and-bound
branch bound technique to instances of the traveling
salesman problem if we come up with a reasonable lower bound on tour lengths. One very
simple lower bound can be obtained by finding the smallest element in the intercity distance
matrix D and multiplying it by the number of cities n.

But there is a less obvious and more informative lower bound for instances with symmetric
matrix D, which does not require a lot of work to compute. We can an compute a lower bound
on the length l of any tour as follows. For each city i, 1≤
1 i ≤ n, find the sum si of the distances
from city i to the two nearest cities; compute the sum s of these n numbers, divide the result
by 2, and, if all the distances are integers, round up the result to the nearest integer:
lb s/2 ... (1)
For example, for the instance in Figure 2.2a,
2.2 formula (1) yields
Moreover, for any subset of tours that must include particular edges of a given graph, we can
modify lower bound (formula
formula 1) accordingly. For example, for all the Hamiltonian circuits of
the graph in Figure 2.2aa that must include edge (a, d), we get the following lower bound by
summing up the lengths of the two shortest edgeses incident with each of the vertices, with the
required inclusion of edges (a, d) and (d, a):
We now apply the branch-and and-bound algorithm, with the bounding ing function given by
formula-1,, to find the shortest Hamiltonian circuit
circuit for the graph in Figure 2.2a.
2.
To reduce the amount of potential work, we take
take advantage of two observations.
1. First, without loss of generality, we can consider only tours that start at a.
2. Second, because our graph is undirected, we can generate only tours in which b is
visited before c. (Refer Note at the end of section 2.2 for more details)
In addition, after visiting n−−1=
1= 4 cities, a tour has no choice but to visit the remaining
unvisited city and return to the starting one. The state-space
state space tree tracing the algorithm’s
application is given in Figure 2.2b.
2.2
Note: An inspection of graph with 4 nodes (figure given below) reveals

reveals three pairs of tours
that differ only by their direction. Hence, we could cut the number of vertex permutations by
half. We could, for example, choose any two intermediate vertices, say, b and c, and then
consider only permutations in which b precedes
precedes c. (This trick implicitly defines a tour’s
direction.)
Figure: Solution to a small instance of the traveling salesman problem by exhaustive search.

Figure 2.2 (a) Weighted graph. (b) State-space

State tree of the branch-and-bound
bound algorithm to
find a shortest Hamiltonian circuit in this graph. The list of vertices in a node specifies a
beginning part of the Hamiltonian circuits represented by the node.
Discussion
The strengths and weaknesses of backtracking are applicable to branch-and
branch and-bound as well.
The state-space tree technique enables us to solve many large instances of difficult
combinatorial problems. As a rule, however, it is virtually impossible to predict which
instances will be solvable in a realistic amount of time and which will not.
In contrast
trast to backtracking, solving a problem by branch-and-bound
branch bound has both the challenge
and opportunity of choosing the order of node generation and finding a good bounding
function. Though the best-first
first rule we used above is a sensible approach, it may or may
ma not
lead to a solution faster than other strategies. (Artificial intelligence researchers are
particularly interested in different strategies for developing state-space
space trees.)
Finding a good bounding function is usually not a simple task. On the one hand, we want this
function to be easy to compute. On the other hand, it cannot be too simplistic - otherwise, it
would fail in its principal task to prune as many branches of a state-space
space tree as soon as
possible. Striking a proper balance between these two competing requirements may require
intensive experimentation with a wide variety of instances of the problem in question.

3. 0/1 Knapsack
sack problem
Note: For this topic as per the syllabus both textbooks T1 & T2 are suggested.
Here we discuss the concepts
conce from T1 first and then that of from T2.
T2
Topic form T1 (Levitin)
Let us now discuss how we can apply the branch-and-bound
branch bound technique to solving the
knapsack problem. Given
iven n items of known weights wi and values vi , i = 1, 2, . . . , n, and a
knapsack of capacity W, find the most valuable subset of the items that fit in the knapsack.
knapsack
, 0 1
It is convenient to order the items of a given instance in descending order by their value-to-
weight ratios.
Each node on the ith level of state space tree, 0 ≤ i ≤ n, represents all the subsets of n items
that include a particular selection made from the first i ordered items. This particular
selection is uniquely determined by the path from the root to the node: a branch going to the
left indicates the inclusion of the next item, and a branch going to the right indicates its
exclusion.
We record the total weight w and the total value v of this selection in the node, along with
some upper bound ub on the value of any subset that can be obtained by adding zero or more
items to this selection. A simple way to compute the upper bound ub is to add to v, the total
value of the items already selected, the product of the remaining capacity of the knapsack
W − w and the best per unit payoff among the remaining items, which is vi+1/wi+1:
ub = v + (W − w)(vi+1/wi+1).
Example: Consider the following problem.
problem. The items are already ordered in descending
order of their value-to-weight
weight ratios.
ratios
Let us apply the branch-and-bound

bound algorithm.
algorithm At the root of the state-space
space tree (see Figure
12.8), no items have been selected as yet. Hence, both the total weight of the items already
selected w and their total value v are equal to 0. The value of the upper bound is 100.
Node 1, the left child of the root, represents the subsets that include item 1. The total weight
and value of the items
ems already included are 4 and 40, respectively; the value of the upperuppe
bound is 40 + (10 − 4) * 6 = 76.

Node 2 represents the subsets that do not include item

item 1. Accordingly, w = 0, v = 0, and ub =
0 + (10 − 0) * 6 = 60. Since node 1 has a larger upper bound than the upper bound of node 2,
it is more promising for this maximization problem, and we branch from node 1 first. Its
children—nodes 3 and 4—represen
representt subsets with item 1 and with and without item 2,
respectively. Since the total weight w of every subset represented by node 3 exceeds the
knapsack’s capacity, node 3 can be terminated immediately.
Node 4 has the same values of w and v as its parent; the upper bound ub is equal to 40 + (10
− 4) * 5 = 70. Selecting node 4 over node 2 for the next branching (Due
(Due to better ub),
ub we get
nodes 5 and 6 by respectively including and excluding item 3. The total weights and values as
well as the upper bounds for these
these nodes are computed in the same way as for the preceding
nodes.
Branching from node 5 yields node 7, which represents no feasible solutions, and node 8,
which represents just a single subset {1, 3} of value 65. The remaining live nodes 2 and 6
have smaller upper-bound
bound values than the value of the solution represented by node 8. Hence,
both can be terminated making the subset {1, 3} of node 8 the optimal solution to the
problem.
Solving the knapsack problem by a branch-and-bound

branch bound algorithm has a rather unusual
characteristic. Typically, internal nodes of a state-space
state space tree do not define a point of the
problem’s search space, because some of the solution’s components remain undefined. (See,
for example, the branch-and and-bound tree for the assignment problem discussed in the

preceding subsection.) For the knapsack problem, however, every node of the tree represents
a subset of the items given. We can use this fact to update the information about the best
subset seen so far after generating each new node in the tree. If we had done this for the
instance investigated above, we could have terminated nodes 2 and 6 before node 8 was
generated because they both are inferior
i to the subset of value 65 of node 5.
Concepts form textbook T2 (Horowitz)

(Horowitz
Let us understandd some of the terminologies used in backtracking & branch and bound.
bound
→ Live node - a node which has been generated and all of whose children
children are not yet been
generated.
→ E-node - is a live node whose children are currently being explored. In other words, an E-
E
node is a node currently being expanded.
→ Dead node - a node that is either not to be expanded further, or for which all of its
children have been generated
→ Bounding Function - will be used to kill live nodes without generating all their children.
→ Backtracking - is depth first node generation with bounding functions.
→ Branch-And-Bound is a method in which E-node
E remains E-node
node until it is dead.
→ Breadth-First-Search: Branch-and
Branch Bound with each new node placed in a queue. queue The
front of the queen becomes the new E-node.
E
→ Depth-Search (D-Search):
Search): New nodes are placed in to a stack. The last node added is the
first to be explored.

0/1 Knapsack problem - Branch and Bound based solution

As the technique discussed here is applicable for minimization problems, let us convert the
knapsack problem (maximizing the profit) into minimization problem by negating the
objective function

3.1 LC (Least Cost) Branch and Bound solution


3.2 FIFO Branch and Bound solution

Conclusion

4. NP-Complete
NP problems
4.1 Basic concepts
For many of the problems we know and study, the best algorithms for their solution have
computing times cann be clustered into two groups;
1. Solutions are bounded by the polynomial- Examples include Binary search O(log n),
Linear search O(n), sorting algorithms like merge sort O(n log n),, Bubble sort O(n2)
trix multiplication O(n3) or in general O(nk) where k is a constant.
& matrix
2. Solutions are bounded by a non-polynomial
non - Examples include travelling salesman
2 n n/2
problem O(n 2 ) & knapsack problem O(2 ). As the time increases exponentially,
even moderate size problems cannot be solved.
So far, noo one has been able to device an algorithm which is bounded by the polynomial for
the problems belonging to the non-polynomial. However impossibility of such an algorithm
is not proved.
4.2 Non deterministic algorithms

We also need the idea of two models of computer (Turing machine): deterministic and non- non
deterministic. A deterministic computer is the regular computer we always thinking of; a non-
non
deterministic computer is one that is just like we’re used to except that is has unlimited
parallelism, so that any time you come to a branch, you spawn a new “process” and
an examine
both sides.
When the result of every operation is uniquely defined then it is called deterministic
algorithm.
When the outcome is not uniquely defined but is limited to a specific set of possibilities, we
call it non deterministic algorithm.
We use new statements to specify such
suc non deterministic h algorithms.
• choice(S) - arbitrarily choose one of the elements of set S
• failure - signals an unsuccessful completion
• success - signals a successful completion
The assignment X = choice(1:n) could result in X being assigned any value from the integer
range[1..n]. There is no rule specifying how this value is chosen.
“The
The nondeterministic algorithms terminates unsuccessfully iff there is no set of choices
which leads to the successful signal”.
signal
Example-1: Searching an element x in a given set of elements A(1:n). We are required to
determine an index j such that A(j) = x or j = 0 if x is not present.
j := choice(1:n)
if A(j) = x then print(j); success endif

print(‘0’); failure
Example-2: Checking whether n integers are sorted or not
procedure NSORT(A,n);
//sort n positive integers//
var integer A(n), B(n), n, i, j;
begin
B := 0; //B is initialized to zero//
for i := 1 to n do
begin
j := choice(1:n);
if B(j) <> 0 then failure;
B(j) := A(j);
end;
for i := 1 to n-11 do //verify order//

if B(i) > B(i+1) then failure;
print(B);
success;
end.
“A
A nondeterministic machine does not make any copies of an algorithm every time a choice
is to be made. Instead it has the ability to correctly choose an element from the given set”.
set
A deterministic interpretation of the nondeterministic algorithm can be done by making
unbounded parallelism
lism in the computation. Each time a choice is to be made, the algorithm
makes several copies of itself, one copy is made for each of the possible choices.
Decision
sion vs Optimization algorithms
An optimization problem tries to find an optimal solution.
A decision problem tries to answer a yes/no question. Most of the problems can be specified
in decision and optimization versions.
For example, Traveling
raveling salesman problem can be stated as two ways
• Optimization - find hamiltonian cycle of minimum weight,
• Decision - is there a hamiltonian cycle of weight ≤ k?
For graph coloring problem,
• Optimization – find the minimum number of colors needed to color the vertices of a
graph so that no two adjacent vertices are colored the same color
• Decision - whether there exists such a coloring of the graph’s
graph s vertices with no more
than m colors?
Many optimization problems can be recast in to decision problems with the property that the
decision algorithm can be solved in polynomial time if and only iff the corresponding
correspondin
optimization problem.
4.3 P, NP, NP-Complete
NP classes

NP stands for Non-deterministic

deterministic Polynomial time.
Definition: P is a set of all decision problems solvable by a deterministic algorithm in
polynomial time.
Definition: NP is the set of all decision problems solvable by a nondeterministic algorithm in
polynomial time. This also implies P ⊆ NP
Problems known to be in P are trivially in NP — the nondeterministic machine just never

troubles itself to fork another process, and acts just like a deterministic one. One example of a
problem not in P but in NP is Integer Factorization.
Factorization
But there are some problems which are known to be in NP but don’t know if they’re
t in P. The
traditional example is the decision-problem
decision version of the Travelling
ing Salesman Problem
(decision-TSP). ). It’s not known whether decision-TSP
decision TSP is in P: there’s no known poly-time
poly
solution, but there’s no proof such a solution doesn’t exist.
There are problems that are known to be neither in P nor NP; a simple example is to
enumerate all the bit vectors of length n. No matter what, that takes 2n steps.
Now, one more concept: given decision problems P and Q, if an algorithm can transform a
tion for P into a solution for Q in polynomial time, it’s said that Q is poly-time
solution
reducible (or just reducible) to P.
The most famouss unsolved problem in computer science
s is “whether P=NP or P≠NP? ”
Figure: Commonly believed Figure: Commonly believed relationship between P, NP, NP-
NP
relationship between P and NP Complete and NP-hard
hard problems
Definition: A decision problem D is said to be NP-complete if:

1. it belongs to class NP
2. every problem in NP is polynomially reducible to D
The fact that closely related decision problems are polynomially reducible to each other is not
very surprising. For example, Hamiltonian circuit problem is polynomially reducible to the
decision version of the traveling salesman problem.
problem

NP-Complete problems have the property that it can be solved in polynomial time if all other
NP-Complete
Complete problems can be solved in polynomial time. i.e if anyone ever finds a poly-time
poly
complete problem, they’ve automatically got one for all the NP-complete
solution to one NP-complete
problems;
roblems; that will also mean that P=NP.
Example for NP-complete
complete is CNF-satisfiability problem. The CNF-satisfiability
satisfiability problem
deals with boolean expressions. This is given by Cook in 1971. The CNF-satisfiability
CNF
problem asks whether or not one can assign values
v true and false to variables of a given
boolean expression in its CNF form to make the entire expression true.
Over the years many problems in NP have been proved to be in P (like Primality Testing).
Still, there are many problems in NP not proved to be in P. i.e. the question still remains
whether P=NP? NP Complete Problems helps in solving this question. They are a subset
of NP problems with the property that all other NP problems can be reduced
duced to any of them in
polynomial time. So, they are the hardest problems in NP, in terms of running time. If it can
be showed that any NP-Complete
omplete problem is in P, then all problems in NP will be in P
(because of NP-Complete definition), and hence P=NP=NPC.
NP Hard Problems - These problems need not have any bound on their running time. If
any NP-Complete Problem is polynomial time reducible to a problem X, that problem X
belongs to NP-Hard
Hard class. Hence, all NP-Complete problems are also NP-Hard.
N In other
words if a NP-Hard problem is non-deterministic
non deterministic polynomial time solvable, it is a NP-
Complete problem. Example of a NP problem that is not NPC is Halting Problem.
Problem
If a NP-Hard problem can be solved
solv in polynomial time then all NP-Complete
Complete can be solved
in polynomial time.
“All NP-Complete
Complete problems are NP-Hard
NP but not all NP-Hard
Hard problems are not NP-
NP
Complete.” NP-Complete
Complete problems are subclass of NP-Hard
NP
The more conventional optimization version of Traveling Salesman Problem for finding the
shortest route is NP-hard,
hard, not strictly NP-complete.
NP
*****

Vivekananda: Lecture Notes On

Uploaded by

Copyright:

Available Formats

Vivekananda: Lecture Notes On

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Vivekananda: Lecture Notes On

Uploaded by

Copyright:

Available Formats

Vivekananda

Module--1 : Introduction to Algorithms

1. Introduction 4. Important Proroblem Types

Prerpared by Harivinod N www.techjourney.in Page|1.2

Prerpared by Harivinod N www.techjourney.in Page|1.3

1.2. Algorithm Specification

In C++ the same algorithm can be specified as follows

Here Type is a basic or user defined

Example 3: Tower of Hanoii problem

Prerpared by Harivinod N www.techjourney.in Page|1.4

1.3. Analysis Framework

Measuring an Input’s Size

Units for Measuring Runnin

Prerpared by Harivinod N www.techjourney.in Page|1.5

Let cop be the execution timee of an algorithm's basic operation on a partic

Algorithms that require an exponential

Worst-Case, Best-Case, and

Prerpared by Harivinod N www.techjourney.in Page|1.6

The running time of above algorithm

Investigation of the average-ccase efficiency is considerably more difficult

Prerpared by Harivinod N www.techjourney.in Page|1.7

Summary of analysis framew

2.1 Space complexity

Here fixed component depend aracteristics Sp=0

Prerpared by Harivinod N www.techjourney.in Page|1.8

2.2 Time complexity

timate that invocation of sum( ) executes tota

Prerpared by Harivinod N www.techjourney.in Page|1.9

Example-2: matrix addition

3.1. Big-Oh notation

Prerpared by Harivinod N www.techjourney.in Page|1.10

Informally, O(g(n)) is the sett of

ormally prove 100n + 5 ∈ O(n2)

Example: To prove n2 + n = O(n3)

Strategies for Big-O Someti

Prerpared by Harivinod N www.techjourney.in Page|1.11

3.2. Omega notation

Here is an example of the formrmal proof that n3 ∈ Ω(n2):

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

3.3. Theta notation

Prerpared by Harivinod N www.techjourney.in Page|1.12

Strategies for Ω and Θ

Prerpared by Harivinod N www.techjourney.in Page|1.13

Prerpared by Harivinod N www.techjourney.in Page|1.14

3.4. Little Oh The function f(n)

For comparing the order of growth

If the case-1 holds good in the

Prerpared by Harivinod N www.techjourney.in Page|1.15

3.5. Basic asymptotic Efficien

Prerpared by Harivinod N www.techjourney.in Page|1.16

3.6. Mathematical Analysis

Here comparison is the basic

Example-2: To check whethe

Prerpared by Harivinod N www.techjourney.in Page|1.17

Other than the worst case, the

Number of basic opera

Total running time:

Prerpared by Harivinod N www.techjourney.in Page|1.18

Example-4: To count the bit