## Page 1

1 1

INTRODUCTION TO ALGORITHM

Unit Structure:

1.1 Objectives

1.2 Introduction to Algorithm

1.3 Why to analysis algorithm

1.4 Running time analysis

1.5 How to Compare Algorithms

1.6 Rate of Growth

1.7 Commonly Used Rates of Growth

1.8 Types of Analysis

1.9 Asymptotic Notation

1. Big-O Not ation

2. Omega -Ω Notation

3. Theta -Θ Notation

1.10 Properties of Notations

1.11 Summary

1.12 Questions

1.13 Reference for further reading

1.1 OBJECTIVE

After going through this unit, you will be able to:

Understand the fundamental concepts of algorithm design and why

algorithm analysis is necessary. How to Compare Algorithms, Rates of

Growth and Their Varieties, Analysis Types, and Asymptotic Notation

1.2 INTRODUCTION TO ALGORITHM

A well -defined computing technique that accepts a value or set of values

as input and outputs a value or set of values is referred to informally as an

algorithm. As a result, an algorithm is a series of computations that

converts an input into an output. A tool for resolving a well -defined

computational problem is another way to look at an algorithm. The

require d input/output connection is briefly described in the issue munotes.in

## Page 2

Fundamental of

Algorit hms

2 statement. In order to achieve that input/output connection, the algorithm

specifies a particular computing method. For instance, it can be necessary

to organise a list of integers in non -decreasi ng order. Numerous common

design strategies and analytical tools may be included into this challenge

because it regularly occurs in real -world settings.

What Makes a Good Algorithm?

It is important to specify input and output clearly.

The algorithm's steps should all be distinct and understandable.

When compared to other possible solutions, algorithms should be the

most efficient.

There should be no computer code in an algorithm. It is preferable to

write the method in a way that it may be applied to severa l

programming languages.

Algorithms operate on the basis of input and output. They start with an

input of some value, follow the precise instructions, and end up with

an output.

Characteristics of an algorithm:

1. Input: External input should be given in a mounts of zero or more.

2. Output: Must generate at least one outcome.

3. Clearness: The actions to complete the task should be explicit and clear.

4. Finiteness: Must come to an end after a set number of steps.

5. Effectiveness: Must yield the intended ou tcome.

Example 1

Algorithm for adding two integers the user providedentered by the user.

Step 1: Start

Step 2: Declare three variables n1, n2 and res.

Step 3: Read the value of variables n1 and n2.

Step 4: Add the value of variablesn1 and n2 and assign t he result to res.

res=n1+n2

Step 5: Display res

Step 6: Stop

munotes.in

## Page 3

Introduction to

Algorithm

3 Example 2

Algorithm for subtraction two integers the user provided.

Step 1: Start

Step 2: Declare three variables n1, n2 and res.

Step 3: Read the value of variables n1 and n2.

Step 4: Subtra ct the value of variables n1 and n2 and assign the result to

res.

res=n1 -n2

Step 5: Display res

Step 6: Stop

Example 3

Algorithm for calculating factorial of an integer the user provided.

Step 1: Start

Step 2: Declare two variables n andfact.

Step 3: Rea d the value of variable n.

Step 4: Variable fact is set as 1

Step 5: fact <= fact * n

Step 6: Decrease n

Step 7: Verify if n is equal to 0

Step 8: If n is equal to zero, goto step 10 (break out of loop)

Step 9: Else goto step 5

Step 10: Display fact

Examp le 4

Algorithm for calculating square of a number the user provided.

Step 1: Start

Step 2: Declare two variables n and res.

Step 3: Read the value of variable n.

Step 4 : res=n*n

Step 5: Display res

Step 6: Stop munotes.in

## Page 4

Fundamental of

Algorit hms

4 1.3 WHY TO ANALYSIS ALGORITHM

An essential component of computational complexity theory is algorithm

analysis, which offers a theoretical estimate of the resources needed by an

algorithm to solve a particular computing issue. Calculating how much

time and space are needed to execute an algorithm i s called algorithm

analysis. As a result, the analysis can only be considered approximate. In

addition, by examining many algorithms, we may contrast them and

choose the most effective one for our needs. The technique of determining

an algorithm's computat ional complexity is known as algorithm analysis.

The time, space, and any other resources required to execute (run) the

algorithm are all referred to as the method's computational complexity.

Comparing several algorithms that are applied to the same issue is the aim

of algorithm analysis. This is performed to measure which approach uses

less memory and resolves a certain problem more rapidly.

Algorithm Analysis Types:

1. Best case

2. Worst case

3. Average case

Best case : Best case: Specify the input for the method that requires the

minimum amount of time. Calculate an algorithm's lower bound in the

best case scenario. The lower bound on the algorithm's running time for

every given input is provided by the best case analysis of algorithms.

Simply stated, it says that every software will require at least (more than

or equal to) that amount of time to do its task.

Example -The perfect scenario occurs in a linear search when the search

data is present at the initial place of large data.

Worst Case : Specify the input for the algorithm to use if you want it to run

quickly. Calculate an algorithm's upper bound as worst case scenario. The

upper bound on the algorithm's running time for any given input is

provided by the worst -case analysis of algorithms. In other words, it sa ys

that any programme will run in a maximum amount of time (less than or

equal to).

Example -The worst case scenario happens in a linear search when there is

no search data at all.

Average case : Consider all random inputs and figure out how long it will

take to process each one on average. The total inputs are then divided by

this number. The average case analysis of algorithms, as the name implies,

adds up the running times on all potential inputs before taking the average.

Therefore, in this instance, the algorithm's execution time serves as both

the lower and upper bounds. In other words, we can determine the

algorithm's typical running time through it. munotes.in

## Page 5

Introduction to

Algorithm

5 Example:

Find the ace of spades from a deck of 52 cards.

One card at a time is flipped until an ace of spades is revealed.

Best case scenario : Everything goes as smoothly as it possibly can, we

complete the task speedily, and we call it a day.

You turned over an ace of spades as your opening card.

Worst case scenario : Everything is getting completely out o f control, so

you must put in the most effort to complete your mission.

The final card you flipped was an ace of spades.

Average case scenario : Neither very poorly nor really well, things go.

The ace of spades is not the first or last card that you see.

1.4 RUNNING TIME ANALYSIS

When algorithms are analysed, their computational complexity —the

amount of time, storage, and/or other resources required to run them —is

determined. To put it simply, to gauge how effective a particular algorithm

is.

In order to con duct performance study, we typically applied to calculate

and evaluate the worst -case theoretical running times complexity of

algorithms.

O(1), also known as Constant Running Time, is the quickest possible

running time for any algorithm. In this example, the algorithm runs at the

same speed regardless of the size of the input. An algorithm should have

this runtime, although it's rarely possible.

In fact, the quantity of the input or amount of operations needed for every

entry element, or n, determines an a lgorithm's runtime (performance).

According to running time complexity, the algorithms can be categorised

as follows in order of best to worst performance where c is a positive

constant and n is the size of the input:

Algorithm category Explanation

logari thmic

O(logn) Running time increases in logarithmic proportion

to n.

linear

O(n) Running time increases directly in proportion to n.

superlinear

O(nlogn) Running time increases in proportion to n. munotes.in

## Page 6

Fundamental of

Algorit hms

6

Polynomial

O(nc) Running time increases faster than p revious

iterations based on n.

exponential

O(cn) Running time becomes even faster than using the

polynomial approach based on n.

factorial

O(n!) Running time increases the fastest and quickly

becomes unsuitable for even tiny values of n.

1.5 HOW TO COM PARE ALGORITHMS

In order to analyse the algorithm, we need to know two fundamental

parameters:

Space Complexity: The amount of space needed for an algorithm to

operate completely might be thought of as the space complexity.

An algorithm's space complexity is a measure of how much memory it

uses over its existence.

An algorithm's space requirements are equal to the sum of the two factors

listed below.

1. A fixed component is a place needed to hold constants, simple

variables, programme sizes, and other variable s that are independent of

the size of the problem.

2. A variable component is the area needed by variables, whose size is

completely based on the scope of the issue. Stack space for recursions,

dynamic memory allocation, etc.

Any algorithm's S(p) space comple xity is defined as S(p) = A + Sp (I)

Where S(I), which depends on instance characteristic I, is viewed as the

variable component of the algorithm while A is treated as the fixed part of

the algorithm.

Time Complexity: Time complexity, which measures how lo ng an

algorithm takes to run completely, is a function of input size n.

The measure of how long an algorithm will take to complete execution is

called the time complexity of the algorithm. Given that each step requires

a fixed amount of time, time requirem ents can be expressed or defined as a

numerical function t(N), where t(N) can be expressed as the number of

steps.

For instance, N steps are required to add two n -bit integers. As a result, the

total calculation time is given by t(N) = c*n, where c is the amount of time

needed to add two bits. Here, we observe that as input size increases, t(N)

climbs linearly..

munotes.in

## Page 7

Introduction to

Algorithm

7 1.6 RATE OF GROWTH

An algorithm's growth rate is the rate at which the cost of the algorithm

increases as the size of its input increases. The ter m "Rate of Growth"

describes how quickly running time grows in response to input.

Let's say you visited a store to purchase a car and a bicycle. If a friend sees

you there and inquires about your purchase, we typically reply that you are

purchasing a car. Because the price of a car is excessively high compared

to the price of a bicycle (approximating the cost of cycle to the cost of a

car).

Overall Cost = Car Cost + Bicycle Cost

Overall Cost ≈ Car Cost (approximation)

For the abovementioned example, we can describe the cost of the car and

the cost of the bike in terms of function, ignoring the low order variables

that are generally irrelevant (for large values of input size, n).

As an example in the below case, n3, 2n2 and 10n are the individual costs

of so me function and approximate it to n3. Since, n3 is the highest rate of

growth.

n3 + 2n2 + 10n ≈ n3

Understanding growth rates is the key to algorithm analysis. How much

more resources will my algorithm need as the volume of data increases, in

other words? Usually, we use a function to express the rate of resource

expansion of a piece of code . This section will look at graphs for various

growth rates, ranging from the most efficient to the least efficient, to assist

comprehend the implications.

Constant Growth Rate

Where the requirement for resources does not increase, it is said to be

constan t. To put it another way, processing 1 piece of data uses the same

resources as processing 1 million pieces of data. A horizontal line appears

on the graph with such a growth rate.

Logarithmic Growth Rate

When the data is doubled, the resource requirements increase by one unit,

which is known as a logarithmic growth rate. This basically indicates that

the growth rate's curve flattens as big data increases (closer to horizontal

but never reaching it). What a curve of this kind would look like is

depicted in the following graph.

Linear Growth Rate

A growth rate that is linear is one in which the demand for resources and

the volume of data are precisely proportionate to one another. That is, the

growth rate can be represented by a straight, non -horizontal line. munotes.in

## Page 8

Fundamental of

Algorit hms

8 Log Linear

A line with a small curve represents a log linear growth rate. Lower

numbers have a more prominent curve than higher ones.

Quadratic Growth Rate

One who can describe a parabola as having a quadratic growth rate.

Cubic Growth Rate

Although this may resemble the quadratic curve very much, it develops

much more quickly.

Exponential Growth Rate

Each additional unit of data demands a doubling of resources, which is

known as an exponential growth rate. As you can see, the growth rate

initially appears to be flat before rapidly rising to almost vertical (keep in

mind that it cannot actually be vertical).

Following graph showing the rates of growth for six equations with n

input values

munotes.in

## Page 9

Introduction to

Algorithm

9

Source: https://opendsa -server.cs.vt.edu/OpenDSA/Books/ CS4104/html/_

images/plot.png

1.7 COMMONLY USED RATES OF GROWTH

Time

Complexity Name Example

1 Constant A linked list's first element being added.

log n Logarithmic In a sorted array, locating a specific

element.

n Linear Locating a specific element in an unsorted

array.

n log n Linear

Logarithmic Separating n things according to "Divide

and Conquer."

n2 Quadratic The graph's shortest route connecting any

two nodes

n3 Cubic Multiplication of a matrix.

2n Exponential The challenge with the Towers of Hanoi.

munotes.in

## Page 10

Fundamental of

Algorit hms

10 Examples

Sequential Statements

If our sentences contain fundamental operations like comparisons,

assignments, and variable reads. We can assume they take the same

amount of time O(1).

Example where we can calculate the square sum of two values.

n1 = a * a;

n2 = b * b;

res = n1 + n2;

Constant time is spent on each line O(1).

1.8 TYPES OF ANALYSIS

It is a method for illustrating limiting behaviour. The appro ach is

applicable to all fields of science. It can be used to evaluate how well an

algorithm performs on a significant amount of data.

When analysing algorithms in computer science, it is important to take

into account how well they function when used with very big input

datasets.

The fastest and slowest potential execution times for an algorithm are

expressed using asymptotic notation. These are also known as "best case"

and "worst case," respectively.

We calculate the complexity based on the input size in asymptotic

notations. These notations are essential because they allow us to assess the

complexity of the algorithms without increasing the cost of running them.

(Example in terms of n) " "

The simplest illustration is a function ƒ (n) = n2+3n, where the term 3n

becomes unimportant in comparison to n2 when n is very high. The

function " ƒ (n) is stated to be asymptotically equivalent to n2 as n → ∞ "

is expressed symbolically as " ƒ (n) ~ n2" here.

The significance of asymptotic notation

1. They provide st raightforward indicators of an algorithm's effectiveness.

2. They make it possible to compare the results of different algorithms.

1.9 ASYMPTOTIC NOTATION

1. Omega(Ω) Notation :

The formal notation for expressing the lowest bound of an algorithm's

executio n time is Ω (n). It assesses the worst -case time complexity or the munotes.in

## Page 11

Introduction to

Algorithm

11 fastest possible runtime for an algorithm. The best -case situation is

depicted in this asymptotic notation, which is the opposite of large o

notation. The lower bound of an algorithm's exec ution time is presented

formally in this manner. This indicates that this is the shortest amount of

time needed to execute an algorithm. It represents the speed at which an

algorithm can operate.

Assume that the most significant term in the function f(n), g(n), represents

the time complexity of an algorithm.

If f(n) >= C g(n) for all n >= n0, C > 0 and n0 >= 1.

Then we can represent f(n) as Ω(g(n)).

f(n) = Ω(g(n))

Example

The least amount of time needed to sort 1000 numbers is "10 seconds," if

we are sorting 1000 numbers. These 1000 numbers cannot be sorted in

less than 10 seconds using omega notation. Not 9 or 8 seconds, but 11 or

12 seconds is OK.

2. Big -o(O) Notation :

The formal notation for expressing an algorithm's running time upper

bound is the big -o O. The worst -case time complexity or the longest time

an algorithm might possibly take to finish is measure d. By indicating the

function's order of increase, this asymptotic notation measures an

algorithm's efficiency. It gives a function an upper bound, assuring that it

will never grow faster than that of the upper bound.

It measures the algorithm's worst -case complexity. Calculates the

execution time that took the most time. As a result, it provides a formal

means of expressing the maximum allowable execution time for an

algorithm.

Assume that the most significant term in the function f(n), g(n), represents

the time complexity of an algorithm.

If f(n) <= C g(n) for all n >= n 0, C > 0 and n 0>= 1.

Then we can represent f(n) as O(g(n)).

f(n) = O(g(n))

Example:

The maximum amount of time needed to sort 1000 numbers is "50 secs,"

if we are sorting 1000 numbers. The se 1000 numbers can be sorted in less

than 50 seconds using big -o notation. 48 or 46 seconds are acceptable but

51 or 52 seconds are not.

munotes.in

## Page 12

Fundamental of

Algorit hms

12 3. Theta(Θ) Notation :

In order to express precise asymptotic behaviour, the theta notation

bounds a functions from a bove and below. The execution time of a given

algorithm will, "on average," be the same for any given input. The typical

case scenario is depicted in this asymptotic notation. When solving a real -

world problem, an algorithm cannot perform worst or best. Th eta notation

(), which denotes the average scenario, shows how the temporal

complexity varies between the best case and worst situation. When the

value of the worst -case and best -case scenarios are equal, theta notation is

commonly utilized. It represents both the top and lower bounds of an

algorithm's running time.

Assume that the most significant term in the function f(n), g(n), represents

the time complexity of an algorithm.

If C1 g(n) <= f(n) <= C2 g(n) for all n >= n0, C1 > 0, C2 > 0 and n0 >= 1.

Then we can represent f(n) as Θ(g(n)).

f(n) = Θ(g(n))

Example:

Let's use the example of sorting 1000 numbers once more. The algorithm

takes 10 seconds the first time, 11 seconds the second time, and 7 seconds

the third time.

1.10 PROPERTIES OF NOTATIONS

Let f(n ) and g(n) be asymptotically positive functions. Properties of

asymptotic notations:

Transitivity:

f(n) = Θ(g(n)) and g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n)). Valid for O and

Ω as well.

Reflexivity:

f(n) = Θ(f(n)). Valid for O and Ω.

Symmetry:

f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n)).

Transpose symmetry:

f(n) = O(g(n)) if and only if g(n) = Ω(f(n)).

If f(n) is in O(kg(n)) for any constant k > 0,

then f(n) is in O(g(n)).

If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n)),

then (f1 + f2)(n) is in O(max(g 1(n)), (g1(n))).

If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n))

then f1(n) f2(n) is in O(g1(n) g1(n)). munotes.in

## Page 13

Introduction to

Algorithm

13 1.11 SUMMARY

An algorithm is a set of clear, step -by-step directions for solving a

particular issue.

We may choose the algorithm that uses the least amount of time and

space by performing an algorithm analysis.

The objective of an algorithm analysis is to evaluate different

algorithms, mostly in terms of running time but also in terms of other

elements.

The Best Case, Worst Case, and Average Case ar e used to evaluate an

algorithm's complexity.

Upper Bounding Function in Big -O Notation.

Lower Bounding Function in the Omega -Ω Notation.

Order Function in Theta - Θ Notation.

1.12 QUESTIONS

1. What are the essential properties of an algorithms? Explain.

2. Define algorithm. State its essential characteristics.

3. Write an algorithm for adding two integers the user provided.

4. Write an algorithm for calculating factorial of an integer the user

provided.

5. Explain why analysis of algorithm is important.

6. Explain the runni ng time of an algorithm.

7. Explain how to compare algorithms. Give example.

8. Explain the terms in Rate of growth.

9. Write a note on Upper and Lower bound of an algorithm.

10. Brief describe Big -O and Omega Ω in algorithm analysis.

1.13 REFERENCE FOR FURTHER READING

https://www.geeksforgeeks.org/method -of-guessing -and-confirming/

Analysis of algorith ms. (2022, November 15). In Wikipedia.

https://en.wikipedia.org/wiki/Analysis_of_algorithms

https://bou rnetocode.com/projects/AQA_A_Theory/pages/4 -3-

Algorithms.html

Data Structure and Algorithmic Thinking with Python, Narasimha

Karumanchi, Career Monk Publications, 2016.

Data Structures and Algorithms in Python, Michael T. Goodrich,

Roberto Tamassia, Micha el H. Goldwasser, 2016, Wiley.

Algorithms by Robert Sedgewick & Kevin Wayne. Addison -Wesley

Professional.

Python Algorithms: Mastering Basic Algorithms in the Python

Language, Magnus Lie Hetland.

munotes.in

## Page 14

14 2

MASTER THEOREM

Unit Structure :

2.1 Objectives

2.2 Commonly used Logarithms and Summations

2.2.1 Guidelines for Asymptotic Analysis

2.3 Performance characteristics of algorithms

2.4 Master Theorem for Divide and Conquer

2.5 Divide and Conquer Master Theorem: Problems & S olutions

2.6 Master Theorem for Subtract and Conquer Recurrences

2.7 Method of Guessing and Confirming

2.8 Summary

2.9 Questions

2.10 Reference for further reading

2.1 OBJECTIVE

After going through this unit, you will be able to understand:

Basic algorithm properties , Perf ormance characteristics of algorithms,

Master Theorem for Divide and Conquer Problems & Solutions, Master

Theorem for Subtract andConquer Recurrences, Method of Guessing and

Confirming.

2.2 COMMONLY USED LOGARITHMS AND

SUMMATIONS

Because of a number of adv antageous characteristics that made complex,

time-consuming calculations simpler, logarithms were quickly adopted by

scientists.

There are numerous uses for the common logarithm in science and

engineering, which is a logarithm to base 10 (b = 10).

A base e logarithm is known as a natural logarithm. Its simpler derivative

makes it useful in both mathematics and science.

The base -2 logarithm known as the binary logarithm is frequently

employed in computer science.

munotes.in

## Page 15

Master Theorem

15 2.2.1 Guidelines for Asymptotic Analysis

There are some rules to help us determine the running time of an

algorithm. I have described with an example using python code

1. Loops: The running time of a loop is, at most, the running time of the

statements inside the loop (including tests) multiplied by t he number

of iterations.

2. Nested loops: Analyse from the inside out. Total running time is the

product of the sizes of all the loops.

3. Consecutive statements: Add the time complexities of each statement.

4. If-then-else statements: Worst -case running time: t he test, plus either

