0% found this document useful (0 votes)

6 views82 pages

Design and Analysis of Algorithms Notes 1 - TutorialsDuniya

The document provides a comprehensive overview of algorithms, including their definitions, characteristics, and performance expectations. It discusses the importance of algorithm efficiency, resource usage, and various methods for analyzing algorithms, such as asymptotic notation and recurrence relations. Additionally, it emphasizes the significance of choosing efficient algorithms for optimal performance in computational tasks.

Uploaded by

Karamjot Kaur

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

6 views82 pages

Design and Analysis of Algorithms Notes 1 - TutorialsDuniya

Uploaded by

Karamjot Kaur

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 82

TUTORIALSDUNIYA.

COM

Design & Analysis of

Algorithm Notes

Computer Science Notes

Download FREE Computer Science Notes, Programs,
Projects, Books for any university student of BCA,
MCA, B.Sc, M.Sc, B.Tech CSE, M.Tech at
https://www.tutorialsduniya.com

Please Share these Notes with your Friends as well

Download FREE Computer Science Notes at TutorialsDuniya.com

Lecture 1 - Introduction to Design and analysis of algorithms

What is an algorithm?
Algorithm is a set of steps to complete a task.

m
For example,
Task: to make a cup of tea.

co
Algorithm:

• add water and milk to the kettle,

a.
• boilit, add tea leaves,
• Add sugar, and then serve it in cup.

What is Computer algorithm?

iy
un
‘’a set of steps to accomplish or complete a task that is described precisely enough that a
computer can run it’’.
sD

Described precisely: very difficult for a machine to know how much water, milk to be added
etc. in the above tea making algorithm.
al

These algorithmsrun on computers or computational devices.Forexample, GPS in our

smartphones, Google hangouts.
ri

GPS uses shortest path algorithm. Online shopping uses cryptography which uses RSA
algorithm.
to

Characteristics of an algorithm:-
Tu

• Must take an input.

• Must give some output(yes/no,valueetc.)
• Definiteness –each instruction is clear and unambiguous.
• Finiteness –algorithm terminates after a finite number of steps.
• Effectiveness –every instruction must be basic i.e. simple instruction.

Download FREE Computer Science Notes at TutorialsDuniya.com

Expectation from an algorithm

• Correctness:-
Correct: Algorithms must produce correct result.

m
Produce an incorrect answer:Even if it fails to give correct results all the time still
there is a control on how often it gives wrong result. Eg.Rabin-Miller PrimalityTest

co
(Used in RSA algorithm): It doesn’t give correct answer all the time.1 out of 250 times
it gives incorrect result.

a.
Approximation algorithm: Exact solution is not found, but near optimal solution can
be found out. (Applied to optimization problem.)
• Less resource usage:

iy
Algorithms should use less resources (time and space).
un
Resource usage:
Here, the time is considered to be the primary measure of efficiency .We are also
sD

concerned with how much the respective algorithm involves the computer memory.But
mostly time is the resource that is dealt with. And the actual running time depends on a
al

variety of backgrounds: like the speed of the Computer, the language in which the
algorithm is implemented, the compiler/interpreter, skill of the programmers etc.
ri

So, mainly the resource usage can be divided into: 1.Memory (space) 2.Time
to

Time taken by an algorithm?

performance measurement or Apostoriori Analysis: Implementing the algorithm
Tu

in a machine and then calculating the time taken by the system to execute the program
successfully.
Performance Evaluation or Apriori Analysis. Before implementing the algorithm in a
system. This is done as follows

Download FREE Computer Science Notes at TutorialsDuniya.com

1. How long the algorithm takes :-will be represented as a function of the size of
the input.

f(n)→how long it takes if ‘n’ is the size of input.

2. How fast the function that characterizes the running time grows with the input

m
size.
“Rate of growth of running time”.

co
The algorithm with less rate of growth of running time is considered better.

a.
How algorithm is a technology ?

iy
Algorithms are just like a technology. We all use latest and greatest processors but we need to
run implementations of good algorithms on that computer in order to properly take benefits of
un
our money that we spent to have the latest processor. Let’s make this example more concrete
by pitting a faster computer(computer A) running a sorting algorithm whose running time on n
values grows like n2 against a slower computer (computer B) running asorting algorithm whose
sD

running time grows like n lg n. They eachmust sort an array of 10 million numbers. Suppose that
computer A executes 10 billion instructions per second (faster than anysingle sequential
al

computer at the time of this writing) and computer B executes only 10 million instructions per
second, so that computer A is1000 times faster than computer B in raw computing power. To
ri

makethe difference even more dramatic, suppose that the world’s craftiestprogrammer codes
in machine language for computer A, and the resulting code requires 2n2 instructions to sort n
to

numbers. Suppose furtherthat just an average programmer writes for computer B, using a high-
level language with an inefﬁcient compiler, with the resulting code taking 50n lg n instructions.
Tu

Computer A (Faster) Computer B(Slower)

Running time grows like n2. Grows innlogn.

10 billion instructions per sec. 10million instruction per sec

2n2 instruction. 50 nlogn instruction.

Download FREE Computer Science Notes at TutorialsDuniya.com

Time taken=

It is more than 5.5hrs it is under 20 mins.

So choosing a good algorithm (algorithm with slower rate of growth) as used by
computer B affects a lot.

m
Lecture 2 - Growth of Functions ( Asymptotic notations)

co
a.
Before going for growth of functions and asymptotic notation let us see how to analyase
an algorithm.

How to analyse an Algorithm

iy
un
Let us form an algorithm for Insertion sort (which sort a sequence of numbers).The pseudo
code for the algorithm is give below.
sD

Pseudo code:

for j=2 to A length -------------------------------------------------- C1

key=A[j]-----------------------------------------------------------------C2
ri

//Insert A[j] into sorted Array A[1.....j-1]------------------------C3

i=j-1------------------------------------------------------------------------C4
to

while i>0 & A[j]>key---------------------------------------------------C5

A[i+1]=A[i]---------------------------------------------------------------C6

i=i-1------------------------------------------------------------------------C7

A[i+1]=key----------------------------------------------------------------C8

Download FREE Computer Science Notes at TutorialsDuniya.com

m
co
Let Ci be the cost of ith line. Since comment lines will not incur any cost C3=0.

a.
Cost No. Of times Executed

C1n

C2 n-1 iy
un
C3=0 n-1

C4n-1
sD

C6 )
al

C7
ri

C8n-1
to
Tu

Running time of the algorithm is:

T(n)=C1n+C2(n-1)+0(n-1)+C4(n-1)+C5 +C6( )+C7( )+ C8(n-1)

Best case:

It occurs when Array is sorted.

Download FREE Computer Science Notes at TutorialsDuniya.com

All tjvalues are 1.

T(n)=C1n+C2(n-1)+0 (n-1)+C4(n-1)+C5 +C6( )+C7( )+ C8(n-1)

=C1n+C2 (n-1) +0 (n-1) +C4 (n-1) +C5 + C8 (n-1)

= (C1+C2+C4+C5+ C8) n-(C2+C4+C5+ C8)

m
• Which is of the forman+b.
• Linear function of n.So, linear growth.

co
a.
Worst case:

It occurs when Array is reverse sorted, and tj =j

T(n)=C1n+C2(n-1)+0 (n-1)+C4(n-1)+C5 +C6( iy )+C7( )+ C8(n-1)

un
=C1n+C2(n-1)+C4(n-1)+C5 +C6( )+C7( )+ C8(n-1)
sD

which is of the form an2+bn+c

Quadratic function. So in worst case insertion set grows in n2.

Why we concentrate on worst-case running time?

• The worst-case running time gives a guaranteed upper bound on the runningtime for
ri

any input.
to

• For some algorithms, the worst case occurs often. For example, when searching, the
worst case often occurs when the item being searched for is not present, and searches
Tu

for absent items may be frequent.

• Why not analyze the average case? Because it’s often about as bad as the worst case.

Order of growth:

It is described by the highest degree term of the formula for running time. (Drop lower-order
terms. Ignore the constant coefficient in the leading term.)

Download FREE Computer Science Notes at TutorialsDuniya.com

Example: We found out that for insertion sort the worst-case running time is of the form
an2 + bn + c.

Drop lower-order terms. What remains is an2.Ignore constant coefficient. It results in n2.But we
cannot say that the worst-case running time T(n) equals n2 .Rather It grows like n2 . But it
doesn’t equal n2.We say that the running time is Θ (n2) to capture the notion that the order of

m
growth is n2.
We usually consider one algorithm to be more efficient than another if its worst-case

co
running time has a smaller order of growth.

Asymptotic notation

a.
• It is a way to describe the characteristics of a function in the limit.
•
•
It describes the rate of growth of functions.
iy
Focus on what’s important by abstracting away low-order terms and constant factors.
un
• It is a way to compare “sizes” of functions:
O≈ ≤
sD

Ω≈ ≥
Θ≈=
o≈<
al

ω≈>
ri
to
Tu

Download FREE Computer Science Notes at TutorialsDuniya.com

m
co
a.
iy
un
sD
al
ri
to
Tu

Download FREE Computer Science Notes at TutorialsDuniya.com

m
co
a.
iy
Example: n2 /2 − 2n = Θ (n2), with c1 = 1/4, c2 = 1/2, and n0 = 8.
un
sD
al
ri
to
Tu

Download FREE Computer Science Notes at TutorialsDuniya.com

Lecture 3-5: Recurrences, Solution of Recurrences by substitution,

Recursion Tree and Master Method

Recursion is a particularly powerful kind of reduction, which can be described loosely as

follows:

m
• If the given instance of the problem is small or simple enough, just solve it.

• Otherwise, reduce the problem to one or more simpler instances of the same problem.

co
Recursion is generally expressed in terms of recurrences. In other words, when an
algorithm calls to itself, we can often describe its running time by a recurrence equation which

a.
describes the overall running time of a problem of size n in terms of the running time on smaller
inputs.

iy
E.g.the worst case running time T(n) of the merge sort procedure by recurrence can be
un
expressed as
T(n)= ϴ(1) ; if n=1
2T(n/2) + ϴ(n) ;if n>1
sD

whose solution can be found as T(n)=ϴ(nlog n)

There are various techniques to solve recurrences.

1. SUBSTITUTION METHOD:
ri

The substitution method comprises of 3 steps

i. Guess the form of the solution

ii. Verify by induction
Tu

iii. Solve for constants

We substitute the guessed solution for the function when applying the inductive
hypothesis to smaller values. Hence the name “substitution method”. This method is powerful,
but we must be able to guess the form of the answer in order to apply it.

e.g.recurrence equation: T(n)=4T(n/2)+n

Download FREE Computer Science Notes at TutorialsDuniya.com

step 1: guess the form of solution

T(n)=4T(n/2)

F(n)=4f(n/2)
F(2n)=4f(n)
F(n)=n2

m
So, T(n) is order of n2
Guess T(n)=O(n3)

co
Step 2: verify the induction

a.
Assume T(k)<=ck3
T(n)=4T(n/2)+n
<=4c(n/2)3 +n
<=cn3/2+n
iy
un
<=cn3-(cn3/2-n)
T(n)<=cn3 as (cn3/2 –n) is always positive
So what we assumed was true.
sD

T(n)=O(n3)

Step 3: solve for constants

Cn3/2-n>=0
n>=1
ri

c>=2
to

Now suppose we guess that T(n)=O(n2) which is tight upper bound

Assume,T(k)<=ck2

so,we should prove that T(n)<=cn2

T(n)=4T(n/2)+n
4c(n/2)2+n
cn2+n

Download FREE Computer Science Notes at TutorialsDuniya.com

So,T(n) will never be less than cn2. But if we will take the assumption of T(k)=c1 k2-c2k, then we
can find that T(n) = O(n2)

2. BY ITERATIVE METHOD:

m
e.g. T(n)=2T(n/2)+n

=> 2[2T(n/4) + n/2 ]+n

co
=>22T(n/4)+n+n

=> 22[2T(n/8)+ n/4]+2n

a.
=>23T(n/23) +3n

After k iterations ,T(n)=2kT(n/2k)+kn--------------(1)

iy
un
Sub problem size is 1 after n/2k=1 => k=logn

So,afterlogn iterations ,the sub-problem size will be 1.

So,when k=logn is put in equation 1

T(n)=nT(1)+nlogn
al

nc+nlogn ( say c=T(1))

O(nlogn)
ri

3.BY RECURSSION TREE METHOD:

In a recursion tree ,each node represents the cost of a single sub-problem somewhere in the set of
recursive problems invocations .we sum the cost within each level of the tree to obtain a set of
Tu

per level cost,and then we sum all the per level cost to determine the total cost of all levels of
recursion .
Constructing a recursion tree for the recurrence T(n)=3T(n/4)+cn2

Download FREE Computer Science Notes at TutorialsDuniya.com

m
co
a.
iy
un
sD
al
ri

Constructing a recursion tree for the recurrence T (n)= 3T (n=4) + cn2.. Part (a) shows T (n),
to

which progressively expands in (b)–(d) to form the recursion tree. The fully expanded tree in part
(d) has height log4n (it has log4n + 1 levels).
Tu

Sub problem size at depth i =n/4i

Sub problem size is 1 when n/4i=1 => i=log4n

So, no. of levels =1+ log4n

Cost of each level = (no. of nodes) x (cost of each node)

Download FREE Computer Science Notes at TutorialsDuniya.com

TutorialsDuniya.com
Download FREE Computer Science Notes, Programs, Projects,
Books PDF for any university student of BCA, MCA, B.Sc,
B.Tech CSE, M.Sc, M.Tech at https://www.tutorialsduniya.com

 Algorithms Notes  Information Security

 Artificial Intelligence  Internet Technologies
 Android Programming  Java Programming
 C & C++ Programming  JavaScript & jQuery
 Combinatorial Optimization  Machine Learning
 Computer Graphics  Microprocessor
 Computer Networks  Operating System
 Computer System Architecture  Operational Research
 DBMS & SQL Notes  PHP Notes
 Data Analysis & Visualization  Python Programming
 Data Mining  R Programming
 Data Science  Software Engineering
 Data Structures  System Programming
 Deep Learning  Theory of Computation
 Digital Image Processing  Unix Network Programming
 Discrete Mathematics  Web Design & Development

Please Share these Notes with your Friends as well

Download FREE Computer Science Notes at TutorialsDuniya.com

No. Of nodes at depth i=3i

Cost of each node at depth i=c (n/4i)2

Cost of each level at depth i=3i c (n/4i)2 = (3/16)icn2

T(n)= i=0∑log4n cn2(3/16)i

m
T(n)= i=0∑log4n -1 cn2(3/16)i + cost of last level

Cost of nodes in last level =3iT(1)

co
c3log4n (at last level i=log4n)
cnlog43

a.
+ c nlog43
T(n)=

iy
un
<= cn2

<= cn2*(16/13)+ cnlog43 => T(n)=O(n2)

4.BY MASTER METHOD:

The master method solves recurrences of the form

T(n)=aT(n/b)+f(n)

where a>=1 and b>1 are constants and f(n) is a asymptotically positive function .
ri