the then part `the else part (whichever is the larger).

5. Logarithmic complexity: An algorithm is O(logn) if it takes a constant

time to cut the problem size by a fraction (usually by 1/2 ).

For any positive values of m, n, and r as we ll as any positive integers a and

b, logarithms have the following arithmetic properties.

Source:

https://d2vlcm61l7u1fs.cloudfront.ne t/media%2F53d%2F53d266b3 -56c1 -

4cea-99a5 -4eaf6ecae629%2FphpjB5pBJ.png

2.3 PERFORMANCE CHARACTERISTICS OF

ALGORITHMS

There are numerous routes we can take to get from city "A" to city "B."

We have the option of travelling by bicycle, bus, train, and aeropl ane. We

select the one that best suits us based on accessibility and convenience.

Similar to this, there are other algorithms available in computer science to

address an issue. When there are multiple algorithms available to address a

problem, the best sol ution must be chosen. We can choose the best munotes.in

## Page 16

Fundamental of

Algorithms

16 algorithm to solve a problem from a variety of algorithms with the use of

performance analysis.

When there are several potential solutions to a problem, we evaluate them

and choose the one that best meets our ne eds. The official explanation is

as follows:

Making an evaluation of an algorithm is the process of measuring its

performance.

The following definitions are also possible:

An algorithm's performance is measured by how well it can predict the

resources need ed to complete its goal.

This indicates that when there are several algorithms available to solve a

problem, we must choose the best algorithm to do so.

To select the best algorithm, we compare algorithms that are solving the

same problem. Algorithms are c ompared using a set of parameters or

elements, such as the amount of memory needed, how quickly the

algorithm runs, how simple it is to understand and apply, etc.

In general, the following factors affect how well an algorithm performs:

1. Does that algorit hm offer a precise solution to the issue?

2. Is it simple to understand?

3. How simple is it to put into practise?

4. How much memory (space) is needed to fix the issue?

5. How long does it take to resolve the issue? Etc.,

When analysing an algorithm, we s olely take into account the time and

space needed for that specific method, ignoring all other factors.

These details can also be used to define performance analysis of an

algorithm, which is calculating the amount of time and space an algorithm

needs to r un is the process of performing performance analysis on the

algorithm.

2.4 MASTER THEOREM FOR DIVIDE AND CONQUER

One of the various algorithm models is the Divide and Conquer strategy.

Essentially, it consists of three steps. −

Divide : In this stage, the problem is divided into a number of smaller,

related problems.

Conquer : Use recursive solutions to solve the sub problems.

Combine : the solutions to the individual problems to arrive at the

solution. munotes.in

## Page 17

Master Theorem

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

where n is the size of the problem

a = the number of sub problems in the recursion, where a >= 1

n/b = the size of each sub problem

f(n) = th e price of work performed in addition to recursive calls, such as

splitting a problem into smaller ones and the cost of combining those

smaller issues to obtain the answer.

2.5 MASTER THEOREM: PROBLEMS & SOLUTIONS

Example 1: Use Master's theorem to solve the recurrence relation shown

below -

T(n) = 3T(n/2) + n2

Solution:

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

Here

a = 3

b = 2

f(n) = n2

log ba = log 23= 1.58

means f(n) ba+ , where, is a constant.

Here, Case 3 suggests -

T(n) = f(n) = Θ(n2)

Example 2: Use Master's theo rem to solve the recurrence relation shown

below -

munotes.in

## Page 18

Fundamental of

Algorithms

18 T(n) = 8T(n/4) – n2logn

Solution:

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

Here

The provided recurrence relation does not match Master's theorem's

general form.

Therefore, the Master's theorem cannot be used to solve it.

Example 3: Use Master's theorem to solve the recurrence relation shown

below -

T(n)=2T(n/2)+n

Solution:

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

Here

a = 2

b = 2

f(n) = n2

log ba = log 22= 1

means f(n) = nlog

ba+ , where, is a constant.

Here, Case 2 suggests -

T(n) = f(n) = Θ(nlog

ba * log n)= Θ(n log n)

Example 4: Use Master's theorem to solve the recurrence relation shown

below -

T(n) = 3T (n/2)+n3

Solution: T(n) = 3T (n/2) + n3 => T (n) =( n3) (Master Theorem Case 3.a)

Solution:

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

Here

a = 3

b = 2

f(n) = n2 munotes.in

## Page 19

Master Theorem

19 log ba = log 23= 1.58

means f(n) = nlog

ba+ , where, is a constant.

Here, Case 3 suggests -

T(n) = f(n) = Θ(n3)

Example 5: Use Master's theorem to solve the recurrence relation shown

below-

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

Solution: T(n) = 4T (n/2) + n² => T (n) = O(nlogn) (Master Theorem Case

2.a)

Solution:

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

Here

a = 4

b = 2

f(n) = n2

log ba = log 24= 2

means f(n) = nlog

ba+ , where, is a constant.

Here, Case 2 suggests -

T(n) = f( n) = Θ(nlog

ba * log n)= Θ(n log n)

Example 6 : Use Master's theorem to solve the recurrence relation shown

below -

T(n)=2nT(n/2)+nn

Solution:

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

Here

The provided recurrence relation does not match Master's theorem's

general form.

Therefo re, the Master's theorem cannot be used to solve it.

munotes.in

## Page 20

Fundamental of

Algorithms

20

Source: https://dotnettutorials.net/lesson/master -theorem/

Source: https://dotnettutorials.net/lesson/master -theorem/

munotes.in

## Page 21

Master Theorem

21 2.6 MASTER THEOREM FOR SUBTRACT AND

CONQUER RECURRENCES

Master theorem is used to determine the Big – O upper bound on functions

which possess recurrence, i.e which can be broken into sub problems.

Let T (n) be a function defined on positive n as shown below:

for some constants c, a>0, b>0, k>=0 and function f(n). If f(n) is O(nk),

then

1. If a<1 then T(n) = O(nk)

2. If a=1 then T(n) = O(nk+1)

3. if a>1 then T(n) = O(nkan/b)

Example 1: Use Master's t heorem for Subtract and Conquer Recurrences

to solve the below -

T(n) = 3T(n -1) when a>0

=1 otherwise

Solution:

Here

a=3

b=1

d=0

Hence T(n) = O(n03n/1)

Here, Case 2 suggests - (a>1)

Therefore T(n)=O(3n). munotes.in

## Page 22

Fundamental of

Algorithms

22 Example 2: Use Mas ter's theorem for Subtract and Conquer Recurrences

to solve the below -

T(n) = 5T(n -3)+O(n2) when n>0

=1 otherwise

Solution:

Here

a=5

b=3

d=2

Hence T(n) = O(n25n/3)

Here, Case 2 suggests - (a>1)

Therefore T(n)= O(n25 n/3)

2.7 METHOD OF GUESSING AND CONFIRMING

This approach's fundamental premise is to make a well -informed

prediction and then use induction to confirm that it is true. Any recurrence

can be resolved using this technique. In general, either the proof will w ork

(in which case we are finished) or the proof will fail if a solution is

guessed and then we attempt to check our guess inductively (in that case

the failure will help us refine our guess).

Consider the recurrence T(N) = N*T(N) + N, for instance. The fo rmat

demanded by the Master Theorems is not met by this. A careful

examination of the recurrence gives us the idea that it is equivalent to the

divide and conquer strategy, which involves breaking the problem into N

subproblems, each of size N. As can be s een, the first level of recursion's

subproblems are N bytes in size. Therefore, let's assume that T(N) =

O(N*log N) and then attempt to support our assumption. Let’s start by

trying to prove an upper bound:

T(N) \le cN*logN:

T(N) = √N*T(√N) + N

T(N) \le √N* c√N*log√N + N

T(N) = N* clog √N + N

T(N) = N*1/2*c*log N + N

T(N) \le cN*log N munotes.in

## Page 23

Master Theorem

23 Only that 1 le 1/2*clog N is assumed in the final inequality. If N is large

enough and c is constant, regardless of how little it is, this is true.

We can see from the previous proof that we were right about the upper

bound. Let's now establish the bottom bound for its occurrence:

T(N) = √N*T(√N) + N

T(N) \ge √N* k√N*log√N + N

T(N) = N* klog √N + N

T(N) = N*1/2*k*log N + N

T(N) \ge N*k*log N

The final inequality just makes the assumption that 1 ge 1/2*k*log N. If N

is large enough and for any constant k, this is false.

We can see from the previous proof that our assumption regarding the

lower bound is unreliable.

It is clear from the reasoning above that (N*log N) is an excessiv ely large

number. How about Θ (N) instead? The direct proof of the lower bound is

simple:

T(N) = √N*T(√N) + N \ge N

Now, let us prove the upper bound for this Θ(N):

T(N) = √N*T(√N) + N \\ \le √N*c√N + N \\ = N c+ N \\ = N (c + 1) \\

\nleqcN

It is clear from t he previous induction that Θ(N) is too small and Θ(N*log

N)(N*log N) is too large. So what do we need that is greater than N and

less than N*log N? Consider N* √log N.

Proving upper bound for N* √log N:

T(N) = √N*T(√N) + N

T(N) \le √n*c√N*√(log √N) + N

T(N) = N* 1/ √2 *c*log √N + N

T(N) \le N*c*log √N

Proving lower bound for N* √log N:

T(N) = √N*T(√N) + N

T(N) \ge √N*k√N*√(log√N) + N

T(N) = N*1/ √2*k*log √N + N

T(N) \ngeq N*k*log √N munotes.in

## Page 24

Fundamental of

Algorithms

24 The last step doesn’t work. So, Θ(N*√log N) doesn’t work. What else is

between N and N*log N? How about N*log(log N)?

Proving upper bound for N*log(log N):

T(N) = √N*T(√N) + N

T(N) \le √N*c√N*log(log √N) + N

T(N) = N*clog(log N) - cN + N

T(N) \le N*clog(log N), if \ c\ge 1

Proving lower bound for N*log(log N):

T(N) = √N*T(√N) + N

T(N) \ge √N*k√N*log(log √N) + N

T(N) = N*k*log(log N) - kN + N

T(N) \ge N*klog(log N), if \ k \le 1

From the above proofs, it can see that T(N) \le N*clog(log N), if \ c \ge 1

and T(N) \ge N*klog(log N), if \ k \le 1.

2.8 SUMMARY

There are numerous uses for the common logarithm in science and

engineering

An algorithm's performance is measured by how well it can predict the

resources needed to complete its goal.

When analysing an algorithm, we solely take into account the time and

space needed for t hat specific method, ignoring all other factors.

The master theorem is used in calculating the time complexity of

recurrence relations (divide and conquer algorithms) in a simple and

quick way.

Master theorem is used to determine the Big – O upper bound on

functions which possess recurrence, i.e which can be broken into sub

problems.

The basic idea behind this method is to guess the answer, and then

prove it correct by induction. This method can be used to solve any

recurrence.

munotes.in

## Page 25

Master Theorem

25 2.9 QUESTIONS

1. Use Maste r's theorem to solve the below:

a. T (n) = 4T(n/2) + n

b. T (n) = 2T(n/2) + log n

c. T (n) = 4T(n/ 2) + n log n (log 24=2)

d. T(n) = 3T(n/3) + n log n

e. T (n) = 4T(n/4) + n

f. T (n) = T(n/2) + 1

g. T (n) = 2T(n/2) + n2

2. What is commonly used Logarithms and Summations.

3. Write a note on Master Theorem. Give an example.

4. Write a note on Master Theorem for Subtract and Conquer

Recurrences

5. Write a note on method of guessing and conforming.

6. Write a note on Master Theorem for Divide and Conquer.

7. Explain Guidelines for Asymptotic Analys is.

8. Which factors affect how well an algorithm performs?

9. Write a note on Performance characteristics of algorithms.

2.10 REFERENCE FOR FURTHER READING

https://www.geeksforgeek s.org/method -of-guessing -and-confirming/

Analysis of algorithms. (2022, November 15). In Wikipedia .

https://en.wikipedia.org/wiki/Analysis_of_algorithms

https://bournetocode.com/projects/AQA_A_Theory/pages/4 -3-

Algorithms.html

Data Structure and Algorithmic Thinking with Python,

NarasimhaKarumanchi ,CareerMonk Publications, 2016.

Data Structures and Al gorithms in Python, Michael T. Goodrich,

Roberto Tamassia, Michael H. Goldwasser, 2016, Wiley.

Algorithms by Robert Sedgewick & Kevin Wayne. Addison -Wesley

Professional.

Python Algorithms: Mastering Basic Algorithms in the Python

Language, Magnus Lie Het land.

munotes.in

## Page 26

26 3

TREE ALGORITHMS

Unit Structure

3.0 Objectives

3.1 Introduction

3.2 An Overview

3.2.1 What is a tree?

3.2.2 Terminology of TREE?

3.2.3 Characteristics of a Trees?

3.2.4 Advantages o f BST

3.2.5 Types of tree?

3.3 Arithematic Tree

3.3.1 Expression Binary Tree

3.3.2 Arithematic VS Expression Bina ry Tree?

3.3.3 Design of Tree?

3.3.4 Representation of tree

3.3.5 Representation of link list

3.3.6 singly vs doubly link li st

3.4 Balanced Tree

3.4.1 From programmers point of view

3.4.2 From users point of view

3.5 What is Binary Se arch Tree?

3.5.1 What is BST?

3.5.2 What does balanced binary tree ?

3.5.3 what is AVL tree?

3.6 Let us Sum Up

3.7 List of References

3.8 Unit End Exercise

munotes.in

## Page 27

Tree Algorithms

27 3.0 OBJECTIVES

What is the objective of algorithm s?

1. Algorithms define how a particular task is to be performed . They

provide computers with instructions. They tell machines on assembly

lines how specific parts should be put together. Or they evaluate

application forms and recommend the best candidates.

2. Provides a hierarchical way of storing data . Reflects structural

relationship in a data set. Allows insertion, deletion and searching

operations that yield results faster t han an array or linked list. Provides

a flexible way to hold and move data.

3. Hierarchi cal Structure: Trees are used to model hierarchical structures,

such as the file system in a computer or the organizational chart in a

company. The tree structure allows f or a natural representation of

parent -child relationships, making it easy to understa nd and

visualize the data .

3.1 INTRODUCTION

A tree is a non -linear abstract data type with a hierarchy -based structure. It

consists of nodes (where th e data is stored) that are connected via links.

The tree data structure stems from a single node called a root node and has

subtrees connected to the root.

Important Terms

Following are the important terms with respect to tree.

Path − Path refers to the sequence of nodes along the edges of a tree.

Root − The node at the top of the tree is called root. There is only one

root per tree and one path frocm the root node to any node. munotes.in

## Page 28

Fundamental of

Algorithms

28 Parent − Any node except the root node has one edge upwa rd to a

node called parent.

Child − The node below a given node connected by its edge

downward is called its child node.

Leaf − The node which does not have any child node is called the leaf

node.

Subtree − Subtree represents the descendants of a node.

Visiting − Visiting refers to checking the value of a node when control

is on the node.

Traversing − Traversing means passing through nodes in a specific

order.

Levels − Level of a node represents the generation of a node. If the

root node is at level 0, then its next child node is at level 1, its

grandchild is at level 2, and so on.

Keys − Key represents a value of a node based on which a search

operation is to be carried out for a node.

Types of Trees

There are three types of trees −

General Trees

Binary Tre es

Binary Search Trees

General Trees

General trees are unordered tree data structures where the root node has

minimum 0 or maximum ‘n’ subtrees.

The General trees have no constraint placed on their hierarchy. The root

node thus acts like the superset of al l the other subtrees.

munotes.in

## Page 29

Tree Algorithms

29 Binary Trees

Binary Trees are general trees in which the root node can only hold up to

maximum 2 subtrees: left subtree and right subtree. Based on the number

of children, binary trees are divided into three types.

Full Binary Tree

A full binary tree is a binary tree type where every node has either 0 or

2 child nodes.

Complete Binary Tree

A complete binary tree is a binary tree type where all the leaf nodes

must be on the same level. However, root and internal nodes in a

complete bi nary tree can either have 0, 1 or 2 child nodes.

Perfect Binary Tree

A perfect binary tree is a binary tree type where all the leaf nodes are

on the same level and every node except leaf nodes have 2 children.

Binary Search Trees

Binary Search Tre es possess all the properties of Binary Trees including

some extra properties of their own, based on some constraints, making

them more efficient than binary trees.

The data in the Binary Search Trees (BST) is always stored in such a way

that the values in the left subtree are always less than the values in the root

node and the values in the right subtree are always greater than the values

in the root node, i.e. left subtree < root node ≤ right subtree.

munotes.in

## Page 30

Fundamental of

Algorithms

30

Advantages of BST

Binary Search Trees are more efficient than Binary Trees since time

complexity for performing variou s operations reduces.

Since the order of keys is based on just the parent node, searching

operation becomes simpler.

The alignment of BST also favors Range Queries, which are executed

to find values existing between two keys. This helps in the Database

Management System.

Disadvantages of BST

The main disadvantage of Binary Search Trees is that if all elements in

nodes are either greater than or lesser than the root node, the tree

becomes skewed . Simply put, the tree becomes slanted to one side

completely.

This skewness will make the tree a linked list rather than a BST, since the

worst case time complexity for searching operation becomes O(n).

To overcome this issue of skewness in the Binary Search Trees, the

concept of Balanced Binary Search Trees was intro duced.

Balanced Binary Search Trees

Consider a Binary Search Tree with ‘m’ as the height of the left subtree

and ‘n’ as the height of the right subtree. If the value of (m -n) is equal to

0,1 or -1, the tree is said to be a Balanced Binary Search Tree .

The trees are designed in a way that they self -balance once the height

difference exceeds 3. Binary Search Trees use rotations as self -balancing

algorithms. There are four different types of rotations: Left Left, Right

Right, Left Right, Right Left.

munotes.in

## Page 31

Tree Algorithms

31 There are various types of self -balancing binary search trees −

AVL Trees

Red Black Trees

B Trees

B+ Trees

Splay Trees

Priority Search Trees

WHAT IS TREE?

Trees: Non-Linear data structure

A data structure is said to be linear if its elements form a sequence or a

linear list. Previous

linear data structures that we have studied like an array, stacks, queues and

linked lists organize data in linear order. A data structure is said to be non

linear if its elements form a hierarchical classification where, data items

appear at various levels.

Trees and Graphs are widely used non -linear data structures. Tree and

graph structures represent hierarchical relationship between individual

data elements. Graphs are nothing but trees with certain restrictions

removed.

Trees repre sent a special case of more general structures known as graphs.

In a graph, there is no restrictions on the number of links that can enter or

leave a node, and cycles may be present in the graph. The figure 5.3.1

shows a tree and a non-tree.

Tree is a pop ular data structure used in wide range of applications. A tree

data structure can be defined as follows...

Tree is a non-linear data structure which organizes data in hierarchical

structure and this is a recursive definition.

A tree data structure can also be defined as follows... A tree is a finite set of

one or more nodes such that:There is a specially designated node called

the root. The remaining nodes are partitioned into n>=0 disjoint sets T1, ...,

munotes.in

## Page 32

Fundamental of

Algorithms

32 Tn, where each of these sets is a tree. We call T1, . .., Tn are the subtrees of

the root.

A tree is hierarchical collection of nodes. One of the nodes, known as the

root, is at the top of the hierarchy. Each node can have at most one link

coming into it. The node where the link originates is called the par ent

node. The root node has no parent. The links leaving a node (any number

of links are allowed) point to child nodes. Trees are recursive structures.

Each child node is itself the root of a subtree. At the bottom of the tree are

leaf nodes, which have no children.

Advantages of trees

Trees are so useful and frequently used, because they have some very

serious advantages:

Trees reflect structural relationships in the data

Trees are used to represent hierarchies

Trees provide an efficient insertion and sear ching

Trees are very flexible data, allowing to move sub trees around with

minimum effort

3.2 AN OVERVIEW

In a Tree, Every individual element is called as Node. Node in a tree data

structure, stores the actual data of that particular element and link to next

element in hierarchical structure. Example

munotes.in

## Page 33

Tree Algorithms

33

1. Root

In a tree data structure, the first node is called as Root Node. Every tree

must have root node. We can say that root node is the origin of tree data

structure. In any tree, there must be on ly one r oot node. We never have

multiple root nodes in a tree. In above tree, A is a Root node

2. Edge

In a tree data structure, the connecting link between any two nodes is

called as EDGE. In a tree with 'N' number of nodes there will be a

maximum of 'N -1' number of edges.

3. Parent

In a tree data structure, the node which is predecessor of any node is called

as PARENT NODE. In simple words, the node which has branch from it to

any other node is called as parent node. Parent node can also be defined as

"The node which has child / children". e.g., Parent (A,B,C,D).

4. Child

In a tree data structure, the node which is descendant of any node is called

as CHILD Node. In simple words, the node which has a link from its

parent node is called as child node. In a tree, any parent node can have any

number of child nodes. In a tree, all the nodes except root are child nodes.

e.g., Children of D are (H, I,J).

5. Siblings

In a tree data structure, nodes which belong to same Parent are called as

SIBLINGS. In simple words, the nodes with sam e parent are called as

Sibling nodes. Ex: Siblings (B,C, D)

6. Leaf

In a tree data structure, the node which does not have a child (or) node

with degree zero is called as LEAF Node. In simple words, a leaf is a node

with no child.In a tree data struct ure, the leaf nodes are also called as

External Nodes. External node is also a node with no child. In a tree, leaf

node is also called as 'Terminal' node. Ex: (K,L,F,G,M,I,J) munotes.in

## Page 34

Fundamental of

Algorithms

34 7. Internal Nodes

In a tree data structure, the node which has atleast one child is called a s

INTERNAL Node. In simple words, an internal node is a node with atleast

one child.

In a tree data structure, nodes other than leaf nodes are called as Internal

Nodes. The root node is also said to be Internal Node if the tree has more

than one no de. Inte rnal nodes are also called as 'Non -Terminal' nodes.

Ex:B,C,D,E,H

8. Degree

In a tree data structure, the total number of children of a node (or)number

of subtrees of a node is called as DEGREE of that Node. In simple words,

the Degree of a node is total numb er of children it has. The highest degree

of a node among all the nodes in a tree is called as 'Degree of Tree'

9. Level

In a tree data structure, the root node is said to be at Level 0 and the

children of root node are at Level 1 and the children of the nod es which

are at Level 1 will be at Level 2 and so on... In simple words, in a tree each

step from top to bottom is called as a Level and the Level count starts with

'0' and incremented by one at each level (Step). Some authors start root

level with 3.

10. Heig ht

In a tree data structure, the total number of edges from leaf node to a

particular node in the longest path is called as HEIGHT of that Node. In a

tree, height of the root node is said to be height of the tree. In a tree, height

of all leaf node s is '0' .

11. Depth

In a tree data structure, the total number of edges from root node to a

particular node is called as DEPTH of that Node. In a tree, the total

number of edges from root node to a leaf node in the

longest path is said to be Depth of the tree. In simp le words, the highest

depth of any leaf node in a tree is said to be depth of that tree. In a tree,

depth of the root node is '0'.

munotes.in

## Page 35

Tree Algorithms

35 12. Path

In a tree data structure, the sequence of Nodes and Edges from one node to

another node is called as PATH between that two Nodes. Length of a Path

is total number of nodes in that path. In below example the path A - B - E -

J has length 4.

13. Sub Tree

In a tree data structure, each child from a node forms a subtree recursively.

Every child node will form a subtree on its parent node.

Tree Representations

A tree data structure can be represented in two methods. Those methods

are as follows...

1.List Representation

2. Left Child - Right Sibling Representation Consider the following tree...

1. List Representation

In this representation, we use two types of nodes one for representing the

node with data and another for representing only references. We start with

a node with data from root node in the tree. Then it is linked to an internal

munotes.in

## Page 36

Fundamental of

Algorithms

36 node t hrough a reference node and is linked to any other node directly.

This process repeats for all the nodes in the tree.

The above tree example can be represented using List representation as

follows...

Fig: List representation of above Tree

Fig: Possible node structure for a tree of degree k

2. Left Child - Right Sibling Representation

In this representation, we use list with one type of node which consists of

three fields namely Data field, Left child reference field and Right sibling

reference field. Data field stores the actual value of a node, left reference

field stores the address of the left child and right reference field stores the

address of the right sibling node. Graphical representation of that node is

as follows...

In this representation, every node's data field stores the actual value of that

node. If that node has left child, then left reference field stores the address

of that left child node otherwise that field stores NULL. If that node has

right sibling then right reference field stores the addre ss of right sibling

node otherwise that field stores NULL.

The above tree example can be represented using Left Child - Right

Sibling representation as follows...

munotes.in

## Page 37

Tree Algorithms

37

Representation as a Degree –Two Tree

To obtain degree -two tree representation of a tree, r otate the right - sibling

pointers in the left child - right sibling tree clockwise by 45 degrees. In a

degree -two representation, the two children of anode are referred as left

and right children.

Binary Trees

Introduction

In a normal tree, every node can have any number of children. Binary tree

is a special type of tree data structure in which every node can have a

maximum of 2 children. One is known as left child and the other is known

as right child.

A tree in which every node can have a maximum of two c hildren is called

as Binary Tree.

In a binary tree, every node can have either 0 children or 1 child or 2

children but not more than 2 children. Example

munotes.in

## Page 38

Fundamental of

Algorithms

38 There are different types of binary trees and they are...Strictly Binary Tree

In a binary tree, every node can have a maximum of two children. But in

strictly binary tree, every node should have exactly two children or none.

That means every internal node must have exactly two children. A strictly

Binary Tree can be defined as follows...

A binary tree in w hich every node has either two or zero number of

children is called Strictly Binary Tree. Strictly binary tree is also called as

Full Binary Tree or Proper Binary Tree or 2-Tree

1. Complete Binary Tree

In a binary tree, every node can have a maximum o f two ch ildren. But in

strictly binary tree, every node should have exactly two children or none

and in complete binary tree all the nodes must have exactly two children

and at every level of complete binary tree there must be 2 level number of

nodes. For example at level 2 there must be 2^2 = 4 nodes and at level 3

there must be 2^3 = 8 nodes.

A binary tree in which every internal node has exactly two children and all

leaf nodes are at same level is called Complete Binary Tree.

Complete binary tree is also called as Perfect Binary Tree

2. Extended Binary Tree

A binary tree can be converted into Full Binary tree by adding dummy

nodes to existing nodes wherever required.

The full binary tree obtained by adding dummy nodes to a binary tree is

called as Extended Binary Tree.

Abstract Data Type Definition: A binary tree is a finite set of nodes

that is either empty or consists of a root and two disjoint binary trees

called left subtree and right subtree.

ADT contains specification for the binary tree ADT.

Structure Binary_ Tree (abbreviated BinTree) is objects: a finite set of

nodes either empty or consisting of a root node, left Binary_Tree, and

right Binary_Tree. Functions:

munotes.in

## Page 39

Tree Algorithms

39 For all bt, bt1, bt2 BinTree, item element Bintree Create()::= creates

an empty binary tree

Boolean IsEmpty(bt)::= if (bt==empty binary tree) return TRUE else

return FALSE

BinTree MakeBT(bt1, item, bt2)::= return a binary tree whose left subtree

is bt1, whose right subtree is bt2, and whose root no de contains the data

item

Bintree Lchild(bt)::= if (IsEmpty(bt)) return error else return the left

subtree of bt element Data(bt)::= if (IsEmpty(bt)) return error else return

the data in the root node of bt Bintree Rchild(bt)::= if (IsEmpty(bt)) re turn

error else return the right subtree of bt

We use linked list to represent a binary tree. In a linked list, every node

consists of three fields. First field, for storing left child address, second for

storing actual data and third for storing right child address. In this linked

list representation, a node has the following structure...

Type def struct node *tree_pointer; typedef struct node {

int data;

tree_pointer left_child, right_child;};

Binary Tree Traversals

When we wanted to display a binary tree, we need to follow some order in

which all the nodes of that binary tree must be displayed. In any binary tree

displaying order of nodes depends on the traversal method. Displaying

(or) visiting order of nodes in a binary tr ee is called as Binary Tree

Trave rsal.

munotes.in

## Page 40

Fundamental of

Algorithms

40 There are three types of binary tree traversals.

1) In - Order Traversal

2) Pre - Order Traversal

3) Post - Order Traversal

Binary Tree Traversals

• 3. In - Order Traversal ( leftChild - root - rightChild )

• I - D - J - B - F - A - G - K - C – H

• 2. Pre - Order Traversal ( root - leftChild - rightChild )

• A - B - D - I - J - F - C - G - K – H

• 3. Post - Order Traversal ( leftChild - rightChild - root )

• I - J - D - F - B - K - G - H - C – A

CHAPTER 5

In - Order Traversal ( left Child - root – right Child )

In In -Order traversal, the root node is visited between left child and right

child. In this traversal, the left child node is visited first, then the root node

is visited and later we go for visiting right child node. This in -order

traversal is applicable for eve ry root node of all subtrees in the tree. This is

performed recursively for all nodes in the tree.

In the above example of binary tree, first we try to visit left child of root

node 'A', but A's left child is a root node fo r left subtree. so we try to visi t

its (B's) left child 'D' and again D is a root for subtree with nodes D, I and

J. So we try to visit its left child 'I' and it is the left most child. So first

wevisit 'I'then go for its root node 'D' and later we visit D 's right child 'J'.

With this we have completed the left part of node B. Then visit 'B' and

next B's right child 'F' is visited. With this we have completed left part of

node A. Then visit root node 'A'. With this we have completed left and

root parts of n ode A. Then we go for right part of the node A. In right of A

again there is a subtree with root C. So go for left child of C and again it is

a subtree with root G. But G does not have left part so we visit 'G' and then

visit G's right child K. With this w e have completed the left part of node

C. Then visit root node'C' and next visit C's right child 'H' which is the

right most child in the tree so we stop the process.

That means here we have visited in the order of I - D - J - B - F - A - G - K

- C - H usi ng In -Order Traversal.

munotes.in

## Page 41

Tree Algorithms

41 In-Order Traversal for above example of binary tree is I - D - J - B - F - A -

G - K - C – H

Algorithm

Until all nodes are traversed −

Step 1 − Recursively traverse left subtree. Step 2 − Visit root node.

Step 3 − Recursively travers e right subtree.

void inorder(tre e_pointer ptr) /* inorder tree traversal */ Recursive

{

if (ptr) {

inorder(ptr ->left_child); printf(“%d”, ptr ->data); indorder(ptr -

>right_child);

}

}

1. Pre - Order Traversal ( root - leftChild - rightChild )

In Pre -Order trav ersal, the root node is visited b efore left child and right

child nodes. In this traversal, the root node is visited first, then its left

child and later its right child. This pre -order traversal is applicable for

every root node of all subtrees in the tree.

In the above example of binary tree, first we visit root node 'A' then visit

its left child 'B' which is a root for D and F. So we visit B's left child 'D'

and again D is a root for I and J. So we visit D's left child'I' which is the

left most child. So next we go for visiting D's righ t child 'J'. With this we

have completed root, left and right parts of node D and root, left parts of

node B. Next visit B's right child'F'. With this we have completed root and

left parts of node A. So we go for A's right child 'C' which is a root

node for G and H. After visiting C, we go for its left child 'G' which is a

root for node K. So next we visit left of G, but it does not have left child

so we go for G's right child 'K'. With this we have completed node C's root

and left parts. Next visit C's rig ht child 'H' which is the right most child

in the tree. So we stop the process. That means here we have visited

in the order of A-B-D-I-J-F-C-G-K-H using Pre-Order Traversal.

Algorithm

Until all nodes are travers ed − Step 1 − Visit root node.

Step 2 − Recursively traverse left subtree. Step 3 − Recursively traverse

right subtree.

void preorder(tree_pointer ptr) /* preorder tree traversal */ Recursive

{ munotes.in

## Page 42

Fundamental of

Algorithms

42 if (ptr) {

printf(“%d”, ptr ->data); preorder(ptr ->left_child); preorder(ptr -

>right_child);

}

}

2. Post - Order Traversal ( leftChild - rightChild - root )

In Post-Order traversal, the root node is visited after left child and right

child. In this traversal, left child node is visited first, then its right child and

then its root node. This is recursively performed until the right most node

is visited.

Here we have visited in the order of I - J - D - F - B - K - G - H - C - A

using Post -Order Traversal. Algorithm

Until all nodes are traversed −

Step 1 − Recursively traverse left subtree. Step 2 − Recursively traverse

right subtree. Step 3 − Visit root node.

void postorder(tree_pointer ptr) /* postorder tree traversal */

Recursive

{

if (ptr) {

postorder(ptr ->left_child); postorder(ptr ->right_chi ld); printf(“%d”, ptr-

>data);

}

}

3.3 ARITHMATIC TREE

Arithmetic Expression Using BT

inorder traversal A / B * C * D + E

infix expression preorder traversal

+ * * / A B C D E prefix expression

postorder traversal A B / C * D * E +

postfix expression level order traversal

+ * E * D / C A B

munotes.in

## Page 43

Tree Algorithms

43

15

Trace Operations of Inorder Traversal

Iterative Inorder Traversal (using stack)

void iter_inorder (tree_pointer node)

{

int top= -1; /* initialize stack */ tree_pointer stack[MAX_STACK_SIZE]; for (;;) {

for (; node; node=node ->left_child) add(&top, node); /* add to stack */

node= delete(&top); /* delete from stack */ if (!node) break; /* empty stack */

printf(“%D”, node->data);

node = node->right_child;

}

}

In iterative in order traversal, we must create our own stack to add and remove nodes

as in recursion.

Analysis: Let n be number of nodes in tree, every node of tree is placed on and

removed from the stack exactly once. So time complexity is O(n). The space

requirement is equal to the depth of tree which is O(n).

Level Order Traversal ( Using Queue) -- Traversal without Stack

void level_order(tree_pointer ptr) /* level order tree traversal */

{

int front = rear = 0;

tree_pointer queue[MAX_QUEUE_SIZE]; if (!ptr) return; /* empty queue */

addq(front, &rear, ptr);

for (;;) {

ptr = deleteq(&front, rear); if (ptr) {

printf(“%d”, ptr->data); if (ptr->left_child) + * E* D/ CABmunotes.in

## Page 44

Fundamental of

Algorithms

44 addq(front, &rear, ptr->left_child); if (ptr->right_child)

addq(front, &rear, ptr->right_child);

}

else break;

} }

Level order Traversal is implemented with circular queue. In this order, we visit the root

first, then root’s left child followed by root’s right child. We continue in this manner,

visiting the nodes at each new level from left most to right most nodes.

We begin by adding root to the queue. The function operates by deleting the node at the

front of the queue, printing out the node’s data field, and adding the node’s left and

right children to the queue. The level order traversal for above arithmetic expression

is + * E * D / C A B.

Binary Search Trees

Binary Search Tree Representation

Binary Search tree exhibits a special behavior. A node's left child must

have value less than its parent's value and node's right child must have

value greater than it's parent value.

We're going to implement tree using node object and connecting them

through references.

Definition: A binary search tree (BST) is a binary tree. It may be empty. If

it is not empty,then all nodes follows the below mentioned properties −

Every element has a unique key.

The keys in a nonempty left subtree (right subtree) are smaller

(larger) than the key in the root of subtree.

The keys in a nonempty right subtree larger than the key in the root of

subtree.

The left and right subtrees are also binary search trees. left sub -tree and

right sub-tree and can be defined as −

munotes.in

## Page 45

Tree Algorithms

45 left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)

Fig: Example Binary Search Trees

ADT for Dictionary:

BST Basic Operations

The basic operations that can be perform ed on binary search tree data

structure, are following −

Search − search an element in a binary search tree.

Insert − insert an element into a binary search tree / create a tree.

Delete − Delete an element from a binary search tree.

Height -- Height of a binary search tree.

Searching a Binary Search Tree

Let an element k is to search in binary search tree. Start search from root

node of the search tree. If root is NULL, search tree contains no nodes

and search unsuccessful. Otherwise, compare k with the key in the root.

If k equals the root’s key, terminate search, if k is less than key value,

searchelement k in left subtree otherwise search element k in right subtree.

The function search recursively searches the subtrees.

Algorithm:Recursive search of a Binary Search Tree

tree_pointer search(tree_pointer root, int key)

{

/* return a pointer to the node that contains key. If there is no such node,

return NULL */

if (!root) return NULL;

if (key == root->data) return root; if (key < root->data)

return search(ro ot->left_child, key); return search(root ->right_child,key);

}

Algorithm: Iteraive search of a Binary Search Tree

tree_pointer search2(tree_pointer tree, int key)

munotes.in

## Page 46

Fundamental of

Algorithms

46 {

while (tree) {

if (key == tree->data) return tree; if (key < tree->data)

tree = tree ->left_c hild; else tree = tree->right_child;

}

return NULL;

}

Analysis of Recursive search and Iterative Search Algorithms:

If h is the height of the binary search tree, both algorithms perform search in O(h) time.

Recursive search requires additional stack space which is O(h).

3.4 BALANCED TREE

Inserting into a Binary Search Tree

The very first insertion creates the tree. Afterwards, whenever an element

is to be inserted. First locate its proper location. Start search from root

node then if data is less than key value, search empty location in left sub

tree and insert the data. Otherwise search empty location in right sub tree

and insert the data.In a binary search tree, the insertion operation is

performed with O(log n) time complexity. In binary search tree, new node

is always ins erted as a leaf node. The insertion operation is performed as

follows...

Step 1: Create a newNode with given value and set its left and right to

NULL. Step 2: Check whether tree is Empty.

Step 3: If the tree is Empty, then set set root to newNode.

Step 4: If the tree is Not Empty, then check whether value of newNode is

smaller or larger than the node (here it is root node).

Step 5: If newNode is smaller than or equal to the node, then move to its

left child. If newNode is larger than the node, then move to its right child.

Step 6: Repeat the above step until we reach a node (e.i., reach to NULL)

where search terminates.

Step 7: After reaching a last node, then insert the newNode as left child if

newNode is smaller or equal to that node e lse insert it as right child.

munotes.in

## Page 47

Tree Algorithms

47 void insert (int data ) {

struct node *tempNode = (struct node *)

malloc (sizeof (struct node )); struct node *current ;

struct

node

*parent ;

tempNo

de-

>data =

data ;

tempNo

de-

>leftChi

ld =

NULL ;

tempNo de->rightChild = NULL ;

//if tree is

empty,

create root Algorithm

Create newnode If root is NULL

then create root node return

If root exists then

compare the data with node.data

while until insertion position is located If data is greater than node.data

goto right subtree else

goto left subtree endw hile

insert newnode end If

Implementation

The implementation of insert function should look like this –

munotes.in

## Page 48

Fundamental of

Algorithms

48

Deleting a node

Remove operation on binary search tree is more complicated, than insert

and search. Ba sically, in can be divided into two stages:

search for a node to remove

if the node is found, run remove algorithm.

Remove algorithm in detail

Now, let's see more detailed description of a remove algorithm. First stage

is identical to algorithm for lookup, except we should track the parent of

the current node. Second part is more tricky. Ther e are three cases, which

are described below .

1. Node to be removed has no children. --This case is quite simple.

Algorithm sets corresponding link of the parent to NULL and disposes

the node.

Example. Remove -4 from a BST.

retur}}//go to right of

the tree else {

current = current -

>rightChild ;

//insert to the

right if(current == NULL) { }}munotes.in

## Page 49

Tree Algorithms

49 2. Node to be removed has one child. In this case , node is cut from the

tree and algorithm links single child (with it's subtree) directly to the

parent of the removed node.

3. Node to be removed has two children. --This is the most complex case.

The deleted node can be replaced by eit her largest key in its left

subtree or the smallest in its right subtree. Preferably which node

has one child.

Deletion Operation in BST

In a binary search tree, the deletion operation is performed with O(log n)

time complexity. Deleting a node from Binar y search tree has f ollowing

three cases...

Case 1: Deleting a Leaf node (A node with no children) Case 2: Deleting a

node with one child

Case 3: Deleting a node with two children Case 1: Deleting a leaf node

We use the following steps to delete a leaf node from BST... Step 1: Find

the node to be deleted using search operation

Step 2: Delete the node using free function (If it is a leaf) and terminate

the function. Case 2: Deleting a node with one child

We use the following steps to delete a node with one child from BST...

Step 1: Find the node to be deleted using search operation

Step 2: If it has only one child, then create a link between its parent and

child nodes. Step 3: Delete the node using free function and terminate the

function.

Case 3: Deleting a node with two childr en

We use the following steps to delete a node with two children from BST...

Step 1: Find the node to be deleted using search operation

Step 2: If it has two children, then find the largest node in its left subtree

munotes.in

## Page 50

Fundamental of

Algorithms

50 (OR) the smallest node in its right subtr ee.

Step 3: Swap both deleting node and node which found in above step.

Step 4: Then, check whether deleting node came to case 1 or case 2 else

goto steps 2 Step 5: If it comes to case 1, then delete using case 1 logic.

Step 6: If it com es to case 2, then delete using case 2 logic.

Step 7: Repeat the same process until node is deleted from the tree.

/* deletion in binary search tree */

void deletion(struct treeNode **node, struct treeNode **parent, int data) {

struct treeNode *tmpNode, *t mpParent;

if (*node == NULL) return;

if ((*node) ->data == data) {

/* deleting the leaf node */

if (!(*node) ->left && !(*node) ->right) { if (parent) {

/* delete leaf node */

if ((*parent) ->left == *node) (*parent) ->left = NULL;

else

(*parent) ->right = NULL;

free(*node);

} else {

/* delete root node with no children */ free(*node);

}

/* deleting node with one child */

} else if (!(*node) ->right && (*node) ->left) {

/* deleting node with left child alone */ tmpNode = *node;

(*parent) ->right = (*node) ->left; free(tmpNode);

*node = (*parent) ->right;

} else if ((*node) ->right && !(*node) ->left) {

/* deleting node with right child alone */ tmpNode = *node;

(*parent) ->left = (*node) ->right; free(tmpNode);

(*node) = (*parent) ->left; munotes.in

## Page 51

Tree Algorithms

51 } else if (!(*node) ->right ->left) {

/*

* deleting a node whose right child

* is the smallest node in the right

* subtree for the node to be deleted.

*/

tmpNode = *node;

(*node) ->right ->left = (*node) ->left;

(*parent) ->left = (*node) ->right; free(tmpNode);

*node = (*parent) ->left;

} else {

/*

* Dele ting a node with tw o children.

* First, find the smallest node in

* the right subtree. Replace the

* smallest node with the node to be

* deleted. Then, do proper connections

* for the children of replaced node.

*/

tmpNode = (*node) ->right; while (tmpNode ->left) {tmp Parent = tmpNode;

tmpNode = tmpNode ->left;

}

tmpParent ->left = tmpNode ->right; tmpNode ->left = (*node) ->left;

tmpNode ->right =(*node) ->right; free(*node);

*node = tmpNode;

}

} else if (data < (*node) ->data) {

/* traverse towards left subtree */ deletion(&( *node) ->left, node, data);

} else if (data > (*node) ->data) {

/* traversing towards right subtree */ deletion(&(*node) ->right, node, munotes.in

## Page 52

Fundamental of

Algorithms

52 data);

}

}

Height of a Binary Search Tree:

Height of a Binary Tree For a tree with just one node, the root node, the

height is defined to be 0 , if there are 2 levels of nodes the height is 1 and

so on. A null tree (no nodes except the null node) is defined to have a

height of –3.

The following height function in pseudocode is defined recursively

Example

Construct a Binar y Search Tree by in serting the following sequence of

numbers... 10,12,5,4,20,8,7,15 and 13

Above elements are inserted into a Binary Search Tree as follows...

munotes.in

## Page 53

Tree Algorithms

53

Generic Trees (N-ary Trees)

Generic trees are a collection of nodes where each node is a data

structure that consi sts of records and a list of references to its

children(duplicate references are not allowed). Unlike the linked list,

each node stores the address of multiple nodes. Every node stores

address of its children and the very first node’s ad dress will be store d in

a separate pointer called root.

The Generic trees are the N -ary trees which have the following

properties:

1. Many children at every node.

2. The number of nodes for each node is not known in advance.

munotes.in

## Page 54

Fundamental of

Algorithms

54 Example:

Generic Tree

To represent the abo ve tree, we have to consider the worst case, that is

the node with maximum children (in above example, 6 children) and

allocate that many pointers for each node.

The node representation based on this method can be written as:

struct Node{

int data;

Node *firstchild;

Node *secondchild;

Node *thirdchild;

Node *fourthchild;

Node *fifthchild;

Node *sixthchild;

};

Disadvantages of the above representation are:

1. Memory Wastage – All the pointers are not required in all th e cases.

Hence, the re is lot of memory wastage.

2. Unknown number of children – The number of children for each

node is not known in advance.

Simple Approach:

For storing the address of children in a node we can use an array or linked

list. But we will face some issues with bo th of them. munotes.in

## Page 55

Tree Algorithms

55 1. In Linked list, we can not randomly access any child’s address. So it

will be expensive.

2. In array , we can randomly access the address of any child, but we can

store only fixed number of children’s addresses in it.

Better Appr oach:

We can use Dynamic Arrays for storing the address of children’s address.

We can randomly access any child’s address and the size of the vector is

also not fixed.

Inorder traversal of a Binary tree can either be done using recursion

or with the use of a auxiliary stack . The idea of threaded binar y trees is

to make inorder traversal faster and do it without stack and without

recursion. A binary tree is made threaded by making all right child

pointers that would normally be NULL point to the inorder successor of

the node (if it exists).

A threaded b inary tree is a typ e of binary tree data structure where the

empty left and right child pointers in a binary tree are replaced with

threads that link nodes directly to their in -order predecessor or successor,

thereby providing a way to traverse the tree wi thout using recursi on or a

stack.

Threaded binary trees can be useful when space is a concern, as they can

eliminate the need for a stack during traversal. However, they can be

more complex to implement than standard binary trees.

There are two types of th readed binary trees .

Single Threaded: Where a NULL right pointers is made to point to the

inorder successor (if successor exists)

Double Threaded: Where both left and right NULL pointers are made

to point to inorder predecessor and inorder successor respec tively. The

predece ssor threads are useful for reverse inorder traversal and postorder

traversal.

The threads are also useful for fast accessing ancestors of a node.

Following diagram shows an example Single Threaded Binary Tree. The

dotted lines represent threads. munotes.in

## Page 56

Fundamental of

Algorithms

56

C and C++ representation of a Threaded Node

Following is C and C++representation of a single -threaded node. struct Node

{

int data;

struct Node *left, *right;

bool rightThread;

}

Java representation of a Threaded Node

Following is Java representat ion of a single -threaded node.

Since right pointer is used for two purposes, the boolean variable

rightThread is used to indicate whether right pointer points to right child

or inorder successor. Similarly, we can add leftThread for a do uble

threaded binar y tree.

Inorder Traversal using Threads Following is code for inorder

traversal in a threaded binary tree.

Following diagram demonstrates inorder order traversal using threads.

munotes.in

## Page 57

Tree Algorithms

57

Advantages of Threaded Binary Tree

In this Tree it enabl es linear traversal of elements.

It eliminates the use of stack as it perform linear traversal, so save

memory. munotes.in

## Page 58

Fundamental of

Algorithms

58 Enables to find parent node without explicit use of parent pointer

Threaded tree give forward and backward traversal of nodes by in -

order fashio n

Nodes contain poi nters to in -order predecessor and successor

For a given node, we can easily find inorder predecessor and

successor. So, searching is much more easier.

In threaded binary tree there is no NULL pointer present. Hence

memory wastage in occ upying NULL links i s avoided.

The threads are pointing to successor and predecessor nodes. This

makes us to obtain predecessor and successor node of any node

quickly.

There is no need of stack while traversing the tree, because using

thread links we can r each to previously visited nodes.

Disadvantages of Threaded Binary Tree

Every node in threaded binary tree need extra information(extra

memory) to indicate whether its left or right node indicated its child

nodes or its inorder predecessor or successor. So , the node consumes

extra memory to implement.

Insertion and deletion are way more complex and time consuming

than the normal one since both threads and ordinary links need to be

maintained.

Implementing threads for every possible node is complicated.

Increased complexity: I mplementing a threaded binary tree requires

more complex algorithms and data structures than a regular binary

tree. This can make the code harder to read and debug.

Extra memory usage: In some cases, the additional pointers used to

threa d the tree can use up more memory than a regular binary tree.

This is especially true if the tree is not fully balanced, as threading a

skewed tree can result in a large number of additional pointers.

Limited flexibility: Threaded binary trees are speciali zed data

structures that are optimized for specific types of traversal. While

they can be more efficient than regular binary trees for these types of

operations, they may not be as useful in other scenarios. For

example, they cannot be easily modified (e.g . inserting or dele ting

nodes) without breaking the threading.

Difficulty in parallelizing: It can be challenging to parallelize

operations on a threaded binary tree, as the threading can introduce

data dependencies that make it difficult to process nodes

independently. This can limit the performance gains that can be

achieved through parallelism. munotes.in

## Page 59

Tree Algorithms

59 Applications of threaded binary tree –

Expression evaluation: Threaded binary trees can be used to evaluate

arithmetic expressions in a way that avoids recursion or a stack. The

tree can be constructed from the input expression, and then traversed

in-order or pre -order to perform the evaluation.

Database indexing: In a database, threaded binary trees can be used

to index data based on a specific field (e.g. last na me). The tree can

be constructed with the indexed values as keys, and then traversed in -

order to retrieve the data in sorted order.

Symbol table management: In a compiler or interpreter, threaded

binary trees can be used to store and manage symbol tables f or

variables and fu nctions. The tree can be constructed with the symbols

as keys, and then traversed in -order or pre -order to perform various

operations on the symbol table.

Disk -based data structures: Threaded binary trees can be used in

disk-based data s tructures (e.g. B -trees) to improve performance. By

threading the tree, it can be traversed in a way that minimizes disk

seeks and improves locality of reference.

Navigation of hierarchical data: In certain applications, threaded

binary trees can be used t o navigate hierarch ical data structures, such

as file systems or web site directories. The tree can be constructed

from the hierarchical data, and then traversed in -order or pre -order to

efficiently access the data in a specific order.

Expression Tree

The expression tree is a binary tree in which each internal node

corresponds to the operator and each leaf node corresponds to the

operand so for example expression tree for 3 + ((5+9)*2) would be:

munotes.in

## Page 60

Fundamental of

Algorithms

60 Inorder traversal of expression tree produces infix version of given

postfix ex pression (same with postorder traversal it gives postfix

expression)

Evaluating the expression represented by an expression tree:

Let t be the expression tree

If t is not null then

If t.value is operand then

Return t.value

A = solve(t.left)

B = solve(t.right)

// calculate applies operator 't.value'

// on A and B, and returns value

Return calculate(A, B, t.value)

Construction of Expression Tree:

Now For constructing an expression tree we use a stack . We loop

through input expression and do the following for every character.

1. If a character is an operand push that into the stack

2. If a character is an operator pop two values from the stack make them

its child and push the current node again.

In the end, the only element of the stack will be the root of an expression

tree.

Examples:

Input: A B C*+ D/

Output: A + B * C / D

The first three symbols are operands, so create tree nodes and push

pointers to them onto a stack as shown below.

munotes.in

## Page 61

Tree Algorithms

61 In the Next step , an operator ‘*’ will going read, so two pointers to trees

are popped, a new tree is formed and a pointer to it is pushed onto the

stack

In the Next step, an operator ‘+’ will read, so two pointers to trees are

popped, a new tree is formed and a pointe r to it is pushed onto the stack.

Below is the implementation of the above approach: import java.util.Stack;

class Node{

char data;

Node left,right;

public Node( char data){

this.data = data;

left = right = null;

}

}

public class Main {

public static boolean isOperator( char ch){

if(ch=='+' || ch==' -'|| ch=='*' || ch=='/' || ch=='^'){

return true;

}

return false ;

} munotes.in

## Page 62

Fundamental of

Algorithms

62 public static Node expressionTree(String postfix){

Stack st = new Stack();

Node t1,t2,temp;

for(int i=0;i if(!isOperator(postfix.charAt(i))){

temp = new Node(postfix.charAt(i));

st.push(temp);

}

else{

temp = new Node(postfix.charAt(i));

t1 = st.pop();

t2 = st.pop();

temp.left = t2;

temp.right = t1;

st.push(temp);

}

}

temp = st.pop();

return temp;

}

public static void inorder(Node root){

if(root== null) return ;

inorder(root.left);

System.out.print(root.data);

inorder(root.right); munotes.in

## Page 63

Tree Algorithms

63 }

public static void main(Str ing[] args) {

String postfix = "ABC*+D/";

Node r = expressionTree(postfix);

inorder(r);

}

}

Output

The Inorder Traversal of Expression Tree: A + B * C / D

Time complexity: O(n)

Auxiliary space: O(n)

3.5 WHAT IS BINA RY SEARCH TREE ?

Binary Search Tree is a node -based binary tree data structure which has

the following properties:

The left subtree of a node contains only nodes with keys lesser than

the node’s key.

The right subtree of a node contains only nodes with keys grea ter than

the node’s key.

The left and right subtree each must also be a binary search tree.

Binary Search Tree munotes.in

## Page 64

Fundamental of

Algorithms

64 Balanced Binary Search Tree

A balanced binary tree is also known as height balanced tree. It is defined

as binary tree in when the difference b etween the height of the left subtree

and right subtree is not more than m, where m is usually equal to 3. The

height of a tree is the number of edges on the longest path between the

root node and the leaf node.

The above tree is a binary search tree . A binary search tree is a tree in

which each node on the left side has a lower value than its parent node,

and the node on the right side has a higher value than its parent node. In

the above tree, n1 is a root node, and n4, n6, n7 are the leaf nodes. The n7

node is the farthest node from the root node. The n4 and n6 contain 2

edges and there exist three edges between the root node and n7 node.

Since n7 is the farthest from the root node; therefore, the height of the

above tree is 3.

Now we will see whether the above tree is balanced or not. The left

subtree contains the nodes n2, n4, n5, and n7, while the right subtree

contains the nodes n3 and n6. The left subtree has two l eaf nodes, i.e., n4

and n 7. There is only one edge between the node n2 and n4 and two edges

between the nodes n7 and n2; therefore, node n7 is the farthest from the

root node. The height of the left subtree is 2. The right subtree contains

only one leaf no de, i.e., n6, and has onl y one edge; therefore, the height of

the right subtree is 3. The difference between the heights of the left subtree

and right subtree is 3. Since we got the value 1 so we can say that the

above tree is a height -balanced tree. This process of calculating th e

difference between the heights should be performed for each node like n2,

n3, n4, n5, n6 and n7. When we process each node, then we will find that

the value of k is not more than 1, so we can say that the above tree is a

balanced binary tree . munotes.in

## Page 65

Tree Algorithms

65

In the above tree, n6, n4, and n3 are the leaf nodes, where n6 is the farthest

node from the root node. Three edges exist between the root node and the

leaf node; therefore, the height o f the above tree is 3. Wh en we consider

n1 as the root node, then the left subtree contains the nodes n2, n4, n5, and

n6, while subtree contains the node n3. In the left subtree, n2 is a root

node, and n4 and n6 are leaf nodes. Among n4 and n6 nodes, n6 is the

farthest node from i ts root node, and n6 has two edges; therefore, the

height of the left subtree is 2. The right subtree does have any child on its

left and right; therefore, the height of the right subtree is 0. Since the

height of the left subtree is 2 and the right subtre e is 0, so the difference

between the height of the left subtree and right subtree is 2. According to

the definition, the difference between the height of left sub tree and the

right subtree must not be greater than 3. In this case , the difference comes

to be 2, which is greater than 1; therefore, the above binary tree is an

unbalanced binary search tree.

The above tree is a binary search tree because all the left subtree nodes are

smaller than its parent node and all the right su btree nodes are greater t han

its parent node. Suppose we want to want to find the value 79 in the above

tree. First, we compare the value of node n1 with 79; since the value of 79

is not equal to 35 and it is greater than 35 so we move to the node n3, i.e. , munotes.in

## Page 66

Fundamental of

Algorithms

66 48. Since the value 79 is not equal to 48 and 79 is greater than 48, so we

move to the right child of 48. The value of the right child of node 48 is 79

which is equal to the value to be searched. The number of hops required to

search an element 79 is 2 a nd the maximum number of hops required to

search any element is 2. The average case to search an element is O(logn).

The above tree is also a binary search tree because all the left subtree

nodes are smaller than its parent node and all the right subtree nodes are

greater than i ts parent node. Suppose we want to find the find the value 79

in the above tree. First, we compare the value 79 with a node n4, i.e., 13.

Since the value 79 is greater than 13 so we move to the right child of node

13, i.e., n2 (21) . The value of the node n 2 is 21 which is smaller than 79,

so we again move to the right of node 2 3. The value of right child of node

21 is 29. Since the value 79 is greater than 29 so we move to the right

child of node 29. The value of right child of node 29 is 35 which is smalle r

than 79 so we move to the right child of node 35, i.e., 48. The value 79 is

greater than 48, so we move to the right child of node 48. The value of

right child node of 48 is 79 which is equal to the value to be searched. In

this case, the number of hops required to search an element is 5. In this

case, the worst case is O(n).

If the number of nodes increases, the formula used in the tree diagram1 is

more efficient than the formula used in the tree diagram2. Suppose the

number of n odes available in both ab ove trees is 100,000. To search any

element in a tree diagram2, the time taken is 100,000µs whereas the time

taken to search an element in tree diagram is log(100,000) which is equal

16.6 µs. We can observe the enormous difference in time between above

two trees. Therefore, we conclude that the balance binary tree provides

searching more faster than linear tree data structure. munotes.in

## Page 67

Tree Algorithms

67 What is AVL Trees?

An AVL tree is a type of binary search tree. Named after it's inventors

Adelson, Velskii , and Landis, AVL trees h ave the property of dynamic

self-balancing in addition to all the other properties exhibited by binary

search trees.

A BST is a data structure composed of nodes. It has the following

guarantees:

1. Each tree has a root node (at the to p)

2. The root node has zero , one, or two child nodes

3. Each child node has zero, one, or two child nodes

4. Each node has up to two children

5. For each node, its left descendants are less than the current node,

which is less than the right descendants

AVL trees hav e an additional guarantee :

1. The difference between the depth of right and left sub -trees cannot be

more than one. This difference is called the balance factor.

In order to maintain this guarantee, an implementation of an AVL will

include an algorithm to re balance the tree when add ing an additional

element would upset this guarantee

AVL trees have a worst case lookup, insert, and delete time of O(log n),

where n is the number of nodes in the tree. The worst case space

complexity is O(n) .

AVL Insertion Proces s

Insertion in an AVL tre e is similar to insertion in a binary search tree. But

after inserting and element, you need to fix the AVL properties using left

or right rotations:

If there is an imbalance in the left child's right sub -tree, perform a left -

right rotation

If there is an imbalance in the left child's left sub -tree, perform a right

rotation

If there is an imbalance in the right child's right sub -tree, perform a left

rotation

If there is an imbalance in the right child's left sub -tree, perform a

right-left rotation munotes.in

## Page 68

Fundamental of

Algorithms

68 AVL Tree Rotations

In AVL trees, after each operation like insertion and deletion, the balance

factor of every node needs to be checked. If every node satisfies the

balance factor condition, then the operation can be concluded. Otherwise,

the tree needs to be rebal anced using rotation operations.

There are four rotations and they are classified into two types:

Left Rotation (LL Rotation)

In left rotations, every node moves one position to left from the current

position.

Right Rotation (RR Rotation)

In right rotati ons, every node moves one position to right from the current

position.

Left-Right Rotation (LR Rotation)

Left-right rotations are a combination of a single left rotation followed by

a single right rotation.

First, every node moves one position to the left, then one position to the

right from the current position.

Right -Left Rotation (RL Rotation)

Right -left rotations are a combination of a single right rotation followed

by a single left rotation.

First, every node moves one position to the right then, then one position to

the left from the current position.

Application of AVL Trees

AVL trees are beneficial in cases like a database where insertions and

deletions are not that frequent, but you frequently check for entries.

Python Funct ions

munotes.in

## Page 69

Tree Algorithms

69 Define the class and initialize the nodes class avl_Node(object):

def __init__(self, value):

self.value = value

self.leaf = None

self.root = None

self.height = 1

Define a function to calculate height and Balance Factor. def avl_Height(s elf, root):

if not root:

return 0

return root.height

def avl_BalanceFactor(self, root):

//base case for leaf nodes

if not root:

return 0

//implementing the above mentio ned formula

retur n self.avl_Height(root.l) - self.avl_Height(root.r)

Define a function to find an empty node def avl_MinValue(self, root):

if root is None or root.left is None:

return root

return self.avl_MinValue(root. left)

Define a function to traverse the tree in a preorder way. def preOrder(self, root):

if not root:

return

print("{0} ".format(root.value), end=" ") munotes.in

## Page 70

Fundamental of

Algorithms

70 self.preOrder(root.left)

self.preOrder(root.right)

Define functions for rotations def leftRotate(self, b):

a = b.right

T2 = a.left

a.left = b

b.right = T2

b.height = 1 + max(self.avl_Height(b.left),

self.avl_Height(b.right))

a.height = 1 + max(self.avl_Height(a.le ft),

self.avl_Height(a.right))

return a

def rightRotate(self, b):

a = b.left

T3 = a.right

a.right = z

b.left = T3

b.height = 1 + max(self.avl_Height( b.left),

self.avl_Height(b.right))

a.height = 1 + max(self.avl_Height(a.left),

self.avl_Height(a.right))

return a

Define a function for inserting a node in AVL tree in Python def insert _node(self, root, value):

if not root:

return avl_Node(value)

elif value < root.value:

root.left = self.insert_node(root.left, value) munotes.in

## Page 71

Tree Algorithms

71 else:

root.right = self.insert_node(root.right, value)

root.height = 1 + max(self.avl_Height(root.left),

self.avl_Height(root.right))

# Update the balance factor and balance the tree

balanceFactor = self.avl_BalanceFactor(root)

if balanceFactor > 1:

if value < root.left.value:

return self.rightRotate(root)

else:

root.left = self.leftRotate(root.left)

return self.rightRotate(root)

if balanceFactor < -1:

if value > root.right.value:

return self.leftRotate(root)

else:

root.right = self.rightRotate(root.right)

return self.leftRotate(root)

return root

Define a function for deleting a node from the AVL tree in Python def delete_node(self, root, value):

# Find the node to be deleted and remove it

if not root:

return root

elif value < root.value:

root.left = self.delete_node(root.left, value)

elif value > root.value:

root.right = self.delete_node(root.right, value) munotes.in

## Page 72

Fundamental of

Algorithms

72 else:

if root.left is None:

temp = root.right

root = None

return temp

elif root.right is None:

temp = root.left

root = None

return temp

temp = self.avl_MinValue(root.right)

root.value = temp.key

root.right = self.delete_node(root.right, temp.value)

if root is None:

retur n root

# Update the balance factor of nodes

root.height = 1 + max(self.avl_Height(root.left),

self.avl_Height(root.right))

balanceFactor = self.avl_BalanceFactor(root)

# Balance the tree

if balanceFactor > 1:

if self.avl_BalanceFactor(root.left) >= 0:

return self.rightRotate(root)

else:

root.left = self.leftRotate(root.left)

return self.rightRotate(root)

if balan ceFactor < -1:

if self.avl_BalanceFactor(root.right) <= 0:

return self.leftRotate(root)

munotes.in

## Page 73

Tree Algorithms

73 else:

root.right = self.rightRotate(root.right)

return self.leftRotate(root)

return root

Complete Code for AVL Tree in Python class avl_Node(object):

def __init__(self, value):

self.value = value

self.left = None

self.right = None

self.height = 1

class AVLTree(object):

def insert_nod e(self, root, value):

if not root:

return avl_Node(value)

elif value < root.value:

root.left = self.insert_node(root.left, value)

else:

root.right = self.insert_node(root.right, value)

root.height = 1 + max(self .avl_Height(root.left),

self.avl_Height(root.right))

# Update the balance factor and balance the tree

balanceFactor = self.avl_BalanceFactor(root)

if balanceFactor > 1:

if value < root.left .value:

return self.rightRotate(root)

else:

root.left = self.leftRotate(root.left)

return self.rightRotate(root) munotes.in

## Page 74

Fundamental of

Algorithms

74 if balanceFactor < -1:

if value > root.right.value:

return self.leftRotate(root)

else:

root.right = self.rightRotate(root.right)

return self.leftRotate(root)

return root

def avl_Height(self, root):

if not root:

return 0

return root.height

# Get balance factore of the node

def avl_BalanceFactor(self, root):

if not root:

return 0

return self.avl_Height(root.left) - self.avl_Height(root.right)

def avl_M inValue(self, root):

if root is None or root.left is None:

return root

return self.avl_MinValue(root.left)

def preOrder(self, root):

if not root:

return

print("{0} ".format(root.value), end=" ")

self.preOrder(roo t.left)

self.preOrder(root.right)

def leftRotate(self, b):

a = b.right

T2 = a.left munotes.in

## Page 75

Tree Algorithms

75 a.left = b

b.right = T2

b.height = 1 + max(self.avl_Height(b.left),

self.avl_Height(b.right))

a.height = 1 + max(self.avl_Height(a.left),

self.avl_Height(a.right))

return a

def rightRotate(self, b):

a = b.left

T3 = a.right

a.right = b

b.left = T3

b.height = 1 + max(self.avl_Height(b.left),

self.avl_Height(b.right))

a.height = 1 + max(self.avl_Height(a.left),

self.avl_Height(a.right))

return a

def delete_node (self, root, value):

# Find the node to be deleted and remove it

if not root:

return root

elif value < root.value:

root.left = self.delete_node(root.left, value)

elif value > root.value:

root.right = self.delete_ node(root.right, value)

else:

if root.left is None:

temp = root.right

root = None munotes.in

## Page 76

Fundamental of

Algorithms

76 return temp

elif root.right is None:

temp = root.left

root = None

return temp

temp = self.avl_MinValue(root.right)

root.value = temp.key

root.right = self.delete_node(root.right, temp.value)

if root is None:

return root

# Update the balance factor of nodes

root.height = 1 + max(self.avl_Height(root.left),

self.avl_Height(root.right))

balanceFactor = self.avl_BalanceFactor(root)

# Balance the tree

if balanceFactor > 1:

if self.avl_BalanceFactor( root.left) >= 0:

return self.rightRotate(root)

else:

root.left = self.leftRotate(root.left)

return self.rightRotate(root)

if balanceFactor < -1:

if self.avl_BalanceFactor(root. right) <= 0:

return self.leftRotate(root)

else:

root.right = self.rightRotate(root.right)

return self.leftRotate(root)

return root

munotes.in

## Page 77

Tree Algorithms

77 Tree = AVLTree()

root = None

root = Tree.insert_node(root,40)

root = Tree.insert_node(root,60)

root = Tree.insert_node(root,50)

root = Tree.insert_node(root,70)

print("PREORDER")

Tree.preOrder(root)

Output:

PREORDER

50 40 60 70

3.6 LET US SUM UP

Give an algorithm for finding the sum of all elements in a binary

tree.

In the above binary tree sum = 106.

// Java Program to print sum of

// all the ele ments of a binary tree

class GFG

{

static class Node

{

int key;

Node left, right;

}

/* utility that allocates a new munotes.in

## Page 78

Fundamental of

Algorithms

78 Node with the given key */

static Node newNode(int key)

{

Node node = new Node();

node.key = key;

node.left = node.right = null;

return (node);

}

/* Function to find sum

of all the elements*/

static int addBT(Node root)

{

if (root == null)

return 0;

return (root.key + addBT(root.left) +

addBT(root.right));

}

// Driver Code

public static void main(String args[])

{

Node root = newNode(1);

root.left = newNode(2);

root.right = newNode(3);

root.left.left = newNode(4);

root.left.right = newNode(5);

root.right.left = newNode(6);

root.right.right = newNode(7);

root.right.left.right = newNode(8);

int sum = addBT(root);

Syste m.out.println("Sum of all the elements is: " + sum);

}

}

Output

Sum of all the elements is: 36

Time Complexity: O(N)

Auxiliary Space: O(1), but if we consider space due to the

recursion call stack then it would be O(h), where h is the height of

the Tree. munotes.in

## Page 79

Tree Algorithms

79 Method 2 – Another way to solve this problem is by using Level

Order Traversal. Every time when a Node is deleted from the

queue, add i t to the sum variable.

Implementation:

C++

Java

Python3

C#

Javascript

# Python3 Program to print sum of all

# the elements of a binary tree

# Binary Tree Node

class newNode:

# Utility function to create a new node

def __init__( self, key):

self.key = key

self.left = None

self.right = None

# Function to find sum of all the element

def sumBT(root):

# sum variable to track the sum of

# all variables.

sum = 0

q = []

# Pushing the first level.

q.append(root)

# Pushing elements at each level from

# the tree.

while len(q) > 0:

temp = q.pop(0)

# After popping each element from queue

# add its data to the sum variable.

sum += temp.key

if (temp.left != None):

q.append(temp.left)

if temp.right != None:

q.append(temp.right) munotes.in

## Page 80

Fundamental of

Algorithms

80 return sum

# Driver Code

if __name__ == '__main__' :

root = newNode( 1)

root.left = newNode( 2)

root.right = newNode( 3)

root.left.left = newNode( 4)

root.left.right = newNode( 5)

root.right.left = newNode( 6)

root.right.right = newNode( 7)

root.right.left.right = newNode( 8)

print("Sum of all elements in the binary tree is: ",

sumBT(root))

# This code is contributed by

# Abhijeet Kumar(abhijeet19403) Output

Sum of all elements in the binary tree is: 36

Time Complexity: O(n)

Auxiliary Space: O(n)

Method 3: Using Morris traversal:

The Morris Traversal algorithm is an in -order tree

traversal algorithm that does not require the use of

a stack or recursion, and uses only constant extra

memory. The basic idea behind the Morris Traver sal

algorithm is to use the right child pointers of th e

nodes to create a temporary link back to the node's

parent, so that we can easily traverse the tree

without using any extra memory.

Follow the steps below to implement the above idea:

1. Initialize a var iable sum to 0 to keep track of the sum of

all nodes i n the binary tree.

2. Initialize a pointer root to the root of the binary tree.

3. While root is not null, perform the following steps:

If the left child of root is null, add the value of root to

sum, and mov e to the right child of root.

If the left child of roo t is not null, find the rightmost node

of the left subtree of root and create a temporary link

back to root.

Move to the left child of root. munotes.in

## Page 81

Tree Algorithms

81 4. After the traversal is complete, return sum.

Below is the imp lementation of the above approach:

C++

// C++ code to implement the morris traversal approach

#include

using namespace std;

// Definition of a binary tree node

struct Node {

int val;

Node* left;

Node* right;

Node(int v)

: val(v)

, left(nullptr)

, right(nullptr)

{

}

};

// Morris Traversal function to find the sum of all nodes in

// a binary tree

long int sumBT(Node* root)

{

long int sum = 0;

while (root != nullptr) {

if (root->left

== nullptr) { // If there is no left child, add

// the value of the current node

// to the sum and move to the

// right child

sum += root->val;

root = root->right;

}

else { // If there is a left child

Node* prev = root->left;

while (

prev->right != nullptr

&& prev->right

!= root) // Find the rightmos t node

// in the left subtree of

// the current node

prev = prev->right;

if (prev->right

== nullptr) { // If the right child of the munotes.in

## Page 82

Fundamental of

Algorithms

82 // rightmost node is null, set

// it to the current node and

// move to the left child

prev->right = root;

root = root->left;

}

else { // If the right child of the rightmost

// node is the current node, set it to

// null, add the value of the current

// node to the sum and move to the right

// child

prev->right = nullptr;

sum += root->val;

root = root->right;

}

}

}

return sum;

}

// Driver code

int main()

{

// Example binary tree: 1

// / \

// 2 3

// / \

// 4 5

Node* root = new Node(1);

root->left = new Node(2);

root->right = new Node(3);

root->left->left = new Node(4);

root->left->right = new Node(5);

// Find the sum of all nodes in the binary tree

long int sum = sumBT(root);

cout << "Sum of all nodes in the binary tree is " << sum

<< endl;

return 0;

}

// This code is contributed by Veerendra_Singh_Rajpoot Output

Sum of all nodes in the binary tree is 15 munotes.in

## Page 83

Tree Algorithms

83 Time Complexity: O(n) , Because of all the nodes are traversing

only once.

Auxiliary Space: O(1)

3.7 LIST OF REFERENCES

http://www.cs.bu.edu/teac hing/c/tree/binary/

http://en.wikipedia.org/wiki/Tree_%28data_structure%29#Common_

uses

3.8 UNIT END EXERCISE

1. What is Inorder Tree Traversal ?

2. Write a shorte note on Preord er Tree Traversal ?

3. What is Postorder Tree Traversal ?

4. Check if two binary trees are identical or not ??

5. Print bottom view of a binary tree ?

6. Print top view of a binary tree ?

7. In-place convert a binary tree to its sum tree ?

8. Determine w hether the given binary tree nodes are cousins of each

other ?

9. Print cousins of a given node in a binary tree ?

10. Check if a binary tree is a sum tree or not ?

11. Combinations of wor ds formed by replacing given numbers with

corresponding alphabets ?

12. Determine wheth er a binary tree is a subtree of another binary t ree?

13. Find the diameter of a binary tree ?

14. Check if a binary tree is symmetric or not ?

15. Convert a binary tree to its mirror ?

16. Determine if a binary tree can be converted to another by doing any

number of swaps of children ?

17. Find the Lowe st Common Ancestor (LCA) of two nodes in a binary

tree?

18. Print all paths from the root to leaf no des of a binary tree ?

19. Find ancestors of a given node in a binary tree ?

20. Find distance between giv en pairs of nodes in a binary tree ? munotes.in

## Page 84

Fundamental of

Algorithms

84 21. Find the diagonal sum of a binary tree ?

22. Sink nodes containing zero to the bottom of a binary tree ?

23. Convert a binary tree to a full tree by removing half nodes ?

24. Truncate a binary tree to remove nodes that lie on a path having a

sum less than `k` ?

25. Find maximum sum root to leaf path in a binary tree ?

26. Check if a binary tree is height -balance d or not ?

27. Convert binary tree to Left -child right -sibling binary tree ?

28. Print all paths from leaf to root node of a binary tree ?

29. Iteratively print the leaf to root path for every leaf node i n a binary

tree?

30. Build a binary tree from a parent array ?

31. Find all nodes at a given distance from leaf nodes in a binary tree ?

32. Count all subtree s having the same value of nodes in a binary tree ?

33. Find the maximum difference between a node and its descendants in

a binary tree ?

34. Find the maximum sum path between two leaves in a binary tree ?

35. Construct a binary tree from inorder and preorder traversal ?

36. Construct a binary tree from inorder and postorder traversals ?

37. Construct a binary tree from inorder and level order sequence ?

38. Construct a full binary tree from the preorder sequence with leaf node

information ?

39. Construct a full binary tree from a preorder and po storder sequence ?

40. Find postorder traversal of a binary tree from its inorder and preorder

sequence ?

41. Set next pointer to the inorder successor of all nodes in a binary tree ?

42. Find preorder traversal of a binary tree from its inorder and postorder

sequence ?

43. Find the difference between the sum of all nodes present a t odd and

even levels in a binary tree ?

44. Clone a binary tree with random pointers ?

45. Threaded Binary Tree — Overview and Implementation ? munotes.in

## Page 85

Tree Algorithms

85 46. Determine if a binary tree satisfies the heig ht-balanced property of a

red–black tree ?

47. Construct an ancestor matrix from a binary tree ?

48. Find all possible binary trees having the same inorder traversal ?

49. Perform boun dary traversal on a binary tree ?

50. Check if each node of a binary tree has exactly one child ?

51. Evaluate a Binary Expression Tree ?

52. Construction of an expression tree ?

53. Fix children -sum property in a binary tree ?

54. Maximum path sum in a binary tree ?

55. Create a m irror of an m –ary tree ?

56. Print a two -dimensional view of a binary tree ?

57. Construct a binary tree from an ancesto r matrix ?

58. Determine whether a given binary tree is a BST or not ?

59. Find inorder successor for the given key in a BST ?

60. Fix a binary tree that is only one swap away from becoming a BST?

61. Find the size of the largest BST in a binary tree ?

62. Print binary tre e structure with its contents in C++ ?

63. Maximum Independent Set Problem ?Huffman Coding Compre ssion

Algorithm

64. Construct a Cartesian tree from an inorder traversal ?

65. Calculate the height of a binary tree with leaf nodes forming a

circular doubly linked list ?

66. Link nodes pre sent in each level of a binary tree in the form o f a

linked list ?

67. Convert a ternary tree to a doubly -linked list ?

68. Extract leaves of a binary tree into a doubly -linked list ?

69. Find the vertical sum of a binar y tree ?

70. In-place convert a binary tree to a doubly -linked list ?

71. Check whether the leaf trav ersal of given binary trees is the same or

not? munotes.in

## Page 86

Fundamental of

Algorithms

86 72. Efficiently print all nodes between two given levels in a binary tree ?

73. Calculate the height of a binary tree ?

74. Delete a binary tree ?

75. Level order traversal of a binary tree ?

76. Spiral order traversal of a binary tree

77. Reverse level order trav ersal of a binary tree ?

78. Print all n odes of a perfect binary tree in a specific order ?

79. Print left view of a binary tree ?

80. Find the next node at the same level as the given node in a binary

tree?

81. Check if a binary tree is a complete binary tree or not ?

82. Print diagonal traversal o f a binary tree ?

83. Print corner n odes of every level in a binary tree ?

84. Invert Binary Tree ?

85. Convert a binary tree into a doubly -linked list in spiral order ?

86. Check if a binary tree is a min -heap or not ?

87. Invert alternate levels of a perfect binary tree ?

88. Perform vertical traversal of a binary tree ?

89. Compute the maximum number of nodes at any level in a binary tree ?

90. Print right view of a binar y tree ?

91. Find the minimum depth of a binary tree ?

92. Depth -First Search (DFS) vs Breadth -First Search (BFS) ?

93. Print nodes of a binary tree in vertical order ?

munotes.in

## Page 87

87 4

GRAPH ALGORITHMS

Unit Structure :

4.0 Objectives

4.1 Introduction to Graph

4.2 An Over view

4.2.1 What is a graph algorithms?

4.2.2 Types of graphs

4.2.3 Application of graphs

4.2.4 Depth first search

4.2.5 Breadth first search

4.2.6 Dijkstra’s pa th algorithm

4.3 Applications of Graphs

4.4 Graph Representation

4.5 Graph traversals

4.6 Topological Sort

4.7 Shortest Path Algorithms

4.8 Minimal Spanning Tree

4.9 conclusions

4.10 Unit End Exercises

4.0 OBJECTIVES

To learn what a graph is and how it is used.

To implement the graph abstract data type using multiple internal

representations.

To see how graphs can be used to solve a wide variety of problems

In this chapter we will study graphs. Graphs are a more general structure

than the trees we studied i n the last chapter; in fact you can think of a tree

as a special kind of graph. Graphs can be used to represent many

interesting things about our world, including systems of roads, airline

flights from city to city, how the Internet is connected, or even t he munotes.in

## Page 88

Fundamental of

Algorithms

88 sequence of classes you must take to complete a major in computer

science. We will see in this chapter that once we have a good

representation for a problem, we can use some standard graph algorithms

to solve what otherwise might seem to be a very diffi cult problem.

While it is relatively easy for humans to look at a road map and

understand the relationships between different places, a computer has no

such knowledge. However, we can also think of a road map as a graph.

When we do so we can have our compu ter do interesting things for us. If

you have ever used one of the Internet map sites, you know that a

computer can find the shortest, quickest, or easiest path from one place to

another.

As a student of computer science you may wonder about the courses yo u

must take in order to get a major. A graph is good way to represent the

prerequisites and other interdependencies among courses. Figure 1. shows

another graph. This one represents the courses and the order in which they

must be taken to complete a major in computer science at Luther College.

Figure 1: Prerequisites for a Computer Science Major

What is the purpose of graph algorithms?

Graph algorithms are used to solve the problems of representing graphs as

networks like airline flights, how the Intern et is connected, or social

network connectivity on Facebook. They are also popular in NLP and

machine learning to form networks. munotes.in

## Page 89

Graph Algorithms

89 The course is designed to develop skills to design and analyze simple

linear and non linear data structures.

4.1 WHAT IS GRAPHS ?

Graph Algorithms: Introduction, Glossary, Applications of Graphs,

Graph

Graph Algorithms

In this article, you would be learning a brief explanation of some of the

most used graph algorithms, which have massive applications in today's

words. Graphs cove r most high -level data structure techniques that one

experiences while implementing them and to know which graph algorithm

is best for the moment effectively is what you would be learning here.

First, let's get a clear idea from the very basics about graph s.

4.2 WHAT IS A GRAPH ?

A graph is a unique data structure in programming that consists of finite

sets of nodes or vertices and a set of edges that connect these vertices to

them. At this moment, adjacent vertices can be called those vertices that

are conn ected to the same edge with each other. In simple terms, a graph is

a visual representation of vertices and edges sharing some connection or

relationship. Although there are plenty of graph algorithms that you might

have been familiar with, only some of th em are put to use. The reason for

this is simple as the standard graph algorithms are designed in such a way

to solve millions of problems with just a few lines of logically coded

technique. To some extent, one perfect algorithm is solely optimized to

achieve such efficient results.

4.2.1 Types of Graphs

There are various types of graph algorithms that you would be looking at

in this article but before that, let's look at some types of terms to imply the

fundamental variations between them. munotes.in

## Page 90

Fundamental of

Algorithms

90 Order: Order de fines the total number of vertices present in the graph.

Size: Size defines the number of edges present in the graph.

Self-loop: It is the edges that are connected from a vertex to itself.

Isolated vertex: It is the vertex that is not connected to any othe r vertices

in the graph.

Vertex degree: It is defined as the number of edges incident to a vertex in

a graph.

Weighted graph: A graph having value or weight of vertices.

Unweighted graph: A graph having no value or weight of vertices.

Directed graph: A gra ph having a direction indicator.

Undirected graph: A graph where no directions are defined.

Let's now carry forward the main discussion and learn about different

types of graph algorithms.

4.2.2 Breadth -First Search

Traversing or searching is one of the most used operations that are

undertaken while working on graphs. Therefore, in breadth -first-

search (BFS), you start at a particular vertex, and the algorithm tries to

visit all the neighbors at the given depth before moving on to the next

level of trave rsal of vertices. Unlike trees, graphs may contain cyclic paths

where the first and last vertices are remarkably the same always. Thus, in

BFS, you need to keep note of all the track of the vertices you are visiting.

To implement such an order, you use a q ueue data structure which First -in,

First-out approach. To understand this, see the image given below. munotes.in

## Page 91

Graph Algorithms

91

Algorithm

1. Start putting anyone vertices from the graph at the back of the queue.

2. First, move the front queue item and add it to the list of the visited

node.

3. Next, create nodes of the adjacent vertex of that list and add them

which have not been visited yet.

4. Keep repeating steps two and three until the queue is found to be

empty.

Pseudocode

1. Set all nodes to "not visited";

2. q = new Queue();

3. q.enqueue(i nitial node);

4. while ( q ? empty ) do

5. {

6. x = q.dequeue();

7. if ( x has not been visited )

8. {

9. visited[x] = true; // Visit node x !

10.

11. for ( every edge (x, y) /* we are using all edges ! */ )

12. if ( y has not been visited )

13. q.enqu eue(y); // Use the edge (x,y) !!! munotes.in

## Page 92

Fundamental of

Algorithms

92 14. }

15. }

Complexity: 0(V+E) where V is vertices and E is edges.

Applications

BFS algorithm has various applications. For example, it is used to

determine the shortest path and minimum spanning tree. It is also used

in web crawlers to creates web page indexes. It is also used as powering

search engines on social media networks and helps to find out peer -to-peer

networks in BitTorrent.

4.2.4 Depth -first search

In depth -first-search (DFS), you start by particularly from the vertex and

explore as much as you along all the branches before backtracking. In

DFS, it is essential to keep note of the tracks of visited nodes, and for this,

you use stack data structure.

Algorithm

1. Start by putting one of the vertexes of the grap h on the stack's top.

2. Put the top item of the stack and add it to the visited vertex list.

3. Create a list of all the adjacent nodes of the vertex and then add those

nodes to the unvisited at the top of the stack.

4. Keep repeating steps 2 and 3, and the stack becomes empty.

Pseudocode

1. DFS(G,v) ( v is the vertex where the search starts )

2. Stack S := {}; ( start with an empty stack )

3. for each vertex u, set visited[u] := false ; munotes.in

## Page 93

Graph Algorithms

93 4. push S, v;

5. while (S is not empty) do

6. u := pop S;

7. if (not visited[u]) then

8. visited[u] := true;

9. for each unvisited neighbour w of uu

10. push S, w;

11. end if

12. end while

13. END DFS()

Applications

DFS finds its application when it comes to finding paths between two

vertices and detecting cycles. Also, topological sorting can b e done using

the DFS algorithm easily. DFS is also used for one -solution puzzles.

Dijkstra's shortest path algorithm

Dijkstra's shortest path algorithm works to find the minor path from one

vertex to another. The sum of the vertex should be such that their sum of

weights that have been traveled should output minimum. The shortest path

algorithm is a highly curated algorithm that works on the concept of

receiving efficiency as much as possible. Consider the below diagram.

Algorithm

1. Set all the vertices to infinity, excluding the source vertex.

2. Push the source in the form (distance, vertex) and put it in the min -

priority queue.

3. From the priority, queue pop out the minimum distant vertex from the

source vertex. munotes.in

## Page 94

Fundamental of

Algorithms

94 4. Update the distance after popping out the minimu m distant vertex and

calculate the vertex distance using (vertex distance + weight <

following vertex distance).

5. If you find that the visited vertex is popped, move ahead without using

it.

6. Apply the steps until the priority queue is found to be empty.

Pseu docode

1. function dijkstra(G, S)

2. for each vertex V in G

3. distance[V] <- infinite

4. previous[V] <- NULL

5. If V != S, add V to Priority Queue Q

6. distance[S] <- 0

7. while Q IS NOT EMPTY

8. U <- Extract MIN from Q

9. for each unvisited neighbour V of U

10. temp Distance <- distance[U] + edge_weight(U, V)

11. if tempDistance < distance [V]

12. distance[V] <- tempDistance

13. previous[V] <- U

14. return distance[], previous[]

Applications

Dijkstra's shortest path algorithm is used in finding the distance of travel

from on e location to another, like Google Maps or Apple Maps. In

addition, it is highly used in networking to outlay min -delay path problems

and abstract machines to identify choices to reach specific goals like the

number game or move to win a match.

Cycle detec tion

A cycle is defined as a path in graph algorithms where the first and last

vertices are usually considered. For example, if you start from a vertex and

travel along a random path, you might reach the exact point where you

eventually started. Hence, thi s forms a chain or cyclic algorithm to cover

along with all the nodes present on traversing. Therefore, cycle detection

is based on detecting this kind of cycle. Consider the below image. munotes.in

## Page 95

Graph Algorithms

95

Pseudocode

1. Brent's Cycle Algorithm Example

2. def brent(f, x0):

3. # main phase: search successive powers of two

4. power = lam = 1

5. tortoise = x0

6. hare = f(x0) # f(x0) is the element/node next to x0.

7. while tortoise != hare:

8. if power == lam: # time to start a new power of two?

9. tortoise = hare

10. power *= 2

11. lam = 0

12. hare = f(hare)

13. lam += 1

14. # Find the position of the first repetition of length ?

15. tortoise = hare = x0

16. for i in range(lam):

17. # range(lam) produces a list with the values 0, 1, ... , lam-1

18. hare = f(hare)

19. # The distance between the hare and tortoise is now ?.

20. # Next, the hare and tortoise move at same speed until they agree

21. mu = 0

22. while tortoise != hare: munotes.in

## Page 96

Fundamental of

Algorithms

96 23. tortoise = f(tortoise)

24. hare = f(hare)

25. mu += 1

26. return lam, mu

Applications

Cyclic algorithms are used in message -based distribu ted systems and

large -scale cluster processing systems. It is also mainly used to detect

deadlocks in the concurrent system and various cryptographic applications

where the keys are used to manage the messages with encrypted values.

4.2.4 Minimum Spaning Trees

A minimum spanning is defined as a subset of edges of a graph having no

cycles and is well connected with all the vertices so that the minimum sum

is availed through the edge weights. It solely depends on the cost of the

spanning tree and the minimu m span or least distance the vertex covers.

There can be many minimum spanning trees depending on the edge

weight and various other factors.

Pseudocode

1. Prim's Algorithm Example

2. ReachSet = {0};

3. UnReachSet = {1, 2, ..., N-1};

4. SpanningTree = {};

5. while ( UnReachSet ? empty )

6. {

7. Find edge e = (x, y) such that:

8. 1. x ? ReachSet

9. 2. y ? UnReachSet

10. 3. e has smallest cost munotes.in

## Page 97

Graph Algorithms

97 11. SpanningTree SpanningTree = SpanningTree ? {e};

12. ReachSet ReachSet = ReachSet ? {y};

13. UnReachSet UnReachSet = UnReachSet - {y};

14. }

Applications

Minimum spanning tree finds its application in the network design and is

popularly used in traveling salesman problems in a data structure. It can

also be used to find the minimum -cost weighted perfect matching and

multi -terminal minimum cut problems. MST also finds its application in

the field of image and handwriting recognition and cluster analysis.

Applications of Graph Data Structure

A graph is a non -linear data structure, which consists of vertices(or nodes)

connected by edge s(or arcs) where edges may be directed or undirected.

Thus the development of algorithms to handle graphs is of major interest

in the field of computer science.

Three Applications of Graphs in the area of computer engineering:

1. The applications of graph split broadly into three categories:

a) First, analysis to determine structural properties of a network, such as

the distribution of vertex degrees and the diameter of the graph. A vast

number of graph measures exist.

b) Second, analysis to find a measurable quantity within the network, for

example, for a transportation network, the level of vehicular flow within

any portion of it.

c) Third, analysis of dynamic properties of network. Map of a coun try can

be represented using a graph. Road network, Air network or rail network

can be represented using a graph. Connection among routers in a

communication network can be represented using a graph. Routing of a

packet between two communicating nodes can be done through the

shortest path. munotes.in

## Page 98

Fundamental of

Algorithms

98 2. Graph theory is useful in biology and conservation efforts where a

vertex can represent regions where certain species exist and the edges

represent migration paths, or movement between the regions. This

information is important when looking at breeding patterns or tracking the

spread of disease.

3. Different activities of a project can be represented using a graph. This

graph can be useful in project scheduling.

Applications of Graphs to Solve Real -World Problems

Graph s are widely used in many fields. Let us take some real -life

examples and solve them through graphs.

Ten Applications of Graphs

Since graphs are powerful abstractions, they can be essential in

modelling data. Given below are some instances for the applicat ions of

graphs.

1. Social network graphs: Graphs show who knows who, how they

communicate with one other, and how they impact each other, as

well as other social structure relationships. The Facebook graph

showing who follows whom or who sends friend invitati ons to

whom is an example. These can be used to figure out how

information spreads, how topics get popular, how communities

grow, and even who could be a good fit for that person.

2. Graphs in epidemiology: Nowadays, the spread of disease is

widespread worldw ide. Analysing such graphs has become an

essential component in understanding and controlling the spread of

diseases.

3. Utility graphs: The power grid, the Internet, and the water

network are graphs with vertices representing connection points

and edges repr esenting the cables or pipes that connect them.

Understanding the reliability of such utilities under failure or

assault and lowering the costs of building infrastructure that meets

desired needs requires analysing the features of these graphs.

4. Transportat ion networks: In transportation network graphs,

vertices are intersections in road networks, and edges are the road

segments that connect them. Vertices are stops in public transit

networks, and edges are the links that connect them. Many map

systems, such as Google Maps, Bing Maps, and Apple iOS 6 maps,

employ such networks to determine the optimal paths between

sites. They’re also utilised to figure out how traffic flows and how

traffic lights work.

5. Constraint graphs: Graphs are often used to represent co nstraints

among items. For example, the GSM network for cell phones

consists of a collection of overlapping cells. Any pair of cells that

overlap must operate at different frequencies. These constraints can munotes.in

## Page 99

Graph Algorithms

99 be modelled as a graph where the cells are vertic es and edges are

placed between overlapping cells.

6. Dependence graphs: Graphs can be used to represent

dependencies or precedences among items. Such graphs are often

used in large projects in laying out what components rely on other

components and used to m inimise the total time or cost to

completion while abiding by the dependences.

7. Document link graphs: The most well -known example is the

web’s link graph, in which each web page is a vertex, and a

directed edge connects each hyperlink. Link graphs are used to

assess the relevancy of online pages, the most acceptable sources

of information, and good link sites, among other things.

8. Finite element meshes: Many models of physical systems in

engineering entail partitioning space into discrete pieces, such as

the flow of air over a vehicle or plane wing, the spread of

earthquakes through the ground, or the structural vibrations of a

building. The elements and the connections between them make up

a graph known as a finite element mesh.

9. Robot planning: The edges repr esent possible transitions between

states, whereas the vertices represent various states for the robot.

This requires approximating continuous motion as a sequence of

discrete steps. Such graph plans are used to plan paths for

autonomous vehicles, for exam ple.

10. Graphs in compilers: Graphs are used extensively in compilers.

They can be used for type inference, so -called data flow analysis,

register allocation, and many other purposes. They are also used in

specialised compilers, such as query optimisation in database

languages.

Graph Representation

In this article, we will discuss the ways to represent the graph. By Graph

representation, we simply mean the technique to be used to store some

graph into the computer's memory.

A graph is a data structure that con sist a sets of vertices (called nodes) and

edges. There are two ways to store Graphs into the computer's memory:

o Sequential representation (or, Adjacency matrix representation)

o Linked list representation (or, Adjacency list representation)

In sequential re presentation, an adjacency matrix is used to store the

graph. Whereas in linked list representation, there is a use of an adjacency

list to store the graph.

In this tutorial, we will discuss each one of them in detail munotes.in

## Page 100

Fundamental of

Algorithms

100 Now, let's start discussing the ways o f representing a graph in the data

structure.

Sequential representation

In sequential representation, there is a use of an adjacency matrix to

represent the mapping between vertices and edges of the graph. We can

use an adjacency matrix to represent the un directed graph, directed graph,

weighted directed graph, and weighted undirected graph.

If adj[i][j] = w, it means that there is an edge exists from vertex i to vertex

j with weight w.

An entry A ij in the adjacency matrix representation of an undirected gr aph

G will be 1 if an edge exists between V i and V j. If an Undirected Graph G

consists of n vertices, then the adjacency matrix for that graph is n x n, and

the matrix A = [aij] can be defined as -

aij = 1 {if there is a path exists from V i to V j}

aij = 0 {Otherwise}

It means that, in an adjacency matrix, 0 represents that there is no

association exists between the nodes, whereas 1 represents the existence of

a path between two edges.

If there is no self -loop present in the graph, it means that the diagonal

entries of the adjacency matrix will be 0.

Now, let's see the adjacency matrix representation of an undirected graph.

In the above figure, an image shows the mapping among the vertices (A,

B, C, D, E), and this mapping is represented by using the adjace ncy

matrix.

There exist different adjacency matrices for the directed and undirected

graph. In a directed graph, an entry A ij will be 1 only when there is an

edge directed from V i to V j.

Adjacency matrix for a directed graph

In a directed graph, edges repr esent a specific path from one vertex to

another vertex. Suppose a path exists from vertex A to another vertex B; it

means that node A is the initial node, while node B is the terminal node. munotes.in

## Page 101

Graph Algorithms

101 Consider the below -directed graph and try to construct the adjace ncy

matrix of it.

In the above graph, we can see there is no self -loop, so the diagonal entries

of the adjacent matrix are 0.

Adjacency matrix for a weighted directed graph

It is similar to an adjacency matrix representation of a directed graph

except th at instead of using the '1' for the existence of a path, here we have

to use the weight associated with the edge. The weights on the graph edges

will be represented as the entries of the adjacency matrix. We can

understand it with the help of an example. C onsider the below graph and

its adjacency matrix representation. In the representation, we can see that

the weight associated with the edges is represented as the entries in the

adjacency matrix.

ADVERTISING

In the above image, we can see that the adjace ncy matrix representation of

the weighted directed graph is different from other representations. It is

because, in this representation, the non -zero values are replaced by the

actual weight assigned to the edges.

Adjacency matrix is easier to implement an d follow. An adjacency matrix

can be used when the graph is dense and a number of edges are large.

Though, it is advantageous to use an adjacency matrix, but it consumes

more space. Even if the graph is sparse, the matrix still consumes the same

space. munotes.in

## Page 102

Fundamental of

Algorithms

102 Linked list representation

An adjacency list is used in the linked representation to store the Graph in

the computer's memory. It is efficient in terms of storage as we only have

to store the values for edges.

Let's see the adjacency list representation of an undirected graph.

In the above figure, we can see that there is a linked list or adjacency list

for every node of the graph. From vertex A, there are paths to vertex B

and vertex D. These nodes are linked to nodes A in the given adjacency

list.

An adjac ency list is maintained for each node present in the graph, which

stores the node value and a pointer to the next adjacent node to the

respective node. If all the adjacent nodes are traversed, then store the

NULL in the pointer field of the last node of th e list.

The sum of the lengths of adjacency lists is equal to twice the number of

edges present in an undirected graph.

Now, consider the directed graph, and let's see the adjacency list

representation of that graph.

For a directed graph, the sum of the lengths of adjacency lists is equal to

the number of edges present in the graph.

Now, consider the weighted directed graph, and let's see the adjacency list

representation of that graph. munotes.in

## Page 103

Graph Algorithms

103

In the case of a weighted directed graph, each node contains an ext ra field

that is called the weight of the node.

In an adjacency list, it is easy to add a vertex. Because of using the linked

list, it also saves space.

Implementation of adjacency matrix representation of Graph

Now, let's see the implementation of adjacen cy matrix representation of

graph in C.

In this program, there is an adjacency matrix representation of an

undirected graph. It means that if there is an edge exists from vertex A to

vertex B, there will also an edge exists from vertex B to vertex A.

Here, there are four vertices and five edges in the graph that are non -

directed.

1. /* Adjacency Matrix representation of an undirected graph in C */

2.

3. #include

4. #define V 4 /* number of vertices in the graph */

5.

6. /* function to initialize the matrix to zero */

7. void init(int arr[][V]) {

8. int i, j;

9. for (i = 0; i < V; i++)

10. for (j = 0; j < V; j++)

11. arr[i][j] = 0;

12. }

13.

14. /* function to add edges to the graph */

15. void insertEdge( int arr[][V], int i, int j) { munotes.in

## Page 104

Fundamental of

Algorithms

104 16. arr[i][j] = 1;

17. arr[j][i] = 1;

18. }

19.

20. /* function to print the matrix elements */

21. void printAdjMatrix( int arr[][V]) {

22. int i, j;

23. for (i = 0; i < V; i++) {

24. printf( "%d: ", i);

25. for (j = 0; j < V; j++) {

26. printf( "%d ", arr[i][j]);

27. }

28. printf( "\n");

29. }

30. }

31.

32. int main() {

33. int adjMatrix[V][V];

34.

35. init(adjMatrix);

36. insertEdge(adjMatrix, 0, 1);

37. insertEdge(adjMatrix, 0, 2);

38. insertEdge(adjMatrix, 1, 2);

39. insertEdge(adjMatrix, 2, 0);

40. insertEdge(adjMatrix, 2, 3);

41.

42. printAdjMatrix(adjMatrix);

43.

44. return 0; munotes.in

## Page 105

Graph Algorithms

105 45. }

Outpu t:

After the execution of the above code, the output will be -

Implementation of adjacency list representation of Graph

Now, let's see the implementation of adjacency list representation of graph

in C.

In this program, there is an adjacency list represen tation of an undirected

graph. It means that if there is an edge exists from vertex A to vertex B,

there will also an edge exists from vertex B to vertex A.

1. /* Adjacency list representation of a graph in C */

2. #include

3. #include

4.

5. /* structure to represent a node of adjacency list */

6. struct AdjNode {

7. int dest;

8. struct AdjNode* next;

9. };

10.

11. /* structure to represent an adjacency list */

12. struct AdjList {

13. struct AdjNode* head;

14. };

15.

16. /* structure to represent the graph */

17. struct Graph {

18. int V; /*number of vertices in the graph*/

19. struct AdjList* array; munotes.in

## Page 106

Fundamental of

Algorithms

106 20. };

21.

22.

23. struct AdjNode* newAdjNode( int dest)

24. {

25. struct AdjNode* newNode = (struct AdjNode*)malloc( sizeof (struct

AdjNode));

26. newNode ->dest = dest;

27. newNode ->next = NULL;

28. return newNode;

29. }

30.

31. struct Graph* createGraph( int V)

32. {

33. struct Graph* graph = (struct Graph*)malloc( sizeof (struct Graph));

34. graph ->V = V;

35. graph -

>array = (struct AdjList*)malloc(V * sizeof (struct AdjList));

36.

37. /* Initiali ze each adjacency list as empty by making head as NUL

L */

38. int i;

39. for (i = 0; i < V; ++i)

40. graph ->array[i].head = NULL;

41. return graph;

42. }

43.

44. /* function to add an edge to an undirected graph */

45. void addEdge( struct Graph* graph , int src, int dest)

46. { munotes.in

## Page 107

Graph Algorithms

107 47. /* Add an edge from src to dest. The node is added at the beginnin

g */

48. struct AdjNode* check = NULL;

49. struct AdjNode* newNode = newAdjNode(dest);

50.

51. if (graph ->array[src].head == NULL) {

52. newNode ->next = graph ->array[src].head;

53. graph ->array[src].head = newNode;

54. }

55. else {

56.

57. check = graph ->array[src].head;

58. while (check ->next != NULL) {

59. check = check ->next;

60. }

61. // graph ->array[src] .head = newNode;

62. check ->next = newNode;

63. }

64.

65. /* Since graph is undirected, add an edge from dest to src also */

66. newNode = newAdjNode(src);

67. if (graph ->array[dest].head == NULL) {

68. newNode ->next = graph ->array[dest] .head;

69. graph ->array[dest].head = newNode;

70. }

71. else {

72. check = graph ->array[dest].head;

73. while (check ->next != NULL) {

74. check = check ->next;

75. } munotes.in

## Page 108

Fundamental of

Algorithms

108 76. check ->next = newNode;

77. }

78. }

79. /* function to print the adjacency list representation of graph*/

80. void print( struct Graph* graph)

81. {

82. int v;

83. for (v = 0; v < graph ->V; ++v) {

84. struct AdjNode* pCrawl = graph ->array[v].head;

85. printf( "\n The Adjacency list of vertex %d is: \n head ", v);

86. while (pCrawl) {

87. printf( "-> %d", pCrawl ->dest);

88. pCrawl = pCrawl ->next;

89. }

90. printf( "\n");

91. }

92. }

93.

94. int main()

95. {

96.

97. int V = 4;

98. struct Graph* g = createGraph( V);

99. addEdge(g, 0, 1);

100. addEdge(g, 0, 3);

101. addEdge(g, 1, 2);

102. addEdge(g, 1, 3);

103. addEdge(g, 2, 4);

104. addEdge(g, 2, 3); munotes.in

## Page 109

Graph Algorithms

109 105. addEdge(g, 3, 4);

106. print(g);

107. return 0;

108. }

Output:

In the output, we will see the adjacen cy list representation of all the

vertices of the graph. After the execution of the above code, the output

will be -

Conclusion

Here, we have seen the description of graph representation using the

adjacency matrix and adjacency list. We have also seen th eir

implementations in C programming language.

So, that's all about the article. Hope, it will be helpful and informative to

you.

Graph traversal

In this section we will see what is a graph data structure, and the traversal

algorithms of it.

The graph i s one non -linear data structure. That is consists of some nodes

and their connected edges. The edges may be director or undirected. This

graph can be represented as G(V, E). The following graph can be

represented as G({A, B, C, D, E}, {(A, B), (B, D), (D, E), (B, C), (C, A)})

The graph has two types of traversal algorithms. These are called the

Breadth First Search and Depth First Search. munotes.in

## Page 110

Fundamental of

Algorithms

110 Breadth First Search (BFS)

The Breadth First Search (BFS) traversal is an algorithm, which is used to

visit all of the nodes of a given graph. In this traversal algorithm one node

is selected and then all of the adjacent nodes are visited one by one. After

completing all of the adjacent vertices, it moves further to check another

vertices and checks its adjacent vertices again.

Algorithm

bfs(vertices, start)

Input: The list of vertices, and the start vertex.

Output: Traverse all of the nodes, if the graph is connected.

Begin

define an empty queue que

at first mark all nodes status as unvisited

add the start vertex into the que

while que is not empty, do

delete item from que and set to u

display the vertex u

for all vertices 1 adjacent with u, do

if vertices[i] is unvisited, then

mark vertices[i] as temporarily visited

add v into the queue

mark

done

mark u as completely visited

done

End

Depth First Search (DFS)

The Depth First Search (DFS) is a graph traversal algorithm. In this

algorithm one starting vertex is given, and when an adjacent v ertex is

found, it moves to that adjacent vertex first and try to traverse in the same

manner. munotes.in

## Page 111

Graph Algorithms

111 Algorithm

dfs(vertices, start)

Input: The list of all vertices, and the start node.

Output: Traverse all nodes in the graph.

Begin

initially make the state to unvisited for all nodes

push start into the stack

while stack is not empty, do

pop element from stack and set to u

display the node u

if u is not visited, then

mark u as visited

for all nodes i connected to u, do

if ith vertex is unvisited, then

push ith vertex into the stack

mark ith vertex as visited

done

done

End

4.6 TOPOLOGICAL SORT

The topological sort algorithm takes a directed graph and returns an

array of the nodes where each node appears before all the nodes it points

to.

Since node 1 points to nodes 2 and 3, node 1 appears before them in the

ordering. And, since nodes 2 and 3 both point to node 4, they appear

before it in the ordering.

So [1, 2, 3, 4, 5] would be a topological ordering of the graph.

Can a graph have more than one valid topological ordering? Yep! In the

example above, [1, 3, 2, 4, 5] works too. munotes.in

## Page 112

Fundamental of

Algorithms

112 Cyclic Graphs

Look at this directed graph with a cycle:

The cycle creates an impossible set o f constraints —B has to be

before and after D in the ordering.

As a rule, cyclic graphs don't have valid topological orderings.

The Algorithm

How can we produce a topological ordering for this directed graph?

Well, let's focus on the first node in the topol ogical ordering. That node

can't have any incoming directed edges; it must have an indegree ↴ of

zero.

Why?

Because if it had incoming directed edges, then the nodes pointing to it

would have to come first.

So, we'll find a node with an indegree of zero and add it to the topological

ordering.

That covers the first node in our topological ordering . What about the next

one?

Once a node is added to the topological ordering, we can take the node,

and its outgoing edges, out of the graph.

Then, we can repeat our earlier approach: look for any node with an

indegree of zero and add it to the ordering.

This is a common algorithm design pattern:

1. Figure out how to get the first thing.

2. Remove the first thing from the problem.

3. Repeat.

Note: this isn't the only way to produce a topological ordering.

Implementation

We'll use the strategy we outlined above:

1. Ident ify a node with no incoming edges.

2. Add that node to the ordering.

3. Remove it from the graph.

4. Repeat. munotes.in

## Page 113

Graph Algorithms

113 We'll keep looping until there aren't any more nodes with indegree zero.

This could happen for two reasons:

There are no nodes left. We've taken all of them out of the graph and

added them to the topological ordering.

There are some nodes left, but they all have incoming edges. This

means the graph has a cycle, and no topological ordering exists.

One small tweak. Instead of actually removing the nodes from th e graph

(and destroying our input!), we'll use a hash map to track each node's

indegree. When we add a node to the topological ordering, we'll

decrement the indegree of that node's neighbors, representing that those

nodes have one fewer incoming edges.

Let's code it up!

deftopological_sort( digraph ):

# digraph is a dictionary:

# key: a node

# value: a set of adjacent neighboring nodes

# construct a dictionary mapping nodes to their

# indegrees

indegrees ={node :0for node in digraph }

for node in digraph :

forneighbor in digraph [node ]:

indegrees [neighbor ]+=1

# track nodes with no incoming edges

nodes_with_no_incoming_edges =[]

for node in digraph :

if indegrees [node ]==0:

nodes_with_no_incoming_edges .append (node )

# initially, no nodes in our orderi ng

topological_ordering =[]

# as long as there are nodes with no incoming edges

# that can be added to the ordering munotes.in

## Page 114

Fundamental of

Algorithms

114 while len(nodes_with_no_incoming_edges )>0:

# add one of those nodes to the ordering

node =nodes_with_no_incoming_edges .pop()

topologi cal_ordering .append (node )

# decrement the indegree of that node's neighbors

forneighbor in digraph [node ]:

indegrees [neighbor ]-=1

if indegrees [neighbor ]==0:

nodes_with_no_incoming_edges .append (neighbor )

# we've run out of nodes with no incoming e dges

# did we add all the nodes or find a cycle?

iflen(topological_ordering )==len(digraph ):

return topological_ordering # got them all

else:

raise Exception ("Graph has a cycle! No topological ordering exists.")

Time and Space Complexity

Breaking the algorithm into chunks, we:

Determine the indegree for each node. This is O(M) time (where M is

the number of edges), since this involves looking at each directed edge

in the graph once.

Find nodes with no incoming edges. This is a simple loop through all

the nodes with some number of constant -time appends. O(N) time

(where N is the number of nodes).

Add nodes until we run out of nodes with no incoming edges. This

loop could run once for every node —O(N) times. In the body, we:

o Do two constant -time operations on an ar ray to add a node to the

topological ordering.

o Decrement the indegree for each neighbor of the node we added. Over

the entire algorithm, we'll end up doing exactly one decrement for

each edge, making this step O(M) time overall .

Check if we included all no des or found a cycle. This is a

fast (1)O(1) comparison. munotes.in

## Page 115

Graph Algorithms

115 All together, the time complexity is O(M+N).

That's the fastest time we can expect, since we'll have to look at all the

nodes and edges at least once.

What about space complexity? Here are the data structures we created:

indegrees —this has one entry for each node in the graph, so it's

O(N) space.

nodesWithNoIncomingEdges —in a graph with no edges, this would

start out containing every node, so it's O(N) space in the worst case.

Topological Ordering —in a graph with no cycles, this will eventually

have every node. O(N) space.

All in all, we have three structures and they're all O(N) space. Overall

space complexity: O(N).

This is the best space complexity we can expect, since we must allocate a

return arra y which costs O(N) space itself.

Uses

The most common use for topological sort is ordering steps of a

process where some the steps depend on each other.

As an example, when making chocolate bundt cake,

The ingredients have to be mixed before going in the b undt pan.

The bundt pan has to be greased and floured before the batter can be

poured in.

The oven has to be preheated before the cake can bake.

The cake has to be baked before it cools.

The cake has to cool before it can be iced.

This process can be repre sented as a directed graph. Each step is a

node, and we'll add directed edges between nodes to represent that one

step has to be done before another. munotes.in

## Page 116

Fundamental of

Algorithms

116

Once we have our dependencies represented using a directed graph, we

can use topological sort to provide a valid ordering to tackle all the

steps.

munotes.in

## Page 117

Graph Algorithms

117 Topological sorting of a graph follows the algorithm of ordering the

vertices linearly so that each directed graph having vertex ordering ensures

that the vertex comes before it. Users can understand it more acc urately by

looking at the sample image given below.

In the above example, you can visualize the ordering of the unsorted graph

and topologically sorted graph. The topologically sorted graph ensures to

sort vertex that comes in the pathway.

Pseudocode

1. topological_sort(N, adj[N][N])

2. T = []

3. visited = []

4. in_degree = []

5. for i = 0 to N

6. in_degree[i] = visited[i] = 0

7. for i = 0 to N

8. for j = 0 to N

9. if adj[i][j] is TRUE

10. in_degree[j] = in_degree[j] + 1

11. for i = 0 to N

12. if in_degree[i] is 0

13. enque ue(Queue, i)

14. visited[i] = TRUE

15. while Queue is not Empty

16. vertex = get_front (Queue)

17. dequeue(Queue)

18. T.append(vertex) munotes.in

## Page 118

Fundamental of

Algorithms

118 19. for j = 0 to N

20. if adj[vertex][j] is TRUE and visited[j] is FALSE

21. in_degree[j] = in_degree[j] - 1

22. if in_degree[j] is 0

23. enqueue(Queue, j)

24. visited[j] = TRUE

25. return T

Application

Topological sorting covers the room for application in Kahn's and DFS

algori thms. In real -life applications, topological sorting is used in

scheduling instructions and serialization of data. It is also popularly used

to determine the tasks that are to be compiled and used to resolve

dependencies in linkers.

Graph coloring

Graph co loring algorithms follow the approach of assigning colors to the

elements present in the graph under certain conditions. The conditions are

based on the techniques or algorithms. Hence, vertex coloring is a

commonly used coloring technique followed here. F irst, in this method,

you try to color the vertex using k color, ensuring that two adjacent

vertexes should not have the same color. Other method includes face

coloring and edge coloring. Both of these methods should also ensure that

no edge or face should be inconsequent color. The coloring of the graph is

determined by knowing the chromatic number, which is also the smaller

number of colors needed. Consider the below image to understand how it

works.

Pseudocode

1. #include

2. #include

3. using namespace std; munotes.in

## Page 119

Graph Algorithms

119 4. // A class that represents an undirected graph

5. class Graph

6. {

7. int V; // No. of vertices

8. list *adj; // A dynamic array of adjacency lists

9. public:

10. // Constructor and destructor

11. Graph(int V) { this->VV = V; adj = new list[V]; }

12. ~Graph() { delete [] adj; }

13. // function to add an edge to graph

14. void addEdge(int v, int w);

15. // Prints greedy coloring of the vertices

16. void greedyColoring();

17. };

18. void Graph::addEdg e(int v, int w)

19. {

20. adj[v].push_back(w);

21. adj[w].push_back(v); // Note: the graph is undirected

22. }

23. // Assigns colors (starting from 0) to all vertices and prints

24. // the assignment of colors

25. void Graph::greedyColoring()

26. {

27. int result[V];

28. // Assign the first color to first vertex

29. result[0] = 0;

30. // Initialize remaining V-1 vertices as unassigned

31. for (int u = 1; u < V; u++)

32. result[u] = -1; // no color is assigned to u munotes.in

## Page 120

Fundamental of

Algorithms

120 33. // A temporary array to store the available colors. True

34. // value of available[cr] would mean that the color cr is

35. // assigned to one of its adjacent vertices

36. bool available[V];

37. for (int cr = 0; cr < V; cr++)

38. available[cr] = false;

39. // Assign colors to remaining V-1 vertices

40. for (int u = 1; u < V; u++)

41. {

42. // Process all adjacent vertices and flag their colors

43. // as unavailable

44. list::iterator i;

45. for (i = adj[u].begin(); i != adj[u].end() ; ++i)

46. if (result[*i] != -1)

47. available[result[*i]] = true;

48. // Find the first available color

49. int cr;

50. for (cr = 0; cr < V; cr++)

51. if (available[cr] == false)

52. break ;

53. result[u] = cr; // Assign the found color

54. // Reset the values back to false for the next iteration

55. for (i = adj[u].begin(); i != adj[u].end(); ++i)

56. if (result[*i] != -1)

57. available[result[*i]] = false;

58. }

59. // print the result

60. for (int u = 0; u < V; u++)

61. cout << "Vertex " << u << " ---> Color " munotes.in

## Page 121

Graph Algorithms

121 62. << result [u] << endl;

63. }

64. // Driver program to test above function

65. int main()

66. {

67. Graph g1(5);

68. g1.addEdge(0, 1);

69. g1.addEdge(0, 2);

70. g1.addEdge(1, 2);

71. g1.addEdge(1, 3);

72. g1.addEdge(2, 3);

73. g1.addEdge(3, 4);

74. cout << "Coloring of graph 1 \n";

75. g1.greedyColoring();

76. Graph g2(5);

77. g2.addEdge(0, 1);

78. g2.addEdge(0, 2);

79. g2.addEdge(1, 2);

80. g2.addEdge(1, 4);

81. g2.addEdge(2, 4);

82. g2.addEdge(4, 3);

83. cout << "\nColoring of graph 2 \n";

84. g2.greedyColoring();

85. return 0;

86. }

Application

Graph coloring has vast applications in data structures as well as in

solving real -life problems. For example, it is used in timetable scheduling

and assigning radio frequencies for mobile. It is also used in Sudoko and

to check if the given graph is bipartite. Graph coloring can also be used in

geographical maps to mark countries and states in different colors. munotes.in

## Page 122

Fundamental of

Algorithms

122 Maximum flow

The maximum flow algorithm is usually treated as a problem -solving

algorithm where the graph is modeled like a network flow infrastructure.

Hence, the maximum flow is determi ned by finding the path of the flow

that has the maximum flow rate. The maximum flow rate is determined

by augmenting paths which is the total flow -based out of source node

equal to the flow in the sink node. Below is the illustration for the same.

1. functio n: DinicMaxFlow(Graph G,Node S,Node T):

2. Initialize flow in all edges to 0, F = 0

3. Construct level graph

4. while (there exists an augmenting path in level graph):

5. find blocking flow f in level graph

6. FF = F + f

7. Update level graph

8. return F

Applications

Like you, the maximum flow problem covers applications of popular

algorithms like the Ford -Fulkerson algorithm, Edmonds -Karp algorithm,

and Dinic's algorithm, like you saw in the pseudocode given above. In rea l

life, it finds its applications in scheduling crews in flights and image

segmentation for foreground and background. It is also used in games like

basketball, where the score is set to a maximum estimated value having

the current division leader.

Matchin g

A matching algorithm or technique in the graph is defined as the edges

that no common vertices at all. Matching can be termed maximum

matching if the most significant number of edges possibly matches with as

many vertices as possible. It follows a specif ic approach for determining

full matches, as shown in the below image. munotes.in

## Page 123

Graph Algorithms

123

Applications

Matching is used in an algorithm like the Hopcroft -Karp algorithm and

Blossom algorithm. It can also be used to solve problems using a

Hungarian algorithm that covers con cepts of matching. In real -life

examples, matching can be used resource allocation and travel

optimization and some problems like stable marriage and vertex cover

problem.

Conclusion

In this article, you came across plenty of graph coloring algorithms and

techniques that find their day -to-day applications in all instances of real

life. You learned how to implement them according to situations, and

hence the pseudo code helped you process the information strategically

and efficiently. Graph algorithms are co nsidered an essential aspect in the

field confined not only to solve problems using data structures but also in

general tasks like Google Maps and Apple Maps. However, a beginner

might find it hard to implement Graph algorithms because of their

complex nat ure. Hence, it is highly recommended to go through this

article since it covers everything from scratch.

Shortest Path Algorithms

Dijkstra's Algorithm finds the shortest path between a given node (which

is called the "source node") and all other nodes in a graph. This algorithm

uses the weights of the edges to find the path that minimizes the total

distance (weight) between the source node and all other nodes.

What is Dijkstra’s Algorithm?

Dijkstra’s algorithm is a popular algorithms for solving many single -

source shortest path problems having non -negative edge weight in the

graphs i.e., it is to find the shortest distance between two vertices on a

graph. It was conc eived by Dutch computer scientist Edsger W.

Dijkstra in 1956.

The algorithm maintains a set of visited vertices and a set of unvisited

vertices. It starts at the source vertex and iteratively selects the unvisited munotes.in

## Page 124

Fundamental of

Algorithms

124 vertex with the smallest tentative distanc e from the source. It then visits

the neighbors of this vertex and updates their tentative distances if a

shorter path is found. This process continues until the destination vertex is

reached, or all reachable vertices have been visited.

What is Dijkstra’s Algorithm?

Need of Dijkstra’s Algorithm (Purpose and Use-Cases)

Basics of Dijkstra’s Algorithm

Basics requirements for Implementation of Dijkstra’s Algorithm

Can Dijkstra’s algorithm work on both directed and undirected graphs?

Algorithm:

How Does Dijkst ra’s Algorithm Works?

Pseudo Code for Dijkstra’s Algorithm

Ways to Implement Dijkstra’s Algorithm

Implementation of Dijkstra’s Algorithm:

1. Dijkstra’s Shortest Path Algorithm using priority_queue (Heap)

2. Dijkstra shortest path algorithm using Prim’s Algorithm

3. Dijkstra’s shortest path with minimum edges

4. Dijkstra’s shortest path algorithm using Set

Complexity Analysis of Dijkstra’s Algorithm

Dijkstra’s Algorithm vs Other Algorithms

Problems Related to Dijkstra’s Algorithm

Need for Dijkstra’s Algorit hm (Purpose and Use-Cases)

The need for Dijkstra’s algorithm arises in many applications where

finding the shortest path between two points is crucial.

For example , It can be used in the routing protocols for computer

networks and also used by map systems to find the shortest path between

starting point and the Destination (as explained in How does Google Maps

work? )

Basic Characterstics of Dijkstra’s Algorithm

Below are the basic steps of how Dijkstra’s algorithm works:

So Basically, Dijkstra’s algorithm starts at the node source node we

choose and then i t analyzes the graph condition and its paths to find the

optimal shortest distance between the given node and all other nodes in

the graph.

Dijkstra’s algorithm keeps track of the currently known shortest

distance from each node to the source node and upda tes the value after

it finds the optimal path once the algorithm finds the shortest path

between the source node and destination node then the specific node is

marked as visited. munotes.in

## Page 125

Graph Algorithms

125 Basics requirements for Implementation of Dijkstra’s Algorithm

1. Graph : Dijkstra’s Algorithm can be implemented on any graph but it

works best with a weighted Directed Graph with non -negative edge

weights and the graph should be represented as a set of vertices and

edges.

2. Source Vertex: Dijkstra’s Algorithm requires a source node which is

starting point for the search.

3. Destination vertex: Dijkstra’s algorithm may be modified to terminate

the search once a specific destination ver tex is reached.

4. Non-Negative Edges: Dijkstra’s algorithm works only on graphs that

have positive weights this is because during the process the weights of

the edge have to be added to find the shortest path. If there is a negative

weight in the graph then the algorithm will not work correctly. Once a

node has been marked as visited the current path to that node is marked

as the shortest path to reach that node.

Can Dijkstra’s algorithm work on both Directed and Undirected

graphs?

Yes, Dijkstra’s algorithm can work on both directed graphs and undirected

graphs as this algorithm is designed to work on any type of graph as long

as it meets the requirements of having non -negative edge weights and

being connected.

In a directed graph, each edge has a direction, indicating the direction

of travel between the vertices connected by the edge. In this case, the

algorithm follows the direction of the edges when searching for the

shortest path.

In an undirected graph, the edges have no direction, and the

algorithm can t raverse both forward and backward along the edges

when searching for the shortest path.

Algorithm for Dijkstra’s Algorithm :

Mark the source node with a current distance of 0 and the rest with

infinity.

Set the non -visited node with the smallest current dis tance as the

current node.

For each neighbor, N of the current node adds the current distance of

the adjacent node with the weight of the edge connecting 0 ->1. If it is

smaller than the current distance of Node, set it as the new current

distance of N.

Mark the current node 1 as visited.

Go to step 2 if there are any nodes are unvisited. munotes.in

## Page 126

Fundamental of

Algorithms

126 How does Dijkstra’s Algorithm works?

Let’s see how Dijkstra’s Algorithm works with an example given below:

Dijkstra’s Algorithm will generate the shortest path from Node 0 to all

other Nodes in the graph.

Consider the below graph:

Dijkstra’s Algorithm

The algorithm will generate the shortest path from node 0 to all the other

nodes in the graph.

For this graph, we will assume that the weight of the edges represents

the distance between two nodes.

As, we can see we have the shortest path from,Node 0 to Node 1, from

Node 0 to Node 2, from

Node 0 to Node 3, from

Node 0 to Node 4, from

Node 0 to Node 6.

Initially we have a set of resources given below :

The Distance from the sou rce node to itself is 0. In this example the

source node is 0.

The distance from the source node to all other node is unknown so we

mark all of them as infinity.

Example: 0 -> 0, 1 -> ∞,2-> ∞,3-> ∞,4-> ∞,5-> ∞,6-> ∞.

we’ll also have an array of unvisited el ements that will keep track of

unvisited or unmarked Nodes. munotes.in

## Page 127

Graph Algorithms

127 Algorithm will complete when all the nodes marked as visited and the

distance between them added to the path. Unvisited Nodes: - 0 1 2 3 4

5 6.

Step 1: Start from Node 0 and mark Node as visited a s you can check in

below image visited Node is marked red.

Dijkstra’s Algorithm

Step 2: Check for adjacent Nodes, Now we have to choices (Either choose

Node1 with distance 2 or either choose Node 2 with distance 6 ) and

choose Node with minimum distance. In this step Node 1 is Minimum

distance adjacent Node, so marked it as visited and add up the distance.

Distance: Node 0 -> Node 1 = 2

Dijkstra’s Algorithm

Step 3: Then Move Forward and check for adjacent Node which is Node

3, so marked it as visited a nd add up the distance, Now the distance will

be:

Distance: Node 0 -> Node 1 -> Node 3 = 2 + 5 = 7 munotes.in

## Page 128

Fundamental of

Algorithms

128

Dijkstra’s Algorithm

Step 4: Again we have two choices for adjacent Nodes (Either we can

choose Node 4 with distance 10 or either we can choose Node 5 with

distance 15) so choose Node with minimum distance. In this step Node

4 is Minimum distance adjacent Node, so marked it as visited and add up

the distance.

Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 = 2 + 5 + 10 = 17

Dijkstra’s Algorithm

Step 5: Again, Move Forward and check for adjacent Node which

is Node 6, so marked it as visited and add up the distance, Now the

distance will be:

Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 -> Node 6 = 2 + 5 + 10

+ 2 = 19 munotes.in

## Page 129

Graph Algorithms

129

Dijkstra’s Algorithm

So, the Shortest Distance from the Source Vertex is 19 which is

optimal one

Pseudo Code for Dijkstra’s Algorithm

function Dijkstra(Graph, source):

// Initialize distances to all nodes as infinity, except for the source node.

distances = map infinity to all nodes

distances = 0

// Initialize an empty set of visited nodes and a priority queue to keep

track of the nodes to visit.

visited = empty set

queue = new PriorityQueue()

queue.enqueue(source, 0)

// Loop until all nodes have been visited.

while queue is not empty:

// Dequeue the node with the smallest distance from the priority

queue.

current = queue.dequeue()

// If the node has already been visited, skip it.

if current in visited:

continue

// Mark the node as visited.

visited.add(current)

// Check all neighboring nodes to see if their distances need to be

updated.

for neighbor in Graph.neighbors(current):

// Calculate the tentative distance to the neighbor through the

current node.

tentative_distance = distances[current] +

Graph.distance(current, neighbor) munotes.in

## Page 130

Fundamental of

Algorithms

130 // If the tentative distance is smaller than the current distance to the

neighbor, update the distance.

if tentative_distance< distance s[neighbor]:

distances[neighbor] = tentative_distance

// Enqueue the neighbor with its new distance to be considered

for visitation in the future.

queue.enqueue(neighbor, distances[neighbor])

// Return the ca lculated distances from the source to all other nodes in

the graph.

return distances

Ways to Implement Dijkstra’s Algorithm:

There are several ways to Implement Dijkstra’s algorithm, but the most

common ones are:

1. Using priority queue to keep track of all vertices.

2. Using an array to keep track of Distances.

3. Using a set to keep track of the visited vertices.

1. Dijkstra’s Shortest Path Algorithm using priority_queue (Heap)

In this Implementation, we are given a graph and a source vertex in the

graph, finding th e shortest paths from the source to all vertices in the given

graph.

Example:

Input: Source = 0

Example

Output: Vertex

Vertex Distance from Source munotes.in

## Page 131

Graph Algorithms

131 0 -> 0

1 -> 2

2 -> 6

3 -> 7

4 -> 17

5 -> 22

6 -> 19

Below is the algorithm based on the above idea:

1. Initialize distances of all vertices as infinite.

2. Create an empty priority_queuepq . Every item of pq is a pair (weight,

vertex). Weight (or distance) is used as first item of pair as first item is

by default used to compare two pairs

3. Insert source vertex into pq and make its distance as 0.

4. While either pq doesn’t become empty

1. Extract minimum distance vertex from pq.

Let the extracted vertex be u.

2. Loop through all adjacent of u and do the following for every vertex v.

3. If there is a shorter path to v throu gh u.

1. Update distance of v, i.e., do dist[v] = dist[u] + weight(u, v)

2. Insert v into the pq (Even if v is already there)

5. Print distance array dist[] to print all shortest paths.

Below is the C++ Implementation of the above approach:

// Program to find Dijkstra's shortest path using

// priority_queue in STL

#include

usingnamespace std;

#define INF 0x3f3f3f3f

// iPair ==> Integer Pair

typedef pair< int, int>iPair;

// This class represents a directed graph using

// adjacency list representation munotes.in

## Page 132

Fundamental of

Algorithms

132 classGraph {

intV; // No. of vertices

// In a weighted graph, we need to store vertex

// and weight pair for every edge

list>* adj;

public :

Graph( intV); // Constructor

// function to add an edge to graph

voidaddEdge( intu, intv, intw);

// prints shortest path from s

voidshortestPath( ints);

};

// Allocates memory for adjacency list

Graph::Graph( intV)

{

this->V = V;

adj = newlist[V];

}

voidGraph::addEdge( intu, intv, intw)

{

adj[u].push _back(make_pair(v, w));

adj[v].push_back(make_pair(u, w));

}

// Prints shortest paths from src to all other vertices

voidGraph::shortestPath( intsrc)

{

// Create a priority queue to store vertices that

// are being preprocessed. This is weird syntax in C++. munotes.in

## Page 133

Graph Algorithms

133 // Refer below link for details of this syntax

// https://www.geeksforgeeks.org/implement -min-heap -using -stl/

priority_queue, greater*> *

pq;

// Create a vector for distances and initialize all

// distances as infinite (INF)

vector< int>dist(V, INF);

// Insert source itself in priority queue and initialize

// its distance as 0.

pq.push(make_pair(0, src));

dist[src] = 0;

/* Looping till priority queue becomes empty (or all

distances are not finalized) */

while (!pq.empty()) {

// The first vertex in pair is the minimum distance

// vertex, extract it from priority queue.

// vertex label is stored in second of pair (it

// has to be done this way to keep the vertices

// sorted distance (distance must be first item

// in pair)

intu = pq.top().second;

pq.pop();

// 'i' is used to get all adjacent vertices of a

// vertex

list>::iterator i;

for(i = adj[u].begin(); i != adj[u].end(); ++i) {

// Get vertex label and weight of current

// adjacent of u. munotes.in

*
* *
*
## Page 134

Fundamental of

Algorithms

134 intv = (*i).first;

intweight = (*i).second;

// If there is shorted path to v through u.

if(dist[v] >dist[u] + weight) {

// Updating distance of v

dist[v] = dist[u] + weight;

pq.push(make_pair(dist[v], v));

}

}

}

// Print shortest distances stored in dist[]

printf ("Vertex Distance from Source \n");

for(inti = 0; i< V; ++i)

printf ("%d \t\t %d\n", i, dist[i]);

}

// Driver program to test methods of graph class

intmain()

{

// create the graph given in above figure

intV = 7;

Graph g(V);

// making above shown graph

g.addEdge(0, 1, 2);

g.addEdge(0, 2, 6);

g.addEdge(1, 3, 5);

g.addEdge(2, 3, 8);

g.addEdge(3 , 4, 10);

g.addEdge(3, 5, 15); munotes.in

## Page 135

Graph Algorithms

135 g.addEdge(4, 6, 2);

g.addEdge(5, 6, 6);

g.shortestPath(0);

return 0;

}

Output

Vertex Distance from Source

0 0

1 2

2 6

3 7

4 17

5 22

6 19

Fina l Answer:

Output

Complexity Analysis of Dijkstra’s Algorithm using Priority Queue:

Time complexity : O(E log V)

Space Complexity: O(V2), here V is the number of Vertices.

2. Dijkstra shortest path algorithm using Prim’s Algorithm munotes.in

## Page 136

Fundamental of

Algorithms

136 Given a graph and a source vertex in the graph, find the shortest paths

from the source to all ver tices in the given graph.

Example:

Example

Output: 0 2 6 7 17 22 19

Follow the below steps to implement Dijkstra’s Algorithm using Prim’s

Algorithm:

Create a set sptSet (shortest path tree set) that keeps track of vertices

included in the shortest -path tree, i.e., whose minimum distance from

the source is calculated and finalized. Initially, this set is empty.

Assign a distance value to all vertices in the input graph. Initialize all

distance values as INFINITE . Assign the distance value as 0 for the

source vertex so that it is picked first.

While sptSet doesn’t include all vertices

Pick a vertex u which is not there in sptSet and has a minimum

distance value.

Include u to sptSet .

Then update distance value of all adjacent vertices of u.

To update t he distance values, iterate through all adjacent vertices.

For every adjacent vertex v, if the sum of the distance value of u (from

source) and weight of edge u-v, is less than the distance value of v,

then update the distance value of v.

Complexity Anal ysis of Dijkstra’s Algorithm using Prims Algorithm:

Time Complexity: O(V2)

Auxiliary Space: O(V) munotes.in

## Page 137

Graph Algorithms

137 3. Dijkstra’s shortest path with minimum edges

In this Implementation w e are given an adjacency atrix graph representing

paths between the nodes in the given graph. The task is to find the shortest

path with minimum edges i. e. if there a multiple short paths with same

cost then choose the one with the minimum number of edges .

Consider the graph given below:

Example

There are two paths from vertex 0 to vertex 3 with a weight of 12:

0 -> 1 -> 2 -> 3

0 -> 4 -> 3

Since Dijkstra’s algor ithm is a greedy algorithm that seeks the minimum

weighted vertex on every iteration, so the original Dijkstra’s algorithm

will output the first path but the result should be the second path a s it

contains minimum number of edges.

Examples :

Input : graph[][] = { {0, 1, INFINITY, INFINITY, 10},

{1, 0, 4, INFINITY, INFINITY},

{INFINITY, 4, 0, 7, INFINITY},

{INFINITY, INFINITY, 7, 0, 2},

{10, INFINITY, INFINITY, 2, 0} };

Output : 0->4->3

INFI NITY here shows that u and v are not neighbors

Input : graph[][] = { {0, 5, INFINITY, INFINITY},

{5, 0, 5, 10},

{INFINITY, 5, 0, 5},

{INFINITY, 10, 5, 0} };

Output : 0->1->3 munotes.in

## Page 138

Fundamental of

Algorithms

138 Approach: The idea of the algorithm is to use the original Dijkstra’s

algorithm , but also to keep track of the length of the paths by an array that

stores the length of the paths from the source vertex, so if we find a shorter

path with the same weight, then we will take it.

Complexity Analysis:

Time Complexity : O(V^2) where V is the number of vertices and E is

the number of edges.

Auxiliary Space : O(V + E)

4. Dijkstra’s shortest path algorithm using Set

Given a graph and a source vertex in graph, find shortest paths from

source to all vertices in the given graph

Example:

Example

Output: 0 2 6 7 17 22 19

Below is algorithm based on set data structure.

1. Initialize distances of all vertices as infinite.

2. Create an empty set. Every item of set is a pair (weight, vertex).

Weight (or distance) is used as first item of pair as first item is by

default used to compare two pairs.

3. Insert sou rce vertex into the set and make its distance as 0.

4. While Set doesn’t become empty, do following

a) Extract minimum distance vertex from Set.

Let the extracted vertex be u.

b) Loop through all adjacent of u and do

following for every vertex v. munotes.in

## Page 139

Graph Algorithms

139 // If there is a shorter path to v through u.

If dist[v] >dist[u] + weight(u, v

(i) Update distance of v, i.e., do dist[v] = dist[u] + weight(u, v)

(i) If v is in set, update its distance in set by removing it first, then

inserting with new distance

(ii) If v is not in set, then insert it in set with new distance

5) Print distance array dist[ ] to print all shortest paths.

Complexity Analysis:

Time Complexity : O(ELogV), where V is the number of vertices and

E is the number of edges.

Auxiliar y Space : O(V2)

Complexity Analysis of Dijkstra’s Algorithm:

The time complexity of Dijkstra’s algorithm depends on the data structure

used for the priority queue. Here is a breakdown of the time complexity

based on different implementations:

Using an unsor ted list as the priority queue: O(V2), where V is the

number of vertices in the graph. In each iteration, the algorithm

searches for the vertex with the smallest distance among all unvisited

vertices, which takes O(V) time. This operation is performed V ti mes,

resulting in a time complexity of O(V^2).

Using a sorted list or a binary heap as the priority queue: O(E + V

log V), where E is the number of edges in the graph. In each iteration,

the algorithm extracts the vertex with the smallest distance from the

priority queue, which takes O(log V) time. The distance updates for the

neighboring vertices take O(E) time in total. This operation is

performed V times, resulting in a time complexity of O(V log V + E

log V). Since E can be at most V^2, the time complex ity is O(E + V log

V).

Dijkstra’s Algorithms vs Bellman -Ford Algorithm

Dijkstra’s algorithm and Bellman -Ford algorithm are both used to find the

shortest path in a weighted graph, but they have some key differences.

Here are the main differences between Dijkstra’s algorithm and Bellman -

Ford algorithm:

munotes.in

## Page 140

Fundamental of

Algorithms

140 Feature: Dijkst ra’s Bellman Ford

Optimization optimized for finding the

shortest path between a

single source node and all

other nodes in a graph with

non-negative edge weights Bellman -Ford algorithm is optimized for finding the shortest path between a single source node and all other nodes in a graph with negative edge weights.

Relaxation Dijkstra’s algorithm uses a

greedy approach where it

chooses the node with the

smallest distance and

updates its neighbors the Bellman -Ford algorithm relaxes all edges in each iteration, updating the distance of each node by considering all possible paths to that node

Time

Complexity Dijkstra’s algorithm has a

time complexity of O(V^2)

for a dense graph and O(E

log V) for a sparse graph,

where V is the number of

vertices and E is the

number of edges in the

graph. Bellman -Ford algorithm has a time complexity of O(VE), where V is the number of vertices and E is the number of edges in the graph.

Negative

Weights Dijkstra’s algorithm does

not work with graphs that

have negative edge

weigh ts, as it assumes that

all edge weights are non -

negative. Bellman -Ford algorithm can handle negative edge weights and can detect negative -weight cycles in the graph.

Dijkstra’s algorithm vs Floyd -Warshall Algorithm

Dijkstra’s algorithm and Floyd -Warshall algorithm are both used to find

the shortest path in a weighted graph, but they have som e key differences.

Here are the main differences between Dijkstra’s algorithm and Floyd -

Warshall algorithm:

munotes.in

## Page 141

Graph Algorithms

141 Feature: Dijkstra’s Floyd -Warshall Algorithm

Optimization Optimized for finding the

shortest path between a

single source node and all

other nod es in a graph

with non -negative edge

weights Floyd -Warshall algorithm is optimized for finding the shortest path between all pairs of nodes in a graph.

Technique Dijkstra’s algorithm is a

single -source shortest

path algorithm that uses a

greedy approach a nd

calculates the shortest

path from the source node

to all other nodes in the

graph. Floyd -Warshall algorithm, on the other hand, is an all -pairs shortest path algorithm that uses dynamic programming to calculate the shortest path between all pairs of nod es in the graph.

Time

Complexity Dijkstra’s algorithm has a

time complexity of

O(V^2) for a dense graph

and O(E log V) for a

sparse graph, where V is

the number of vertices

and E is the number of

edges in the graph. Floyd -Warshall algorithm, on the other hand, is an all -pairs shortest path algorithm that uses dynamic programming to calculate the shortest path between all pairs of nodes in the graph.

Negative

Weights Dijkstra’s algorithm does

not work with graphs that

have negative edge

weights, as it assu mes that

all edge weights are non -

negative. Floyd -Warshall algorithm, on the other hand, is an all -pairs shortest path algorithm that uses dynamic programming to calculate the shortest path between all pairs of nodes in the graph.

Dijkstra’s algorithm vs A* Algorithm

Dijkstra’s algorithm and A* algorithm are both used to find the shortest

path in a weighted graph, but they have some key differences. Here are the

main differences between Dijkst ra’s algorithm and A* algorithm:

Feature: A* Algorithm

Search

Technique Optimized for finding the

shortest path between a A* algorithm is an informed search algorithm that uses a munotes.in

## Page 142

Fundamental of

Algorithms

142 Feature: A* Algorithm

single source node and all

other nodes in a graph

with non -negative edge

weights heuristic function to guide the search towards the goal node.

Heuristic

Function Dijkstra’s algorithm, does

not use any heuristic

function and considers all

the nodes in the graph. A* algorithm uses a heuristic function that estimates the distance from the current node to the goal node. This heuristic function is admissible, meaning that it never overestimates the actual distance to the goal node

Time

Complexity Dijkstra’s algorithm has a

time complexity of

O(V^2) for a dense graph

and O(E log V) f or a

sparse graph, where V is

the number of vertices

and E is the number of

edges in the graph. The time complexity of A* algorithm depends on the quality of the heuristic function.

Application Dijkstra’s algorithm is

used in many applications

such as rou ting

algorithms, GPS

navigation systems, and

network analysis . A* algorithm is commonly used in pathfinding and graph traversal problems, such as video games, robotics, and planning algorithms.

Conclusion: Overall, Dijkstra’s algorithm is a simple and ef ficient way to

find the shortest path in a graph with non -negative edge weights.

However, it may not work well with graphs that have negative edge

weights or cycles. In such cases, more advanced algorithms such as the

Bellman -Ford algorithm or the Floyd -Warshall algorithm may be used.

Minimal Spanning Tree

Before knowing about the minimum spanning tree, we should know about

the spanning tree.

To understand the concept of spanning tree, consider the below

graph: munotes.in

## Page 143

Graph Algorithms

143

The above graph can be represented as G(V, E ), where 'V' is the number

of vertices, and 'E' is the number of edges. The spanning tree of the above

graph would be represented as G`(V`, E`). In this case, V` = V means that

the number of vertices in the spanning tree would be the same as the

number of vertices in the graph, but the number of edges would be

different. The number of edges in the spanning tree is the subset of the

number of edges in the original graph. Therefore, the number of edges can

be written as:

E` € E