To use the master method, we have to remember 3 cases:

1. If f(n)=O(nlogba - Ɛ) for some constants Ɛ >0,then T(n)=ϴ(nlogba)

2. If f(n)=ϴ( nlogba) then T(n)=ϴ(nlogbalogn)

3. If f(n)=Ὠ(nlogba+Ɛ) for some constant Ɛ>0 ,and if a*f(n/b)<=c*f(n) for some constant c<1
and all sufficiently large n,then T(n)=ϴ(f(n))

Download FREE Computer Science Notes at TutorialsDuniya.com

e.g. T(n)=2T(n/2)+nlogn

ans: a=2 b=2

f(n)=nlogn
using 2nd formula
f(n)=ϴ( nlog22logkn)

m
=>ϴ(n1 logkn)=nlogn =>K=1

T(n)=ϴ( nlog22 log1n)

co
=>ϴ(nlog2n)

a.
Lecture 6 - Design and analysis of Divide and Conquer
Algorithms
iy
un
DIVIDE AND CONQUER ALGORITHM

• In this approach ,we solve a problem recursively by applying 3 steps

1. DIVIDE-break the problem into several sub problems of smaller size.

2. CONQUER-solve the problem recursively.
3. COMBINE-combine these solutions to create a solution to the original problem.
al

CONTROL ABSTRACTION FOR DIVIDE AND CONQUER ALGORITHM

Algorithm D and C (P)