It can also be written as:

E` = |V| - 1

Two conditions exist in the spanning tree, which is as follows:

o The number of vertices in the spanning tree would be the same as

the number of vertices in the original graph.

V` = V

o The number of edges in the spanning tree would be equal to the

number of edges minus 1.

E` = |V| - 1

o The spanning tree should not contain any cycle.

o The spanning tree should not be disconnected.

Note: A graph can have more than one spanning tree.

Consider the below graph:

The above graph contains 5 vertices. As we know, the vertices in the

spanning tree would be the same as the graph; therefore, V` is equal 5. The

number of edges in the spanning tree would be equal to (5 - 1), i.e., 4. The

following are the possible spanning trees: munotes.in

## Page 144

Fundamental of

Algorithms

144

munotes.in

## Page 145

Graph Algorithms

145

What is a minimum spanning tre e?

The minimum spanning tree is a spanning tree whose sum of the edges is

minimum. Consider the below graph that contains the edge weight:

The following are the spanning trees that we can make from the above

graph.

o The first spanning tree is a tree in whic h we have removed the edge

between the vertices 1 and 5 shown as below:

The sum of the edges of the above tree is (1 + 4 + 5 + 2): 12

o The second spanning tree is a tree in which we have removed the edge

between the vertices 1 and 2 shown as below:

The sum of the edges of the above tree is (3 + 2 + 5 + 4) : 14

o The third spanning tree is a tree in which we have removed the edge

between the vertices 2 and 3 shown as below:

The sum of the edges of the above tree is (1 + 3 + 2 + 5) : 11

o The fourth spanning tree is a tree in which we have removed the edge

between the vertices 3 and 4 shown as below:

The sum of the edges of the above tree is (1 + 3 + 2 + 4) : 10. The edge

cost 10 is minimum so it is a minimum spanning tree.

General properties of minimum spanning tr ee:

o If we remove any edge from the spanning tree, then it becomes

disconnected. Therefore, we cannot remove any edge from the

spanning tree.

o If we add an edge to the spanning tree then it creates a loop. Therefore,

we cannot add any edge to the spanning tr ee.

o In a graph, each edge has a distinct weight, then there exists only a

single and unique minimum spanning tree. If the edge weight is not

distinct, then there can be more than one minimum spanning tree. munotes.in

## Page 146

Fundamental of

Algorithms

146 o A complete undirected graph can have an nn-2 numbe r of spanning

trees.

o Every connected and undirected graph contains atleast one spanning

tree.

o The disconnected graph does not have any spanning tree.

o In a complete graph, we can remove maximum (e -n+1) edges to

construct a spanning tree.

Let's understand th e last property through an example.

Consider the complete graph which is given below:

The number of spanning trees that can be made from the above complete

graph equals to nn-2 = 44-2 = 16.

Therefore, 16 spanning trees can be created from the above graph .

The maximum number of edges that can be removed to construct a

spanning tree equals to e -n+1 = 6 - 4 + 1 = 3.

Application of Minimum Spanning Tree

1. Consider n stations are to be linked using a communication network &

laying of communication links between any two stations involves a

cost.

The ideal solution would be to extract a subgraph termed as minimum

cost spanning tree.

2. Suppose you want to construct highways or railroads spanning several

cities then we can use the concept of minimum spanning trees.

3. Designing Local Area Networks.

4. Laying pipelines connecting offshore drilling sites, refineries and

consumer markets. munotes.in

## Page 147

Graph Algorithms

147 5. Suppose you want to apply a set of houses with

o Electric Power

o Water

o Telephone lines

o Sewage lines

To reduce cost, you can connect houses with m inimum cost spanning

trees.

For Example, Problem laying Telephone Wire.

munotes.in

## Page 148

Fundamental of

Algorithms

148

Methods of Minimum Spanning Tree

There are two methods to find Minimum Spanning Tree

1. Kruskal's Algorithm

2. Prim's Algorithm

Kruskal's Algorithm:

An algorithm to construct a Minim um Spanning Tree for a connected

weighted graph. It is a Greedy Algorithm. The Greedy Choice is to put the

smallest weight edge that does not because a cycle in the MST constructed

so far.

If the graph is not linked, then it finds a Minimum Spanning Tree.

Steps for finding MST using Kruskal's Algorithm:

1. Arrange the edge of G in order of increasing weight.

2. Starting only with the vertices of G and proceeding sequentially add

each edge which does not result in a cycle, until (n - 1) edges are used.

3. EXIT.

MST - KRUSKAL (G, w)

1. A ← ∅

2. for each vertex v ∈ V [G]

3. do MAKE - SET (v)

4. sort the edges of E into non decreasing order by weight w

5. for each edge (u, v) ∈ E, taken in non decreasing order by weight

6. do if FIND -SET (μ) ≠ if FIND -SET (v) munotes.in

## Page 149

Graph Algorithms

149 7. then A ← A ∪ {(u, v)}

8. UNION (u, v)

9. return A

Analysis: Where E is the number of edges in the graph and V is the

number of vertices, Kruskal's Algorithm can be shown to run in O (E log

E) time, or simply, O (E log V) time, all with simple data structures. These

running times are equivalent because:

o E is at most V2 and log V2= 2 x log V is O (log V).

o If we ignore isolated vertices, which will each their components of the

minimum spanning tree, V ≤ 2 E, so log V is O (log E).

Thus the total time is

1. O (E log E) = O (E log V).

For Example: Find the Minimum Spanning Tree of the following graph

using Krus kal's algorithm.

Solution: First we initialize the set A to the empty set and create |v| trees,

one containing each vertex with MAKE -SET procedure. Then sort the

edges in E into order by non -decreasing weight.

There are 9 vertices and 12 edges. So MST fo rmed (9 -1) = 8 edges

Now, check for each edge (u, v) whether the endpoints u and v belong to

the same tree. If they do then the edge (u, v) cannot be supplementary.

Otherwise, the two vertices belong to different trees, and the edge (u, v) is munotes.in

## Page 150

Fundamental of

Algorithms

150 added to A, and the vertices in two trees are merged in by union

procedure.

Step1: So, first take (h, g) edge

Step 2: then (g, f) edge.

Step 3: then (a, b) and (i, g) edges are considered, and the forest becomes

Step 4: Now, edge (h, i). Both h and i vertices are in the same set. Thus it

creates a cycle. So this edge is discarded.

Then edge (c, d), (b, c), (a, h), (d, e), (e, f) are considered, and the forest

becomes. munotes.in

## Page 151

Graph Algorithms

151

Step 5: In (e, f) edge both endpoints e and f exist in the same tree so

discarded this edg e. Then (b, h) edge, it also creates a cycle.

Step 6: After that edge (d, f) and the final spanning tree is shown as in

dark lines.

Step 7: This step will be required Minimum Spanning Tree because it

contains all the 9 vertices and (9 - 1) = 8 edges

1. e → f, b → h, d → f [cycle will be formed]

Minimum Cost MST

Prim's Algorithm

It is a greedy algorithm. It starts with an empty spanning tree. The idea is

to maintain two sets of vertices:

o Contain vertices already included in MST.

o Contain vertices not yet included. munotes.in

## Page 152

Fundamental of

Algorithms

152 At every step, it considers all the edges and picks the minimum weight

edge. After picking the edge, it moves the other endpoint of edge to set

containing MST.

Steps for finding MST using Prim's Algorithm:

1. Create MST set that keeps track of vert ices already included in MST.

2. Assign key values to all vertices in the input graph. Initialize all key

values as INFINITE ( ∞). Assign key values like 0 for the first vertex so

that it is picked first.

3. While MST set doesn't include all vertices.

a. Pick vertex u which is not is MST set and has minimum key value.

Include 'u'to MST set.

b. Update the key value of all a djacent vertices of u. To update, iterate

through all adjacent vertices. For every adjacent vertex v, if the weight

of edge u.v less than the previous key value of v, update key value as a

weight of u.v.

MST -PRIM (G, w, r)

1. for each u ∈ V [G]

2. do key [u] ← ∞

3. π [u] ← NIL

4. key [r] ← 0

6. Q ← V [G]

7. While Q ? ∅

8. do u ← EXTRACT - MIN (Q)

9. for each v ∈Adj [u]

10. do if v ∈ Q and w (u, v) < key [v]

11. then π [v] ← u

12. key [v] ← w (u, v)

Example: Generate minimum cost spanning tree for the following graph

using Prim's algorithm. munotes.in

## Page 153

Graph Algorithms

153

Solution: In Prim's algorithm, first we initialize the priority Queue Q. to

contain all the vertices and the key of each vertex to ∞ except for the root,

whose key is set to 0. Suppose 0 vertex is the root, i.e., r. By EXTRACT -

MIN (Q) procure, now u = r a nd Adj [u] = {5, 1}.

Removing u from set Q and adds it to set V - Q of vertices in the tree.

Now, update the key and π fields of every vertex v adjacent to u but not in

a tree.

1. Taking 0 as starting vertex

2. Root = 0

3. Adj [0] = 5, 1

4. Parent, π [5] = 0 and π [1] = 0

5. Key [5] = ∞ and key [1] = ∞

6. w [0, 5) = 10 and w (0,1) = 28

7. w (u, v) < key [5] , w (u, v) < key [1]

8. Key [5] = 10 and key [1] = 28

9. So update key value of 5 and 1 is:

munotes.in

## Page 154

Fundamental of

Algorithms

154

Now by EXTRACT_MIN (Q) Removes 5 b ecause key [5] = 10 which is

minimum so u = 5.

1. Adj [5] = {0, 4} and 0 is already in heap

2. Taking 4, key [4] = ∞ π [4] = 5

3. (u, v) < key [v] then key [4] = 25

4. w (5,4) = 25

5. w (5,4) < key [4]

6. date key value and parent of 4.

munotes.in

## Page 155