{
if small(P)
then return S(P)
Tu

else
{ divide P into smaller instances P1 ,P2 .....Pk
Apply D and C to each sub problem
Return combine (D and C(P1)+ D and C(P2)+.......+D and C(Pk))
}

Download FREE Computer Science Notes at TutorialsDuniya.com

Let a recurrence relation is expressed as T(n)=

ϴ(1), if n<=C
aT(n/b) + D(n)+ C(n) ,otherwise

m
then n=input size a=no. Of sub-problemsn/b= input size of the sub-problems

co
Lecture 7: Worst case analysis of merge sort, quick sort

a.
Merge sort

iy
It is one of the well-known divide-and-conquer algorithm. This is a simple and very efﬁcient
un
algorithm for sorting a list of numbers.

We are given a sequence of n numberswhich we will assume is stored in an array A [1...n].

Theobjective is to output a permutation of this sequence, sorted in increasing order. This is

normally done by permuting the elements within the array A.

How can we apply divide-and-conquer to sorting? Here are the major elements of the Merge
al

Sort algorithm.
ri

Divide: Split A down the middle into two sub-sequences, each of size roughly n/2 .
to

Conquer: Sort each subsequence (by calling MergeSort recursively on each).

Combine: Merge the two sorted sub-sequences into a single sorted list.
Tu

The dividing process ends when we have split the sub-sequences down to a single item. A
sequence of length one is trivially sorted. The key operation where all the work is done is in the
combine stage,which merges together two sorted lists into a single sorted list. It turns out that
the merging process is quite easy to implement.

Download FREE Computer Science Notes at TutorialsDuniya.com

The following ﬁgure gives a high-level view of the algorithm. The “divide” phase is shown on the
left. It works top-down splitting up the list into smaller sublists. The “conquer and combine”
phases areshown on the right. They work bottom-up, merging sorted lists together into larger
sorted lists.

m
co
a.
Merge Sort

iy
Designing the Merge Sort algorithm top-down. We’ll assume that the procedure thatmerges
two sortedlist is available to us. We’ll implement it later. Because the algorithm is called
un
recursively on sublists,in addition to passing in the array itself, we will pass in two indices,
which indicate the ﬁrst and lastindices of the subarray that we are to sort. The call
sD

MergeSort(A, p, r) will sort the sub-arrayA [ p..r ] and return the sorted result in the same
subarray.

Here is the overview. If r = p, then this means that there is only one element to sort, and we
al

may returnimmediately. Otherwise (if p < r) there are at least two elements, and we will invoke
the divide-and-conquer. We ﬁnd the index q, midway between p and r, namely q = ( p + r ) / 2
ri

(rounded down to thenearest integer). Then we split the array into subarrays A [ p..q ] and A [ q
to

+ 1 ..r ] . Call Merge Sort recursively to sort each subarray. Finally, we invoke a procedure
(which we have yet to write) whichmerges these two subarrays into a single sorted array.
Tu

MergeSort(array A, int p, int r) {

if (p < r) { // we have at least 2 items
q = (p + r)/2
MergeSort(A, p, q) // sort A[p..q]
MergeSort(A, q+1, r) // sort A[q+1..r]

Download FREE Computer Science Notes at TutorialsDuniya.com

Merge(A, p, q, r) // merge everything together

} }

Merging: All that is left is to describe the procedure that merges two sorted lists. Merge(A, p, q,
r)assumes that the left subarray, A [ p..q ] , and the right subarray, A [ q + 1 ..r ] , have already
been sorted.We merge these two subarrays by copying the elements to a temporary working

m
array called B. Forconvenience, we will assume that the array B has the same index range A,
that is, B [ p..r ] . We have to indices i and j, that point to the current elements ofeach subarray.

co
We move the smaller element into the next position of B (indicated by index k) andthen
increment the corresponding index (either i or j). When we run out of elements in one array,

a.
thenwe just copy the rest of the other array into B. Finally, we copy the entire contents of B
back into A.

iy
un
Merge(array A, int p, int q, int r) { // merges A[p..q] with A[q+1..r]
array B[p..r]
i=k=p //initialize pointers
sD

j = q+1
while (i <= q and j <= r) { // while both subarrays are nonempty
al

if (A[i] <= A[j]) B[k++] = A[i++] // copy from left subarray

else B[k++] = A[j++] // copy from right subarray
ri

}
while (i <= q) B[k++] = A[i++] // copy any leftover to B
to

while (j <= r) B[k++] = A[j++]

for i = p to r do A[i] = B[i] // copy B back to A }
Tu

Analysis: What remains is to analyze the running time of MergeSort. First let us consider the
running timeof the procedure Merge(A, p, q, r). Let n = r − p + 1 denote the total length of both
the leftand right subarrays. What is the running time of Merge as a function of n? The algorithm
contains fourloops (none nested in the other). It is easy to see that each loop can be executed
at most n times. (Ifyou are a bit more careful you can actually see that all the while-loops

Download FREE Computer Science Notes at TutorialsDuniya.com

together can only be executed ntimes in total, because each execution copies one new element
to the array B, and B only has space forn elements.) Thus the running time to Merge n items is
Θ ( n ) . Let us write this without the asymptoticnotation, simply as n. (We’ll see later why we
do this.)

Now, how do we describe the running time of the entire MergeSort algorithm? We will do this

m
throughthe use of a recurrence, that is, a function that is deﬁned recursively in terms of itself.
To avoidcircularity, the recurrence for a given value of n is deﬁned in terms of values that are

co
strictly smallerthan n. Finally, a recurrence has some basis values (e.g. for n = 1 ), which are
deﬁned explicitly.

a.
Let’s see how to apply this to MergeSort. Let T ( n ) denote the worst case running time of

iy
MergeSort onan array of length n. For concreteness we could count whatever we like: number
of lines of pseudocode,number of comparisons, number of array accesses, since these will only
un
differ by a constant factor.Since all of the real work is done in the Merge procedure, we will
count the total time spent in theMerge procedure.

First observe that if we call MergeSort with a list containing a single element, then the running
sD

time is aconstant. Since we are ignoring constant factors, we can just write T ( n ) =1 .
When we call MergeSortwith a list of length n >1 , e.g. Merge(A, p, r), where r − p +1 = n, the
al

algorithm ﬁrst computes q = ( p + r ) / 2 . The subarray A [ p..q ] , which contains q − p + 1

elements. You can verify that is of size n/ 2 . Thus the remaining subarray A [ q +1 ..r ] has n/ 2
ri

elements in it. How long does it taketo sort the left subarray? We do not know this, but
because n/ 2< n for n >1 , we can express this as T (n/ 2) . Similarly, we can express the time
to

that it takes to sort the right subarray as T (n/ 2).

Finally, to merge both sorted lists takes n time, by the comments made above. In conclusion we
have

T ( n ) =1 if n = 1 ,

2T (n/ 2) + n otherwise.

Solving the above recurrence we can see that merge sort has a time complexity of Θ (n log n) .

Download FREE Computer Science Notes at TutorialsDuniya.com

QUICKSORT

Worst-case running time: O (n2).

Expected running time: O (n lgn).
Sorts in place.

m
Description of quicksort
Quicksort is based on the three-step process of divide-and-conquer.
• To sort the subarrayA[p . . r ]:

co
Divide: Partition A[p . . r ], into two (possibly empty) subarraysA[p . . q − 1] and
A[q + 1 . . r ], such that each element in the ÞrstsubarrayA[p . . q − 1] is ≤ A[q] and

a.
A[q] is ≤ each element in the second subarrayA[q + 1 . . r ].
Conquer: Sort the two subarrays by recursive calls to QUICKSORT.

iy
Combine: No work is needed to combine the subarrays, because they are sorted in place.
• Perform the divide step by a procedure PARTITION, which returns the index q that marks the
un
position separating the subarrays.
QUICKSORT (A, p, r)
ifp < r
sD

thenq ←PARTITION(A, p, r )
QUICKSORT (A, p, q − 1)
al

QUICKSORT (A, q + 1, r)
ri

Initial call is QUICKSORT (A, 1, n)

Partitioning
to

Partition subarrayA [p . . . r] by the following procedure:

PARTITION (A, p, r)
Tu

x ← A[r ]
i ← p –1
for j ← p to r –1
do if A[ j ] ≤ x

theni ← i + 1

Download FREE Computer Science Notes at TutorialsDuniya.com

exchangeA[i ] ↔ A[ j ]
exchangeA[i + 1] ↔ A[r ]
returni + 1

• PARTITION always selects the last element A[r ] in the subarrayA[p . . r ] as the pivot the
element around which to partition.

m
• As the procedure executes, the array is partitioned into four regions, some of which may be
empty:

co
a.
iy
un
sD
al
ri
to

Performance of Quicksort
Tu

The running time of Quicksort depends on the partitioning of the subarrays:

• If the subarrays are balanced, then Quicksort can run as fast as mergesort.
• If they are unbalanced, then Quicksort can run as slowly as insertion sort.

Worst case
• Occurs when the subarrays are completely unbalanced.
• Have 0 elements in one subarray and n − 1 elements in the other subarray.

Download FREE Computer Science Notes at TutorialsDuniya.com

• Get the recurrence

T (n) = T (n − 1) + T (0) + Θ (n)
= T (n − 1) + Θ (n)
= O (n2) .
• Same running time as insertion sort.

m
• In fact, the worst-case running time occurs when Quicksort takes a sorted array as input, but
insertion sort runs in O(n) time in this case.

co
Best case
• Occurs when the subarrays are completely balanced every time.

a.
• Each subarray has ≤ n/2 elements.
• Get the recurrence
T (n) = 2T (n/2) + Θ (n) = O(n lgn).
iy
un
Balanced partitioning
• QuickPort’s average running time is much closer to the best case than to the worst case.
sD

• Imagine that PARTITION always produces a 9-to-1 split.

• Get the recurrence
T (n) ≤ T (9n/10) + T (n/10) + _ (n) = O (n lgn).
al

• Intuition: look at the recursion tree.

• It’s like the one for T (n) = T (n/3) + T (2n/3) + O (n).
ri

• Except that here the constants are different; we get log10 n full levels and log10/9 n levels that
are nonempty.
to

• As long as it’s a constant, the base of the log doesn’t matter in asymptotic notation.
• Any split of constant proportionality will yield a recursion tree of depth O (lgn).
Tu

Download FREE Computer Science Notes at TutorialsDuniya.com

Lecture 8 - Heaps and Heap sort

HEAPSORT

Inplace algorithm
Running Time: O(n log n)

m
Complete Binary Tree

co
The (binary) heap data structure is an array object that we can view as a nearly complete binary
tree.Each node of the tree corresponds to an element of the array. The tree is completely filled on
all levels except possibly the lowest, which is filled from the left up to a point.

a.
The root of the tree is A[1], and given the index i of a node, we can easily compute the indices of
its parent, left child, and right child:

iy
un
sD
al
ri

PARENT (i) => return [ i / 2]

LEFT (i) => return 2i
to

RIGHT (i) => return 2i+ 1

On most computers, the LEFT procedure can compute 2i in one instruction by simply shifting the
binary representation of i left by one bit position.

Similarly, the RIGHT procedure can quickly compute 2i + 1 by shifting the binary
representation of i left by one bit position and then adding in a 1 as the low-order bit.

Download FREE Computer Science Notes at TutorialsDuniya.com

The PARENT procedure can compute [i/2] by shifting i right one bit position. Good
implementations of heapsort often implement these procedures as "macros" or "inline"
procedures.

There are two kinds of binary heaps: max-heaps and min-heaps.

• In a max-heap,the max-heap property is that for every node i other than the root,

m
A[PARENT(i)] >= A[i] ,that is, the value of a node is at most the value of its parent.
Thus, the largest element in a max-heap is stored at the root, and the subtree rooted at a

co
node contains values no larger than that contained at the node itself.
• A min-heap is organized in the opposite way; the min-heap property is that for every

a.
node i other than the root, A[PARENT(i)<=A[i] ,

The smallest element in a min-heap is at the root.

iy
The height of a node in a heap is the number of edges on the longest simple downward
un
path from the node to a leaf and
The height of the heap is the height of its root.
Height of a heap of n elements which is based on a complete binary tree is O(log n).
sD

Maintaining the heap property

MAX-HEAPIFY lets the value at A[i] "float down" in the max-heap so that the
subtree rooted at index i obeys the max-heap property.
ri

MAX-HEAPIFY(A,i)
to

1. l LEFT(i)
2. r RIGHT(i)
Tu

3. if A[l] > A[i]

4. largest l
5. if A[r] > A[largest]
6. Largest r
7. if largest != i
8. Then exchange A[i] A[largest]

Download FREE Computer Science Notes at TutorialsDuniya.com

9. MAX-HEAPIFY(A,largest)

At each step, the largest of the elements A[i], A[LEFT(i)], and A[RIGHT(i)] is
determined, and its index is stored in largest. If A[i] is largest, then the subtree rooted at node i is
already a max-heap and the procedure terminates. Otherwise, one of the two children has the
largest element, and A[i ] is swapped with A[largest], which causes node i and its children to

m
satisfy the max-heap property. The node indexed by largest, however, now has the original value
A[i], and thus the subtree rooted at largest might violate the max-heap property. Consequently,

co
we call MAX-HEAPIFY recursively on that subtree.

a.
iy
un
sD
al
ri
to
Tu

Figure: The action of MAX-HEAPIFY (A, 2), where heap-size = 10. (a) The initial con-
figuration, with A [2] at node i = 2 violating the max-heap property since it is not larger than
both children. The max-heap property is restored for node 2 in (b) by exchanging A [2] with
A[4], which destroys the max-heap property for node 4. The recursive call MAX-HEAPIFY (A,4)

Download FREE Computer Science Notes at TutorialsDuniya.com

now has i = 4. After swapping A[4] with A[9], as shown in (c), node 4 is fixed up, and the
recursive call MAX-HEAPIFY(A, 9) yields no further change to the data structure.

The running time of MAX-HEAPIFY by the recurrence can be described as

T (n) < = T (2n/3) + O (1)

m
The solution to this recurrence is T(n)=O(log n)

co
Building a heap

Build-Max-Heap(A)

a.
1. for i[n/2] to 1
2. do MAX-HEAPIFY(A,i)
iy
un
4 1 3 2 1 9 1 1 8 7
sD
al
ri
to
Tu

Download FREE Computer Science Notes at TutorialsDuniya.com

m
We can derive a tighter bound by observing that the time for MAX-HEAPIFY to run at a node

co
varies with the height of the node in the tree, and the heights of most nodes are small. Our
tighter analysis relies on the properties that an n-element heap has height [log n] and at most

a.
[n/2h+1] nodes of any height h.

The total cost of BUILD-MAX-HEAP as being bounded is T(n)=O(n)

The HEAPSORT Algorithm

iy
un
HEAPSORT(A)

1. BUILD MAX-HEAP(A)
sD

2. for i=n to 2
3. exchange A[1] with A[i]
4. MAX-HEAPIFY(A,1)
al
ri
to
Tu

Download FREE Computer Science Notes at TutorialsDuniya.com

TutorialsDuniya.com
Download FREE Computer Science Notes, Programs, Projects,
Books PDF for any university student of BCA, MCA, B.Sc,
B.Tech CSE, M.Sc, M.Tech at https://www.tutorialsduniya.com

 Algorithms Notes  Information Security

Please Share these Notes with your Friends as well

Download FREE Computer Science Notes at TutorialsDuniya.com

m
co
a.
iy
un
A 1 2 3 4 7 8 9 10 14 16

TheHEAPSORT procedure takes time O(n log n), since the call to BUILD-MAX- HEAP takes time
O(n) and each of the n - 1 calls to MAX-HEAPIFY takes time O(log n).
sD

Lecture 10: Lower Bounds For Sorting

al
ri

Review of Sorting: So far we have seen a number of algorithms for sorting a list of numbers in
ascendingorder. Recall that an in-place sorting algorithm is one that uses no additional array
to

storage (however,we allow Quicksort to be called in-place even though they need a stack of size
O(log n) for keepingtrack of the recursion). A sorting algorithm is stable if duplicate elements
Tu

remain in the same relativeposition after sorting.

Slow Algorithms: Include BubbleSort, InsertionSort, and SelectionSort. These are all simple
Θ (n2)in-place sorting algorithms. BubbleSort and InsertionSort can be implemented as stable
algorithms,but SelectionSort cannot (without significant modifications).

Download FREE Computer Science Notes at TutorialsDuniya.com

Mergesort: Mergesort is a stable Θ(n log n) sorting algorithm. The downside is that MergeSort
isthe only algorithm of the three that requires additional array storage, implying that it is not
anin-place algorithm.

Quicksort: Widely regarded as the fastest of the fast algorithms. This algorithm is O(n log n) in

m
theexpected case, and O(n2) in the worst case. The probability that the algorithm takes
asymptoticallylonger (assuming that the pivot is chosen randomly) is extremely small for large n.
It is an(almost) in-place sorting algorithm but is not stable.

co
Heapsort: Heapsort is based on a nice data structure, called a heap, which is a fast priority

a.
queue.Elements can be inserted into a heap in O(log n) time, and the largest item can be
extracted inO(log n) time. (It is also easy to set up a heap for extracting the smallest item.) If you

iy
only wantto extract the k largest values, a heap can allow you to do this is O(n + k log n) time. It
is anin-place algorithm, but it is not stable.
un
Lower Bounds for Comparison-Based Sorting: Can we sort faster than O(n log n) time?
We will give anargument that if the sorting algorithm is based solely on making comparisons
sD

between the keys in thearray, then it is impossible to sort more efficiently than (n log n) time.
Such an algorithm is called acomparison-based sorting algorithm, and includes all of the
al

algorithms given above.Virtually all known general purpose sorting algorithms are based on
making comparisons, so this isnot a very restrictive assumption. This does not preclude the
ri

possibility of a sorting algorithm whoseactions are determined by other types of operations, for
example, consulting the individual bits ofnumbers, performing arithmetic operations, indexing
to

into an array based on arithmetic operations onkeys.We will show that any comparison-based
sorting algorithm for a input sequence ha1; a2; : : : ; animust
Tu

make at least (n log n) comparisons in the worst-case. This is still a difficult task if you think
about it.It is easy to show that a problem can be solved fast (just give an algorithm). But to show
that a problemcannot be solved fast you need to reason in some way about all the possible
algorithms that might everbe written. In fact, it seems surprising that you could even hope to
prove such a thing. The catch hereis that we are limited to using comparison-based algorithms,
and there is a clean mathematical way ofcharacterizing all such algorithms.

Download FREE Computer Science Notes at TutorialsDuniya.com

Decision Tree Argument: In order to prove lower bounds, we need an abstract way of modeling
“any possible”comparison-based sorting algorithm, we model such algorithms in terms of an
abstract modelcalled a decision tree.In a comparison-based sorting algorithm only comparisons
between the keys are used to determinethe action of the algorithm. Let ha1; a2; : : : ; anibe the

m
input sequence. Given two elements, aiandaj, their relative order can only be determined by the
results of comparisons likeai<aj, ai<=aj,ai=aj, ai>=aj, and ai>aj.A decision tree is a
mathematical representation of a sorting algorithm (for a fixed value of n). Eachnode of the

co
decision tree represents a comparison made in the algorithm (e.g., a4 : a7), and the twobranches
represent the possible results, for example, the left subtree consists of the remaining

a.
comparisonsmade under the assumption that a4 _ a7 and the right subtree for a4 > a7.
(Alternatively, onemight be labeled with a4 < a7 and the other with a4 _ a7.)Observe that once

iy
we know the value of n, then the “action” of the sorting algorithm is completelydetermined by
the results of its comparisons. This action may involve moving elements around in thearray,
un
copying them to other locations in memory, performing various arithmetic operations on non-
keydata. But the bottom-line is that at the end of the algorithm, the keys will be permuted in the
final array in some way. Each leaf in the decision tree is labeled with the final permutation that
sD

the algorithmgenerates after making all of its comparisons.To make this more concrete, let us
assume that n = 3, and let’s build a decision tree for SelectionSort.Recall that the algorithm
al

consists of two phases. The first finds the smallest element of the entire list,and swaps it with the
first element. The second finds the smaller of the remaining two items, and swapsit with the
ri

second element. Here is the decision tree (in outline form). The first comparison is betweena1
and a2. The possible results are:
to

a1 <= a2: Then a1 is the current minimum. Next we compare a1 with a3 whose results might
be either:
Tu

a1 <=a3: Then we know that a1 is the minimum overall, and the elements remain in their
originalpositions. Then we pass to phase 2 and compare a2 with a3. The possible
results are:
a2 <=a3: Final output is ha1; a2; a3i.
a2 > a3: These two are swapped and the final output is ha1; a3; a2i.

Download FREE Computer Science Notes at TutorialsDuniya.com

a1 > a3: Then we know that a3 is the minimum is the overall minimum, and it is swapped
witha1. The we pass to phase 2 and compare a2 with a1 (which is now in the third
position ofthe array) yielding either:
a2 <=a1: Final output is ha3; a2; a1i.
a2 > a1: These two are swapped and the final output is ha3; a1; a2i.

m
a1 > a2: Then a2 is the current minimum. Next we compare a2 with a3 whose results might be
either:
a2 <=a3: Then we know that a2 is the minimum overall. We swap a2 with a1, and then pass to

co
phase 2, and compare the remaining items a1 and a3. The possible results are:
a1 <=a3: Final output is ha2; a1; a3i.

a.
a1 > a3: These two are swapped and the final output is ha2; a3; a1i.
a2 > a3: Then we know that a3 is the minimum is the overall minimum, and it is swapped

iy
witha1. We pass to phase 2 and compare a2 with a1 (which is now in the third position
of thearray) yielding either:
un
a2<= a1: Final output is ha3; a2; a1i.
a2 > a1: These two are swapped and the final output is ha3; a1; a2i.
sD

The final decision tree is shown below. Note that there are some nodes that are unreachable. For
example,in order to reach the fourth leaf from the left it must be that a1 _ a2 and a1 > a2, which
al

cannotboth be true. Can you explain this? (The answer is that virtually all sorting algorithms,
especiallyinefficient ones like selection sort, may make comparisons that are redundant, in the
ri

sense that theiroutcome has already been determined by earlier comparisons.) As you can see,
converting a complexsorting algorithm like HeapSort into a decision tree for a large value of n
to

will be very tedious andcomplex, but I hope you are convinced by this exercise that it can be
done in a simple mechanical way.
Tu

Download FREE Computer Science Notes at TutorialsDuniya.com

m
co
(Decision Tree for SelectionSort on 3 keys.)

a.
Using Decision Trees for Analyzing Sorting: Consider any sorting algorithm. Let T(n) be the

iy
maximumnumber of comparisons that this algorithm makes on any input of size n. Notice that
the running timefo the algorithm must be at least as large as T(n), since we are not counting data
un
movement or othercomputations at all. The algorithm defines a decision tree. Observe that the
height of the decisiontree is exactly equal to T(n), because any path from the root to a leaf
sD

corresponds to a sequence ofcomparisons made by the algorithm.

As we have seen earlier, any binary tree of height T (n) has at most 2T(n) leaves. This means that
thissorting algorithm can distinguish between at most 2T (n) different final actions. Let’s call this
al

quantityA (n), for the number of different final actions the algorithm can take. Each action can be
thought of asa specific way of permuting the original input to get the sorted output.How many
ri

possible actions must any sorting algorithm distinguish between? If the input consists of ndistinct
numbers, then those numbers could be presented in any of n! different permutations. For
to

eachdifferent permutation, the algorithm must “unscramble” the numbers in an essentially

different way,that is it must take a different action, implying that A(n) >= n!. (Again, A (n) is
Tu

usually not exactlyequal to n! because most algorithms contain some redundant unreachable
leaves.)

Since A(n) ≤ 2T(n) we have 2T(n) ≥ n!, implying that

T(n) ≥ lg(n!):

Download FREE Computer Science Notes at TutorialsDuniya.com

We can use Stirling’s approximation for n! yielding:

n! ≥

T(n) ≥

m
=

co
Thus we have the following theorem.

a.
Theorem: Any comparison-based sorting algorithm has worst-case running time (n log n).
This can be generalized to show that the average-case time to sort is also (n log n) (by arguing

iy
aboutthe average height of a leaf in a tree with at least n! leaves). The lower bound on sorting
can begeneralized to provide lower bounds to a number of other problems as well.
un
sD
al
ri
to
Tu

Download FREE Computer Science Notes at TutorialsDuniya.com

MODULE -II
• Lecture 11 - Dynamic Programming algorithms

• Lecture 12 - Matrix Chain Multiplication

• Lecture 13 - Elements of Dynamic Programming

m
• Lecture 14 - Longest Common Subsequence

• Lecture 15 - Greedy Algorithms

co
• Lecture 16 - Activity Selection Problem

• Lecture 17 - Elements of Greedy Strategy

a.
• Lecture 18 - Knapsack Problem

• Lecture 19 - Fractional Knapsack Problem

• Lecture 20 - Huffman Codes

iy
un
sD
al
ri
to
Tu

Download FREE Computer Science Notes at TutorialsDuniya.com

m
co
a.
iy
un
Greedy Method
sD

Introduction
al

Let we are given a problem to sort the array a = {5, 3, 2, 9}. Someone says the array after sorting
is {1, 3, 5, 7}. Can we consider the answer is correct? The answer is definitely “no” because the elements
ri

of the output set are not taken from the input set. Let someone says the array after sorting is {2, 5, 3, 9}.
Can we admit the answer? The answer is again “no” because the output is not satisfying the objective
function that is the first element must be less than the second, the second element must be less than
to

the third and so on. Therefore, the solution is said to be a feasible solution if it satisfies the following
constraints.
Tu

(i) Explicit constraints: - The elements of the output set must be taken from the input set.
(ii) Implicit constraints:-The objective function defined in the problem.

The best of all possible solutions is called the optimal solution. In other words we need to find the
solution which has the optimal (maximum or minimum) value satisfying the given constraints.

Download FREE Computer Science Notes at TutorialsDuniya.com

The Greedy approach constructs the solution through a sequence of steps. Each step is chosen such
that it is the best alternative among all feasible choices that are available. The choice of a step once
made cannot be changed in subsequent steps.

Let us consider the problem of coin change. Suppose a greedy person has some 25p, 20p, 10p,
5paise coins. When someone asks him for some change then be wants to given the change with
minimum number of coins. Now, let someone requests for a change of top then he first selects 25p.
Then the remaining amount is 45p. Next, he selects the largest coin that is less than or equal to 45p i.e.

m
25p. The remaining 20p is paid by selecting a 20p coin. So the demand for top is paid by giving total 3
numbers of coins. This solution is an optimal solution. Now, let someone requests for a change of 40p
then the Greedy approach first selects 25p coin, then a 10p coin and finally a 5p coin. However, the

co
some could be paid with two 20p coins. So it is clear from this example that Greedy approach tries to
find the optimal solution by selecting the elements one by one that are locally optimal. But Greedy
method never gives the guarantee to find the optimal solution.

a.
The choice of each step is a greedy approach is done based in the following:

• It must be feasible
•
•
It must be locally optimal
It must be unalterable
iy
un
Fractional Knapsack Problem

Let there are n number of objects and each object is having a weight and contribution to profit. The
sD

knapsack of capacity M is given. The objective is to fill the knapsack in such a way that profit shall be
maximum. We allow a fraction of item to be added to the knapsack.
al

Mathematically, we can write

ri
to

n
maximize∑ pi xi
i =1

Subject to
Tu

∑w x
i =1
i i ≤M

1 ≤ i ≤ n and 0 ≤ xi ≤ 1.

Download FREE Computer Science Notes at TutorialsDuniya.com

Where pi and wi are the profit and weight of ith object and xi is the fraction of ith object to be
selected.

For example

Given n = 3, (p1, p2, p3) = {25, 24, 15}

( w1, w2, w3) = {18, 15, 10} M = 20

m
Solution

co
Some of the feasible solutions are shown in the following table.

Solution No x1 x2 x3 ∑wi xi ∑pi xi

a.
1 1 2/15 0 20 28.2

3
0

0
2/3

1
1

1/2
iy 20

20
31.0

31.5
un
These solutions are obtained by different greedy strategies.
sD

Greedy strategy I: In this case, the items are arranged by their profit values. Here the item with
maximum profit is selected first. If the weight of the object is less than the remaining capacity of the
knapsack then the object is selected full and the profit associated with the object is added to the total
al

profit. Otherwise, a fraction of the object is selected so that the knapsack can be filled exactly. This
process continues from selecting the highest profitable object to the lowest profitable object till the
knapsack is exactly full.
ri
to

Greedy strategy II: In this case, the items are arranged by fair weights. Here the item with minimum
weight in selected first and the process continues like greedy strategy-I till the knapsack is exactly full.
Tu

Greedy strategy III: In this case, the items are arranged by profit/weight ratio and the item with
maximum profit/weight ratio is selected first and the process continues like greedy strategy-I till the
knapsack is exactly full.

Therefore, it is clear from the above strategies that the Greedy method generates optimal solution if we
select the objects with respect to their profit to weight ratios that means the object with maximum
profit to weight ratio will be selected first. Let there are n objects and the object i is associated with

Download FREE Computer Science Notes at TutorialsDuniya.com

p1 pn
profit piand weight wi. Then we can say that if ≥ p2 ≥ LL ≥ the solution
w1 w2 wn
(x1 , x2 , x3 LL xn ) generated by greedy method is an optimal solution. The proof of the above
statement is left as an exercise for the readers. The algorithm 6.1 describes the greedy method for
finding the optimal solution for fractional knapsack problem.

m
AlgorithmFKNAPSACK (p, w, x, n, M)

co
// p[1:n] and w[1:n] contains the profit and weight of n objects. Mis the maximum capacity of knapsack
and x[1:n] in the solution vector.//

a.
for (i = 1; i<= n; i ++)

x[i] = 0 ; // initialize the solution to 0 //

cu = M
iy
// cu is the remaining capacity of the knapsack//
un
for (i =1; i<= n ; i ++){

if(w[i] >cu )

break;
sD

else{

x[i] = 1 ;

cu = cu – w[i] ;
al

}
ri

if( i<= n){

x[i] = cu/w[i] ;

returnx;
Tu

Algorithm 1. Greedy algorithm for fractional knapsack problem.

Huffman Coding
Each character is represented in 8 bits when characters are coded using standard codes such as
ASCII. It can be seen that the characters coded using standard codes have fixed-length code word

Download FREE Computer Science Notes at TutorialsDuniya.com

representation. In this fixed-length coding system the total code length is more. For example, let we
have six characters (a, b, c, d, e, f) and their frequency of occurrence in a message is {45, 13, 12, 16, 9,
5}. In fixed-length coding system we can use three characters to represent each code. Then the total
code length of the message is (45+13+12+16+9+5) x 3 = 100 x 3 = 300.

Let us encode the characters with variable-length coding system. In this coding system, the
character with higher frequency of occurrence is assigned fewer bits for representation while the
characters having lower frequency of occurrence in assigned more bits for representation. The variable

m
length code for the characters are shown in the following tableThe total code length in variable length
coding system is 1 × 45 + 3 × 12 + 3 × 16 × 4 × 9 + 4 × 5 = 224. Hence fixed length code requires 300 bits
while variable code requires only 224 bits.

co
a b c d e f

0 101 100 111 1101 1100

a.
Prefix (Free) Codes
We have seen that using variable-length code word we minimize the overall encoded string length.

iy
But the question arises whether we can decode the string. If a is encoded 1 instead of 0 then the
encoded string “111” can be decoded as “d” or “aaa”. It can be seen that we get ambiguous string. The
key point to remove this ambiguity is to use prefix codes. Prefix codes is the code in which there is no
un
codeword that is a prefix of other codeword.

The representation of “decoding process” is binary tree whose leaves are characters. We interpret
the binary codeword for a character as path from the root to that character, where
sD

⇒ “0” means “go to the left child”

⇒ “1” means “go to the right child”
Greedy Algorithm for Huffman Code:
Code
al

According to Huffman algorithm, a bottom up tree is built starting from the leaves. Initially, there
are n singleton trees in the forest, as each tree is a leaf. The greedy strategy first finds two trees having
minimum frequency of occurrences. Then these two trees are merged in a single tree where the
ri

frequency of this tree is the total sum of two merged trees. The whole process is repeated until there in
only one tree in the forest.
to

Let us consider a set of characters S=<a, b, c, d, e, f> with the following frequency of occurrences P =
< 45, 13, 12, 16, 5, 9 >. Initially, these six characters with their frequencies are considered six singleton
trees in the forest. The step wise merging these trees to a single tree is shown in Fig. 6.3. The merging is
Tu

done by selecting two trees with minimum frequencies till there is only one tree in the forest.

a : 45 b : 13 c : 12 d : 16 e:5 f:9

Download FREE Computer Science Notes at TutorialsDuniya.com

m
co
a.
iy
un
sD
al
ri

Step wise merging of the singleton trees.

Now the left branch is assigned a code “0” and right branch is assigned a code “1”. The decode tree
after assigning the codes to the branches.
Tu

The binary codeword for a character is interpreted as path from the root to that character; Hence,
the codes for the characters are as follows

a=0

b = 101

c = 100

d = 111

Download FREE Computer Science Notes at TutorialsDuniya.com

e = 1100

f = 1101

Therefore, it is seen that no code is the prefix of other code. Suppose we have a code 01111001101.
To decode the binary codeword for a character, we traverse the tree. The first character is 0 and the
character at which the tree traversal terminates is a. Then, the next bit is 1 for which the tree is
traversed right. Since it has not reached at the leaf node, the tree is next traversed right for the next bit
1. Similarly, the tree is traversed for all the bits of the code string. When the tree traversal terminates at

m
a leaf node, the tree traversal again starts from the root for the next bit of the code string. The character
string after decoding is “adcf”.

co
AlgorithmHUFFMAN(n, S)

a.
{

// n is the number of symbols and S in the set of characters, for each character c∈ S, the frequency of
occurrence in f(c) //

Initialize the priority queue;

iy
un
Q = S ; // Inilialize the priority Q with the frequencies of all the characters of set S//

for(i =1 ; i<= n-i, i++){

z = CREAT _NODE ( ); // create a node pointed by z; //

// Delete the character with minimum frequency from the Q and store in node x//

x = DELETE _MIN (Q);

// Delete the character with next minimum frequency from the Q and store in node y//

y = DELETE_MIN (Q);
ri

z→left = x; // Place x as the left child of z//

z→right = y; // Place y as the right child of z//

//The value of node z is the sum of values at node x and node y//

f(z) = f(x) + f(y);

//insert z into the priority Q//

INSERT (Q, z);

returnDELETE_MIN(Q)

Download FREE Computer Science Notes at TutorialsDuniya.com

TutorialsDuniya.com
Download FREE Computer Science Notes, Programs, Projects,
Books PDF for any university student of BCA, MCA, B.Sc,
B.Tech CSE, M.Sc, M.Tech at https://www.tutorialsduniya.com

 Algorithms Notes  Information Security

Please Share these Notes with your Friends as well

Download FREE Computer Science Notes at TutorialsDuniya.com

Algorithm 2. Algorithm of Huffman coding.

Activity Selection Problem

Suppose we have a set of activities S = {a1, a2 ………an} that with to use a common resource. The
objective is to schedule the activities in such a way that maximum number of activities can be
performed. Each activity ai has a start timesi and a finish time fi, where 0 ≤ Si<fi< ∞. The activities ai and

m
aj are said to compatible if the intervals [si, fi] and [Sj, fj] do not overlap that means si ≥ fj or sj ≥ fi.

For example, let us consider the following set S of activities, which are sorted in monotonically

co
increasing order of finish time.

a.
i a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11

si 1 3 0 5 3 5 6 8 8 2 12

fi 4

iy
5 6 7 8 9 10 11 72 13 14
un
For this example, the subsets {a3, a9, a11}, {a1, a4, a8, a11} and {a2, a4, a9, a11} consist of mutually
compatible activities. We have two largest subsets of mutually compatible activities.

Now, we can devise greedy algorithm that works in a top down fashion. We assume that the n
sD

input activities are ordered by monotonically increasing finish time or it can be sorted into this order in
O(nlog2n) time. The greedy algorithm for activity selection problem is given below.
al

AlgorithmACTIVITY SELECTION (S, f)

{
ri

n = LENGTH (S) ; // n is the total number of activities //

A = {a1} ; // A is the set of selected activities and initialized to a1)//

i = 1; // i represents the recently selected activity //

for (j = 2 ; j< = n ; j++)

if (sj ≥ fi) {

A = A∪ {am} ;

i=j;

Download FREE Computer Science Notes at TutorialsDuniya.com

returnA ;

Algorithm 3. Algorithm of activity selection problem.

m
The algorithm takes the start and finish times of the activities, represented as arrays s and f , length
(s) gives the total number of activities. The set A stores the selected activities.Since the activities are
ordered with respect to their finish times the set A is initialized to contain just the first activity a1. The

co
variable i stores the index of the recently selected activity. The for loop considers each activityaj and
adds to the set A if it is mutually compatible with the previously selected activities. To see whether
activity aj is compatible with every activity assumingly in A, it needs to check whether the short time of

a.
aj is greater or equal to the finish time of the recently selected activity ai.

Minimum Cost Spanning Tree

iy
Let G = (V, E) be the graph where V is the set of vertices, E is the set of edges and |V|= n. The
un
spanning tree G′= (V, E′) is a sub graph of G in which all the vertices of graph G are connected with
minimum number of edges. The minimum number of edges required to correct all the vertices of a
graph G in n – 1. Spanning tree plays a very important role in designing efficient algorithms.
sD

Let us consider a graph shown in Fig 6.6(a). There are a number of possible spanning trees that is
shown in Fig 6.6(b).

If we consider a weighted graph then all the spanning trees generated from the graph have different
weights. The weight of the spanning tree is the sum of its edges weights. The spanning tree with
al

minimum weight is called minimum spanning tree (MST). Fig. 6.7 shows a weighted graph and the
minimum spanning tree.
ri

A greedy method to obtain the minimum spanning tree would construct the tree edge by edge,
where each edge is chosen accounting to some optimization criterion. An obvious criterion would be to
choose an edge which adds a minimum weight to the total weight of the edges selected so far. There are
to

two ways in which this criterion can be achieved.

1. The set of edges selected so far always forms a tree, the next edge to be added is such that not
only it adds a minimum weight, but also forms a tree with the previous edges; it can be shown
that the algorithm results in a minimum cost tree; this algorithm is called Prim’s algorithm.
2. The edges are considered in non decreasing order of weight; the set T of edges at each stage is
such that it is possible to complete T into a tree; thus T may not be a tree at all stages of the
algorithm; this also results in a minimum cost tree; this algorithm is called Krusleat’s algorithm.

Prim’s Algorithm

Download FREE Computer Science Notes at TutorialsDuniya.com

This algorithm starts with a tree that has only one edge, the minimum weight edge. The edges (j, q)
is added one by one such that node j is already included, node q is not included and weight wt(j, q) is the
minimum amongst all the edges (x, y) for which x is in the tree and yis not. In order to execute this
algorithm efficiently, we have a node index near(j) associated with each node j that is not yet included in
the tree. If a node is included in the tree, near(j) = 0. The node near(j) is selected into the tree such that
wt(j, near(j)) in the minimum amongst all possible choices for near(j).

m
AlgorithmPRIM (E, wt, n, T)

//E is the set of edges, wt(n, n) is the weight adjacency matrix for G, n is the number of nodes and T(n–1,

co
2) stores the spanning tree.

a.
(k, l) = edge with minimum wt.

minwt = wt[k, l] ;

T[1, 1] = k, T[1, 2] = l ;

for(i = 1; i<=n; i++){ iy

un
if(wt[i, k] <wt [i, l] )

near[i] = k;
sD

else

near[i] = l;

}
al

near[k] = near[l] = 0;

for(i = 2; i≤=n-1 ; i++)

letj be an index such that near[j] ≠ 0 and wt[j, near[j]] is minimum.

T[i, 1] = j; T[i, 2] = near[j];

minwt = minwt + wt[j, near[j]] ;

near[j] = 0 ;

for(k = 1; k<= n ; k++){

if (near[k] ≠ 0 and wt[k, near[k]] >wt[k, j])

near[k] = j;

Download FREE Computer Science Notes at TutorialsDuniya.com

if(minwt == ∞)

print(“No spanning tree”);

returnminwt;

m
Algorithm 4. Prim’s algorithm for finding MST.

co
Fig 6. The weighted undirected graph to illustrate Prim’s algorithm

a.
Let us consider the weighted undirected graph shown in Fig.6.8 and the objective is to construct a
minimum spanning tree. The step wise operation of Prim’s algorithm is described as follows.

iy
Step 1 The minimum weight edge is (2, 3) with weight 5. Hence, the edge (2, 3) is added to the tree.
un
near(2) and near(3) are set 0.

Step 2 Find near of all the nodes that are not yet selected into the tree and its cost.
sD

near(1) = 2 weight = 16

near(4) = 2 weight = 6

near (5) = - weight = ∞

near (6) = 2 weight = 11

The node 4 is selected and the edge (2, 4) is added to the tree because

weight(4, near(4) ) is minimum. Then near(4) is set 0.

Step 3 near(1) = 2 weight = 16

near(5) = 4 weight = 18
Tu

near(6) = 2 weight = 11

As weight(6, near(6)) is minimum, the node 6 is selected and edge (2, 6) is added to the tree. So
near(6) is set 0

Step 4 near (1) = 2 weight = 16

near (5) = 4 weight = 18

Next, the edge (2, 1) is added to the tree as weight(1, near(1)) is minimum. So near(1) is set 0.

Download FREE Computer Science Notes at TutorialsDuniya.com

Step 5 near (5) = 1 weight 12

The edge (1, 5) is added to the tree. The Fig. 6.9(a) to 6.9(e) show the step wise construction of
MST by Prim’s algorithm.

Fig. 6.9 Step wise construction of MST by Prim’s algorithm

m
Time complexity of Prim’s Algorithm
Prim’s algorithm has three for loops. The first for loop finds the near of all nodes which require O(n)
time. The second for loop is to find the remaining n-2 edges and the third for loop updates near of each

co
node after adding a vertex to MST. Since the third for loop is within the second for loop, it requires O(n2)
time. Hence, the overall time complexity of Prim’s algorithm is O(n2).

a.
Kruskal’s Algorithm

iy
This algorithm starts with a list of edges sorted in non decreasing order of weights. It repeatedly
adds the smallest edge to the spanning tree that does not create a cycle. Initially, each vertex is in its
own tree in the forest. Then, the algorithm considers each edge ordered by increasing weights. If the
un
edge (u, v) connects two different trees, then (u, v) is added to the set of edges of the MST and two
trees connected by an edge (u, v) are merged in to a single tree. If an edge (u, v) connects two vertices in
the same tree, then edge (u, v) is discarded.

The Krushal’s algorithm for finding the MST is presented as follows. It starts with an empty set A,
sD

and selects at every stage the shortest edge that has not been chosen or rejected regardless of where
this edge is situated in the graph. The pseudo code of Kruskal’s algorithm is given in Algorithm .
al

The operations an disjoint sets used for Krushal’s algorithm is as follows:

Make_set(v) : create a new set whose only member is pointed to v.

Find_set(v) : returns a pointer to the set containing v.

Union(u, v) : unites the dynamic sets that contain u and v into a new set that is union of these
two sets.
Tu

AlgorithmKRUSKAL (V, E, W)

// V is the set of vertices, E is the set of edges and W is the adjacency matrix to store the weights of the
links. //

A=Φ;

Download FREE Computer Science Notes at TutorialsDuniya.com

for (each vertex u in V)

Make_set(u)

Create a min heap from the weights of the links using procedure heapify.

for (each least weight edge (u, v) in E) // least weight edge is the root of the heap//

if (Find_set(u) ≠Find_set(v)){ // u and v are in two different sets //

m
A = A∪{u, v}

Union(u, v)

co
}

a.
return A ;

Algorithm. 5 Kruskal’s algorithm for finding MST.

iy
un
Let us consider the graph shown in Fig.6.10 to illustrate Kruskal’s algorithm.
sD

The step wise procedure to construct MST by following the procedure presented given below.
al
ri
to
Tu

Download FREE Computer Science Notes at TutorialsDuniya.com

m
co
a.
iy
un
sD
al
ri

Step wise construction of MST by Kruskal’s algorithm

Time complexity of Kruskal’s Algorithm

The Kruskal’s algorithm first creates n trees from n vertices which is done in O(n) time. Then, a heap is
Tu

created in O(n) time using heapify procedure. The least weight edge is at the root of the heap. Hence,
the edges are deleted one by one from the heap and either added to the MST or discarded if it forms a
cycle. This deletion process requires O(nlog2n). Hence, the time complexity of Kruskal’s algorithm is
O(nlog2n).

Shortest Path Problem

Let us consider a number of cities connected with roads and a traveler wants to travel form his
home city A to the destination B with a minimum cost. So the traveler will be interested to know the
following:

Download FREE Computer Science Notes at TutorialsDuniya.com

• Is there a path from city A to city B?

• If there is more than one path from A to B, which is the shortest or least cost path?

Let us consider the graph G = (V, E), a weighting function w(e) for the edges in E and a source node
v0. The problem is to determine the shortest path from v0 to all the remaining nodes of G. The solution
to this problem is suggested by E.W. Dijkstra and the algorithm is popularly known as Dijustra’s
algorithm.

m
This algorithm finds the shortest paths one by one. If we have already constructed i shortest paths,
then the next path to be constructed should be the next shortest path. Let S be the set of vertices to
which the shortest paths have already been generated. For z not in S, let dist[z] be the length of the

co
shortest path starting form v0, going through only those vertices that are in S and ending at z. Let u is the
vertex in S to which the shortest path has already been found. If dist[z] >dist[u] + w(u,z) then dist[z] is
updated to dist[u] + w(u,z) and the predecessor of z is set to u. The Dijustra’s algorithm is presented in

a.
Algorithm 6.6.

AlgorithmDijkstra (v0, W, dist, n)

iy
// v0 is the source vertex, W is the adjacency matrix to store the weights of the links, dist[k] is the array
to store the shortest path to vertex k, n is the number of vertices//
un
{

for (i = 1 ; i < = n ; i ++){

S[i] = 0; // Initialize the set S to empty i.e. i is not inserted into the set//
sD

dist[i] = w(v0,i) ; //Initialize the distance to each node

}
al

S[vo] = 1; dist[v0] = 0;

for (j = 2; j<= n; j++) {

choose a vertex u from those vertices not in S such that dist [u] is minimum.

S[u] = 1;
to

for (each z adjacent to u with S[z] = 0) {

if(dist[z] >dist [u] + w[u, z])

dist[z] = dist [u] + w[u, z];

Algorithm 6.6. Dijkstra’s algorithm for finding shortest path.

Download FREE Computer Science Notes at TutorialsDuniya.com

Let us consider the graph. The objective is to find the shortest path from source vertex 0 to the all
remaining nodes.

Iteration Set of nodes to which the shortest Vertex selected Distance

path is found

m
0 1 2 3 4

Initial {0} - 0 10 ∞ 5 ∞

co
1 {0, 3} 3 0 8 14 5 7

2 {0, 3,4} 4 0 8 13 5 7

a.
3 {0, 3, 4, 1} 1 0 8 9 5 7

4 {0, 3, 4, 1, 2} 2 0 8 9 5 7

The time complexity of the algorithm is O(n2).

iy
un
sD
al

Dynamic Programming
ri

Introduction
The Dynamic Programming (DP) is the most powerful design technique for solving optimization
to

problems. It was invented by mathematician named Richard Bellman inn 1950s. The DP in closely
related to divide and conquer techniques, where the problem is divided into smaller sub-problems and
each sub-problem is solved recursively. The DP differs from divide and conquer in a way that instead of
Tu

solving sub-problems recursively, it solves each of the sub-problems only once and stores the solution to
the sub-problems in a table. The solution to the main problem is obtained by the solutions of these sub-
problems.
The steps of Dynamic Programming technique are:
• Dividing the problem into sub-problems: The main problem is divided into smaller sub-
problems. The solution of the main problem is expressed in terms of the solution for the smaller
sub-problems.
• Storing the sub solutions in a table: The solution for each sub-problem is stored in a table so
that it can be referred many times whenever required.

Download FREE Computer Science Notes at TutorialsDuniya.com

• Bottom-up computation: The DP technique starts with the smallest problem instance and
develops the solution to sub instances of longer size and finally obtains the solution of the
original problem instance.
The strategy can be used when the process of obtaining a solution of a problem can be viewed as a
sequence of decisions. The problems of this type can be solved by taking an optimal sequence of
decisions. An optimal sequence of decisions is found by taking one decision at a time and never making
an erroneous decision. In Dynamic Programming, an optimal sequence of decisions is arrived at by using
the principle of optimality. The principle of optimality states that whatever be the initial state and

m
decision, the remaining decisions must constitute an optimal decision sequence with regard to the state
resulting form the first decision.
A fundamental difference between the greedy strategy and dynamic programming is that in the

co
greedy strategy only one decision sequence is generated, wherever in the dynamic programming, a
number of them may be generated. Dynamic programming technique guarantees the optimal solution
for a problem whereas greedy method never gives such guarantee.

a.
Matrix chain Multiplication

iy
Let, we have three matrices A1, A2 and A3, with order (10 x 100), (100 x 5) and (5 x 50) respectively.
Then the three matrices can be multiplied in two ways.
un
(i) First, multiplying A2 and A3, then multiplying A1 with the resultant matrix i.e. A1(A2 A3).
(ii) First, multiplying A1 and A2, and then multiplying the resultant matrix with A3 i.e. (A1A2) A3.

The number of scalar multiplications required in case 1 is 100 * 5 * 50 + 10 * 100 * 50 = 25000 + 50,000
sD

= 75,000 and the number of scalar multiplications required in case 2 is 10 * 100 * 5 + 10 * 5 * 50 = 5000
+ 2500 = 7500

To find the best possible way to calculate the product, we could simply parenthesize the expression
al

in every possible fashion and count each time how many scalar multiplications are required. Thus the
matrix chain multiplication problem can be stated as “find the optimal parenthesisation of a chain of
matrices to be multiplied such that the number of scalar multiplications is minimized”.
ri

Dynamic Programming Approach for Matrix Chain Multiplication

Let us consider a chain of n matrices A1, A2……….An, where the matrix Ai has dimensions P[i-1] x P[i].
to

Let the parenthesisation at k results two sub chains A1…….Ak and Ak+1……..An. These two sub chains must
each be optimal for A1……An to be optimal. The cost of matrix chain (A1….An) is calculated as
cost(A1……Ak) + cost(Ak+1…...An) + cost of multiplying two resultant matrices together i.e.
Tu

cost(A1……An)= cost(A1……Ak) + cost(Ak+1…...An) + cost of multiplying two resultant matrices together.

Here, the cost represents the number of scalar multiplications. The sub chain (A1….Ak) has a dimension
P[0] x P[k] and the sub chain (Ak+1……An) has a dimension P[k] x P[n]. The number of scalar
multiplications required to multiply two resultant matrices is P[0] x P[k] x P[n].

Download FREE Computer Science Notes at TutorialsDuniya.com

Let m[i, j] be the minimum number of scalar multiplications required to multiply the matrix chain
(Ai………..Aj). Then

(i) m[i, j] = 0 if i = j
(ii) m[i, j] = minimum number of scalar multiplications required to multiply (Ai….Ak) + minimum
number of scalar multiplications required to multiply (Ak+1….An) + cost of
multiplying two resultant matrices i.e.
m[i, j ] = m[i, k ] + m[ k , j ] + P[i − 1] × P[ k ] × P[ j ]

m
However, we don’t know the value of k, for which m[i, j] is minimum. Therefore, we have to try all j – i

co
possibilities.

 0 if i = j
m[i, j ] = 
min {m[i, k ] + m[k , j ] + P[i − 1] × P[k ] × P[ j ]} Otherwise

a.
i≤k < j

Therefore, the minimum number of scalar multiplications required to multiply n matrices A1 A2……An is

m[1, n] = min{m[1, k ] + m[ k , n] + P[0] × P[ k ] × P[ n]}

1≤ k < n
iy
un
The dynamic programming approach for matrix chain multiplication is presented in Algorithm 7.2.
sD

AlgorithmMATRIX-CHAIN-MULTIPLICATION (P)

// P is an array of length n+1 i.e. from P[0] to P[n]. It is assumed that the matrix Ai has the dimension P[i-
al

1] ×P[i].

{
ri

for(i = 1; i<=n; i++)

m[i, i] = 0;
to

for(l = 2; l<=n; l++){

for(i = 1; i<=n-(l-1); i++){

j = i + (l-1);

m[i, j] = ∞;

for(k = i; k<=j-1; k++)

q = m[i, k] + m[k+1, j] + P[i-1] P[k] P[j] ;

if (q<m [i, j]){

Download FREE Computer Science Notes at TutorialsDuniya.com

m[i, j] = q;

s[i, j] = k;

m
}

returnm and s.

co
}

Algorithm 7.2 Matrix Chain multiplication algorithm.

a.
Now let us discuss the procedure and pseudo code of the matrix chain multiplication. Suppose, we

iy
are given the number of matrices in the chain is n i.e. A1, A2………An and the dimension of matrix Ai is P[i-
1] ×P[i]. The input to the matrix-chain-order algorithm is a sequenceP[n+1] = {P[0], P[1], …….P[n]}. The
algorithm first computes m[i, i] = 0 for i = 1, 2, …….n in lines 2-3. Then, the algorithm computes m[i, j] for
un
j– i = 1 in the first step to the calculation of m[i, j] for j – i = n -1 in the last step. In lines 3 – 11, the value
of m[i, j] is calculated for j – i = 1 to j –i = n – 1 recursively. At each step of the calculation of m[i, j], a
calculation on m[i, k] and m[k+1, j] for i≤k<j, are required, which are already calculated in the previous
steps.
sD

To find the optimal placement of parenthesis for matrix chain multiplication Ai, Ai+1, …..Aj, we should
test the value of i≤k<j for which m[i, j] is minimum. Then the matrix chain can be divided from (A1 ……Ak)
and (Ak+1 ……. Aj).
al

Let us consider matrices A1,A2……A5 to illustrate MATRIX-CHAIN-MULTIPLICATIONalgorithm. The matrix

chain order P = {P0, P1, P2, P3, P4, P5} = {5, 10, 3, 12, 5, 50}. The objective is to find the minimum number
of scalar multiplications required to multiply the 5 matrices and also find the optimal sequence of
ri

multiplications.

The solution can be obtained by using a bottom up approach that means first we should calculate mii
to

for 1≤i ≤ 5. Then mijis calculated for j – i = 1 to j – i = 4. We can fill the table shown in Fig. 7.4 to find the
solution.
Tu

Fig. 7.4Table to store the partial solutions of the matrix chain multiplication problem

The value of mii for 1≤i ≤ 5 can be filled as 0 that means the elements in the first row can be assigned 0.
Then

For j – i = 1

Download FREE Computer Science Notes at TutorialsDuniya.com

m12 = P0 P1 P2 = 5 x 10 x 3 = 150

m23 = P1 P2 P3 = 10 x 3 x 12 = 360

m34 = P2 P3 P4 = 3 x 12 x 5 = 180

m45 = P3 P4 P5 = 12 x 5 x 50 = 3000

For j – i = 2

m
m13 = min {m11 + m23 + P0 P1 P3, m12 + m33 + P0 P2 P3}

= min {0 + 360 + 5 * 10 * 12, 150 + 0 + 5312}

co
= min {360 + 600, 150 + 180} = min {960, 330} = 330

m24 = min {m22 + m34 + P1 P2 P4, m23 + m44 + P1 P3 P4}

a.
= min {0 + 180 + 10*3*5, 360 + 0 +10*12*5}

= min {180 + 150, 360 + 600} = min {330, 960} = 330

m35

iy
= min {m33 + m45 + P2 P3 P5, m34 + m55 + P2 P4 P5}

= min {0 + 3000 + 31250, 180 + 0 + 3550}

un
= min {3000 + 1800 + 180 + 750} = min {4800, 930} = 930

For j – i = 3
sD

m14 = min {m11 + m24 + P0 P1 P4, m12 + m34 + P0 P2 P4, m13+m44+P0 P3 P4}

= min {0 + 330 + 5105, 150 + 180 + 535, 330+0+5125}

= min {330 + 250, 150 + 180 + 75, 330 +300}

= min {580, 405, 630} = 405

m25 = min {m22 + m35 + P1 P2 P5, m23 + m45 + P1 P3 P5, m24+m55+P1 P4 P5}
ri

= min {0 + 930 +10350, 360+3000+101250, 330+0+10550}

= min {930 + 1500, 360 +3000+6000, 330+2500}

= min {2430, 9360, 2830} = 2430

For j - i = 4

m15 = min{m11+ m25+ P0 P1 P5, m12+m35+ P0 P2 P5, m13 + m45 +P0 P3 P5, m14+m55+P0 P4 P5 }

= min{0+2430+51050, 150+930+5350, 330+3000+51250,

405+0+5*5*50}

= min {2430+2500, 150+930+750, 330+3000+3000, 405+1250}

= min {4930, 1830, 6330, 1655} = 1655

Download FREE Computer Science Notes at TutorialsDuniya.com

Hence, minimum number of scalar multiplications required to multiply the given five matrices in
1655.

To find the optimal parenthesization of A1……….A5, we find the value of k is 4 for which m15 is
minimum. So the matrices can be splitted to (A1….A4) (A5). Similarly, (A1….A4) can be splitted to (A1A2) (A3
A4) because for k = 2, m14 is minimum. No further splitting is required as the subchains (A1A2) and (A3 A4)
has length 1. So the optimal paranthesization of A1 …….A5 in ( (A1 A2) (A3 A4) ) (A5).

m
Time complexity of multiplying a chain of n matrices
Let T(n) be the time complexity of multiplying a chain of n matrices.

co
Θ(1) if n = 1
 n −1
T ( n) = 
Θ(1) + ∑ [T (k ) + T (n − k ) + Θ(1)] if n > 1

a.
 k =1
n −1
⇒ T (n) = Θ(1) + ∑ [T (k ) + T (n − k ) + Θ(1)] if n > 1
k =1
n −1

iy
= Θ(1) + Θ(n − 1) + ∑ [T (k ) + T (n − k )]
un
k =1

⇒ T (n) = Θ(n ) + 2[T (1) + T (2) + LL + T (n − 1)]LLL (7.1)

Replacing n by n-1, we get

T (n − 1) = Θ(n − 1) + 2[T (1) + T (2) + LL + T (n − 2)]LLL(7.2)

Subtracting equation 7.2 from equation 7.1, we have

T (n) − T (n − 1) = Θ(n ) − Θ(n − 1) + 2T (n − 1)

⇒ T (n) = Θ(1) + 3T (n − 1)
= Θ(1) + 3[Θ(1) + 3T (n − 2)] = Θ(1) + 3Θ(1) + 32 T (n − 2)
ri

[ ]
= Θ(1) 1 + 3 + 32 + LL + 3n −2 + 3n −1T (1)
= Θ(1)[1 + 3 + 3 + LL + 3 ]
2 n −1
to

3 −1
= Ο(2 )
n
= n

2
Tu

Longest Common Subsequence

The longest common subsequence (LCS) problem can be formulated as follows “Given two
sequences X = 〈x1, x2 ……….xn〉 and Y = 〈y1, y2………yn〉 and the objective is to find the LCS Z = 〈z1, z2
………zn〉 that is common to x and y”.

Download FREE Computer Science Notes at TutorialsDuniya.com

TutorialsDuniya.com
Download FREE Computer Science Notes, Programs, Projects,
Books PDF for any university student of BCA, MCA, B.Sc,
B.Tech CSE, M.Sc, M.Tech at https://www.tutorialsduniya.com

 Algorithms Notes  Information Security

Please Share these Notes with your Friends as well

Download FREE Computer Science Notes at TutorialsDuniya.com

Given two sequences X and Y, we say Z is a common sub sequence of X and Y if Z is a subsequence of
both X and Y. For example, X = 〈 A, B, C, B, D, A, B〉 and Y = 〈 B, D, C, A, B, A〉, the sequence 〈B, C, A〉 is a
common subsequence. Similarly, there are many common subsequences in the two sequences X and Y.
However, in the longest common subsequence problem, we wish to find a maximum length common
subsequence of X and Y, that is 〈 B, C, B, A〉 or 〈 B, D, A, B〉. This section shows that the LCS problem can
be solved efficiently using dynamic programming.

4.7.1 Dynamic programming for LCS problem

m
Theorem.4.1.(Optimal Structure of an LCS)

Let X = 〈x1, x2 ……….xn〉 and Y = 〈y1, y2………yn〉 be sequences and let Z = 〈z1, z2 ………zn〉 be any LCS of X and

co
Y.

Case 1. If xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1.

Case 2. If xm≠yn, then zk≠xm implies that Z is an LCS of Xm-1 and Y.

a.
Case 3. If xm≠yn, then zk≠yn implies that Z is an LCS of X and Yn-1.

iy
Proof The proof of the theorem is presented below for all three cases.
un
Case 1. If xm = yn and we assume that zk≠xm or zk≠yn then xm = yn can be added to Z at any index after k
violating the assumption that Zk is the longest common subsequence. Hence zk = xm = yn. If we do not
sD

consider Zk-1 as LCS of Xm-1 and Yn-1, then there may exist another subsequence W whose length is more
than k-1. Hence, after adding xm = yn to the subsequence W increases the size of subsequence more than
k, which again violates our assumption.
al

Hence, Zk=xm = yn and Zk-1 must be an LCS of Xm-1 and Yn-1.

Case 2.If xm≠yn, then zk≠xm implies that Z is an LCS of Xm-1 and Yn. If there were a common subsequence
W of Xm-1and Y with length greater then k than W would also be an LCS of Xm and Yn violating our
ri

assumption that Zk is an LCS of Xm and Yn.

Case 3. The proof is symmetric to case-2.

Thus the LCS problem has an optimal structure.

Overlapping Sub-problems
From theorem 4.1, it is observed that either one or two cases are to be examined to find an LCS of
Xmand Yn. If xm = yn, then we must find an LCS of Xm-1 and Yn-1. If xm≠yn, then we must find an LCS of Xm-1
and Yn and LCS of Xm and Yn-1. The LCS of X and Y is the longer of these two LCSs.

Download FREE Computer Science Notes at TutorialsDuniya.com

Let us define c[m, n] to be the length of an LCS of the sequences Xm and Yn. The optimal structure of
the LCS problem gives the recursive formula

 0 if m = 0 or n = 0

c[m,n] =  c[m − 1, n − 1] + 1 if xm = yn ..............(7.1)
 max{c[m − 1, n], c[m, n − 1]} if x ≠ y
 m n

Generalizing equation 7.1, we can formulate

m
 0 if i = 0 or j = 0

c[i,j ] =  c[i − 1, j − 1] + 1 if xi = y j ..............(7.2)

co
 max{c[i − 1, j ], c[i, j − 1]} if x ≠ y
 i j

a.
Computing the length of an LCS
Based on equation (7.1), we could write an exponential recursive algorithm but there are only m*n

iy
distinct problems. Hence, for the solution of m*n distinct subproblems, we use dynamic programming to
compute the solution using bottom up approach.
un
The algorithm LCS_length (X, Y) takes two sequences X = 〈x1, x2………..xn〉 and Y = 〈y1, y2………..yn〉 as
inputs and find c[m, n] as the maximum length of the subsequence in X and Y. It stores c[i, j] and b[i, j] in
tables c[m, n] and b[m, n] respectively, which simplifies the construction of optimal solution.
sD

AlgorithmLCS_LENGTH (X, Y)

m=length [X]
al

n=length [Y]

for( i =1; i<=m; i++)

c[i,0] = 0;
to

for(j=0; j<n; j++)

c[0, j]= 0;
Tu

for(i=1; i< m; i++){

for(j = 1; j <= n; j++){

if(x[i] = = y[j]) {

c[i, j] = 1 + c[i-1, j-1];

b[i,j] = ‘ ’;

Download FREE Computer Science Notes at TutorialsDuniya.com

else{

if(c[ i-1, j] ≥ c[i, j-1] )

c[i, j] = c[i-1, j];

↑’;
b[i,j] = ‘↑

else

m
c[i,j] = c[i, j-1];

←’
b[i, j] = ‘←

co
}

return c and b ;

a.
}

Algorithm 7.3 Algorithm for finding Longest common subsequence .

Constructing an LCS iy
un
The algorithm LCS_LENGTH returns c and b tables. The b table can be used to construct the LCS of X and Y
quickly.
sD

AlgorithmPRINT_LCS (b, X, i, j)

{
al

if (i == 0 || j == 0)

return;
ri

if (b[i, j] = = ‘ ‘) {

PRINT_LCS (b, X, i-1, j-1)

Printxi

}
Tu

else if (b[i, j] = = ‘↑’)

PRINT_LCS (b, X, i-1, j)

else

PRINT_LCS (b, X, i, j-1)

Download FREE Computer Science Notes at TutorialsDuniya.com

Algorithm 7.4 Algorithm to print the Longest common subsequence .

Let us consider two sequences X = 〈C, R, O, S, S〉 and Y = 〈R, O, A, D, S〉 and the objective is to find the LCS
and its length. The c and b table are computed by using the algorithm LCS_LENGTH for X and Y that is
shown in Fig.7.5. The longest common subsequence of X and Y is 〈R, O, S〉 and the length of LCS is 3.

m
Reliability Design Problem
In this section, we present the dynamic programming approach to solve a problem with

co
multiplicative constraints. Let us consider the example of a computer return in which a set of nodes are
connected with each other. Let ri be the reliability of a node i.e. the probability at which the node
forwards the packets correctly in ri. Then the reliability of the path connecting from one node s to

a.
k
another node d is ∏ r where k is the number of intermediate node. Similarly, we can also consider a
i =1
i

system is
iy
system with n devices connected in series, where the reliability of device i is ri. The reliability of the
k

∏ r . For example if there are 5 devices connected in series and the reliability of each device
i =1
i
un
is 0.99 then the reliability of the system is 0.99 × 0.99 × 0.99 × 0.99 × 0.99=0.951. Hence, it is desirable to
connect multiple copies of the same devices in parallel through the use of switching circuits. The
switching circuits determine the devices in any group functions properly. Then they make use of one
such device at each stage.
sD

Let mi be the number of copies of device Di in stage i. Then the probability that all mi have
malfunction i.e. (1-ri)mi.Hence, the reliability of stage i becomes 1-(1-ri)mi . Thus, if ri =0.99 and mi=2, the
reliability of stage i is 0.9999. However, in practical situations it becomes less because the switching
circuits are not fully reliable. Let us assume that the reliability of stage i in φ i(mi), i≤n. Thus the reliability
al

k
of the system is ∏ φ (m ) . i i
ri

i =1
to

Fig. 7.9

The reliability design problem is to use multiple copies of the devices at each stage to increase
reliability. However, this is to be done under a cost constraint. Let ci be the cost of each unit of device Di
Tu

and let c be the cost constraint. Then the objective is to maximize the reliability under the condition that
the total cost of the system mici will be less than c.

Mathematically, we can write

maximize ∏ φ (m )
1≤ i ≤ n
i i

Download FREE Computer Science Notes at TutorialsDuniya.com

subject to ∑c m ≤ c
1≤ i ≤ n
i i

mi ≥ 1 and 1 ≤ i ≤ n .

We can assume that each ci>0 and so each mi must be in the range 1 ≤ mi ≤ ui , where

 c + ∑n c 
 j 

m
j =1 and j ≠ i
ui =  .
 c i 
 

co
The dynamic programming approach finds the optimal solution m1,m2…mn. An optimal sequence of
decision i.e. a decision for each mi can result an optimal solution.

a.
n
Let fn(c) be the maximum reliability of the system i.e. maximum ∏φ (m ) , subject to the constraint
i =1
i i

∑ c m ≤ c and 1 ≤ mi ≤ xi , 1 ≤ i ≤ n . Let we take a decision on the value of mn from {1,2… un}. Then
1≤ i ≤ n
i i

the value of the remaining mn 1 ≤ i ≤ n can be chosen in such a way that

iy φ (mi ) for
un
1 ≤ i ≤ n ≤ n − 1 can be maximized under the cost constraint c-cnmn. Thus the principle of optimality
holds and we can write

{ ( ) (
fn(c)= max φ j m j f j −1 x − m j c j
1≤ m n ≤ u n
)} (8.1)
sD

We can generalized the equation 8.1 and we can write

{ ( ) (
fj(x)= max φ j m j f j −1 x − m j c j
1≤ m j ≤ u j
)} (8.2)
al

It is clear that f0(x)=1 for all x, 0 ≤ x ≤ c . Let Si consists of tuples of the form (f,x) where f = fi(x).
There is atmost one tuple for each different x that remits from a sequence of decisions on m1,m2…mn. If
ri

there are two tuples (f1,x1) and (f2,x2) such that f1 ≥ f2 and x1≤ x2 then (f2,x2) is said to be dominated tuple
and discarded from Si.
to

Let us design a three stage system with devices D1,D2 and D3. The costs are Rs 30,Rs 15 and Rs 20
respectively. The cost constraint of the system is Rs 105. The reliability of the devices are 0.9, 0.8 and 0.5
(
respectively. If stage i has mi devices in parallel then φ (mi ) = 1 − (1 − ri )
mi
). We can write c =30, c
1 2
Tu

=15,c3=20, c=105, r1=0.9, r2=0.8 and r3=0.5. We can calculate the value of ui, for 1 ≤ i ≤ 3

Download FREE Computer Science Notes at TutorialsDuniya.com

105 − (15 + 20 )   70 
x1 =   =  30  = 2
 30
105 − (30 + 20)   55 
x2 =   =  15  = 3
 15
105 − (30 + 15)   60 
x3 =   =  20  = 3
 20

m
Then we start with S0={(1,0)}. We can obtain each Si from Si-1 by trying out all possible values for mi
and combining the resulting tuples together.

co
S11 ={(0.9,30)} S 21 ={(0.99,60)} S 1 ={(0.9,30),(0.99,60)}

Considering 1 device at stage q, we can write S12 as follows

a.
S12 ={(0.9 × 0.8,30+15),(0.99 × 0.8,60+15)}

={(0.72,45),(0.792,75)}

iy
Considering 2 devices of D2 in stage 2, we can compute the reliability at stage 2

φ2 (m2 ) =1-(1-0.8)2=0.96 cost at stage 2=2 × 15=30

un
Hence, we can write

S 22 ={(0.9 × 0.96,30+30),(0.99 × 0.96,60+30)}

={(0.864,60),(0.9504,90)}

The tuple (0.9504, 90) is removed as it left only Rs 15 and the maximum cost of the third stage is 20.
al

Now, we can consider 3 devices of D2 in stage 2 and compute the reliability at stage 2 is

φ2 (m2 ) =1-(1-0.8)3=1-0.008=0.992.
ri

Hence, we can write

S32 ={(0.9 × 0.992,30+45),(0.99 × 0.992,60+45)}

={(0.8928,75),(0.98208,105)}
Tu

The tuple (0.98208,105) is discarded as there is no cost left for stage 3. Combining S12 , S 22 and S32 , we
get

S 2 ={(0.72,45),(0.792,75),(0.864,60),(0.8928,75)}

The tuple (0.792,75) is discarded from S 2 as it is dominated by (0.864,60).

Now, we can compute S13 assuming 1 device at stage 3.

Download FREE Computer Science Notes at TutorialsDuniya.com

S13 ={(0.72 × 0.5,45+20),(0.864 × 0.5,60+20),(0.8928 × 0.5,75+20)}

={(0.36,65),(0.432,80),(0.4464,95)}

If there are 2 devices at stage 3, then

φ3 (m3 ) =(1-(1-0.5)2)=0.75

We can write S 23 as follows

m
S 23 ={(0.72 × 0.75,45+40),(0.864 × 0.75,60+40),(0.8928 × 0.75,75+40)}

co
={(0.54,85),(0.648,100)} (tuple(0.8928 × 0.75,115) is discarded as cost

constraint is 105).

a.
If there are 3 devices at stage 3 then

φ3 (m3 ) =(1-(1-0.5)3)=1-0.125=0.875

iy
Hence, we can write S33 ={(0.72 × 0.875,45+60)}={(0.63,105)}

Combining S13 , S 23 and S33 we can write S3 discarding the dominant tuples ass given below
un
S3={(0.36,65),(0.432,80),(0.54,85),(0.648,100)}

The best design has the reliability 0.648 and a cost of 100. Now, we can track back to find the number of
sD

devices at each stage. The tuple(0.648,100) is taken from S 23 that is with 2 devices at stage 2. Thus m3=2.
The tuple (0.648,100) was derived from the tuple (0.864,60) taken from S 22 and computed with
considering 2 devices at stage 2. Thus m2=2. The tuple (0.864,60) is derived from the tuple (0.9,30) taken
al

from S11 computed with 1 device at stage 1. Thus m1=1.

Bellman Ford Algorithm

In the previous chapter, it is observed that the Dijkstra’s algorithm finds the shortest path from one
node to another node in a graph G = (V, E) where the weights of the links are positive. However, if there
to

are some negative weight edges then dijkstra’s algorithm may fail to find the shortest path from one
node to another. Hence, Bellman-ford algorithm solves the single source shortest paths problem in
general case. Let us consider the graph G= (V, E) shown in Fig.7.10. Let us assume that node 1 is the
Tu

source, node 2 and node 3 are destinations. Then by using Dijkstra’s algorithm, we can compute the
shortest path to node 2 and node 3 as 5 and 7 respectively whereas it is not actually the case. The
shortest path from 1 to 3 is 123 and the path length is 2. This can be computed by Bellman-ford
algorithm.

Before applying Bellman-ford algorithm, we assume that the negative weight edges are permitted
but there should not be any negative weight cycle. This is necessary to answer that the shortest paths
consists of a finite number of edges. In Fig.7.11 , the path from 1 to 3 is 121212…123 and the path

Download FREE Computer Science Notes at TutorialsDuniya.com

length is −∞. When there are no negafve weight cycles, the shortest path between any two nodes in n-
node graph contains n−1 edges.

Let distl[u] be the length of the shortest path from source node v to the node u under the constraint
that the shortest path contains at most l edges. The dist1[u]=cost[v,u], for 1≤u≤n. As we discussed
earlier, if there is no negative weight cycle then the shortest path contains atmostn−1 edges. Hence,
distn-1[u] in the length of the shortest path from v to u. Our goal is to compute distn-1[u] and this can be
done by using Dynamic programming approach. We can make the following observations

m
(i) If the shortest path from v to u with at most k, k>1 edges has no more than k−1 edges, then
distk[u]= distk-1[u].
(ii) If the shortest path from v to u with at most k, k>1 edges has exactly k edges, then it is made up

co
of a shortest path from v to some vertex j followed by edge<j, u>. The path from v to j has k−1
edges and its length is distk-1[j]. All vertices i such that <i, u>∈E are the candidates of j. Since we

{ }}
are interested in a shortest path, the i that minimizes distk-1[i]=cost[i,u] is the correct value for j.
{
dist k -1[u ], min dist k −1[i ] + cos t (i, u )

a.
Distk[u]=
min (i , u )∈E

The Bellman ford algorithm is presented in Algorithm 7.6.

iy
un
AlgorithmBELLMAN FORD(v,cost,dist,n)

//v is the source, cost is the adjacency matrix representing the cost of edges, dist stores the distance to
all nodes, n is the number of nodes//
sD

1 for(i=1;i<=n; i++)

2 dist[i]=cost[v][i];
al

3 for(k=2; k<= n-1; k++){

4 for each u such that k ≠ v and (j, u)∈E

5 if(dist[u]>dist[j]+cost[j][u])
to

6 dist[u]=dist[j]+cost[j][u];

7 }//end for k
Tu

Algorithm 7.6 Bellman FordAlgorithm.

The Bellman ford algorithm starts with computing the path from source to each node i in v. Since there
are n nodes in a graph, the path to any node can contain atmostn-1 nodes. Then for each node u,
remaining n-2 nodes are required to be examined. If <j, u>∈E then the condition dist[u] is compared

Download FREE Computer Science Notes at TutorialsDuniya.com

with dist[j] + cost[j][u]. If dist[u] is greater than dist[j]+dist[j][u] then dist[u] is updated to
dist[j]+cost[j][u].

Let us consider the example network shown in Fig. 7.12.

m
co
a.
The example graph and its adjacency matric

iy
The time complexity of Bellman ford algorithm is O(ne). The lines 1-2 takes O(n) time. If the matrix is
stored in an adjacency list then lines 4-6 takes O(e) time. Hence, the lines 3-7 takes O(ne) time.
Therefore, the several time of Bellman ford algorithm is O(ne).
un
sD
al
ri
to
Tu

Stepwise working procedure of Bellman Ford Algorithm

Download FREE Computer Science Notes at TutorialsDuniya.com

Assembly Line Scheduling

m
co
a.
Assembly lines for automobile manufacturing factory

iy
An automobile company has two assembly lines as shown in Fig.7.13.The automobile chassis enters an
un
assembly line and goes through all stations of the assembly line and complete auto exists at the end of
the assembly line. Each assembly line has n stations and the jth station of ith line is denoted as Sij. The
time required at station Sij is aij and the time required to travel from one station to the next station is
negligible. Normally, the chassis enters in a line goes through all the stations of the same line. However,
sD

in overload situations, the factory manager has the flexibility to switch partially completed auto from a
station of one line to the next station of other line. The time required to transfer the partially completed
auto from station Sij to the other line is tij; where i=1,2 and j=1,2…n-1. Now the objective to choose some
station from line 1 and some station from line 2 so that the total time to manufacture an auto can be
al

minimized.

If there are many stations in the assembly lines the brute force search takes much time to
ri

determine the stations through which the auto can be assembled. There are 2n possible ways to chose
stations from the assembly line. Thus determining the fastest way for assembling the auto takes O(2n)
time, which is infeasible when n is large. This problem can be efficiently solved by dynamic programming
to

technique.

The first step of dynamic programming technique is to characterize the structure of an optimal
Tu

solution. Since, there are 2 assembly lines with stations in each line, the computation of time to move to
the 1st station of any assembly line is straight forward. However, there are two choices for j=2,3… n in
each assembly line. First, the chassis may come from station S1,j-1 and then directly move to S1,j since the
time to move from one station to the next station in the same assembly line is negligible. The second
choice is the chassis can come from station S2,j-1 and then been transferred to station S1,j with a transfer
time t2,j-1. Let the fastest way through station S1,j is through station S1,j-1. Then there must be a fastest
way through from the starting point through station S1,j-1. Similarly, if there is a fastest way through
station S2,j-1 then the chassis must have taken a fastest way from the starting point through station S2,j-1.

Download FREE Computer Science Notes at TutorialsDuniya.com

Thus the optimal solution to the problem can be found by solving optimal solution of the sub-problems
that in the fastest way to either S1,j-1 or S2,j-1. This is referred as optimal structure of assembly line
scheduling problem.

If we find the fastest way to solve assembly line scheduling problem through station j-1 on either
line 1 or line 2. Thus the fastest way through station S1,j is either

• the fastest way to S1, j-1 and then directly through station S1,j.
• the fastest way to S2,j-1 and a transfer from line 2 to line 1 and then through station S1,j.

m
Similarly, the fastest way through station S2,j is

• the fastest way to S2,j-1 and then directly through station S2,j.

co
• the fastest way to S1,j-1, a transfer time from station 1.
Let fi[j] be the fastest possible time to get a chassis from the starting point through station Si,j of the
assembly line i. Then chassis directly goes to the first station of each line.

a.
f 1 [1] = e1 + a1,1

f 2 [1] = e2 + a 2 ,1

Now, we can compute fi[j], 2<j≤n and 1≤i≤2 as

iy
un
f1[j]=min{f1[j-1] + a1,j, f2[j-1] + t2,j-1 + a1,j }

f2[j]=min{f2[j-1] + a2,j, f1[j-1] + t1,j-1 + a2,j }

If the chassis goes all the way through station n either line 1 or line 2 and then exits, we have
sD

e1 + a1,1 if n = 1
f1 [n] = 
min{ f 1 [n − 1] + a1, n , f 2 [n − 1] + t 2 , n −1 , a1, n }Otherwise
al

e2 + a1,1 if n = 1
f 2 [n] = 
min{ f 2 [n − 1] + a2, n , f1 [n − 1] + t1, n −1 , a1,n } Otherwise
ri

Let the fastest time to get the chassis all the way through the factory is denoted by f*. Then

f*= min{f1[n] + x1, f2[n] + x2 }

Now, we can compute the stations through which the chassis must move to deliver the end product at
minimum time. This can be calculated with a backward approach. Let l* denote the line whose station n
Tu

is used in a fastest way through the entire process. If f1[n] + x1<f2[n] + x2 then l*=1 else l*=2. Then let us
denote li[j] be the line number 1 or 2 whose station j-1 is used in a fastest way through station Si,j. li[1] is
not required to be calculated since there is no station proceeding to station Si,1.

If f1[j-1] + a1,j ≤f2[j-1]+t2,j-1 + a1,j then l1[j]=1.Otherwise, l1[j]=2. Similarly, if f2[j-1]+ a2,j≤ f1[j-1]+t1,j-1 + a2,j
then l2[j]=2. Otherwise, l2[j]=1. The algorithm for assembly line scheduling problem is presented in
Algorithm7.7.

Download FREE Computer Science Notes at TutorialsDuniya.com

m
co
a.
iy
Illustration of assembly line scheduling procedure.
un
f1[1] = e1 + a1,1 = 2 + 4 = 6 f2[1] = e2 + a2,1 = 3 + 7 = 10

f1[2] = min{f1[1] + a1,2, f2[1] + t2,1 + a1,2 }

= min{6 + 7, 10 + 2 + 7} =13

f2[2] = min{f2[1] + a2,2, f1[1] + t1,1 + a2,2 }

= min{10 + 2, 6 + 2 + 2} =10
al
ri

The time required at all the stations of both theassembly lines are shown above. The minimum time
required to assemble an auto is 33. The assembly lines through which the complete auto is assembled is
shown above.
to
Tu

Download FREE Computer Science Notes at TutorialsDuniya.com

MODULE - III
• Lecture 21 - Data Structure for Disjoint Sets
• Lecture 22 - Disjoint Set Operations, Linked list Representation
• Lecture 23 - Disjoint Forests
• Lecture 24 - Graph Algorithm - BFS and DFS
• Lecture 25 - Minimum Spanning Trees
• Lecture 26 - Kruskal algorithm
• Lecture 27 - Prim's Algorithm

m
• Lecture 28 - Single Source Shortest paths
• Lecture 29 - Bellmen Ford Algorithm
• Lecture 30 - Dijkstra's Algorithm

co
a.
iy
un
sD
al
ri
to
Tu

Download FREE Computer Science Notes at TutorialsDuniya.com

Lecture – 21 Disjoint Set Data Structure

In computing, a disjoint-set data structure, also called a union–find data structure or merge–
find set, is a data structure that keeps track of a set of elements partitioned into a number
of disjoint (non-overlapping) subsets.
It supports the following useful operations:

m
• Find: Determine which subset a particular element is in. Find typically returns an item
from this set that serves as its "representative"; by comparing the result of

co
two Find operations, one can determine whether two elements are in the same subset.
• Union: Join two subsets into a single subset.
• Make Set, which makes a set containing only a given element (a singleton), is generally

a.
trivial. With these three operations, many practical partitioning problems can be solved.
In order to define these operations more precisely, some way of representing the sets is needed.

iy
One common approach is to select a fixed element of each set, called its representative, to
represent the set as a whole. Then, Find(x) returns the representative of the set that x belongs to,
and Union takes two set representatives as its arguments.
un
Example :
sD

Make Set creates 8 singletons.

After some operations of Union, some sets are grouped together.

Applications :
ri

• partitioning of a set
• Boost Graph Library to implement its Incremental Connected Components functionality.
to

• implementing Kruskal's algorithm to find the minimum spanning tree of a graph.

• Determine the connected components of an undirected graph.
Tu

CONNECTED-COMPONENTS(G)
1. for each vertex v∈V[G]
SAME-COMPONENT(u,v)
2. do MAKE-SET(v)
1. if FIND-SET(u)=FIND-SET(v)
3. for each edge (u,v) ∈E[G]
2. thenreturn TRUE
4. doif FIND-SET(u) ≠ FIND-SET(v)
3. elsereturn FALSE
5. then UNION(u,v)

Download FREE Computer Science Notes at TutorialsDuniya.com

Lecture 22 - Disjoint Set Operations, Linked list Representation

• A disjoint-set is a collection ={S1, S2,…, Sk} of distinct dynamic sets.
• Each set is identified by a member of the set, called representative.
Disjoint set operations

m
– MAKE-SET(x): create a new set with only x. assume x is not already in some
other set.

co
– UNION(x,y): combine the two sets containing x and y into one new set. A new
representative is selected.

a.
– FIND-SET(x): return the representative of the set containing x.
Linked list Representation
•

iy
Each set as a linked-list, with head and tail, and each node contains value, next node
pointer and back-to-representative pointer.
un
• Example:
• MAKE-SET costs O(1): just create a single element list.
• FIND-SET costs O(1): just return back-to-representative pointer.
sD
al
ri
to
Tu

Download FREE Computer Science Notes at TutorialsDuniya.com

UNION Implementation
• A simple implementation: UNION(x,y) just appends x to the end of y, updates all back-to-
representative pointers in x to the head of y.
• Each UNION takes time linear in the x’s length.
• Suppose n MAKE-SET(xi) operations (O(1) each) followed by n-1 UNION

m
– UNION(x1, x2), O(1),
– UNION(x2, x3), O(2),

co
– …..
– UNION(xn-1, xn), O(n-1)

a.
• The UNIONs cost 1+2+…+n-1=Θ(n2)
So 2n-1 operations cost Θ(n2), average Θ(n) each

Lecture 23 - Disjoint Forests iy

un
sD
al
ri
to

• Three operations
– MAKE-SET(x): create a tree containing x. O(1)
Tu

– FIND-SET(x): follow the chain of parent pointers until to the root. O(height of x’s
tree)
– UNION(x,y): let the root of one tree point to the root of the other. O(1)
• It is possible that n-1 UNIONs results in a tree of height n-1. (just a linear chain of n
nodes).
• So n FIND-SET operations will cost O(n2).

Download FREE Computer Science Notes at TutorialsDuniya.com

Union by Rank & Path Compression

• Union by Rank: Each node is associated with a rank, which is the upper bound on the
height of the node (i.e., the height of subtree rooted at the node), then when UNION, let
the root with smaller rank point to the root with larger rank.
• Path Compression: used in FIND-SET(x) operation, make each node in the path from x
to the root directly point to the root. Thus reduce the tree height.

m
co
a.
iy
un
sD
al
ri
to
Tu

Download FREE Computer Science Notes at TutorialsDuniya.com

Lecture 24 - Graph Algorithm - BFS and DFS

In graph theory, breadth-first search (BFS) is a strategy for searching in a graph when search is
limited to essentially two operations:
(a) visit and inspect a node of a graph;
(b) gain access to visit the nodes that neighbor the currently visited node.

• The BFS begins at a root node and inspects all the neighboring nodes.

m
• Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which
were unvisited, and so on.
• Compare BFS with the equivalent, but more memory-efficient.

co
Historical Background
•

a.
BFS was invented in the late 1950s by E. F. Moore, who used to find the shortest path out
of a maze,
• discovered independently by C. Y. Lee as a wire routing algorithm (published 1961).

Example
iy
un
sD

A BFS search will visit the nodes in the following order: A, B, C, E, D, F, G

BFS Algorithm
al

The algorithm uses a queue data structure to store intermediate results as it traverses the graph, as
follows:
ri

1. Enqueue the root node

2. Dequeue a node and examine it

• If the element sought is found in this node, quit the search and return a result.
• Otherwise enqueue any successors (the direct child nodes) that have not yet been
Tu

discovered.
3. If the queue is empty, every node on the graph has been examined – quit the search and
return "not found".
4. If the queue is not empty, repeat from Step 2.

Download FREE Computer Science Notes at TutorialsDuniya.com

Applications
Breadth-first search can be used to solve many problems in graph theory, for example:

• Copying Collection, Cheney's algorithm

• Finding the shortest path between two nodes u and v (with path length measured by number
of edges)

m
• Testing a graph for bipartiteness
• (Reverse) Cuthill–McKee mesh numbering
•

co
Ford–Fulkerson method for computing the maximum flow in a flow network
• Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to
be re-constructed in an efficient manner.

a.
Pseudo Code

Input: A graph G and a root v of G

1 procedure BFS(G,v) is iy
un
2 create a queue Q
3 create a set V
4 add v to V
sD

5 enqueuev onto Q
6 whileQ is not empty loop
7 t ← Q.dequeue()
8 ift is what we are looking for then
al

9 returnt
10 end if
11 for all edges e in G.adjacentEdges(t) loop
ri

12 u ← G.adjacentVertex(t,e)
13 ifu is not in Vthen
to

14 add u to V
15 enqueueu onto Q
16 end if
Tu

17 end loop
18 end loop
19 return none
20 end BFS

Download FREE Computer Science Notes at TutorialsDuniya.com

Time and space complexity

[3]
The time complexity can be expressed as since every vertex and every edge will
be explored in the worst case. Note: may vary between and , depending
on how sparse the input graph is.

m
When the number of vertices in the graph is known ahead of time, and additional data structures are
used to determine which vertices have already been added to the queue, the space complexity can
be expressed as where is the cardinality of the set of vertices. If the graph is

co
[4]
represented by an Adjacency list it occupies space in memory, while anAdjacency
matrix representation occupies .

a.
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.
One starts at the root(selecting some arbitrary node as the root in the case of a graph) and explores
as far as possible along each branch beforebacktracking.

Historical Background

iy
A version of depth-first search was investigated in the 19th century by French mathematician
Charles Pierre Trémaux
un
Example
sD
al

A DFS search will visit the nodes in the following order: A, B, D, F, E, C, G

Pseudo Code
to

Input: A graph G and a vertex v of G

Output: All vertices reachable from v labeled as discovered
Tu

A recursive implementation of DFS

1 procedure DFS(G,v):
2 label v as discovered
3 for all edges from v to winG.adjacentEdges(v) do
4 if vertex w is not labeled as discovered then
5 recursively call DFS(G,w)

Download FREE Computer Science Notes at TutorialsDuniya.com

A non-recursive implementation of DFS

1 procedure DFS-iterative(G,v):
2 let S be a stack
3 S.push(v)
4 whileS is not empty
5 v ← S.pop()

m
6 ifv is not labeled as discovered:
7 label v as discovered

co
8 for all edges from v to winG.adjacentEdges(v) do
9 S.push(w)

Applications

a.
• Finding connected components.
•
•
•
Topological sorting.
Finding the bridges of a graph.
iy
un
Generating words in order to plot the Limit Set of a Group.
• Finding strongly connected components.
• Planarity testing
• Solving puzzles with only one solution, such as mazes. (DFS can be adapted to find all
sD

solutions to a maze by only including nodes on the current path in the visited set.)
• Maze generation may use a randomized depth-first search.
• Finding bi-connectivity in graphs.
al
ri
to
Tu

Download FREE Computer Science Notes at TutorialsDuniya.com

TutorialsDuniya.com
Download FREE Computer Science Notes, Programs, Projects,
Books PDF for any university student of BCA, MCA, B.Sc,
B.Tech CSE, M.Sc, M.Tech at https://www.tutorialsduniya.com

 Algorithms Notes  Information Security

Please Share these Notes with your Friends as well

TT - Stage 8 End of Unit 5 Test - 22.11.22
100% (8)
TT - Stage 8 End of Unit 5 Test - 22.11.22
8 pages
GuardLogix Safety Application Instruction Set
No ratings yet
GuardLogix Safety Application Instruction Set
398 pages
Report Painter COPA
67% (3)
Report Painter COPA
15 pages
Introduction 1
No ratings yet
Introduction 1
6 pages
Lecture 1428551222
No ratings yet
Lecture 1428551222
80 pages
Algorithm Design (16cse22c2) Notes
No ratings yet
Algorithm Design (16cse22c2) Notes
77 pages
lECTURE NOTES
No ratings yet
lECTURE NOTES
77 pages
CSC2204 Analysis of Algorithms Lecture Note2
No ratings yet
CSC2204 Analysis of Algorithms Lecture Note2
22 pages
Analyse Data Structures and Algorithms
No ratings yet
Analyse Data Structures and Algorithms
51 pages
Lecture 05
No ratings yet
Lecture 05
51 pages
Ads Unit 1
No ratings yet
Ads Unit 1
15 pages
CP 4154
No ratings yet
CP 4154
8 pages
Design and Analysis of Algorithms Notes 2 - TutorialsDuniya
No ratings yet
Design and Analysis of Algorithms Notes 2 - TutorialsDuniya
208 pages
Lec-4 AymptoticNotations
No ratings yet
Lec-4 AymptoticNotations
16 pages
L1 AlgoAnalysis
No ratings yet
L1 AlgoAnalysis
57 pages
DAA Notes
No ratings yet
DAA Notes
80 pages
Lecture 2
No ratings yet
Lecture 2
41 pages
Lecture 1 - Introduction To Design and Analysis of Algorithms
No ratings yet
Lecture 1 - Introduction To Design and Analysis of Algorithms
3 pages
Comparing Algorithms
No ratings yet
Comparing Algorithms
5 pages
Computer Algorithms: Muralikrishna S.N
No ratings yet
Computer Algorithms: Muralikrishna S.N
13 pages
Lecture 2
No ratings yet
Lecture 2
42 pages
Algorithm
No ratings yet
Algorithm
7 pages
Module 1 - Complexity and Order Notations
No ratings yet
Module 1 - Complexity and Order Notations
72 pages
Data Structure Lecture 6
No ratings yet
Data Structure Lecture 6
49 pages
AOP Unit 1 Chapter 1
No ratings yet
AOP Unit 1 Chapter 1
58 pages
Lecture#04, DAA, Asymptotic Notations - Growth Rate
No ratings yet
Lecture#04, DAA, Asymptotic Notations - Growth Rate
51 pages
Design and Analysis of Algorithms (DAA) Notes
No ratings yet
Design and Analysis of Algorithms (DAA) Notes
112 pages
Ada 1
No ratings yet
Ada 1
95 pages
CSE373: Design and Analysis of Algorithms
No ratings yet
CSE373: Design and Analysis of Algorithms
52 pages
Efficiency of Algorithm
No ratings yet
Efficiency of Algorithm
27 pages
Algorithem Chapter One
No ratings yet
Algorithem Chapter One
43 pages
CS350-CH03 - Algorithm Analysis
No ratings yet
CS350-CH03 - Algorithm Analysis
88 pages
Lecture 5,6, DAA, Asymptotic Notations Growth Rate
No ratings yet
Lecture 5,6, DAA, Asymptotic Notations Growth Rate
50 pages
ADSA Unit-I
No ratings yet
ADSA Unit-I
21 pages
Lecture 1
No ratings yet
Lecture 1
25 pages
Complexity Lec#3
No ratings yet
Complexity Lec#3
25 pages
Lecture 2
No ratings yet
Lecture 2
43 pages
CSE373L1
No ratings yet
CSE373L1
72 pages
DSweek3 Algo
No ratings yet
DSweek3 Algo
29 pages
Unit 1 Introduction To Algorithm
No ratings yet
Unit 1 Introduction To Algorithm
29 pages
Growth of Functions Unit 1
No ratings yet
Growth of Functions Unit 1
18 pages
Complexity of Algorithms 1
No ratings yet
Complexity of Algorithms 1
27 pages
Algorithm Analysis
No ratings yet
Algorithm Analysis
37 pages
Design and Analysis of Algorithm Course Code: 5009
No ratings yet
Design and Analysis of Algorithm Course Code: 5009
50 pages
Design and Analysis of Algorithm Course Code: 5009
No ratings yet
Design and Analysis of Algorithm Course Code: 5009
46 pages
Algorithm Up To 7 Lectures
No ratings yet
Algorithm Up To 7 Lectures
13 pages
Time Complexity - Class Lecture
No ratings yet
Time Complexity - Class Lecture
10 pages
Complexity of Algorithms
No ratings yet
Complexity of Algorithms
26 pages
1 Algorithm
No ratings yet
1 Algorithm
46 pages
Comparison of Algorithms: Modified From Clifford A. Shaffer and George Bebis
No ratings yet
Comparison of Algorithms: Modified From Clifford A. Shaffer and George Bebis
52 pages
Ehb208e 4
No ratings yet
Ehb208e 4
41 pages
Module 1 ADA
No ratings yet
Module 1 ADA
35 pages
Algorithm Efficiency Measuring The Efficiency of Algorithms
No ratings yet
Algorithm Efficiency Measuring The Efficiency of Algorithms
3 pages
33 تحليل
No ratings yet
33 تحليل
33 pages
Advanced Programming Techniques
No ratings yet
Advanced Programming Techniques
25 pages
2 Algorithm Analysis and Time Complexity
No ratings yet
2 Algorithm Analysis and Time Complexity
23 pages
Ada 1
No ratings yet
Ada 1
62 pages
1 Analysis of Algorithm
No ratings yet
1 Analysis of Algorithm
22 pages
Analysis of Algorithm
No ratings yet
Analysis of Algorithm
51 pages
DESIGN ALGORITHMS TO SOLVE COMMON PROBLEMS: Mastering Algorithm Design for Practical Solutions (2024 Guide)
From Everand
DESIGN ALGORITHMS TO SOLVE COMMON PROBLEMS: Mastering Algorithm Design for Practical Solutions (2024 Guide)
ARCHER PAUL
No ratings yet
Python Advanced Programming: The Guide to Learn Python Programming. Reference with Exercises and Samples About Dynamical Programming, Multithreading, Multiprocessing, Debugging, Testing and More
From Everand
Python Advanced Programming: The Guide to Learn Python Programming. Reference with Exercises and Samples About Dynamical Programming, Multithreading, Multiprocessing, Debugging, Testing and More
Marcus Richards
No ratings yet
Neural Networks: Neural Networks Tools and Techniques for Beginners
From Everand
Neural Networks: Neural Networks Tools and Techniques for Beginners
John Slavio
5/5 (10)
C++ Learn in 24 Hours
From Everand
C++ Learn in 24 Hours
Alex Nordeen
No ratings yet
Mediveal India A - 20250331 - 212751 - 0000
No ratings yet
Mediveal India A - 20250331 - 212751 - 0000
52 pages
Medieval History Notes
No ratings yet
Medieval History Notes
28 pages
Modern History 3 - 20250331 - 213331 - 0000
No ratings yet
Modern History 3 - 20250331 - 213331 - 0000
56 pages
Modern History 1 - 20250331 - 213146 - 0000
No ratings yet
Modern History 1 - 20250331 - 213146 - 0000
81 pages
Sports Section Complete
No ratings yet
Sports Section Complete
112 pages
History Notes Complete
No ratings yet
History Notes Complete
265 pages
Science & Technology
No ratings yet
Science & Technology
42 pages
Ecology & Environment
No ratings yet
Ecology & Environment
61 pages
Culture Compressed
No ratings yet
Culture Compressed
70 pages
Afcat Defence Notes
No ratings yet
Afcat Defence Notes
165 pages
PYQ Sem 5
No ratings yet
PYQ Sem 5
32 pages
TEG Water Equilibrium
100% (1)
TEG Water Equilibrium
9 pages
Rugh W.J. Linear System Theory (2ed., PH 1995) (ISBN 0134412052) (T) (596s) PDF
0% (1)
Rugh W.J. Linear System Theory (2ed., PH 1995) (ISBN 0134412052) (T) (596s) PDF
596 pages
International Journal of Pharmaceutics
No ratings yet
International Journal of Pharmaceutics
12 pages
Data Analytics Hands-On Using MS Excel
No ratings yet
Data Analytics Hands-On Using MS Excel
48 pages
Endianness and ARM Processors
No ratings yet
Endianness and ARM Processors
6 pages
Lego Education Wedo 2.0 Computational Thinking
No ratings yet
Lego Education Wedo 2.0 Computational Thinking
42 pages
Neutron
No ratings yet
Neutron
1,164 pages
1265 Full
No ratings yet
1265 Full
8 pages
Bankers 2
No ratings yet
Bankers 2
2 pages
SHRP P 394 PDF
No ratings yet
SHRP P 394 PDF
219 pages
Module-4 Lecture-1 Measurement of Straightness, Flatness and Squareness (Refer Slide Time: 00:13)
No ratings yet
Module-4 Lecture-1 Measurement of Straightness, Flatness and Squareness (Refer Slide Time: 00:13)
22 pages
Infrared Plastic Solar Cell
No ratings yet
Infrared Plastic Solar Cell
19 pages
840 D ProtectionLevel Concept
No ratings yet
840 D ProtectionLevel Concept
8 pages
Albert Einstein's Biography: Name: Angela Putri Class: X MIPA 5
No ratings yet
Albert Einstein's Biography: Name: Angela Putri Class: X MIPA 5
2 pages
SD Questions About Pricing Condition
100% (1)
SD Questions About Pricing Condition
9 pages
Excel-Exercise-3 - Ver 2024
No ratings yet
Excel-Exercise-3 - Ver 2024
4 pages
Unit 2
No ratings yet
Unit 2
21 pages
Wood Species Identification Using Convolutional Neural Network (CNN) Architectures On Macroscopic Images
No ratings yet
Wood Species Identification Using Convolutional Neural Network (CNN) Architectures On Macroscopic Images
11 pages
Class 11 Syllabus 23 24
No ratings yet
Class 11 Syllabus 23 24
10 pages
Handbook of Instrumentation PDF
100% (1)
Handbook of Instrumentation PDF
354 pages
(Week 1) : TOPIC TITLE: Introduction: Fraction, Decimal, and
No ratings yet
(Week 1) : TOPIC TITLE: Introduction: Fraction, Decimal, and
10 pages
Classes in C#
No ratings yet
Classes in C#
20 pages
Quarter 1 Week 1 Grade 2 Daily Lesson Log in Math
No ratings yet
Quarter 1 Week 1 Grade 2 Daily Lesson Log in Math
4 pages
Stachowiak - 1998 - Numerical Characterization of Wear Particles Morphology and Angularity of Particles and Surfaces
No ratings yet
Stachowiak - 1998 - Numerical Characterization of Wear Particles Morphology and Angularity of Particles and Surfaces
19 pages
3KC ATC6300 and 6500 Transfer Control Device - Product Overview
No ratings yet
3KC ATC6300 and 6500 Transfer Control Device - Product Overview
38 pages
D430 Advanced
No ratings yet
D430 Advanced
128 pages
WST01 01 Que 20220113
No ratings yet
WST01 01 Que 20220113
28 pages