Graph Algorithms

155 Now remove 4 because key [4] = 25 which is minimum, so u =4

1. Adj [4] = {6, 3}

2. Key [3] = ∞ key [6] = ∞

3. w (4,3) = 22 w (4,6) = 24

4. w (u, v) < key [v] w (u, v) < key [v]

5. w (4,3) < key [3] w (4,6) < key [6]

Update key value of key [3] as 22 a nd key [6] as 24.

And the parent of 3, 6 as 4.

1. π[3]= 4 π[6]= 4

1. u = EXTRACT_MIN (3, 6) [key [3] < key [6]]

2. u = 3 i.e. 22 < 24

Now remove 3 because key [3] = 22 is minimum so u =3.

1. Adj [3] = {4, 6, 2}

2. 4 is alread y in heap

3. 4 ≠ Q key [6] = 24 now becomes key [6] = 18

4. Key [2] = ∞ key [6] = 24

5. w (3, 2) = 12 w (3, 6) = 18

6. w (3, 2) < key [2] w (3, 6) < key [6] munotes.in

## Page 156

Fundamental of

Algorithms

156 Now in Q, key [2] = 12, key [6] = 18, key [1] = 28 and parent of 2 and 6

is 3.

1. π [2] = 3 π[6]=3

Now by EXTRACT_MIN (Q) Removes 2, because key [2] = 12 is

minimum.

1. u = EXTRACT_MIN (2, 6)

2. u = 2 [key [2] < key [6]]

3. 12 < 18

4. Now the root is 2

5. Adj [2] = {3, 1}

6. 3 is already in a heap

7. Taking 1, key [1] = 28

8. w (2,1) = 16

9. w (2,1) < key [1]

So update key value of key [1] as 16 and its parent as 2.

1. π[1]= 2

Now by EXTRACT_MIN (Q) Removes 1 because key [1] = 16 is

minimum. munotes.in

## Page 157

Graph Algorithms

157 1. Adj [1] = {0, 6, 2}

2. 0 and 2 are already in heap.

3. Taking 6, key [6] = 18

4. w [1, 6] = 14

5. w [1, 6] < key [6]

Update key value of 6 as 14 and its parent as 1.

1. Π [6] = 1

Now all the vertices have been spanned, Using above the table we get

Minimum Spanning Tree.

1. 0 → 5 → 4 → 3 → 2 → 1 → 6

2. [Because Π [5] = 0, Π [4] = 5, Π [3] = 4, Π [2] = 3, Π [1] =2, Π [6] =1]

Thus the final spanning Tree is

Total Cost = 10 + 25 + 22 + 12 + 16 + 14 = 99

4.9 QUESTION BANK AND EXCERCISE

1. What is Data Structure: Types, Classifications and Applications

2. Applications, Advantages and Disadvantages of Directed Graph

3. Applications, Advantages and Disadvantages of Unweighted Graph

4. Graph Coloring | Set 1 (Introduction and Applications)

5. Applications, Advantages and Disadvantages of Weighted Graph munotes.in

## Page 158

Fundamental of

Algorithms

158 6. Applications, Advantag es and Disadvantages of Graph

7. Check whether the structure of given Graph is same as the game of

Rock -Paper -Scissor

8. Maximum number of edges that N-vertex graph can have such that

graph is Triangle free | Mantel's Theorem

9. Python Program to Find Independent Sets in a Graph using Graph

Coloring

10. What is graphs? Enlist Types of Graphs.

11. Explain Shortest Path First Algorithms?

12. What is BFS & DFS?

13. Explain minimal spanning tree with examples?

14. Explain Graph Representation & Graph Traversal?

15. Enlist Applications of Graphs?

16. Explain Topological Sort in detail?

17. Explain Graph Algorithms in details?

18. Write a short note on Weighted Graphs & Directed graphs?

19. Expalin What is Dijkstra’s Algorithm? Introduction to Dijkstra’s

Shortest Path Algorithm.

20. What is Graph Colouring ?

4.10 CONCLUSION

In this article, you came across plenty of graph coloring algorithms and

techniques that find their day -to-day applications in all instances of rea l

life. You learned how to implement them according to situations, and

hence the pseudo code helped you process the information strategically

and efficiently. Graph algorithms are considered an essential aspect in the

field confined not only to solve probl ems using data structures but also in

general tasks like Google Maps and Apple Maps. However, a beginner

might find it hard to implement Graph algorithms because of their

complex nature. Hence, it is highly recommended to go through this

article since it c overs everything from scratch.

munotes.in

## Page 159

159 5

SELECTION ALGORITHMS

UnitStructure

5.0 Objectives

5.1 Introduction

5.2 What are the Selection Algorithm

5.3 Selection by Sorting

5.4 Linear Selection A lgorithm

5.5 Median of median Algorithms

5.6 Finding the K Smallest Elements in Sorted Order

5.7 List of References

5.8 Bibliography

5.0 OBJECTIVES

A sorting algorithm is a method for reorganizing a large number of items

into a specific order , such as alphabetical, highest -to-lowest value or

shortest -to-longest distance. Sorting algorithms take lists of items as input

data, perform specific operations on those lists and deliver ordered arrays

as output.

5.1 INTRODUCTION OF SELECT ION SORT

ALGORITHMS

What Is a Selection Sort Algorithm? Selection sort is an effective and

efficient sort algorithm based on comparison operations . It adds one

element in each iteration. You need to select the smallest element in the

array and move it to the beginning of the array by swapping with the front

element.

Selection Algorithm is an algorithm for finding the kth smallest (or

largest) number in a list or an array . That number is ca lled the kth order

statistic . It includes the various cases for finding the minimum, maximum

and median elements in a list or an array . For finding the minimum (or

maximum) element by iter ating through the list, we keep the track of

current minimum (or maximum) elements that occur so far and it is related

to the selection sort. Below are the different ways of selecting the kth

smal lest(or largest) element in an unordered list:

munotes.in

## Page 160

Fundamental of

Algorithms

160 5.2 WHAT ARE THE SELECTION ALGORITHM

1. Selection by Sorting

Sorting the list or an array then selecting the required element can make

selection easy. This method is inefficient for selecting a single element but

is efficient when many selections need to be made from an array for which

it only needs sorting of an array. For selection in a linked list is O(n) even

if the linked list is sorted due to lack of random access.

Instead o f sorting the entire list or an array , we can use partial sorting to

select the kth smallest(or largest) element in a list or an array . Then the kth

smallest(or largest) is the largest(or smallest) element of the partially

sorted list. This tak es O(1) to access in an array and O(k) to access in a

list.

Unordered Partial Sorting

Unordered partial sorting is a sorting algorithm in such a way that first k

element are in sorted order and rest element are in random order. For

finding the kth smallest(or largest) element. The time complexity reduces

to O(k log k). But since K ≤ n, The asymptotic Time Complexity

converges to O(n) . Note: Due to the possibility of equality of elements,

one must not include the element less than or equals to the kth element

while sorting a list or an array , as element greater than the kth element

may also be equal to the kth smallest element.

Partial selection sort

The concept used in Selection Sort helps us to partially sort the array up to

kth smallest(or largest) element for finding the kth smallest(or largest)

element in an array. Thus a partial selection sort yields a simple selection

algorithm th at takes O(k*n) time to sort the array . This is asymptotically

inefficient but can be sufficiently efficient if k is small, and is easy to

implement.

Below is the algorithm for partial selection sort:

function partialSelectionSort(arr[0..n], k) {

fori in [0, k){

minIndex = i

minValue = arr[i]

for j in [i+1, n){

if (arr[j] minIndex = j

minValue = arr[j]

swap(arr[i], arr[minIndex]) munotes.in

## Page 161

Selection Algorithms

161 }

}

return arr[k]

}

2. Partition Based Selection:

For partition -based selection, the Quick select Algorithm is used. It is a

variant of quicksort algorithm. In both, we choose a pivot element and

using the partition step from the quicksort algorithm arranges all the

elements smaller than the pivot on it s left and the elements greater than it

on its right. But while Quicksort recurses on both sides of the

partition, Quickselect only recurses on one side, the side on which the

desired kth element is present. The partition -based algorithms are done in

place, which results in partially sorting the data. They can be done out of

place by not changing the original data at the cost of O(n) auxiliary space.

3. Median selected as pivot:

A median -selection algorithm can be used to perform a selection algorithm

or sorting algorithm, by selecting the median of the array as the pivot

element in Quickselect or Quicksort algorithm. In practice the overhead of

pivot computation is significant, so these algorithms are generally not

used, but this technique is of theoretical interest in relating selection and

sorting algorithms. The median of an array is the best pivot for sorting of

an array because it evenly divides the data into two parts., and thus

guarantees optimal sorting, assuming the selection algorithm is optimal.

4. selecti on sort in python:

In this tutorial, we will implement the selection sort algorithm in Python.

It is quite straightforward algorithm using the less swapping.

In this algorithm, we select the smallest element from an unsorted array in

each pass and swap wit h the beginning of the unsorted array. This process

will continue until all the elements are placed at right place. It is simple

and an in -place comparison sorting algorithm.

5.3 WORKING OF SELECTION SORT

The following are the steps to explain the working of the Selection sort in

Python.

Let's take an unsorted array to apply the selection sort algorithm.

[30, 10, 12, 8, 15, 1]

Step - 1: Get the length of the array.

length = len(array) → 6

Step - 2: First, we set the first element as minimum element. munotes.in

## Page 162

Fundamental of

Algorithms

162 Step - 3: Now compare the minimum with the second element. If the

second element is smaller than the first, we assign it as a minimum.

Again we compare the second element to the third and if the third element

is smaller than second, assign it as minimum. This process goes on until

we find the last element.

Step - 4: After each iteration, minimum element is swapped in front of the

unsorted array.

Step - 5: The second to thi rd steps are repeated until we get the sorted

array.

Selection Sort Algorithm

The selection sort algorithm as follows.

Algorithm

1. selection_sort(array)

2. repeat (0, length - 1) times

3. set the first unsorted element as the minimum

4. for each of the unsorted elements

5. if element < currentMinimum

6. set element as new minimum

7. swap minimum with first unsorted position

8. end selection_sort

Selection Sort Program using Python

The following code snippet shows the selection sort algorithm

implementation using Python.

Code -

1. def selection_sort(array):

2. length = len(array)

3.

4. for i in range(length -1):

5. minIndex = i

6.

7. for j in range(i+ 1, length):

8. if array[j]

## Page 163

Selection Algorithms

163 9. minIndex = j

10.

11. array[i], array[minIndex] = array[minIndex], array[i]

12.

13.

14. return array

15. array = [21,6,9,33,3]

16.

17. print( "The sorted array is: ", selection_sort(array))

Output:

The sorted array is: [3, 6, 9, 21, 33]

Explanation -

Let's understand the above code -

o First, we define the selection_sort() function that takes array as an

argument.

o In the function, we get the length of the array which used to determine

the number of passes to be made comp aring values.

o As we can see that, we use two loops - outer and inner loop. The outer

loop uses to iterate through the values of the list. This loop will iterate

to 0 to (length -1). So the first iteration will be perform (5 -1) or 4 times.

In each iteration, the value of the variable i is assigned to the variable

o The inner loop uses to compare the each value of right -side element to

the other value on the leftmost element. So the second loop starts its

iteration from i+1. It will only pick the value that is u nsorted.

o Find the minimum element in the unsorted list and update the minIndex

position.

o Place the value at the beginning of the array.

o Once the iteration is completed, the sorted array is returned.

o At last we create an unsorted array and pass to the selec tion_sort() It

prints the sorted array.

Time Complexity of Selection Sort

Time complexity is an essential in term of how much time an algorithm

take to sort it. In the selection sort, there are two loops. The outer loop

runs for the n times (n is a total n umber of element). munotes.in

## Page 164

Fundamental of

Algorithms

164 The inner loop is also executed for n times. It compares the rest of the

value to outer loop value. So, there is n*n times of execution. Hence the

time complexity of merge sort algorithm is O(n2).

The time complexity can be categorized i nto three categories.

5.4 LINEAR SELECTION ALGORITHM

A linear search is the simplest approach employed to search for an element

in a data set. It examines each element until it finds a match, starting at the

beginning of the data set, until the end. The search is finished and

terminated once the target element is located. If it finds no match, the

algorithm must terminate its execution and return an appropriate result.

The linear search algorithm is easy to imple ment and efficient in two

scenarios:

When the list contains lesser elements

When searching for a single element in an unordered array

What Is Searching?

Searching is the process of fetching a specific element in a collection of

elements. The collection ca n be an array or a linked list. If you find the

element in the list, the process is considered successful, and it return s the

location of that element.

And in contrast, if you do not find the element, it deems the search

unsuccessful.

Two prominent search strategies are extensively used to find a specific

item on a list. However, the algorithm chosen is determined by the li st's

organization.

1. Linear Search

2. Binary Search

Moving ahead in this tutorial, you will understand what exactly a linear

search algorithm is.

What Is a Linear Search Algorithm?

Linear search, often known as sequential search, is the most basic search

technique. In this type of search, you go through the entire list and try to

fetch a match for a single element. If you find a match, then the address of

the matching target element is returned.

On the other hand, if the element is not found, then it returns a NULL

value.

Following is a step -by-step approach employed to perform Linear Search

Algorithm. munotes.in

## Page 165

Selection Algorithms

165

The procedures for implementing linear search are as follows:

Step 1: First, read the search element (Target element) in the array.

Step 2: In the second step compare the search element with the first

element in the array.

Step 3: If both are matched, display "Target element is found" and

terminate the Line ar Search function.

Step 4: If both are not matched, compare the search element with the next

element in the array.

Step 5: In this step, repeat steps 3 and 4 until the search (Target) element

is compared with the last element of the array.

Step 6: If the last element in the list does not match, the Linear Search

Function will be terminated, and the message "Element is not found" will

be displayed.

So far, you have explored the fundamental definition and the working

terminology of the Linear Search Algori thm.

Algorithm and Pseudocode of Linear Search Algorithm

Algorithm of the Linear Search Algorithm

Linear Search ( Array Arr, Value a ) // Arr is the name of the array, and a

is the searched element.

Step 1: Set i to 0 // i is the index of an array which s tarts from 0

Step 2: ifi> n then go to step 7 // n is the number of elements in array

Step 3: if Arr[i] = a then go to step 6

Step 4: Set i to i + 1

Step 5: Goto step 2

Step 6: Print element a found at index i and go to step 8

Step 7: Print element not fou nd

Step 8: Exit

Pseudocode of Linear Search Algorithm

Start munotes.in

## Page 166

Fundamental of

Algorithms

166 linear_search ( Array , value)

For each element in the array

If (searched element == value)

Return's the searched lament location

end if

end for

end

Following your understanding o f the linear search algorithm and

pseudocode, in the next segment, you will go through the practical

implementation of the algorithm.

Example of Linear Search Algorithm

Consider an array of size 7 with elements 13, 9, 21, 15, 39, 19, and 27 that

starts wit h 0 and ends with size minus one, 6.

Search element = 39

Step 1: The searched element 39 is compared to the first element of an

array, which is 13.

The match is not found, you now move on to the next element and try to

implement a comparison.

Step 2: N ow, search element 39 is compared to the second element of an

array, 9.

munotes.in

## Page 167

Selection Algorithms

167 As both are not matching, you will continue the search.

Step 3: Now, search element 39 is compared with the third element,

which is 21.

Again, both the elements are not matching, you move onto the next

following element.

Step 4; Next, search element 39 is compared with the fourth element,

which is 15.

As both are not matching, you move on to the next element.

Step 5: Next, search element 39 is compared with the fifth element 39.

A perfect match is found, you stop comparing any further elements and

terminate the Linear Search Algorithm and display the element found at

location 4.

Followed by the practical implementation, you will move on to the

complexity of the linear search alg orithm.

The Complexity of Linear Search Algorithm

You have three different complexities faced while performing Linear

Search Algorithm, they are mentioned as follows.

1. Best Case

2. Worst Case

3. Average Case munotes.in

## Page 168

Fundamental of

Algorithms

168 You will learn about each one of them in a bit more det ail.

Best Case Complexity

1. The element being searched could be found in the first position.

2. In this case, the search ends with a single successful comparison.

3. Thus, in the best -case scenario, the linear search algorithm performs

O(1) operations.

Worst Case Complexity

The element being searched may be at the last position in the array or

not at all.

In the first case, the search succeeds in ‘n’ comparisons.

In the next case, the search fails after ‘n’ comparisons.

Thus, in the worst -case scenario, the linear search algorithm performs

O(n) operations.

Average Case Complexity

When the element to be searched is in the middle of the array, the average

case of the Linear Search Algorithm is O(n).

Next, you will learn about the Space Complexity of Linear Search

Algorithm.

Space Complexity of Linear Search Algorithm

The linear search algorithm takes up no extra space; its space

comple xity is O(n) for an array of n elements.

Now that you’ve grasped the complexity of the linear search algorithm,

look at some of its applications.

Application of Linear Search Algorithm

The linear search algorithm has the following applications:

Linear sea rch can be applied to both single -dimensional and multi -

dimensional arrays.

Linear search is easy to implement and effective when the array

contains only a few elements.

Linear Search is also efficient when the search is performed to fetch a

single search in an unordered -List.

Finally, in this tutorial, you will implement the linear search algorithm

in code .

Also Read: Arrays in Data Structure munotes.in

## Page 169

Selection Algorithms

169 Code Implementation of Linear Search Algorithm

#include

#include

#include

int main()

{

int array[50],i,target,num;

printf("How many elements do you want in the array");

scanf("%d",&num);

printf("Enter array elements:");

for(i=0;i scanf("%d",&array[i]);

printf("Enter element to search: ");

scanf("%d",&target);

for(i=0;i if(array[i]==target)

break;

if(i printf("Target element found at location %d",i);

else

printf("Target element not found in an array");

return 0;

}

The output of linear search algorithm code: munotes.in

## Page 170

Fundamental of

Algorithms

170

5.5 MEDIAN OF MEDIANS ALGORITHM

Median of Medians Algorithm

It is a divide and conquer algorithm in that, it returns a pivot that in

the worst case will divide a list of unsorted elements into sub -

problems of size 3n/10 and 7n/10 assuming we choose a sublist size of

5.

It guarantees a good pivot that in the worst case will give a pivot in the

range between 30th and 70th percentile of the list of size n.

For a pivot to be considered good it is essential for it to be around the

middle, 30 -70% guarantees the pivot will be around the middle 40% of the

list.

The algorithm is as follows,

1. Divide the list into sublists if size n, assume 5.

2. Initialize an empty array M to store medians we obtain from smaller

sublists.

3. Loop through the whole list in sizes of 5, assuming our list is divisible

by

4. For n/5 sublists, use select brute -force subroutine to select a median m,

which is in the 3rd rank o ut of 5 elements.

5. Append medians obtained from the sublists to the array M. munotes.in

## Page 171

Selection Algorithms

171 6. Use quickSelect subroutine to find the true median from array M, The

median obtained is the viable pivot.

7. Terminate the algorithm once the base case is hit, that is, when the

subli st becomes small enough. Use Select brute -force subroutine to find

the median.

Note: We used chunks of size 5 because selecting a median from a list

whose size is an odd number is easier. Even numbers require additional

computation. We could also select 7 or any other odd number as we shall

see in the proofs below.

Here is the procedure pictorially;

Pseudocode of Median of Medians Algorithm

medianOfMedians( arr[1...n])

if(n <5return Select( arr[1...n], n/2))

Let M be an empty list

For i from 0 to n/5-1:

Let m =Select( arr[5i +1...5i+5],3)

Add m to M

Return QuickSelect( M[1...n/5], n/10)

End medianOfMedians

It is recursive, it calls QuickSelect which in turn will call Median Of

Medians. munotes.in

## Page 172

Fundamental of

Algorithms

172 Time and Space Compl exity of Median of Medians Algorithm

This algorithm runs in O(n) linear time complexity, we traverse the list

once to find medians in sublists and another time to find the true median to

be used as a pivot.

The space complexity is O(logn) , memory used wil l be proportional to

the size of the lists.

Proofs: Why is this pivot good?

1. Lemma:

The median of medians will return a pivot element that is greater than and

less than at least 30% of all elements in the whole list.

proof:

Array M consists of n/5 medians of sub lists of size 5, these elements in

list M is greater than and less than at -least two elements in the original list.

QuickSelect will return a true median that represents the whole list which

is greater than and less than n/5/2 elements of list M and since each one of

the M elements is greater than and less than at least two other elements in

their previous sublists, therefore the true median is greater than and less

than at least 3n/10 , 30 percentile of elements of the whole list.

2. Lemma:

With that, we guarantee that quickselect finds a good pivot in linear time

O(n) which in turn guarantees quickSort's worst case to be O(nlogn).

proof:

Recurrence relation;

T(n) = {c if(n ≤ 1)

T(n/5) + T(7n/10) + dn if(n > 1)

Theorem:

1. T(n) ≤ k . n for n ≥ n’

2. T(n) = T(n/5) + T(7n/10) + dn

Base Case:

n = 1

T(1) = c ≤ k . 1 therefore k ≥ c

Induction Hypothesis:

Assume, T(j) ≤ b . k for(k ≤ n)

munotes.in

## Page 173

Selection Algorithms

173 Induction Step:

T(n) = T(n5) + T(7n/10) + dn

T(n) ≤k . n/5 + k . 7n/10 + dn = 9/10kn + dn

By induction;

T(n) ≤ k . n for n ≥ 1

The above proof worked because n/5 + 7n/10 < 1 ,we split the original list

in chunks of 5 assuming the original list is divisible by 5. We cou ld also

use another odd number provided the above equation results in a number

below 1, then our theorem will perform its operations in O(n) linear time.

Therefore we get a big theta(n) time complexity for QuickSelect which

proves using this heuristic for QuickSelect ad QuickSort improves worst

case to O(n) and O(nlogn) for the respective algorithms.

1.6 Find the Kth smallest element in the sorted generated array

Given an array arr[] of N elements and an integer K, the task is to

generate an B[] with the fo llowing rules:

1. Copy elements arr[1…N] , N times to array B[].

2. Copy elements arr[1…N/2] , 2*N times to array B[].

3. Copy elements arr[1…N/4] , 3*N times to array B[].

4. Similarly, until only no element is left to be copied to array B[].

Finally print the Kth smallest element from the array B[]. If K is out of

bounds of B[] then return -1.

Examples:

Input: arr[] = {1, 2, 3}, K = 4

Output: 1

{1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 1, 1, 1, 1, 1} is the required array B[]

{1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3} in the sorted form where

1 is the 4th smallest element. Input: arr[] = {2, 4, 5, 1}, K = 13

Output: 2

Approach:

Maintain a Count_Array where we must store the count of times every

element occurs in array B[]. It can be done for range of elements by

adding the count at start index and subtracting the same count at end index

+ 1 location.

1. Take cumulative sum of count array.

2. Maintain all elements of arr[] with their count in Array B[] along with

their counts and sort them based on element value.

3. Traverse th rough vector and see which element has Kth position in B[]

as per their individual counts. munotes.in

## Page 174

Fundamental of

Algorithms

174 4. If K is out of bounds of B[] then return -1.

Below is the implementation of the above approach:

# Python3 implementation of the approach

# Function to return the K th element in B[]

def solve(Array, N, K) :

# Initialize the count Array

count_Arr = [0]*(N + 2) ;

factor = 1;

size = N;

# Reduce N repeatedly to half its value

while (size) :

start = 1;

end = size;

# Add count to start

count_Arr[1] += factor * N;

# Subtract same count after end index

count_Arr[end + 1] -= factor * N;

factor += 1;

size //= 2;

for i in range(2, N + 1) :

count_Arr[i] += count_Arr[i - 1];

# Store each element of Array[] with their count

element = [];

for i in range( N) :

element.append(( Array[i], count_Arr[i + 1] ));

# Sort the elements wrt value

element.sort();

start = 1;

for i in range(N) : munotes.in

## Page 175

Selection Algorithms

175 end = start + element[i][1] - 1;

# If Kth element is in range of element[i]

# return element[i]

if (K >= start a nd K <= end) :

return element[i][0];

start += element[i][1];

# If K is out of bound

return -1;

# Driver code

if __name__ == "__main__" :

arr = [ 2, 4, 5, 1 ];

N = len(arr);

K = 13;

print(solve(arr, N, K));

# This code is contributed by AnkitRai 01

Output:

2

Time Complexity: O(N * log N)

Auxiliary Space: O(N)

Find the kth element in the series generated by the given N ranges

Given N non-overlapping ranges L[] and R[] where the every range

starts after the previous range ends i.e. L[i] > R[i – 1] for all valid i. The

task is to find the Kth element in the series which is formed after sorting

all the elements in all the given ranges in ascending order.

Examples:

Input: L[] = {1, 8, 21}, R[] = {4, 10, 23}, K = 6

Output: 9

The generated series w ill be 1, 2, 3, 4, 8, 9, 10, 21, 22, 23

And the 6th element is 9

Input: L[] = {2, 11, 31}, R[] = {7, 15, 43}, K = 13

Output: 32

munotes.in

## Page 176

Fundamental of

Algorithms

176 Approach: The idea is to use binary search . An array total to store the

number of integers that are present upto ith index, now with the help of

this array find out the index in which the kth integer will lie. Suppose that

index is j, now compute the position of the kth smallest integer in the

interval L[j] to R[j] and find the kth smallest integer using binary search

where low will be L[j] and high will be R[j]. Below is the implementation

of the above approach:

# Python3 implementation of the approach

# Function to return the kth element

# of the required series

def getKthElement(n, k, L, R):

l = 1

h = n

# To store the number of integers that lie

# upto the ith index

total=[0 for i in range(n + 1)]

total[0] = 0

# Compute the number of integers

for i in range(n):

total[i + 1] = total[i] + (R[i] - L[i]) + 1

# Stores the index, lying from 1

# to n,

index = -1

# Using binary search, find the index

# in which the kth element will lie

while (l <= h):

m = (l + h) // 2

if (total[m] > k):

index = m

h = m - 1

elif (total[m] < k):

l = m + 1 munotes.in

## Page 177

Selection Algorithms

177 else :

index = m

break

l = L[index - 1]

h = R[index - 1]

# Find the position of the kth element

# in the interval in which it lies

x = k - total[index - 1]

while (l <= h):

m = (l + h) // 2

if ((m - L[index - 1]) + 1 == x):

return m

elif ((m - L[index - 1]) + 1 > x):

h = m - 1

else:

l = m + 1

# Driver code

L=[ 1, 8, 21]

R=[4, 10, 23]

n = len(L)

k = 6

print(getKthElement(n, k, L, R))

Output:

9

Time Complexity: O(N) Auxiliary Space: O(N)

5.6 FIND THE KTH SMALLEST ELEMENT FROM AN

ARRAY USING SORTING

Finding the kth smallest element of an array (efficiently) may seem a little

tricky at first; however, it can easily be found using a min -heap or by

sorting the arr ay. munotes.in

## Page 178

Fundamental of

Algorithms

178 Algorithm

The following steps are involved in finding the kth smallest element using

sorting.

1. Sort the given array in ascending order using a sorting algorithm

like merge sort , bubble sort , or heap sort .

2. Return the element at index k−1 in the sorted array.

The illustration below furt her explains this concept:

Implementation

The following code snippet implements the above algorithm in C++:

#include

#include

using namespace std;

int main() {

int arr[] = {10, 1, 0, 8, 7, 2};

int size = sizeof(arr)/sizeof(arr[0]) ;

// Sorting the array

sort(arr, arr + size);

// Finding the third smallest element in the array

cout<< "The third smallest element in the array is: "<<

arr[2]< return 0;

}

Find the Kth smallest element in the sorted generated array

Given an array arr[] of N elements and an integer K, the task is to

generate an B[] with the following rules:

1. Copy elements arr[1…N] , N times to array B[].

2. Copy elements arr[1…N/2] , 2*N times to array B[].

3. Copy elements arr[1…N/4] , 3*N times to array B[].

4. Similar ly, until only no element is left to be copied to array B[].

Finally print the Kth smallest element from the array B[]. If K is out of

bounds of B[] then return -1.

Examples:

Input: arr[] = {1, 2, 3}, K = 4

Output: 1

{1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 1, 1 , 1, 1, 1} is the required array B[] munotes.in

## Page 179

Selection Algorithms

179 {1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3} in the sorted form where

1 is the 4th smallest element.

Input: arr[] = {2, 4, 5, 1}, K = 13

Output: 2

Approach:

1. Maintain a Count_Array where we must store the count of times every

element occurs in array B[]. It can be done for range of elements by

adding the count at start index and subtracting the same count at end

index + 1 location.

2. Take cumulative sum of count array.

3. Maintain all elements of arr[] with their coun t in Array B[] along with

their counts and sort them based on element value.

4. Traverse through vector and see which element has Kth position in

B[] as per their individual counts.

5. If K is out of bounds of B[] then return -1.

Below is the implementation of t he above approach:

# Python3 implementation of the approach

# Function to return the Kth element in B[]

defsolve(Array, N, K) :

# Initialize the count Array

count_Arr =[0]*(N +2) ;

factor =1;

size =N;

# Reduce N repeatedly to half its value

while (size) :

start =1;

end =size;

# Add count to start

count_Arr[ 1] +=factor *N;

# Subtract same count after end index

count_Arr[end +1] -=factor *N;

factor +=1; munotes.in

## Page 180

Fundamental of

Algorithms

180 size //=2;

foriinrange (2, N +1) :

count_Arr[i] +=count_Arr[i -1];

# Store each element of Array[] with their count

element =[];

foriinrange (N) :

element.append(( Array[i], count_Arr[i +1] ));

# Sort the elements wrt value

elem ent.sort();

start =1;

foriinrange (N) :

end =start +element[i][ 1] -1;

# If Kth element is in range of element[i]

# return element[i]

if(K >=start andK <=end) :

return element[i][ 0];

start +=eleme nt[i][ 1];

# If K is out of bound

return -1;

# Driver code

if__name__ =="__main__" :

arr=[ 2, 4, 5, 1];

N =len(arr);

K =13;

print (solve(arr, N, K));

# This code is contributed by AnkitRai01

munotes.in

## Page 181

Selection Algorithms

181 Output:

2

Time Complexity: O(N * log N)

Auxiliary Space: O(N)

Exercise end up

1. What is meant by sorting?

2. What are the two main classifications of sorting based on the source

of data?

3. What is meant by external and internal sorting?

4. What is the purpose of quick sort?

5. What is the advantage of quick sort?

6. What is the purpose of insertion sort?

7. Define merge sort.

8. What are the advantages of merge sort?

9. What is linear search?

10. What is binary search?

11. Differentiate linear search and binary search.

12. Differentiate quick sort and merge

13. Give the adv antage of merge sort

14. Distinguish quick sort and insertion sort.

15. Define sorting.

16. Narrate insertion sort with example

17. List examples for various sorting

18. Give the advantage of Merge sort

19. List linear search and binary search with example

20. Narrate insertion sort with example

1. Write and trace the following algorithms with suitable example.

I. Breadth first traversal II. Depth first traversal

2. Sort the sequence 3,1,4,1,5,9,2,6,5 using insertion sort.

3. Give short notes of : (i) Merge sort with suitable example. munotes.in

## Page 182

Fundamental of

Algorithms

182 4. Write an algorithm to sort ‘n’ numbers using quicksort.

5. Show how the following numbers are sorted using quicksort : 42, 28,

90,2, 56. 39, 12, 87 5. Sort the sequence 13,11, 74,37,85,39,22,56,25

using Insertion sort.

6. Explain the operation and implementatio n of merge sort.

7. Explain the operation and implementation of external sorting.

8. Write quick sort algorithm

9. Trace the quick sort algorithm for the following list of numbers.

90,77,60,99,55,88,66

10. Write down the merge sort algorithm and give its worst case, best

case and average case analysis.

11. Explain linear search algorithm with an example.

12. Explain linear search & binary search algorithm in detail.

13. Briefly differentiate linear search algorithm with binary search

algorithm.

5.7 LIST OF REFERENCES

List of r eference materials used in this book.

Quicksort, C.A.R. Hoare, Comput. J., 5 (1962), p. 10 -15.

Sorting, Lloyd Allison, csse.monash.edu.au/~lloyd/tildeAlgDS/Sort .

Sequential and parallel sor ting algorithms, H.W. Lang, iti.fh -

flensburg.de/lang/algorithmen/sortieren/algoen.htm .

5.8 BIBILOGRAPHY

1 In computer science , selection sort is an in-place comparison sorting

algorithm . It has an O(n2) time complexity , which makes it inefficient

on large lists, and generally performs worse than the similar insertion

sort. Selection sort is noted for its simplicity and has performance

advantages over more complicated algorithms in certain situations,

particularly where auxiliary memory is limited.

2 The algorithm divides the input list into two parts: a sorted sublist of

items which is built up from left to right at the front (left) of the list and

a sublist of the remaining unsorted items that occupy the rest of the list.

Initially, the sorted sublist is empty and the unsorted sublist i s the entire

input list. The algorithm proceeds by finding the smallest (or largest,

depending on sorting order) element in the unsorted sublist, exchanging

(swapping) it with the leftmost unsorted element (putting it in sorted

order), and moving the subli st boundaries one element to the right. munotes.in

## Page 183

Selection Algorithms

183 3 The time efficiency of selection sort is quadratic, so there are a number

of sorting techniques which have better time complexity than selection

sort.

4 Example

Here is an example of this sort algorithm sorting five elements:

Sorted sublist Unsorted sublist Least element in unsorted list () (11, 25, 12, 22, 64) 11

(11) (25, 12, 22, 64) 12

(11, 12) (25, 22, 64) 22

(11, 12, 22) (25, 64) 25

(11, 12, 22, 25) (64) 64

(11, 12, 22, 25, 64) ()

arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4]

// and place it at beginning

11 25 12 22 64

// Find the minimum element in arr[1...4]

// and place it at beginning of arr[1...4]

11 12 25 22 64

// Find the min imum element in arr[2...4]

// and place it at beginning of arr[2...4]

11 12 22 25 64

// Find the minimum element in arr[3...4]

// and place it at beginning of arr[3...4]

11 12 22 25 64

munotes.in

## Page 184

Fundamental of

Algorithms

184 Conclusion of selection sort algorithms

Conclusion: Selection sort is s orting algorithm known by its simplicity.

Unfortunately, it lacks efficiency on huge lists of items, and also, it does

not stop unless the number of iterations has been achieved (n -1, n is the

number of elements) even though the list is already sorted.

munotes.in

## Page 185

185 6

ALGORITHM AND DESIGN

TECHNIQUES

Unit Structure :

6.0 Objectives

6.1 Introduction

6.2 Algorithm & it’s classification

6.2.1 Classification by implementation method

6.2.2 Classification by design method

6.2.3 Classification by design approaches

6.2.4 Other classification

6.3 Summary

6.4 Questions

6.5 References

6.0 OBJECTIVES

After this chapter, you will be

Able to Understand Algorithm design and techniques.

Able to develop your own versions for a given computational task and

to compare and contr ast their performance.

Able to apply important algorithmic design paradigms and methods of

analysis.

Able to select appropriate algorithms for a given problem, integrate

multiple algorithms effectively.

6.1 INTRODUCTION

Before solving a new problem, the ge neral tendency is to look for the

similarity of the current problem to other problems for which we have

solutions. This helps us in getting the solution easily. In this chapter, we

will see different ways of classifying the algorithms and in subsequent

chapters we will focus on a few of them (Greedy, Divide and Conquer,

Dynamic Programming).

munotes.in

## Page 186

Fundamental of

Algorithms

186 6.2 ALGORITHM & IT’S CLASSIFICATION

The word Algorithm means ” A set of finite rules or instructions to be

followed in calculations or other problem -solving operations ” Or ” A

procedure for solving a mathematical problem in a finite number of steps

that frequently involves recursive operations”. Therefore an Algorithm is

a procedure to solve a particular problem in a finite number of steps for a

finite -sized input. The algorithms can be classified in various ways. They

are:

1. Implementation Method

2. Design Method

3. Design Approaches

4. Other Classifications

The different algorithms in each classification method are discussed

below.

6.2.1 Classification By Implementation Method

An algorithm may be implemented according to different basical

principles. There are primarily three main categories into which an

algorithm can be named in this type of classification. They are:

Recursion or Iteration:

A recursive algorithm is an alg orithm which calls itself again and

again until a base condition is achieved whereas iterative algorithms

use loops and/ or data structures like stacks , queues to solve any

problem. Every recursive solution can be implemented as an iterative

solution and v ice versa.

Example: The Tower of Hanoi is implemented in a recursive fashion

while Stock Span problem is implemented iteratively.

Exact or Approximate:

Algorithms that are capable of finding an optimal solution for any

problem are known as the exact al gorithm. For all those problems,

where it is not possible to find the most optimized solution, an

approximation algorithm is used. Approximate algorithms are the type

of algorithms that find the result as an average outcome of sub

outcomes to a problem. Example: For NP-Hard Problems ,

approximation algorithms are used. Sorting algorithms are the exact

algorithms.

Serial or Parallel or Distributed Algorithms:

In serial algorithms, one instruction is executed at a time while

parallel algorithms are those in which we divide the problem into

subproblems and execute them on different processors. If parallel munotes.in

## Page 187

Algorithm and Design

Techniques

187 algorithms are distributed on different machines, then they are known

as distributed algorithms.

6.2.2 Classification By Design Method

There are primarily three main categories into which an algorithm can be

named in this type of classification. They are:

Greedy Method: Greedy algorithms work in stages. In each stage, a

decision is made that is good at that point. It assumes that the local

best selection also makes for the global optimal solution. In

the greedy method , at each step, a decision is made to choose

the local optimum , without thinking about the future consequences.

Example : Fractional Knapsack , Activity Selec

Divide and Conquer: The D & C stra tegy solves a problem by:

o Divide: Breaking the problem into sub problems that are

themselves smaller instances of the same type of problem.

o Recursion: Recursively solving these sub problems.

o Conquer: Appropriately combining their answers.

The Divide and Conquer strategy involves dividing the problem into sub

problem, recursively solving them, and then recombining them for the

final answer. Example: Merge sort, Quick sort.

Dynamic Programming:

The approach of Dynamic programming is similar to divide and

conquer . The difference is that whenever we have recursive function

calls with the same result, instead of calling them again we try to store

the result in a data structure in the form of a table and retrieve the

results from the table. Thus, the overall ti me complexity is reduced.

“Dynamic” means we dynamically decide, whether to call a function

or retrieve values from the table. Dynamic programming (DP) and

memoization work together. The difference between DP and divide

and conquer is that in the case of the latter there is no dependency

among the sub problems, whereas in DP there will be an overlap of

sub-problems. By using memoization [maintaining a table for already

solved sub problems] , DP reduces the exponential complexity to

polynomial complexity fo r many problems.

Example: 0-1 Knapsack , subset -sum problem .

Linear Programming:

In Linear Programming, there are inequalities in terms of inputs and

maximizing or minimizing some linear functions of inputs.

Example: Maximum flow of Directed Graph.

munotes.in

## Page 188

Fundamental of

Algorithms

188 Reduc tion (Transform and Conquer ):

In this method, we solve a difficult problem by transforming it into a

known problem for which we have an optimal solution. Basically, the

goal is to find a reducing algorithm whose complexity is not

dominated by the resultin g reduced algorithms. Example: Selection

algorithm for finding the median in a list involves first sorting the list

and then finding out the middle element in the sorted list. These

techniques are also called transform and conquer.

Backtracking:

This tech nique is very useful in solving combinatorial problems that

have a single unique solution . Where we have to find the correct

combination of steps that lead to fulfillment of the task. Such

problems have multiple stages and there are multiple options at ea ch

stage. This approach is based on exploring each available option at

every stage one -by-one. While exploring an option if a point is

reached that doesn’t seem to lead to the solution, the program control

backtracks one step, and starts exploring the next option. In this way,

the program explores all possible course of actions and finds the route

that leads to the solution. Example: N-queen problem , maize problem.

Branch and Bound: This technique is very useful in solving

combinatorial optimization problem that have multiple solutions and

we are interested in find the most optimum solution. In this approach,

the entire solution space is represented in the form of a state space

tree. As the program progresses each state combination is explored,

and the previ ous solution is replaced by new one if it is not the

optimal than the current solution.

Example: Job sequencing, Travelling salesman problem.

6.2.3 Classification By Design Approaches

There are two approaches for designing an algorithm these approaches

include

1. Top-Down Approach :

2. Bottom -up approach

Top-Down Approach: In the top -down approach, a large problem is

divided into small sub -problem. and keep repeating the process of

decomposing problems until the complex problem is solved.

Bottom -up appro ach: The bottom -up approach is also known as the

reverse of top -down approaches. In approach different, part of a

complex program is solved using a programming language and then

this is combined into a complete program.

6.2.4 Other Classifications

Apart fr om classifying the algorithms into the above broad categories,

the algorithm can be classified into other broad categories like: munotes.in

## Page 189

Algorithm and Design

Techniques

189 Randomized Algorithms: Algorithms that make random choices for

faster solutions are known as randomized algorithms .

Example: Randomized Quicksort Algorithm .

Classification by complexity: Algorithms that are classified on the

basis of time taken to get a solution to any problem for input size.

This analysis is known as time complexity analysis . Example: Some

algorithms take O(n), while some take exponential time.

Classification by Research Area: In computer science each field

has its own problems and needs efficient algorithms. Examples:

search algorithms, sorting algorithms, merge algorithms, numerical

algorithms, graph algorit hms, string algorithms, geometric algorithms,

combinatorial algorithms, machine learning, cryptography, parallel

algorithms, data compression algorithms, parsing techniques, and

more.

Branch and Bound Enumeration and Backtracking: These are

mostly used in Artificial Intelligence.

6.3 SUMMARY

In this chapter we have foremost seen an introduction about

algorithm. There are many ways of classifying algorithms and a few

of them we have discuss in brief. We have classify algorithm into

Implementation Method, De sign Approaches, Design Method and few

other types of classifications.

6.4 QUESTIONS

1. Explain Classification by implementation method.

2. Explain classification by design approaches.

3. Explain classification by design method.

4. Explain Other Classification type s.

6.5 REFERENCES

1. Data Structure and Algorithmic Thinking with Python, Narasimha

Karumanchi , CareerMonk Publications, 201 6.

2. Introduction to Algorithm, Thomas H Cormen, PHI

munotes.in

## Page 190

190 7

GREEDY ALGORITHMS

Unit Structure :

7.0 Objectives

7.1 Introduction

7.2 What is greedy algorithm?

7.3 Greedy strategy

7.3.1 Elements of greedy algorithms

7.3.2 Does greedy always work?

7.3.3 Why to use the greedy algorithm?

7.4 Advantages & disa dvantages of greedy algorithm

7.5 Greedy applications

7.6 Understanding greedy technique

7.6.1 Huffman coding

7.6.2 Fractional knapsack problem

7.6.3 Minimum coin change problem

7.7 Summary

7.8 Questions

7.9 References

7.0 OBJECTIVES

In an algori thm design there is no one 'silver bullet' that is a cure for

all computation problems. Different problems require the use of

different kinds of techniques.

To be able to be a good programmer we must know to use all the

different techniques based on the t ype of problem.

After this chapter the learners will be able to understand how to

build up a solution piece by piece, always choosing the next piece

that offers the most obvious and immediate benefit.

munotes.in

## Page 191

Greedy Algorithms

191 7.1 INTRODUCTION

Let us start our discussion with si mple theory that will give us an

understanding of the Greedy technique. In the game of Chess, every

time we make a decision about a move, we have to also think about the

future consequences. Whereas, in the game of Tennis (or Volleyball),

our action is bas ed on the immediate situation. This means that in some

cases making a decision that looks right at that moment gives the best

solution (Greedy), but in other cases it doesn’t. The Greedy technique is

best suited for looking at the immediate situation.

7.2 WHAT IS GREEDY ALGORITHM?

It simply means to pick up a choice/solution that seems the best at the

moment ( being greedy) . This technique is best suited when we want

an immediate situation. It helps to solve optimization problems i.e.

which gives either min imum results or maximum results.

A solution satisfying the condition in the problem is a feasible

solution. The solution having minimum cost out of all possible

feasible solutions is the optimal solution i.e. it is the best solution.

The goal of the greed y algorithm is to find the optimal solution. There

can be only 1 optimal solution. For Example: Let us consider the

example of the container loading problem. In a container loading

problem, a large ship is loaded with cargo. The cargo has containers of

equal sizes but different weights. The cargo capacity is of the ship is

cp. We need to load the containers in the ship in such a way that the

ship has maximum containers. For example, let us say there are a total

of 4 containers with weights: w1=20, w2=75, w3 =40, w4=20. Let cp =

80. Then, to load maximum containers we will load container -1,3, 4.

We will load the containers in the order of increasing weights so that

maximum containers load inside the ship. Here, the order of loading

is container1 →co ntainer4 →container3. C1 C4 C 3 C1 C4 C3

C1,C4,C3 : - Cylinder Cargo with maximum numbers of containers munotes.in

## Page 192

Fundamental of

Algorithms

192 7.3 GREEDY STRATEGY

Greedy algorithms work in stages. In each stage, a decision is made

that is good at that point, without bothering about the future. This

means that some local best is chosen. It assumes that a local good

selection m akes for a global optimal solution.

The choice made by the greedy approach does not consider future

data and choices. In some cases making a decision that looks right at

that moment gives the best solution (Greedy), but in other cases, it

doesn’t.

The gre edy technique is used for optimization problems (where we

have to find the maximum or minimum of something). The Greedy

technique is best suited for looking at the immediate situation. Let us

study Greedy Strategy with an example:

1. Let's start with the root node 20. The weight of the right child is 3

and the weight of the left child is 2.

2. Our problem is to find the largest path. And, the optimal solution at

the moment is 3. So, the greedy algorithm will choose 3.

3. Finally the weight of an only child of 3 is 1 . This gives us our final

result 20 + 3 + 1 = 24.

4. However, it is not the optimal solution. There is another path that

carries more weight (20 + 2 + 10 = 32) as shown in the image below.

Therefore, greedy algorithms do not always give an optimal/fea sible

solution.

7.3.1 Elements Of Greedy Algorithms

Assume that you have an objective function that needs to be

optimized (either maximized or minimized) at a given point. A

Greedy algorithm makes greedy choices at each step to ensure that

the objective f unction is optimized. The Greedy algorithm has only

one shot to compute the optimal solution so that it never goes back

and reverses the decision. The two basic properties of optimal

Greedy algorithms are: 20 2 3

7 100 1 munotes.in

## Page 193

Greedy Algorithms

193 o Greedy choice property.

o Optimal substructure.

Gree dy choice property: - This property says that the globally

optimal solution can be obtained by making a locally optimal

solution (Greedy). The choice made by a Greedy algorithm may

depend on earlier choices but not on the future. It iteratively makes

one Gr eedy choice after another and reduces the given problem to a

smaller one.

Optimal substructure: - A problem exhibits optimal substructure if

an optimal solution to the problem contains optimal solutions to the

subproblems. That means we can solve subproblem s and build up the

solutions to solve larger problems.

7.3.2 D oes greedy always work?

Making locally optimal choices does not always work. Hence,

Greedy algorithms will not always give the best solutions.

7.3.3 Why to use the greedy algorithm?

In many ca ses greedy algorithm is the most intuitive approach to

solve a given optimization problem, that is, it is often the first

guessed solution and is easy to formulate.

Correct greedy algorithms are often more powerful and fast as

compared to other approaches such as dynamic programming. This is

because the greedy approach has to consider only one locally optimal

choice while moving ahead with the solution, while dynamic

programming must check all possible cases.

Greedy algorithms work for a wide range of probl ems (such listed

here), many of which have real -life applications in fields such as

designing networking protocols and scheduling multiple events.

7.4 ADVANTAGES AND DISADVANTAGES OF

GREEDY METHOD

Easy to understand

Easy to code

We do not have to spend t ime re -examining the already computed

values.

Typically have less time complexity.

Analyzing the run time for greedy algorithms will generally be

much easier than for other techniques (like Divide and conquer). For

the Divide and conquer technique, it is n ot clear whether the technique

is fast or slow. This is because at each level of recursion the size of

gets smaller and the number of sub -problems increases. munotes.in

## Page 194

Fundamental of

Algorithms

194 Greedy algorithms can be used for optimization purposes or finding

close to optimization in case o f Hard problems.

The difficult part is that for greedy algorithms you have to work

much harder to understand correctness issues. Even with the correct

algorithm, it is hard to prove why it is correct.

The local optimal solution may not always be globally o ptimal.

Not applicable for many problems

7.5 GREEDY APPLICATIONS

Sorting: Selection sort, Topological sort.

Priority Queues: Heap sort.

Huffman coding compression algorithm.

Prim’s and Kruskal’s algorithms.

Shortest path in Weighted Graph [Dijkstra’s].

Coin change problem.

Fractional Knapsack problem.

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

Job scheduling algorithm.

Greedy techniques can be used as an approximation algorithm for

complex problems.

7.6 UNDERSTANDING GREEDY TECHNIQUE

7.6.1 Huffman Coding

Huffman Coding is a technique of compressing data to reduce its

size without losing any of the details. It was first developed by David

Huffman.

Huffman Coding is generally useful to compress the data in which

there are frequently occurring c haracters. We know that each

character takes 8 bits for representation. But in general, we do not

use all of them. Also, we use some characters more frequently than

others. When reading a file, the system generally reads 8 bits at a

time to read a single c haracter. But this coding scheme is inefficient.

The reason for this is that s ome characters are more frequently used

than other characters. Let’s say that the character ′e′ is used 10 times

more frequently than the character ′q′. It would then be advantageous

for us to instead use a 7 bit code for e and a 9 bit code for q because

that could reduce our overall message length.

On average, using Huffman coding on standard files can reduce them

anywhere from 10% to 30% depending on the character frequencies.

The idea behind the character coding is to give longer binary codes for munotes.in

## Page 195

Greedy Algorithms

195 less fr equent characters and groups of characters. Also, the character

coding is constructed in such a way that no two character codes are

prefixes of each other.

An ExampleLet’s assume that after scanning a file we find the

following character frequencies

Given this, create a binary tree for each character that also stores

the frequency with which it occurs (as shown below): -

The algorithm works as follows: In the list, find the two binary trees

that store minimum frequencies at their nodes. Connect these two

nodes at a newly created common node that will store no character

but will store the sum of the frequencies of all the nodes connected

below it. So our picture looks like this:

Repeat this process until only one tree is left:

munotes.in

## Page 196

Fundamental of

Algorithms

196

Once the tr ee is built, each leaf node corresponds to a letter with a

code. To determine the code for a particular node, traverse from the

root to the leaf node. For each move to the left, append a 0 to the

code, and for each move to the right, append a 1. As a resul t, for the

above generated tree, we get the following codes:

Calculating Bits Saved

Now, let us see how many bits that Huffman coding algorithm is

saving. All we need to do for this calculation is see how many bits

are originally used to store the data a nd subtract from that the

number of bits that are used to store the data using the Huffman

code. In the above example, since we have six characters, let’s

assume each character is stored with a three bit code.

Since there are 133 such characters (multiply total frequencies by 3),

the total number of bits used is 3 * 133 = 399. Using the Huffman

coding frequencies we can calculate the new total number of bits

used:

Thus, we saved 399 – 238 = 161 bits, or nearly 40% of the storage

space. munotes.in

## Page 197

Greedy Algorithms

197

Time Complexity: O(nlogn), since there will be one build_heap, 2n –

2 delete_mins, and n – 2 inserts, on a priority queue that never has

more than n elements.

7.6.2 Fractional knapsack problem

The fractional knapsack problem is also one of the techniques which

are used to solve the knapsack problem. In fractional knapsack, the

items are broken in order to maximize the profit. The problem in

which we break the item is known as a Fractional knapsack problem.

There are basically three approaches to solve the problem:

o The firs t approach is to select the item based on the maximum

profit.

o The second approach is to select the item based on the minimum

weight.

o The third approach is to calculate the ratio of profit/weight.

It is an optimization problem in which we can select fractio nal items

rather than binary choices. The objective is to obtain a filling

knapsack that maximizes the total profit earned. Consider the below

example:

OBJECTS 1 2 3 4 5 6 7

PROFIT(p) 5 10 15 7 8 9 4

WEIGHT(w) 1 3 5 4 1 3 2

W:Weight of the

knapsack 15

n (no of items) 7

munotes.in

## Page 198

Fundamental of

Algorithms

198 First approach : The first approach is to select the item based on the

maximum profit.

Object Profit Weight Remaining weight

3 15 5 15 - 5 = 10

2 10 3 10 - 3 = 7

6 9 3 7 - 3 = 4

5 8 1 4 - 1 = 3

7 7 * ¾ = 5.25 3 3 - 3 = 0

The to tal profit would be equal to (15 + 10 + 9 + 8 + 5.25) = 47.25

Second approach : The second approach is to select the item based on

the minimum weight.

Object Profit Weight Remaining weight

1 5 1 15 - 1 = 14

5 7 1 14 - 1 = 13

7 4 2 13 - 2 = 11

2 10 3 11 - 3 = 8

6 9 3 8 - 3 = 5

4 7 4 5 - 4 = 1

3 15 * 1/5 = 3 1 1 - 1 = 0

In this case, the total profit would be equal to (5 + 7 + 4 + 10 + 9 +

7 + 3) = 4 5.

Third approach :

In the third approach, we will calculate the ratio of profit/weight.

In this case, we first calculate the profit/weight ratio.

1. Object 1: 5/1 = 5

2. Object 2: 10/3 = 3. 33

3. Object 3: 15/5 = 3

4. Object 4: 7/4 = 1.7

5. Object 5: 8/1 = 8 munotes.in

## Page 199

Greedy Algorithms

199 6. Object 6: 9/3 = 3

7. Object 7: 4/2 = 2

Object Profit Weight Remaining weight

5 8 1 15 - 1 = 14

1 5 1 14 - 1 = 13

2 10 3 13 - 3 = 10

3 15 5 10 - 5 = 5

6 9 3 5 - 3 = 2

7 4 2 2 - 2 = 0

As we can observe in the above table that the remaining weight is zero

which means that the knapsack is full. We cannot add more objects in

the knapsack. Therefore, the total prof it would be equal to (8 + 5 + 10

+ 15 + 9 + 4), i.e., 51.

In the first approach, the maximum profit is 47.25. The maximum

profit in the second approach is 4 5. The maximum profit in the third

approach is 51. Therefore, we can say that the third approach, i. e.,

maximum profit/weight ratio is the best approach among all the

approaches.

7.7.3 Minimum Coin Change Problem

The Minimum Coin Change problem is actually a variation of the

problem where you find whether a change of the given amount exists

or not

Give n a set of coins and a value, we have to find the minimum

number of coins which satisfies the value.

Example

o coins[] = {5,10,20,25}

o value = 50

Possible Solutions: - {coin * count}

o {5 * 10} = 50 [10 coins].

o {5 * 8 + 10 * 1} = 50 [9 coins] goes on.

o {10 * 5} = 50 [5 coins].

o {20 * 2 + 10 * 1} = 50 [3 coins].

o {20 * 2 + 5 * 2} = 50 [4 coins].

o {25 * 2} = 50 [2 coins] etc etc

Best Solution: - Two 25 rupees. Total coins two. {25 * 2 }=50. munotes.in

## Page 200

Fundamental of

Algorithms

200 7.7 SUMMARY

In this chapter you learned what a greedy programming paradigm is an d

discovered different techniques and steps to build a greedy solution. The

chapter also discussed applications and mentions the advantages and

disadvantages of greedy algorithm. Towards the end the chapter

introduced different examples to understand greed y techniques.

7.8 QUESTIONS

1. Explain Greedy Strategy with an example.

2. What are the elements of Greedy Strategy.

3. Give advantages and disadvantages of greedy method.

4. Explain in brief Huffman coding.

5. Write a note on Fractional KnapSack Problem.

7.9 REFERENCE S

1. Data Structure and Algorithmic Thinking with Python, Narasimha

Karumanchi, CareerMonk Publications, 201 7.

2. Introduction to Algorithm, Thomas H Cormen, PHI.

3. https://www.javatpoint.com/fractional -knapsack -problem .

4. https://www.geeksforgeeks.org/

5. https://www.codechef.com/wiki/

munotes.in

## Page 201

201 8

DIVIDE AND CONQUER ALGORITHMS

Unit Structure :

8.0 Objectives

8.1 Introduction

8.2 What is divide and conquer strategy?

8.3 Does divide and conquer always work?

8.4 Divide and conquer visualization

8.5 Understanding divide and conquer

8.6 Advant ages & disadvantages of divide & conquer

8.6.1 Advantages of divide & conquer (D&C)

8.6.2 Disadvantages of divide & conquer (D&C)

8.7 Master theorem

8.8 Divide and conquer: problems & solutions

8.9 Summary

8.10 Questions

8.11 References

8.0 OBJECTI VE

After this chapter learners will understand about divide and conquer a

powerful algorithm design technique.

Learners will be able to solve many important problems such as

mergesort, quicksort, calculating Fibonacci numbers, and performing

matrix multip lication.

Learners will be able to solve recursion based problem.

8.1 INTRODUCTION

In the Greedy chapter, we have seen that for many problems the Greedy

strategy failed to provide optimal solutions. Among those problems,

there are some that can be easily s olved by using the Divide and

Conquer (D & C) technique. Divide and Conquer is an important

algorithm design technique based on recursion. munotes.in

## Page 202

Fundamental of

Algorithms

202 The D & C algorithm works by recursively breaking down a problem into

two or more sub problems of the same type, unti l they become simple

enough to be solved directly. The solutions to the sub problems are then

combined to give a solution to the original problem.

8.2 WHAT IS DIVIDE AND CONQUER STRATEGY?

Many useful algorithms are recursive in structure, i.e., to solve th e given

problem, they call themselves recursively one or more times to deal with

closely related sub -problems. These algorithms typically follow a divide -

and-conquer algorithm. The divide and conquer algorithm involves three

steps at each level of recursio n.

The D & C strategy solves a problem by:

o Divide: Breaking the problem into sub problems that are themselves

smaller instances of the same type of problem.

o Recursion: Recursively solving these sub problems.

o Conquer: Appropriately combining their answer.

8.3 DOES DIVIDE AND CONQUER ALWAYS WORK?

It’s not possible to solve all the problems with the Divide & Conquer

technique. As per the definition of D & C, the recursion solves the

subproblems which are of the same type. For all problems it is not possible

to find the subproblems which are the same size and D & C is not a choice

for all problems.

8.4 DIVIDE AND CONQUER VISUALIZATION

Divide and Conquer is an algorithmic pattern. In algorithmic methods,

the design is to take a dispute on a huge input, break the input into

small pieces (sub -problem), decide the problem on each of the small

pieces, and then merge the piecewise solutions into a global solution.

This mechanism of solving the problem is called the Divide & Conquer

Strategy.

For better understandin g, consider the following visualization. Assume

that n is the size of the original problem. As described above, we can

see that the problem is divided into sub problems with each of size n/b

(for some constant b). We solve the sub problems recursively and

combine their solutions to get the solution for the original problem.

Here's how to view one step, assuming that each divide step creates two

subproblems (though some divide -and-conquer algorithms create more

than two): munotes.in

## Page 203

Divide and Conquer

Algorithms

203

If we expand out two more recur sive steps, it looks like this:

8.5 UNDERSTANDING DIVIDE AND CONQUER

For a clear understanding of D & C, let us consider a story. There was

an old man who was a rich farmer and had seven sons. He was afraid

that when he died, his land and his possess ions would be divided

among his seven sons, and that they would quarrel with one another. So

he gathered them together and showed them seven sticks that he had

tied together and told them that anyone who could break the bundle

would inherit everything. The y all tried, but no one could break the

bundle. Then the old man untied the bundle and broke the sticks one by

one. The brothers decided that they should stay together and work

together and succeed together. Source: https://www.khanacademy.org Source: https://www.khanacademy.org

munotes.in

## Page 204

Fundamental of

Algorithms

204 The moral for problem solvers is different. If we can’t solve the

problem, divide it into parts, and solve one part at a time. Therefore a

divide and conquer algorithm is a strategy of solving a large problem

by breaking the problem into smaller sub -problems, solving the sub -

problems, and combining the m to get the desired output. To use the

divide and conquer algorithm, recursion is used.

The divide -and-conquer paradigm is often used to find an optimal

solution of a problem. Its basic idea is to decompose a given problem

into two or more similar, but si mpler, subproblems, to solve them in

turn, and to compose their solutions to solve the given problem.

Problems of sufficient simplicity are solved directly.

Example of Divide and Conquer Algorithm: - Here, we will sort an

array using the divide and conq uer approach, i.e. merge sort.

1. Assume the given array is:

6

5

1

4

3

2

2. Break the array into two segments: - Recursively split each subpart

again into two parts until you have separate elements.

3. Merge the individual parts in an ordered manner. Here, t he steps to

conquer and merge go hand in hand.

8.6 ADVANTAGES OF DIVIDE AND CONQUER (D&C)

8.6.1 Advantages Of Divide And Conquer (D&C)

1. Solving difficult problems: D & C is a powerful method for solving

difficult problems. As an example, consider the Tower of Hanoi

problem. This requires breaking the problem into subproblems, solving

the trivial cases and combining the subproblems to solve the original

problem. Dividing the problem into subproblems so that subproblems

can be combined again is a major difficu lty in designing a new

algorithm. For many such problems D & C provides a simple solution. Source https://mobisoftinfotech.com/resources/blog/ munotes.in

## Page 205

Divide and Conquer

Algorithms

205 2. Parallelism: Since D & C allows us to solve the subproblems

independently, this allows for execution in multiprocessor machines,

especially shared -memory systems whe re the communication of data

between processors does not need to be planned in advance, because

different subproblems can be executed on different processors.

3. Memory access: D & C algorithms naturally tend to make efficient use

of memory caches. This is be cause once a subproblem is small, all its

subproblems can be solved within the cache, without accessing the

slower main memory.

8.6.2 DISADVANTAGES OF DIVIDE AND CONQUER (D&C)

One disadvantage of this approach is that recursion is slow. This is

beacause o f the overhead of the repeated subproblem calls. Also the

algorithm need stack for storing the calls. Actually this depends upon

the implementation style. With large enough recursive base cases , the

overhead of recursion can become negligible for many pro blems.

Another problem with D & C is that, for some problems, it may be

more complicated than an iterative approach. For example, to add n

numbers, a simple loop to add them up in sequence is much easier than

a D & C approach that breaks the set of numbers into two halves, adds

them recursively, and then adds the sums.

Since most of its algorithms are designed by incorporating recursion, so

it necessitates high memory management.

An explicit stack may overuse the space.

It may even crash the system if the r ecursion is performed rigorously

greater than the stack present in the CPU.

8.7 MASTER THEOREM

As stated above, in the D & C method, we solve the sub problems

recursively. All problems are generally defined in terms of recursive

definitions. These recursiv e problems can easily be solved using Master

theorem.

The above algorithm divides the problem into a subproblems, each of

size n/b and solve them recursively to compute the problem and the

extra work done for problem is given by f(n), i.e., the time to cre ate the

subproblems and combine their results in the above procedure.

So, according to master theorem the runtime of the above algorithm can

be expressed as:

T(n) = aT(n/b) + f(n) where n = size of the problem

a = number of subproblems in the recursion and a >= 1.

n/b = size of each subproblem. munotes.in

## Page 206

Fundamental of

Algorithms

206 f(n) = cost of work done outside the recursive calls like dividing into

subproblems and cost of combining them to get the solution.

If the recurrence is of the form T(n)=aT

+

, where a ≥

1, b > 1, k ≥ 0 and p is a real number, then the complexity can be

directly given as:

1. Example -1: Binary Search – T(n) = T(n/2) + O(1)

a = 1, b = 2, k = 0 and p = 0

= 1. So, a =

and p > -1 [Case 2.(a)]

T(n) = θ(

)

T(n) = θ(logn)

2. Example -2: Merge Sort – T(n) = 2T(n/2) + O(n)

a = 2, b = 2, k = 1, p = 0

= 2. So, a =

and p > -1 [Case 2.(a)]

T(n) = θ(

)

T(n) = θ(nlogn)

3. Example -3: T(n) = 3T(n/2) + n2

a = 3, b = 2, k = 2, p = 0

= 4. So, a <

and p = 0 [Case 3.(a)]

T(n) = θ(

n)

T(n) = θ(

)

8.8 DIVIDE AND CONQUER APPLICATIONS

1. Binary Search: Binary Search is a searching algorithm for finding an

element's p osition in a sorted array. In this approach, the element is

always searched in the middle of a portion of an array.

2. Merge Sort: Merge Sort is one of the most popular sorting algorithms

that is based on the principle of Divide and Conquer Algorithm. Here, a

problem is divided into multiple sub -problems. Each sub -problem is munotes.in

## Page 207

Divide and Conquer

Algorithms

207 solved individually. Finally, sub -problems are combined to form the

final solution.

3. Quick Sort: Quicksort is a sorting algorithm based on the divide and

conquer approach where

a. An array is divided into subarrays by selecting a pivot element

(element selected from the array).

b. While dividing the array, the pivot element should be positioned in

such a way that elements less than pivot are kept on the left side and

elements greater than pivo t are on the right side of the pivot.

c. The left and right subarrays are also divided using the same

approach. This process continues until each subarray contains a

single element. At this point, elements are already sorted. Finally,

elements are combined to form a sorted array.

4. Median Finding: The median -of-medians algorithm is a deterministic

linear -time selection algorithm. The algorithm works by dividing a list

into sublists and then determines the approximate median in each of the

sublists. Then, it take s those medians and puts them into a list and finds

the median of that list. It uses that median value as a pivot and

compares other elements of the list against the pivot. If an element is

less than the pivot value, the element is placed to the left of th e pivot,

and if the element has a value greater than the pivot, it is placed to the

right. The algorithm recurses on the list, honing in on the value it is

looking for.

5. Min and Max Finding: Max-Min problem is to find a maximum and

minimum element from the given array. We can effectively solve it

using divide and conquer approach. Divide and conquer approach for

Max. Min problem works in three stages.

a. If a1 is the only element in the array, a1 is the maximum and

minimum.

b. If the array contains only two eleme nts a1 and a2, then the single

comparison between two elements can decide the minimum and

maximum of them.

c. If there are more than two elements, the algorithm divides the array

from the middle and creates two subproblems. Both subproblems are

treated as an independent problem and the same recursive process is

applied to them. This division continues until subproblem size

becomes one or two.

After solving two subproblems, their minimum and maximum numbers

are compared to build the solution of the large proble m. This process

continues in a bottom -up fashion to build the solution of a parent problem.

6. Matrix Multiplication: Matrix multiplication is an important operation

in many mathematical and image processing applications. Suppose we

want to multiply two matri ces A and B, each of size n x n,

multiplication is operation is defined as munotes.in

## Page 208

Fundamental of

Algorithms

208

=

*

=

+

=

+

=

+

=

+

This approach is very costly as it required 8 multi plications and 4

additions.

8.9 DIVIDE AND CONQUER: PROBLEMS &

SOLUTIONS

Problem -1 Let us consider an algorithm A which solves problems by

dividing them into five subproblems of half the size, recursively solving

each subproblem, and then combining the sol utions in linear time. What is

the complexity of this algorithm?

Solution: Let us assume that the input size is n and T(n) defines the

solution to the given problem. As per the description, the algorithm

divides the problem into 5 sub problems with each of size

. So we need

to solve 5T(

). subproblems. After solving these sub problems, the given

array (linear time) is scanned to combine these solutions. The total

recurrence algorithm for this problem can be given as: T(n)=5T (

) + O(n)

. Using the Master theorem (of D & C), we get the complexity O(n

)

O(

)

O(

).

Problem 2: - We are given two sorted lists of size n. Give an algorithm for

finding the media n element in the union of the two lists.

Solution: We use the Merge Sort process. Use merge procedure of merge

sort. Keep track of the count while comparing elements of two arrays. If

the count becomes n (since there are 2n elements), we have reached the

median. Take the average of the elements at indexes n – 1 and n in the

merged array.

Time Complexity: O(n).

Problem 3: - Can we give the algorithm if the size of the two lists are not

the same?

Solution: The solution is similar to the previous problem. Let us assume

that the lengths of two

lists are m and n. In this case we need to stop when the counter reaches (m

+ n)/2.

munotes.in

## Page 209

Divide and Conquer

Algorithms

209 Time Complexity: O((m + n)/2).

Problem 4: - Can we improve the time complexity of Problem -2 to

O(logn)?

Solution: Yes, using the D & C app roach. Let us assume that the given

two lists are L1 and L2.

Algorithm:

1. Find the medians of the given sorted input arrays L1[] and L2[].

Assume that those medians are m1 and m2.

2. If m1 and m2 are equal then return m1 (or m2).

3. If m1 is greater than m2, then the final median will be below two sub

arrays.

4. From first element of L1 to m1.

5. From m2 to last element of L2.

6. If m2 is greater than m1, then median is present in one of the two sub

arrays below.

8. From m1 to last element of L1.

8. From f irst element of L2 to m2.

9. Repeat the above process until the size of both the sub arrays

becomes 2.

10. If size of the two arrays is 2, then use the formula below to get the

median.

11. Median = (max(L1[0],L2[0]) + min(L1[1],L2[1])/2

Problem 5: - We are testing “unbreakable” laptops and our goal is to find

out how unbreakable they really are. In particular, we work in an n -story

building and want to find out the lowest floor from which we can drop the

laptop without breaking it (call this “the ceiling”). Suppose we are given

two laptops and want to find the highest ceiling possible. Give an

algorithm that minimizes the number of tries we need to make f(n)

(hopefully, f(n) is sub -linear, as a linear f(n) yields a trivial solution).

Solution : For the given problem, we cannot use binary search as we

cannot divide the problem and solve it recursively. Let us take an example

for understanding the scenario. Let us say 14 is the answer. That means we

need 14 drops to find the answer. First we drop from height 14, and if

it breaks we try all floors from 1 to 13. If it doesn’t break then we are left

13 drops, so we will drop it from 14 + 13 + 1 = 28th floor. The reason

being if it breaks at the 28th floor we can try all the floors from 15 to 27 in

12 drops (total of 14 drops). If it did not break, then we are left with 11 munotes.in

## Page 210

Fundamental of

Algorithms

210 drops and we can try to figure out the floor in 14 drops. From the above

example, it can be seen that we first tried with a gap of 14 floors, and then

followed by 13 floors, then 1 2 and so on. So if the answer is k then we are

trying the intervals at k, k – 1, k – 2 ....1. Given that the number of floors

is n, we have to relate these two. Since the maximum floor from which we

can try is n, the total skips should be less than n.

This gives:

= k + (k -1) + (k -2) + ---- + 1 ≤ n

=

≤ n

= k ≤

8.10 SUMMARY

In this chapter we studied the Divide and Conquer strategy(D&C)

which works in three stages as follows:

Divide: This involves dividing the problem into smaller sub-problems.

Conquer: Solve sub -problems by calling recursively until solved.

Combine: Combine the sub -problems to get the final solution of the

whole problem.

We have also understood various advantages and disadvantages of this

strategy.

We studied abou t various algorithms under D&C techniques.

At the end some problems and its solution using D&C technique was

mentioned.

8.11 QUESTIONS

1. Write a short note on Divide and Conquer Strategy.

2. Explain advantages and disadvantages of divide and conquer.

3. Explain disadvantages of divide and conquer.

4. Explain any 5 applications of divide and conquer.

5. Describe master theorem in detail.

munotes.in

## Page 211

Divide and Conquer

Algorithms

211 8.12 REFERENCES

1. Data Structure and Algorithmic Thinking with Python, Narasimha

Karumanchi, CareerMonk Publications, 2016.

2. Introduction to Algorithm, Thomas H Cormen, PHI.

3. https://www.javatpoint.com/fractional -knapsack -problem .

4. https://www.geeksforgeeks.org/

5. https://www.codechef.com/wiki/

munotes.in

## Page 212

212 9

DYNAMIC PROGRAMMING

Unit Structure

9.0 Objectives

9.1 Introduction

9.2 What i s Dynamic Programming Strategy?

9.2.1 What is Recursion?

9.2.2 Difference between dynamic programming & recursion?

9.3 Properties of dynamic programming strategy

9.3.1 Can dynamic programming solve all problems?

9.4 Dynamic programming approaches

9.4.1 Bottom -up versus top -down programming

9.4.2 Which one is better?

9.5 Examples of dynamic programming algorithms

9.6 Understanding dynamic programming

9.7 Longest c ommon subsequence

9.8 summary

9.9 Questions

9.10 References

9.0 OBJECTIVE

To gain an understanding of the technique of dynamic programming.

To be able to adapt it to new problems. To be able to use dynamic

programming to develop new logic.

Towards the end of this chapter, you will have a better understanding of

the recursion and dynamic programming approach

Learners will also be able to analyze and solve various application

using dynamic strategy.

Learners will also be able to analyze the problem and wi ll be able to

recognize the order in which the sub -problems are solved and will start

solving from the trivial subproblem, up towards the given problem . munotes.in

## Page 213

Dynamic

Programming

213 Learners will be able to reason about different dynamic algorithm

correctness and complexity

9.1 INTR ODUCTION

In this chapter we will try to solve the problems for which we failed to get

the optimal solutions

using other techniques (say, Divide & Conquer and Greedy methods).

Dynamic Programming (DP) is a simple technique but it can be difficult to

master. One easy way to identify and solve DP problems is by solving as

many problems as possible. The ter m Programming is not related to

coding but it is from literature, and means filling tables (similar to Linear

Programming).

9.2 WHAT IS DYNAMIC PROGRAMMING STRATEGY?

Dynamic programming and memoization work together. The main

difference between dynamic programming and divide and conquer is

that in the case of the latter, sub problems are independent, whereas in

DP there can be an overlap of sub problems. By u sing memorization

[maintaining a table of sub problems already solved], dynamic

programming reduces the exponential complexity to polynomial

complexity (O(

,O(

,etc) for many problems.

The major components of DP are:

o Recursion: Solves sub problems recursively.

o Memoization: Stores already computed values in table

(Memoization means caching).

Dynamic Programming = Recursion + Memoization .

Therefore, dynamic p rogramming is mainly an optimization over plain

recursion. Wherever we see a recursive solution that has repeated calls

for the same inputs, we can optimize it using Dynamic Programming.

The idea is to simply store the results of subproblems so that we do not

have to re -compute them when needed later. This simple optimization

reduces time complexities from exponential to polynomial.

9.2.1 What is Recursion?

The process in which a function calls itself directly or indirectly is

called recursion and the corresponding function is called a recursive

function. Using a recursive algo rithm, certain problems can be solved

quite easily.

Examples of such problems are Towers of Hanoi (TOH),

Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc. A

recursive function solves a particular problem by calling a copy of itself munotes.in

## Page 214

Fundamental of

Algorithms

214 and solvin g smaller subproblems of the original problems. Many more

recursive calls can be generated as and when required. It is essential to

know that we should provide a certain case in order to terminate this

recursion process.

So we can say that every time the function calls itself with a simpler

version of the original problem.

9.2.2 Difference between a dynamic programming algorithm and

recursion?

In dynamic programming, problems are solved by breaking them down

into smaller ones to solve the larger ones, whil e recursion is when a

function is called and executed by itself. While dynamic programming

can function without making use of recursion techniques, since the

purpose of dynamic programming is to optimize and accelerate the

process, programmers usually make use of recursion techniques to

accelerate and turn the process efficiently.

When a function can execute a specific task by calling itself, receive

the name of the recursive function. In order to perform and accomplish

the work, this function calls itself when it has to be executed.

Using dynamic programming, you can break a problem into smaller

parts, called subproblems, to solve it. Dynamic programming involves

solving the problem for the first time, then using memoization to store

the solutions.

Therefor e, the main difference between the two techniques is their

intended use; recursion is used to automate a function, whereas

dynamic programming is an optimization technique used to solve

problems.

Recursive functions recognize when they are needed, execute

themselves, then stop working. When the function identifies the

moment it is needed, it calls itself and is executed; this is called a

recursive case. As a result, the function must stop once the task is

completed, known as the base case.

By establishing s tates, dynamic programming recognizes the problem

and divides it into sub -problems in order to solve the whole scene.

After solving these sub -problems, or variables, the programmer must

establish a mathematical relationship between them. Last but not least ,

these solutions and results are stored as algorithms, so they can be

accessed in the future without having to solve the whole problem again.

9.3 PROPERTIES OF DYNAMIC PROGRAMMING

STRATEGY

The two dynamic programming properties which can tell whether it c an

solve the given problem or not are:

o Optimal substructure: Optimal substructure property materializes

when you can arrive at an optimal solution after constructing all the munotes.in

## Page 215

Dynamic

Programming

215 other solutions that occurred from every subproblem you solved.

The solution you c alculate from each overlap applies to the overall

problem in order to function and optimize recursion. In the example

of the Fibonacci sequence, each subproblem contains a solution that

you can apply to each successive subproblem to find the next

number in the series, making the entire problem display optimal

substructure property. Therefore we can conclude it means that an

optimal solution to a problem contains optimal solutions to sub

problems.

o Overlapping sub problems: Subproblems are smaller variations of

an original, larger problem. For example, in the Fibonacci sequence,

each number in the series is the sum of its two preceding numbers

(0, 1, 1, 2, 3, 5, 8,...). If you want to calculate the nth Fibonacci

value in the sequence, you can break down the en tire problem into

smaller subproblems. These subproblems then overlap with one

another as you find solutions by solving the same subproblem

repeatedly. The overlap in subproblems occurs with any problem,

which allows you to apply dynamic programming to bre ak down

complex programming tasks into smaller parts. Therefore we can

conclude that a recursive solution contains a small number of

distinct sub problems repeated many times.

9.3.1 Can dynamic programming solve all problems?

Like Greedy and Divide and Co nquer techniques, DP cannot solve

every problem. There are problems which cannot be solved by any

algorithmic technique [Greedy, Divide and Conquer and Dynamic

Programming].

The difference between Dynamic Programming and straightforward

recursion is in mem orization of recursive calls. If the sub problems are

independent and there is no repetition then memorization does not help,

so dynamic programming is not a solution for all problems.

9.4 DYNAMIC PROGRAMMING APPROACHES

Basically there are two approaches f or solving DP problems:

1. Bottom -up dynamic programming .

2. Top-down dynamic programming

9.4.1 Bottom -Up Dynamic Programming

o In this method, we evaluate the function starting with the smallest

possible input argument value and then we step through possible

values, slowly increasing the input argument value. While computing

the values we store all computed values in a table (memory). As larger

arguments are evaluated, pre -computed values for smaller arguments

can be used. munotes.in

## Page 216

Fundamental of

Algorithms

216 o Analyze the problem and see in what orde r the subproblems are solved,

and work your way up from the trivial subproblem to the given

problem. This process ensures that the subproblems are solved before

the main problem.

2. TOP -DOWN DYNAMIC PROGRAMMING

o In this method, the problem is broken into su b problems; each of

these sub problems is solved; and the solutions remembered, in case they

need to be solved. Also, we save each computed value as the final action

of the recursive function, and as the first action we check if pre -computed

value exists.

o You solve all the related sub -problems first instead of applying

recursion. As bottom -up tabulation requires multiple solvencies, dynamic

programming uses an n -dimensional table, where n represents a value of

zero or greater. As you solve each subproblem w ithin the table, you can

then use the results to compute the original problem.

9.4.1 Bottom -Up Versus Top -Down Programming

In bottom -up programming, the programmer has to select values to

calculate and decide the order of calculation. In this case, all su b

problems that might be needed are solved in advance and then used to

build up solutions to larger problems. In top -down programming, the

recursive struct ure of the original code is preserved, but unnecessary

recalcula tion is avoided. The problem is broke n into sub problems,

these sub problems are solved and the solutions remembered, in case

they need to be solved again.

Let us understand the difference between the two approaches with an

example.

Apply the Fibonacci sequence, where each number in the seri es

represents the sum of the first two preceding numbers:

1. Bottom -up Approach - In this example, apply the Fibonacci sequence

to break down the entire computation when you want to calculate the

nth value in the series. With the same number sequence {0, 1, 1, 2, 3, 5,

8,...}, you can see that the next value in the series results in 13, since 5

and 8 give a sum of 13.

Using the bottom -up method to break down the entire problem Fib(n),

apply the sequence equation [Fib(n - 1) + Fib(n - 2), when n > 1] for eac h

subproblem you want to find an optimal solution for. Suppose you want to

compute the next nth values when n = 23:

Fib(n) = Fib(n - 1) + Fib(n - 2) =

Fib(23) = Fib(23 - 1) + Fib(23 - 2) =

Fib(23) = Fib(22) + Fib(21) = Fib(43) . munotes.in

## Page 217

Dynamic

Programming

217 The result Fib(43) then applies to the computation of the next values in the

series when n = 43:

Fib(n) = Fib(n - 1) + Fib(n - 2) =

Fib(43) = Fib(43 - 1) + Fib(43 - 2) =

Fib(n) = Fib(42) + Fib(41) = Fib(83) then

Fib(83) = Fib(83 - 1) + Fib(83 - 2) =

Fib(83) = Fib(82) + Fib(81) = Fib(163) .

You can continue using this optimal solution for each subproblem to

calculate the next values within the Fibonacci sequence, giving you the

ability to break down the initial problem of Fib(n) = Fib(n - 1) + Fib(n -

2), when n > 1.

2. Top Down Approach : Understanding that the sum of the first two

preceding values is the next number in the series can help you solve the

entire problem when you want to calculate the nth Fibonacci number.

Because you know the pattern for computing the future values in the

series, you can apply a formula to determine the optimal solution without

breaking down the problem into smaller subproblems. Using the

appropriate formula when n > 1, you can compute an optimal solution

with the top -down method when solving for an nth value of 13:

Fib(n) = Fib(n - 1) + Fib(n - 2) =

Fib(13) = Fib(13 - 1) + Fib(13 - 2) =

Fib(n) = Fib(12) + Fib(11) = 23

Using the top -down approach and applying memorization, you can cache

the result of 23 in the database to input and call on your code s tring for

additional tasks.

9.4.2 Which one is better?

The top -down approach is typically recursive. It has the overhead of

recursive calls and therefore is slower than the bottom -up approach.

One might find the top -down approach easier to implement becau se we

use an array of some sort of lookup table to store results during

recursion. While for the bottom -up approach we need to define the

order of iteration and define an n -dimensional table for storing results.

The top -down approach might also run into s tack overflow conditions

in the case of a very deep recursion tree .

munotes.in

## Page 218

Fundamental of

Algorithms

218 9.5 EXAMPLES OF DYNAMIC PROGRAMMING

ALGORITHMS

1. Many String algorithms including longest common subsequence,

longest increasing subsequence, longest common substring, edit distance.

9.6 LONGEST COMMON SUBSTRING

o Let m and n be the lengths of the first and second strings respectively.

o A simple solution is to one by one consider all substrings of the first

string and for every substring check if it is a substring in the second

string. Keep track of the maximum length substring. There will be

O(m^2) substrings and we can find whether a string is substring on

another string in O(n) time (See this). So overall time complexity of

this method would be O(n *

).

o Dynamic Programming can be used to find the longest common

substring in O(m*n) time. The idea is to find the length of the longest

common suffix for all substrings of both strings and store these lengths

in a table.

o The longest common suffix has following optimal substructure

property.

If last characters match, then we reduce both lengths by 1 : - LCSuff(X,

Y, m, n) = LCSuff(X, Y, m -1, n-1) + 1 if X[m -1] = Y[n -1] .

If last characters do not match, then result is 0, i.e., : -

LCSuff(X, Y, m, n) = 0 if (X[m -1] != Y[n -1]).

Now we c onsider suffixes of different substrings ending at different

indexes. The maximum length Longest Common Suffix is the longest

common substring.

LCSubStr(X, Y, m, n) = Max(LCSuff(X, Y, i, j)) where 1 <= i <= m

and 1 <= j <= n.

o Given two strings ‘X’ and ‘Y’ , find the length of the longest

common substring .

Input : X = “zxabcdezy”, y = “yzabcdezx”

Output : 6

Explanation:

The longest common substring is “abcdez” and is of length 6.

munotes.in

## Page 219

Dynamic

Programming

219 EDIT DISTANCE

o Levenshtein (1966) introduced the edit distance between two s trings as

the minimum number of elementary operations (insertions, deletions,

and substitutions) needed to transform one string into the other .

o The Edit distance is a problem to measure how much two strings are

different from one another by counting the m inimum number of

operations required to convert one string into the other. Edit distance

problem can be solved by many different approaches.But the most

efficient approach to solve the Edit distance problem is Dynamic

programming approach which takes the O (N * M) time complexity,

where N and M are sizes of the strings.

o Edit distance has different definitions which uses different sets of string

operations. Levenshtein distance operations is the basic set of

operations which is used in Edit distance Problem.

o Operation allowed are:

Delete any character from the string.

Replace any character with any other .

Add any character into any part of the string.

o d(v,w) = MIN number of elementary operations to transform v

w .

o Let us Transform TGCATAT → ATCCG AT to understand the

concept

TGCATAT (delete last T)

TGCATA (delete last A)

ATGCAT (insert A at front)

ATCCAT (substitute C for G)

ATCCGAT (insert G before last A) d(v,w)=5

o EXAMPLE: - Input: str1 = “bat”, str2 = “b ut”

Output: d(v,w)= 1 (We can convert str1 into str2 by replacing ‘a’ with

‘u’.)

Input: str1 = “sunday”, str2 = “saturday” ; Output: d(v,w)= 3

Last three and first characters are same. We basically need to

convert “un” to “atur”. This can be done using following

operations: -

Replace ‘n’ with ‘r’, insert t, insert a

munotes.in

## Page 220

Fundamental of

Algorithms

220 COMMON SUBSEQUENCE

o Given two sequences v =

,

, …,

, and w =

,

, …,

a

common subsequence of v and w is a sequence of positions in

o v: 1 <

<

< … <

< m and a sequence of positions in

o w: 1 <

<

< … <

< n such that the

-th letter of v is equal to the

-th letter of w.

o Example: v = ATGCCAT, w = TCGGGCTATC. Then take:

= 2,

= 3,

= 6,

= 7

= 1,

= 3, ,

= 8, ,

= 9

o This gives us that the common subsequence is TGAT.

2. Bellman -Ford algorithm :-

o The B ellman -Ford Algorithm determines the shortest route from a

particular source vertex to every other weighted digraph vertices. The

Bellman -Ford algorithm can handle graphs where some of the edge

weights are negative numbers and produce a correct answer, unl ike

Dijkstra’s algorithm, which does not confirm whether it makes the

correct answer. However, it is much slower than Dijkstra’s algorithm.

o The Bellman -Ford algorithm works by relaxation; that is, it gives

approximate distances that better ones continuous ly replace until a

solution is reached. The approximate distances are usually

overestimated compared to the distance between the vertices. The

replacement values reflect the minimum old value and the length of a

newly found path.

o This algorithm terminates upon finding a negative cycle and thus can

be applied to cycle -canceling techniques in network flow analysis .

3. Floyd -Warshall algorithm

o The all pair shortest path algorithm is also known as Floyd -Warshall

algorithm is used to find all pair shortest path pr oblem from a given

weighted graph. As a result of this algorithm, it will generate a matrix,

which will represent the minimum distance from any node to all other

nodes in the graph.

o The Floyd -Warshall method uses a technique of dynamic programming

to locat e the shortest pathways. It determines the shortest route across

all pairings of vertices in a graph with weights. Both directed and

undirected weighted graphs can use it.

o This program compares each pair of vertices’ potential routes through

the graph. It gradually optimizes an estimate of the shortest route

between two vertices to determine the shortest distance between two munotes.in

## Page 221

Dynamic

Programming

221 vertices in a chart. With simple modifications to it, one can reconstruct

the paths.

o This method for dynamic programming contains two subtypes:

Behavior with negative cycles : Users can use the Floyd -Warshall

algorithm to find negative cycles. You can do this by inspecting the

diagonal path matrix for a negative number that would indicate the

graph contains one negative cycle. In a neg ative cycle, the sum of the

edges is a negative value; thus, there cannot be a shortest path between

any pair of vertices. Exponentially huge numbers are generated if a

negative cycle occurs during algorithm execution.

Time complexity: The Floyd -Warshall a lgorithm has three loops, each

with constant complexity. As a result, the Floyd -Warshall complexity

has a time complexity of O(n3). Wherein n represents the number of

network nodes.

4. Chain matrix multiplication

o If a chain of matrices is given, we have to fi nd the minimum number of

the correct sequence of matrices to multiply.

o We know that the matrix multiplication is associative, so four matrices

ABCD, we can multiply A(BCD), (AB)(CD), (ABC)D, A(BC)D, in

these sequences. Like these sequences, our task is to find which

ordering is efficient to multiply.

o In the give Matrix chain multiplication problem: Determine the optimal

parenthesization of a product of n matrices.

o Matrix chain multiplication (or Matrix Chain Ordering Problem,

MCOP) is an optimization proble m that to find the most efficient way

to multiply a given sequence of matrices. The problem is not actually to

perform the multiplications but merely to decide the sequence of the

matrix multiplications involved.

o The matrix multiplication is associative a s no matter how the product is

parenthesized, the result obtained will remain the same.n input there is

an array say arr, which contains arr[] = {1, 2, 3, 4}. It means the

matrices are of the order (1 x 2), (2 x 3), (3 x 4). Input: The orders of

the input matrices. {1, 2, 3, 4}. It means the matrices are {(1 x 2), (2 x

3), (3 x 4)}. Output: Minimum number of operations need multiply

these three matrices. Here the result is 1 9.

o EXAMPLE: Lets take four matrices A, B, C, and D, we would have:

((AB)C)D = ((A(B C))D) = (AB)(CD) = A((BC)D) = A(B(CD))

However, the order in which the product is parenthesized affects the

number of simple arithmetic operations needed to compute the

product. munotes.in

## Page 222

Fundamental of

Algorithms

222 For example, if A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is

a 5 × 60 matrix, then computing (AB)C needs (10×30×5) +

(10×5×60) = 1500 + 3000 = 4500 operations while computing

A(BC) needs (30×5×60) + (10×30×60) = 9000 + 18000 = 27000

operations.

Clearly, the first method is more efficient.

o Chain Matrix Multiplication Proble m: Given a sequence of matrices

A1, A2,...,An and dimensions p0, p1,...,pn where Ai is of dimension

pi−1 × pi, determine the order of multiplication (represented, say, as a

binary tree) that minimizes the number of operations.

o Important Note : This algorith m does not perform the multiplications,

it just determines the best order in which to perform the multiplications.

5. Subset Sum

o A subset is a set that contains the elements of a previously defined set.

For eg. {a, b} is a subset of {a,b,c,e,f}. In this, you have to find a subset

or the set of numbers from the given array that amount to the given

value in the input .

o Given a set of N non -negative integers and a target sum S, determine if

there exists a subset of the given set such that the sum of the elements

of the subset equals to S. Return 1 if there exists such subset, otherwise

return 0.

o Therefore a subset sum problem is that given a subset A of n positive

integers and a value sum is given, find whether or not there exists any

subset of the given set, the s um of whose elements is equal to the given

value of sum.

o Let's look at the problem statement: "You are given an array of non -

negative numbers and a value 'sum'. You have to find out whether a

subset of the given array is present whose sum is equal to the g iven

value."

o Input: {10, 0, 5, 8, 6, 2, 4}

15 Output: True

o Explanation: The sum of the subset {5,8,2} gives the sum as 15.

Therefore, the answer comes out to be true.

10

0

5

8

6

2

4

o We create a boolean subset[][] and fill it in bottom up manner .

o subset[i][j] denotes if there is a subset of sum j with element at index i -

1 as the last element

munotes.in

## Page 223

Dynamic

Programming

223

o Base cases include:

j=0 then subset[i][0] will be true as the sum for empty set is 0 .

If i=0, then subset[0][j] will be false, as with no e lements, we can get no

sum.

o If element at index i (E1) is greater than j, then subset[i][j] = false as

we cannot get a subset of positive numbers with E1 as a member. If we

include element at index i (E1), we get

6. 0/1 Knapsack: -

o A knapsack (kind o f shoulder bag) with limited weight capacity.

o Few items each having some weight and value.

o The Knapsack problem states - Which items should be placed into the

knapsack such that - The value or profit obtained by putting the items

into the knapsack is maximum and the weight limit of the knapsack

does not exceed.

o 0/1 Knapsack Problem is one of the variant of Knapsack problem

where s the name suggests, items are indivisible here.We can not take

the fraction of any item. We have to either take an item completely or

leave it completely.It is solved using dynamic programming approach.

o Step-01: Draw a table say ‘T’ with (n+1) number of rows and (w+1)

number of columns. Fill all the boxes of 0th row and 0th column with

zeroes as shown -

subset[i][j] = true if there is a subset with:

* the i -th element as the last element

* sum equal to j subset[i][0] = true as sum of {} = 0

subset[0][j] = false as with no elements

we can get no sum

subset[i][j] = subset[i -1][j-E1];

where E1 = array[i -1]

munotes.in

## Page 224

Fundamental of

Algorithms

224 0 1 2 3 W

0 0 0 0 0 ………… 0

1 0

2 0

……

n 0

o Step-02: Start filling the table row wise top to bottom from left to right.

Use the following formula - :- T (i , j) = max { T ( i -1 , j ) ,

+ T( i -

1 , j –

+ ) } . Here, T(i , j) = maxi mum value of the

selected items if we can take items 1 to i and have weight restrictions of

j. This step leads to completely filling the table.Then, value of the last

box represents the maximum possible value that can be put into the

knapsack.

o Step-03: To identify the items that must be put into the knapsack to

obtain that maximum profit, consider the last column of the table. Start

scanning the entries from bottom to top.On encountering an entry

whose value is not same as the value stored in the entry imm ediately

above it, mark the row label of that entry.After all the entries are

scanned, the marked labels represent the items that must be put into the

knapsack.

o Time Complexity: - Each entry of the table requires constant time θ(1)

for its computation.It takes θ(nw) time to fill (n+1)(w+1) table entries.It

takes θ(n) time for tracing the solution since tracing process traces the n

rows. Thus, overall θ(nw) time is taken to solve 0/1 k napsack problem

using dynamic programming.

9.6 UNDERSTANDING DYNAMIC PROGRAMMING

Dynamic Programming is mainly an optimization compared to simple

recursion. The main idea is to decompose the original question into

repeatable patterns and then store the re sults as many sub -answers.

Therefore, we do not have to re -compute the pre -step answers when

needed later. In terms of big O, this optimization method generally

reduces time complexities from exponential to polynomial .

You can imagine we have a tree of a p roblem and their sub -problems.

We start with solving the “leaf” level problems and then move on to

their “parent” problems and so on. We save the results as we solve sub -

problems for future reference. Thereby avoiding working on the same

sub-problem if enc ountered again. T-Table munotes.in

## Page 225

Dynamic

Programming

225 Dynamic Programming and Recursion are very similar. Both recursion

and dynamic programming are starting with the base case where we

initialize the start. he main difference is that, for recursion, we do not

store any intermediate values wh ereas dynamic programming do utilize

that.Let’s get a bit deeper with the Fibonacci Number.

1. FIBONACCI NUMBER

The Fibonacci numbers are the numbers in the following integer

sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

In mathematical terms, t he sequence Fn of Fibonacci numbers is

defined by the recurrence relation Fn = F n-1 + F n-2 for n>1with seed

values F0 = 0 and F 1 = 1.

Analyzing Time complexity of both solutions it was clear that the

recursive solution was getting significantly slower for each

additional number in the sequence due to exponential time growth.

There is, however, a smart way of improving this solution and that is

using Memoizatio n.

For our recursive solution we want to store the arguments of each

function call as well as function’s output, and reuse it later on if the

function was called with the same arguments.Our recursive solution

looked like this:

From above visualization you can see the recursive implementation

reaches the correct answer through the addition o f 1s (and 0s). It’s good

to understand recursion by visualizing the call stack. In the case of

fib(4), function fib is called 9 times. For a computer keeping track of

the fib function 9 times is not a huge burden, so this is not a big deal. It

will become a big deal as the entered index increases . Incrementing the function fib(n) {

if (n < 2) {

return n;

}

return fib(n - 1) + fib(n - 2);

}

Source: munotes.in

## Page 226

Fundamental of

Algorithms

226 index by 1 raised the number of fib calls to 15. You can imagine what

problem this will raise once we want to find the Fibonacci number at

higher indexes. Its complexity in Big O notation is O(2^n ).Now here

comes memorization.

In computing, memoization or memoisation is an optimization

technique used primarily to speed up computer programs by storing the

results of expensive function calls and returning the cached result when

the same inputs occur again.

How does Memoization help? Calling fib(5) produces a call tree that

calls the function on the same value many times:

fib(5)

fib(4) + fib(3)

(fib(3) + fib(2)) + (fib(2) + fib(1))

((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

In the above example, fib(2) was calculated three times (overlapping of

subproblems). If n is big, then many more values of fib (sub problems)

are recalculated, which le ads t o an exponential time algorithm. Instead

of solving the same sub problems again and again we can store the

previous calculated va lues and reduce the complexity. Memoization

works like this: Start with a recursive functio n and add a table that

maps the function’s parameter values to the results computed by the

function. Then if this function is called twice with the same parameters,

we simply look up the answer in the table . Source: munotes.in

## Page 227

Dynamic

Programming

227 Hence w hile solving the problems using DP, try to figure out the

following:

See how the problems are defined in terms of subproblems

recursively.

See if we can use some table [memoization] to a void the repeated

calculations.

2. Factorial

Let’s create a factorial program using recursive functions. Until the

value is not equal to zero, t he recursive function will call itself.

Factorial can be calculated using the following recursive formula.

n! = n * (n – 1)!

n! = 1 if n = 0 or n = 1

This definition can easily be converted to implementation. Here the

problem is finding the value of n! , and the sub -problem is finding the

value of (n – l)!. In the recursive case, when n is greater than 1, the

function calls itself to find the value of (n – l)! and multiplies that

with n. In the base case, when n is 0 or 1, the function simply returns

1.

The recurrence implementation can be given as: T(n) = n × T(n – 1) ≈

O(n). Time Complexity: O(n). Space Complexity: O(n), recursive

calls need a stack of size .

In the recursion method as gien above fact(n) is calculated from

fact(n -1) and n and noth ing else. Instead of calling fact(n) every time,

we can store the previous calculated values in a table and use these

values to calculate a new value.

int[] factorialDP(int n)

{

int fact [n+1],i,j; // factorials array

fact[0]=1;

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

{

fact[i] = i * fact [i-1];

}

return fact ;

} int fact(int n){ {

if (n == 1) return 1;

else if (n==0) return 1l

else //recursive call

return (n * fact(n -1));

}

munotes.in

## Page 228

Fundamental of

Algorithms

228 The above implementation clearly reduc es the complexity as compared

to recursive implementati on. This is because if the fact(n) is already

there, then we are not recalculating the value again. If we fill these

newly computed values, then the subsequent calls further reduce the

complexity .

9.7 LONGEST COMMON SUBSEQUENCE

Given a sequence of element s, a subsequence of it can be obtained by

removing zero or more elements from the sequence, preserving the

relative order of the elements. Note that for a substring, the elements

need to be contiguous in a given string, for a subsequence it need not

be. Eg : S1="ABCDEFG" is the given string. "ACEG", "CDF" are

subsequences, where as "AEC" is not. For a string of lenght n the total

number of subsequences is 2n ( Each character can be taken or not

taken ). Now the question is, what is the length of the longest

subsequence that is common to the given two Strings S1 and S2. Lets

denote length of S1 by N and length of S2 by M.

1. BruteForce: - Consider each of the 2N subsequences of S1 and check if

its also a subsequence of S2, and take the longest of all such

subseque nces. Clearly, very time consuming.

2. Recursion: - Can we break the problem of finding the LCS of S1[1...N]

and S2[1...M] in to smaller subproblems ?

In dynamic programming, the phrase “largest common subsequence”

(LCS) refers to the subsequence that is share d by all of the supplied

sequences and is the one that is the longest. It is different from the

challenge of finding the longest common substring in that the

components of the LCS do not need to occupy consecutive locations

within the original sequences to be considered part of that problem.

The LCS is characterized by an optimal substructure and overlapping

subproblem properties. This indicates that the issue may be split into

many less complex sub -issues and worked on individually until a

solution is foun d. The solutions to higher -level subproblems are often

reused in lower -level subproblems, thus, overlapping subproblems.

Therefore, when solving an LCS problem, it is more efficient to use a

dynamic algorithm than a recursive algorithm. Dynamic programming

stores the results of each function call so that it can be used in future

calls, thus minimizing the need for redundant calls.

For instance, consider the sequences (MNOP) and (MONMP). They

have five length -2 common subsequences (MN), (MO), (MP), (NP),

and (OP); two length -3 common subsequences (MNP) and (MOP);

MNP and no longer frequent subsequences (MOP). Consequently,

(MNP) and (MOP) are the largest shared subsequences. LCS can be

applied in bioinformatics to the process of genome sequencing. Longest

Common Subsequence Algorithm munotes.in

## Page 229

Dynamic

Programming

229

The method of dynamic programming reduces the number of function

calls. It stores the result of each function call so that it can be used in

future calls without the need for redundant calls.

In the above dynamic algorit hm, the results obtained from each

comparison between elements of X and the elements of Y are stored in

a table so that they can be used in future computations.

9.8 SUMMARY

Recursion which is calling a function within its elf. Sub -problems

might have to be solved multiple times when a problem is solved using

recursion. At the same time, Dynamic programming is a technique

where you store the result of the previous calculation to avoid

calculating the same once again .

One might find dynamic programming a bit intimidating initially. But if

one understands the basics well, one can master dynamic programming

problems. Having a strong programming foundation is key to getting

comfortable with such problems. Applications of dynamic

programming are common and relevan t to everyday challenges, and

mastering dynamic programming gives you the superpower to tackle

them.

There are numerous applications of dynamic programming in real life.

Algorithms that are aimed at solving optimization problems use a

dynamic programming approach. Examples of dynamic programming

algorithms are string algorithms like the longest common subsequence,

longest increasing subsequence, and the longest palindromic substring.

Optimizing the order for chain matrix multiplication. The Bellman -

Ford al gorithm for finding the shortest distance in a graph.Many of

which we have seen in brief in the chapter.

X and Y be two given sequences

Initialize a table LCS of dimension X.length * Y.length

X.label = X

Y.label = Y

LCS[0][] = 0

LCS[][0] = 0

Start from LCS[1][1]

Compare X[i] and Y[j]

If X[i] = Y[j]

LCS[i][j] = 1 + LCS[i -1, j-1]

Point an arrow to LCS[i][j]

Else

LCS[i][j] = max(LCS[i -1][j], LCS[i][j -1]) Point an arrow to max(LCS[i-1][j], LCS[i][j-1]) munotes.in

## Page 230

Fundamental of

Algorithms

230 9.9 QUESTIONS

1. Write a short note on Dynamic Programming Strategy .

2. Difference Between A Dynamic Prog ramming Algorithm And

Recursion.

3. Explain propertie s of dynamic programming.

4. Bottom -Up Versus Top -Down Programming

5. Describe Longest common subsequence.

6. Explain Fibonacci number using dynmamic programming approach.

9.10 REFERENCES

1. Data Structure and Algorithmic Thinking with Python, Narasimha

Karumanchi, C areerMonk Publications, 2016.

2. Introduction to Algorithm, Thomas H Cormen, PHI.

3. https://www.knowledgehut.com/blog/programming/dynamic -

programming

4. https://www.spiceworks.com/tech/devops/articles/what -is-dynamic -

programming/

5. https://en.wikipedia.org/wiki/Dynamic_programming

6. https://www.geeksforgeeks.org/

7. https://www.thelearningpoint.net/computer -science/dynamic -

programming

munotes.in