Module: Algorithms

Notes
IBPS SO IT Prelims
Contains 26 PDF lessons

Generated: 3 July 2026

KnowledgeGate
Module

Algorithms

Topic
Algorithm Analysis

Subtopic
Algo Basics & Analysis

Lesson

Algo Basics & Analysis Notes

Lesson 1 of 26
 t
Algorithm Analysis
a e
eG
Algo basics & Analysis

g
l ed
n ow
•

at e
Algorithm
Core subjects for CS/IT Students. In GATE 8-10 Marks out of 100 Marks, and 5-6 questions on an average. Most

G
of questions are Numerical. Needs a little time, good scoring. Applied in Industry .

Syllabus
• Introduction, Searching, Sorting.

d ge
e
• Algorithm design techniques

l
• Divide and conquer, Greedy, Dynamic programming

w
• Graph search

o
• Minimum spanning trees, Shortest paths

n
• Asymptotic worst case time and space complexity.
 t e
Q Find the Largest Number Among Three Numbers ?

a
geG
l ed
n ow
 Q Find the Largest Number Among Three Numbers ?
1. Start

at e
G
2. Read the three numbers to be compared, as A, B and C.
3. Check if A is greater than B.
3.1 If true, then check if A is greater than C.

e
3.1.1 If true, print 'A' as the greatest number.
3.1.2 If false, print 'C' as the greatest number.

g
3.2 If false, then check if B is greater than C.
3.2.1 If true, print 'B' as the greatest number.

d
3.2.2 If false, print 'C' as the greatest number.
4. End

l e
#include <stdio.h>
int main()
{
int A, B, C;

w
printf("Enter the numbers A, B and C: ");
scanf("%d %d %d", &A, &B, &C);

o
if (A >= B && A >= C)

n
printf("%d is the largest number.", A);

if (B >= A && B >= C)

if (C >= A && C >= B)

return 0;
}
•

at e
Introduction to Algorithm
In mathematics and computer science, an algorithm is a finite sequence of well-defined,

G
computer-implementable instructions, typically to solve a class of problems or to perform a
computation. A stem by step Procedure.

e
• Algorithms are unambiguous specifications for performing calculation, data processing, automated

g
reasoning, and other tasks.
•

d
Will accept Zero or more input, but generate at least one output.
• Every instruction in algo should be effective

wl e
n o
बेटा कताबों को आग लगा दो
 t e
Problem Solving Cycle

a
G
• Problem Definition: Understand Problem

e
• Constraints & Conditions: Understand constraints if any

g
• Design Strategies (Algorithmic Strategy)

d
• Express & Develop the algo

l e
• Validation (Dry run)
• Analysis (Space and Time analysis)
•
•
•
•
Coding

ow
Testing & Debugging

n
Installation
Maintenance
•

at e
Need for Analysis
What parameters can be considered for comparison between cars?

geG
•

l ed
We do analysis of algorithm to do a performance comparison between different algorithm to figure

w
out which one is best possible option. Following are the parameters which can be considered while

o
analysis of an algorithm
• Time

n
• Space
• Bandwidth
• Register
• Battery power
 t
Types of Analysis

a e
G
Aspect Experimental (A Posteriori) Analysis Apriori (Asymptotic) Analysis
Performed after code implementation and

e
Timing Done before implementation, purely theoretical.
execution.

g
Result Type Measures actual time or space usage. Estimates time or space complexity.
Influencing Affected by hardware, software, environment,

d
Independent of hardware or software factors.
Factors etc.

e
Accuracy Provides exact, real-world results. Provides approximate, theoretical results.

l
Useful for analysing algorithm efficiency for large
Use Case Useful for real-world performance comparison.
inputs.

n ow
 at e
geG
l ed
n o
1w
57
2
12
3
43
4
68
5
26
6
35
 t e
Conclusion

a
G
• The average case analysis is not easy to do in most of the practical cases and it is rarely done.

e
In the average case analysis, we must know (or predict) the mathematical distribution of all
possible inputs.

g
• Most useful analysis is worst case analysis, as help designers to make reliable system even in

d
worst case.

wl e
n o
 t e
Algorithm Classification : - Deterministic vs Non - Deterministic

a
G
Deterministic Algorithm - Always produces the same output for a given input and follows a predictable sequence of
steps.

ge
Deterministic_Search(int A[ ], int n, int key)
{

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

e
{

l
if(A[i] == key)

w
{
print("Found");

o
return;

n
}
}
print("Not Found");
}
 t e
Non - Deterministic Algorithm - May produce different output for the Same input due to inherit randomness of
variability in execution.

a
G
NonDeterministic_Search(int A[ ], int n, int key)

e
{

g
int i;

d
i = random(1, n); // randomly choose any index

l e
if(A[i] == key)
{

w
print("Found");
}

o
else

n
{
print("Not Found");
}
}
Module

Algorithms

Topic
Algorithm Analysis

Subtopic
Asymptotic Notations

Lesson

Asymptotic Notation Notes

Lesson 2 of 26
 t
Algorithm Analysis
a e
eG
Asymptotic Notations

g
l ed
n ow
•

at e
Asymptotic Notations
Asymptotic notations are Abstract notation for describing the behavior of algorithm and determine the rate of

G
growth of a function.
• Asymptotic notations are mathematical tools to represent time complexity of algorithms for asymptotic analysis.

e
• The main idea of asymptotic analysis is to have a measure of efficiency of algorithms that doesn’t depend on

g
machine specific constants, and doesn’t require algorithms to be implemented and time taken by programs to
be compared.

l ed
n ow
•

at e
Big O Notation
The Big O notation defines an upper bound of an algorithm, it bounds a function only from above.

G
• The Big O notation is useful when we only have upper bound on time complexity of an algorithm.

e
• Many times, we easily find an upper bound by simply looking at the algorithm.
• O(g(n)) = {f(n): there exist positive constants C and N0 such that 0 <= f(n) <= C*G(n) for all N >= N0}

ed g
wl
n o
 t e
Ω Notation

a
• Just as Big O notation provides an asymptotic upper bound on a function, Ω notation provides an

G
asymptotic lower bound.
• Ω Notation can be useful when we have lower bound on time complexity of an algorithm.

e
• For a given function g(n), we denote by Ω(g(n)) the set of functions.

g
• Ω (g(n)) = {f(n): there exist positive constants c and n0 such that 0 <= c*g(n) <= f(n) for all n >= n0}.

l ed
n ow
•

at e
Theta Notation
Θ Notation: The theta notation bounds a function from above and below, so it defines exact

G
asymptotic behaviour.
• For a given function g(n), we denote Θ(g(n)) is following set of functions.

e
• Θ(g(n)) = {f(n): there exist positive constants C1, C2 and n0 such that 0 <= C1*g(n) <= f(n) <=

g
C2*g(n) for all n >= n0}
•

d
The above definition means, if f(n) is theta of g(n), then the value f(n) is always between
C1*g(n) and C2*g(n) for large values of n (n >= n0).

e
•

l
The definition of theta also requires that f(n) must be non-negative for values of n greater
than n0.

n ow
 t e
Small notations

a
• Every thing is same as big notations just, just we take strictly increasing or

G
monotonically increasing case and equal case is not allowed.

• f(n) is O((g(n))
• f(n) is Ω (g(n))
a <= b

d ge
• Analogy of asymptomatic notation with real numbers

e
a >= b

l
• f(n) is Θ (g(n)) a=b
• f(n) is o(g(n)) a<b

w
• f(n) is ω(g(n)) a>b

n o
• Reflexivity:
t e
Properties of Asymptotic notations

a
G
• f(n) = O(f(n))

e
• f(n) = Ω(f(n))

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

d
• Symmetry:

l e
• f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n))

w
• Transitivity:
• f(n) = O(g(n)) and g(n) = O(h(n)) ⇒ f(n) = O(h(n))

o
• f(n) = Θ(g(n)) and g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n))

n
• f(n) = Ω(g(n)) and g(n) = Ω(h(n)) ⇒ f(n) = Ω(h(n))
• f(n) = o(g(n)) and g(n) = o(h(n)) ⇒ f(n) = o(h(n))
• f(n) = ω(g(n)) and g(n) = ω(h(n)) ⇒ f(n) = ω(h(n))
• Transpose Symmetry:

at e
• f(n) = O(g(n)) if and only if g(n) = Ω(f(n))

• if f(n) = O (g(n))
• a f(n) = O(g(n))

geG
l ed
• if f(n) is O(g(n)) and p(n) is O(q(n))
• f(n) + p(n) is O(max (g(n), q(n)))

ow
• f(n) * p(n) is O(g(n) . q(n))

n
Module

Algorithms

Topic
Algorithm Analysis

Subtopic
Growth Rate Comparisons

Lesson

Growth Rate Comparisons Notes

Lesson 3 of 26
 t
Algorithm Analysis
a e
eG
Growth Rate Comparisons

g
l ed
n ow
Q. Consider the functions:

at e
Which one of the following is correct?

geG
l ed
n ow
Q. Consider the functions:

at e
Which one of the following is correct?

geG
l ed
n ow
 t e
Logarithm Properties

a
geG
l ed
n ow
 at e
geG
led
n ow
 at e
geG
led
n ow
 t e
Polynomial Functions – Basic Properties

a
geG
l ed
n ow
 t e
Asymptotic Comparison of Functions

a
G
1. Decrement Functions
2. Constant Functions

e
3. Logarithmic Functions

g
4. Polynomial Functions

d
5. Exponential Functions

wl e
n o
1. Decreasing (Decrement) Functions :-

at e
A function f(n) is called a decreasing function if its value decreases as n increases.

eG
As input size grows, the running time keeps getting smaller.

g
Examples :- Arrange the following functions in increasing order of growth (as n→∞).

l ed
n ow
2. Constant Functions :-

at e
A function is called a constant function if its value does not depend on the input size n.

G
f(n) = c (where c is a fixed constant)

e
Such functions have constant time complexity:

g
f(n) = Θ(1) (also written as O(1))

d
Examples : - 5, 10, 1000, 1, π, e

wl e
n o
 t e
3. Logarithmic Functions :- A logarithmic function grows when the input increases, but very slowly.

a
G
f(n) = log n

e
Examples :- Arrange the following functions in increasing order of growth (as n→∞).

g
f1(n) = log n
f2(n) = (log n)10

d
f3(n) = log logn

l e
f4(n) = (log logn)10
f5(n) = log log log n

w
f6(n) = (log log logn)10

o
f7(n) = log n log log n

n
 t e
Q. Let f(n) = log₁₀ n, g(n) = (log₁₀ log₁₀ n)¹⁰

a
Which of the following is asymptotically correct?

G
A) f(n) = o(g(n)) B) g(n) = o(f(n))

e
C) f(n) = Θ(g(n)) D) f(n) = O(g(n))

ed g
wl
n o
 t e
All logarithmic functions with different bases are asymptotically equal.
logan = Θ(logn)

a
eG
In asymptotic analysis (Big-O, Θ, Ω), constant factors are ignored.
Therefore:

g
ed
Examples :- log₂ n , log5 n , log10 n, logc n

l
n ow
 t e
4. Polynomial Functions :- Polynomial functions contain powers of the variable .

a
G
Examples :- Arrange the following functions in increasing order of growth (as ).

d ge
wl e
n o
5. Exponential Functions :-

at e
A function is called an exponential function if the variable n appears in the exponent.

G
n
f(n) = a where a > 1

e
Examples:- 2n, 3n, 5n, 10n, en , n!, nn

ed g
wl
n o
To Compare the Growth Rates of f(n) and g(n), Apply Logarithms
1.

at e
logf(n) is asymptotically bigger than logg(n) if and only if is asymptotically bigger than g(n).

2.

eG
logf(n) is asymptotically equal to logg(n) if and only if f(n) and g(n) may or may not be asymptotically equal.

g
If logf(n)=logg(n) (asymptotically), then the possible cases are:

d
○

e
f(n) < g(n)

l
○ f(n) > g(n)
○ f(n) = g(n)

w
Example:
f(n)=n2, g(n)=n10

o
Here,
logf(n)=2 logn,log g(n)=10 logn

n
Hence,
logf(n) = Θ(logg(n))
but
f(n) ≠ Θ(g(n))

3. logf(n) is asymptotically smaller than logg(n) if and only if f(n) is asymptotically smaller than g(n).
Compare the following functions asymptotically
1. f(n) = logn g(n) = √n

at e
geG
2. f(n) = 2n

l g(n) = 22n

ed
n ow
3. f(n) = n² g(n) = n log n

at e
geG
4. f(n) = n100

l
g(n) = 2ⁿ

ed
n ow
5. f(n) = n! g(n) = 2ⁿ

at e
geG
6. f(n) = n!

l
g(n) = nⁿ

ed
n ow
7. f(n) = 2n g(n) = n√n

at e
geG
l
8. f(n) = (log n)logn g(n) = (log log n)logn

ed
n ow
9. f(n) = n2 (log n)√n g(n) = n2(√n)log n

at e
geG
l
10. f(n) = log(n!) g(n) = n log n

ed
n ow
 t
Q Which of the following is not O(n2)?

a e
G
10
(A) (15 ) * n + 12099

(B) n1.98

d ge
wl
(C) n3 / (sqrt(n)) e
n
(D) (220) * n o
Module

Algorithms

Topic
Time Complexity Analysis

Subtopic
Iterative Loops & Code

Lesson

Iterative Loops & Code Notes

Lesson 4 of 26
Time Complexity
at e
Analysis
geG
ed
Iterative Loops & Code
l
n ow
 t e
Performance Analysis

a
G
Time Complexity - Time Complexity measures the amount of time an algorithm takes to Complete, based on the
number of operation performed.

Sum_Of_Numbers(int n)
{
int sum = 0;

d ge
{

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

sum = sum + i;
e
o
}

n
print(sum);
}
 t e
Space Complexity : - Space Complexity refers to the total amount of memory an algorithm requires to execute
including:

a
G
● Memory for Input Data and variables - Space needed to store the input and and variables used.

e
● Data Structures :- Memory used by arrays, linked lists, Stacks, Jueves, trees, and graphs.
● Recursive Calls :- space for function Call Stats and local Variables in recursive functions

g
● Auxiliary storages :- Memory for temporary results. and intermediate Calculations.

Example : - Store n Elements in Array

l
Store_Array(int n)

ed
w
{
int arr[n]; // array of size n

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

n
{
arr[i] = i;
}
}
 t e
Loops Time Complexity Analysis

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

e
{

g
printf("Knowledge Gate");

d
}

l
2. for(i = n; i > 0; i--)
{

w e
o
printf("Knowledge Gate");

n
}
3. for(i = 1; i <= n; i = i + 3)
{

at e
G
printf("Knowledge Gate");

e
}

ed g
l
4. for(i = 1; i <= n; i = i + 10)
{

w
printf("Knowledge Gate");

o
}

n
5. for(i = n; i > 0; i = i - 3)
{

at e
G
printf("Knowledge Gate");

e
}

6. for(i = n; i > 0; i = i - 10)

ed g
l
printf("Knowledge Gate");

w
}

n o
7. for(i = 1; i <= n; i = i * 2)
{

at e
G
printf("Knowledge Gate");

e
}

8. for(i = 1; i <= n; i = i * 7)
{

ed g
l
printf("Knowledge Gate");

w
}

n o
9. for(i = n; i >= 1; i = i / 2)
{

at e
G
printf("Knowledge Gate");

e
}

10. for(i = n; i >= 1; i = i / 7)

ed g
l
printf("Knowledge Gate");

w
}

n o
 2
11. for(i = 2; i <= n; i = i )

at e
G
{

e
printf("Knowledge Gate");

g
}

5
12. for(i = 5; i <= n; i = i )
{

l ed
w
printf("Knowledge Gate");

o
}

n
13. for(i = n; i >= 2; i = √i)
{

at e
G
printf("Knowledge Gate");

e
}

14. for(i = n; i >= 5; i = ⁵√i)

ed g
l
{
printf("Knowledge Gate");

w
}

n o
 n
15. for(i = 1; i <= 5 ; i = i * 5)

at e
G
{

e
printf("Knowledge Gate");

g
}

l
n 5
16. for(i = 5; i <= 5 ; i = i )
{
ed
w
print("Knowledge Gate");

o
}

n
17. for(i = 1; i < n; i = i + (n/2))
{

at e
G
printf("Knowledge Gate");

e
}

18. for(i = n; i > 0; i = i - (n/2))

ed g
l
{

w
printf("Knowledge Gate");
}

n o
19. i = n;
while(i >= 1)

at e
G
{

e
printf("Knowledge Gate");

g
i = i / 2;

d
}

wl
20. for(i = 1; i2 <= n; i = i ++)

printf("Knowledge Gate"); e
o
}

n
 t
Nested Loops

a e
Nested loop means a loop that is placed inside another loop.

G
Nested loops are classified into two categories:

e
1. Independent Nested Loops

g
2. Dependent Nested Loops

d
1. Independent Nested Loops

l e
An Independent Nested Loop is a nested loop in which the number of iterations executed by the inner
loop does not depend on the current value of the outer loop.

ow
The inner loop executes a fixed number of iterations for every iteration of the outer loop.
The loop boundaries of the inner loop are independent of the outer loop variable.

n
The total number of iterations is obtained by multiplying the iterations of all loops.
General Form
for(...)

at e
G
{
for(...)

e
{

g
// statements

d
}

e
}

wl
Complexity Analysis

o
If the outer loop executes times and the inner loop executes times for each outer iteration, then

n
When both loops execute n times,
1. for(i = 1; i <= n; i++)
{

at e
G
for(j = 1; j <= n; j = j * 2)
{

e
printf("Knowledge Gate");

g
}

d
}

l
2. for(i = 2; i <= n; i = i2)
{

w e
o
for(j = n; j > 0; j = j / 5)

n
{
printf("Knowledge Gate");
}
}
3. for(i = n; i >=10; i = 10√i)
{

at e
G
for(j = n; j >= 5; i = 2√j)
{

e
printf("Knowledge Gate");

g
}

d
}

l
4. for(i = 2; i <= n; i = i++)
{

w e
o
for(j = 5; j <= n; j = j5)

n
{
printf("Knowledge Gate");
}
}
5. for(i = 1; i <= n; i++)
{

at e
G
for(j = 1; j <= n2; j++)
{

e
for(k = 1; k <= n; k = k + (n/2))

g
{

d
printf("Knowledge Gate");

e
}

l
}
}

n ow
6. for(i = 1; i <= n2; i++)
{

at e
G
for(j = 1; j <= n; j = j * 2)

e
{
for(k = 1; k <= n3; k = k * 2)

g
{

d
printf("Knowledge Gate");

e
}

l
}

w
}

n o
Module

Algorithms

Topic
Time Complexity Analysis

Subtopic
Master Theorem

Lesson

Master Method Notes

Lesson 5 of 26
 t
Time Complexity
a e
Analysis
geG
ed
Master Theorem
l
n ow
 t e
Master Theorem

a
• In the analysis of algorithms, the master theorem for divide-and-conquer recurrences provides

G
an asymptotic analysis (using Big O notation) for recurrence relations of types that occur in

e
the analysis of many divide and conquer algorithms.

g
• The approach was first presented by Jon Bentley, Dorothea Haken, and James B. Saxe in 1980,

d
where it was described as a "unifying method" for solving such recurrences.

l e
• The name "master theorem" was popularized by the widely used algorithms
textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.

w
n o
• T(n) = a T(n/b) + f(n)

at e
G
• The above equation divides the problem into ‘a’ number of subproblems

e
recursively, a >= 1

not recurse. (b > 1)

ed g
• Each subproblem being of size n/b. the subproblems (of size less than k) that do

wl
• where f(n) is the time to create the subproblems and combine their results in
the above procedure.

n o
 t e
• The master theorem allows many recurrence relations of this form to be

a
converted to Θ-notation directly, without doing an expansion of the recursive

G
relation.

ge
• The master theorem often yields asymptotically tight bounds to some
recurrences from divide and conquer algorithms that partition an input into

d
smaller subproblems of equal sizes, solve the subproblems recursively, and then

l e
combine the subproblem solutions to give a solution to the original problem.

n ow
 t
Case 1

a e
G
• f(n) = O (n - ϵ) for some constant ϵ > 0,
log a

e
b
• then T(n) = Θ (n logba)

ed g
wl
n o
Q T(n) = 4T(n/2) + n

at e
geG
l ed
n ow
Q T(n) = 9T(n/3) + n

at e
geG
l ed
n ow
Q T(n) = 7T(n/2) + n 2

at e
geG
l ed
n ow
Q T(n) = 8T(n/2) + n 2

at e
geG
l ed
n ow
∙ f(n) = Θ (n t
Case 2

a e
G
log a
b
),
∙ then T(n) = Θ (n

e
log a
lg n)

g
b

l ed
n ow
Q T(n) = 2T(n/2) + n

at e
geG
l ed
n ow
Q T(n) = T(2n/3) + 1

at e
geG
l ed
n ow
 t
Case 3

a e
• f(n) = Ω (n logb a + ϵ) for some constant ϵ > 0,

large n,
• then T(n) = Θ (f(n))

g G
• and if a f(n/b) <= c f(n) for some constant c < 1 and all sufficiently

e
l ed
n ow
Q T(n) = T(n/3) + n

at e
geG
l ed
n ow
Module

Algorithms

Topic
Sorting Algorithms

Subtopic
Introduction to Sorting

Lesson

Basics of sorting notes

Lesson 6 of 26
Sorting
 Sorting
• Sorting is the process of arranging data (numbers or characters) in a specific order (increasing or
decreasing).Sorting is crucial in many applications that require data to be in order. There are number
of approaches available for sorting and some parameter based on which we judge the performance
of these algorithm.
• Space Complexity:
• Internal Sorting (In-Place): Sorting that requires no extra memory beyond what is needed for the problem
itself (e.g., Heap Sort).
• External Sorting: Sorting that requires additional memory to store data (e.g., Merge Sort).
• Stability:
• A sorting algorithm is Stable if it preserves the relative order of equal elements (e.g., Bubble Sort).
• Unstable sorting algorithms do not preserve the order of equal elements (e.g., Insertion Sort).
Module

Algorithms

Topic
Sorting Algorithms

Subtopic
Selection Sort

Lesson

Selection Sort Notes

Lesson 7 of 26
 t e
Sorting Algorithms
a
eG
Selection Sort

g
l ed
n ow
 t e
Selection Sort

a
• The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left

G
to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest
of the list.

1 2 3 4 5

d ge
6

wl e
n o
 t e
• Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The

a
algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in

G
the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it
in sorted order), and moving the sublist boundaries one element to the right.

d ge
wl e
n o
 Selection sort (A, n)

t e
Selection Sort(Algo)

a
G
{ 1 2 3 4 5 6
for k 🡨1 to n-1

e
{

g
min = A[k]

d
Loc = k
for j 🡨k+1 to n

l e
{
if(min > A[j])

w
{
min = A[j]

o
Loc = j

n
}
}
swap(A[k],A[Loc])
}
}
 Selection sort (A, n)

at e
Selection Sort(Analysis)
• Depends on structure or content ?

G
{
for k 🡨1 to n-1 • Structure

e
{
• Internal/External sort algorithm ?

g
min = A[k]
Loc = k • Internal

d
for j 🡨k+1 to n
{
• Stable/Unstable sort algorithm ?

e
• Unstable

l
if(min > A[j])
{ • Best case time complexity ?
min = A[j]

w
Loc = j • O(n2)
• Worst case time complexity ?

o
}
}
• O(n2)

n
swap(A[k],A[Loc])
} • Algorithmic Approach?
} • Subtract and Conquer
• Selection sort is noted for its simplicity and has performance advantages over more complicated algorithms in certain
situations(number of swaps, which is n − 1 in the worst case). It has an O(n2) time complexity, which makes it inefficient on
large lists.
Module

Algorithms

Topic
Sorting Algorithms

Subtopic
Bubble Sort

Lesson

Bubble Sort Notes

Lesson 8 of 26
 t e
Sorting Algorithms
a
eG
Bubble Sort

g
l ed
n ow
 t e
Bubble / Shell / Sinking Sort

a
• Bubble sort, sometimes referred to as sinking sort, is a simple sorting

G
algorithm that repeatedly steps through the list, compares adjacent

e
elements and swaps them if they are in the wrong order. The pass

g
through the list is repeated until the list is sorted. The algorithm, which is

d
a comparison sort, is named for the way smaller or larger elements

e
"bubble" to the top of the list.

wl
n o
 at e
geG
led
n ow
 t e
Bubble / Shell / Sinking Sort(Algo without flag)

a
G
Bubble sort (A, n)
1 2 3 4 5 6

e
{

g
for k 🡨1 to n-1
{

d
ptr = 1

l e
while(ptr <= n-k)
{

w
if(A[ptr] > A[ptr+1])

o
{
exchange(A[ptr],A[ptr+1])

n
}
ptr = ptr+1
}
}
}
 t e
Bubble / Shell / Sinking Sort (Analysis with flag)
Bubble sort (A, n)

a
G
{ • Depends on structure or content ?
for k 🡨1 to n-1

e
{
• Internal/External sort algorithm ?

g
ptr = 1
while(ptr <= n-k)

d
{ • Stable/Unstable sort algorithm ?
if(A[ptr] > A[ptr+1])

e
{

l
exchange(A[ptr],A[ptr+1])
• Best case time complexity ?
flag = 1

w
} • Worst case time complexity ?
ptr = ptr+1

o
}
if(!flag) • Algorithmic Approach?

n
{
break;
}
}
}
 t e
Bubble / Shell / Sinking Sort (Analysis with flag)
Bubble sort (A, n)

a
G
{ • Depends on structure or content ?
for k 🡨1 to n-1 • Both

e
{
• Internal/External sort algorithm ?

g
ptr = 1
while(ptr <= n-k) • Internal

d
{ • Stable/Unstable sort algorithm ?
if(A[ptr] > A[ptr+1]) • Stable

e
{

l
exchange(A[ptr],A[ptr+1])
• Best case time complexity ?
flag = 1 • O(n)

w
} • Worst case time complexity ?
ptr = ptr+1 • O(n2)

o
}
if(!flag) • Algorithmic Approach?

n
{ • Subtract and Conquer
break;
}
}
}
 t e
Bubble / Shell / Sinking Sort (Conclusion)

a
G
• Efficiency: Bubble Sort performs poorly in real-world scenarios compared to other O(n2)
algorithms like Insertion Sort and Selection Sort, which generally run faster and have similar

e
complexity.

g
• Practical Use: It's not a practical sorting algorithm and is mostly used for educational purposes.

d
• Comparison with Efficient Algorithms: Efficient algorithms like Heap Sort and Merge Sort are
preferred in real-world applications and are used in sorting libraries of languages like Python

l e
and Java.
• Best Case: When the list is already sorted, Bubble Sort has a time complexity of O(n), which is

w
a benefit over algorithms that continue their full sorting process even in best-case scenarios.

n o
 t e
Q What is the best time complexity of Bubble sort ?
(A) N

a
(B) NlogN

geG
(C) N2

l ed
n o
(D) N(logN)2w
Module

Algorithms

Topic
Sorting Algorithms

Subtopic
Insertion Sort

Lesson

Insertion Sort notes

Lesson 9 of 26
 Insertion Sort
• Process: Insertion Sort removes one element from the input at a time, finds its correct position in the sorted list,
and inserts it there.
• Repetition: The process repeats until no input elements are left.
• Comparison: At each position, the algorithm compares the element with the largest value in the sorted part of
the list (adjacent element).
• If Larger: If the element is larger than the adjacent sorted value, it stays in place, and the next element is
checked.
• If Smaller: If the element is smaller, the larger values are shifted to make room, and the element is inserted into
its correct position.

1 2 3 4 5 6
 Insertion Sort (Analysis)
Insertion sort (A, n) 1 2 3 4 5 6
{
for j 🡨2 to n
{
key = A[j]
i=j-1
while(i>0 and A[i] > key)
{
A[i+1] = A[i]
i = i-1
}
A[i+1]=key
}
}
 Insertion Sort (Analysis)
Insertion sort (A, n) • Depends on structure or content ?
{ • Both
for j 🡨2 to n • Internal/External sort algorithm ?
{ • Internal
• Stable/Unstable sort algorithm ?
key = A[j] • Stable
i=j-1 • Best case time complexity ?
while(i>0 and A[i] > key) • O(n)
{ • Worst case time complexity ?
A[i+1] = A[i] • O(n2)
i = i-1 • Algorithmic Approach?
• Subtract and Conquer
}
A[i+1]=key
}
}
 Insertion Sort (Conclusion)
• Less Efficient for Large Lists: Insertion Sort is less efficient compared to advanced algorithms like Heap Sort and
Merge Sort, which both have O(nlogn) time complexity.
• Advantages for Small Data Sets: Insertion Sort performs well on small data sets and is more efficient than other
quadratic algorithms like Selection Sort and Bubble Sort.
• Practical Use: Despite its inefficiency on large lists, Insertion Sort remains useful for smaller or nearly sorted
datasets.
Q What is the worst-case time complexity of insertion sort where
position of the data to be inserted is calculated using binary search?
(A) N

(B) NlogN

(C) N2

(D) N(logN)2
Module

Algorithms

Topic
Sorting Algorithms

Subtopic
Merge Sort

Lesson

Merge Sort Notes

Lesson 10 of 26
 t e
Sorting Algorithms
a
eG
Merge Sort

g
l ed
n ow
•

at e
Merge Sort
In computer science, merge sort is an efficient, general-purpose, comparison-based sorting algorithm.

G
Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

e
• Conceptually, a merge sort works as follows:
• Divide the unsorted list into n sublists, each containing one element (a list of one element is

g
considered sorted).
• Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining.

d
This will be the sorted list.

wl e
n o
 at e
geG
led
n ow
 at e
geG
led
n ow
 t e
Merge Sort(Algo)

a
G
Merge_Sort(A, p, r)

e
{

g
if(p < r)

d
{
q 🡨 ⌊ (p + r)/2 ⌋

l
Merge_Sort (A, p, q)
Merge_Sort (A, q + 1, r)

w
Merge (A, p, q, r) e
o
}

n
}
Merge (A, p, q, r)
{
n1 🡨 q – p + 1
n2 🡨 r – q

at e
Merge Sort(Algo)

G
Create array L [1……... n1+1] and R [1……... n2+1]
for i 🡨 1 to n1

e
do L[i] = A [p + i - 1]
for j 🡨 1 to n2

g
do R[j] = A [j + q]
L [n1+1] 🡨 ∞

d
R [n2+1] 🡨 ∞
i🡨1

e
j🡨1

l
for k 🡨 p to r
{
if(L[i] <= R[j])

w
{
A[k] = L[i]

o
i=i+1
}
Else

n
{
A[k] = R[j]
j=j+1
}
}
}
 t e
Merge Sort(Analysis)

a
G
• Depends on structure or content ?
• Structure

e
• Internal/External sort algorithm ?

g
• External

d
• Stable/Unstable sort algorithm ?
• Stable

l e
• Best case time complexity ?
• O(nlogn)

w
• Worst case time complexity ?
• O(nlogn)

o
• Algorithmic Approach?

n
• Divide and Conquer
 t e
Merge Sort(Conclusion)

a
• Recurrence Relation: The time complexity of Merge Sort for a list of length nnn is expressed by

G
the recurrence relation T(n)=2T(n/2)+n, reflecting the divide-and-conquer approach.

e
• Comparison with Quick Sort: In the worst case, Merge Sort performs about 39% fewer

g
comparisons than Quick Sort in its average case.
• Sequential Access Efficiency: Merge Sort is more efficient than Quick Sort for lists that are

d
accessed sequentially, making it popular in languages like Lisp, where such data structures are

e
common.

l
• Space Complexity: Merge Sort requires O(n)O(n)O(n) extra space, as it needs additional
memory for the merging process.

n ow
 t e
Q Which of the following is true about merge sort?

a
(A) Merge Sort works better than quick sort if data is accessed from slow

G
sequential memory.

e
(B) Merge Sort is stable sort by nature

g
(C) Merge sort outperforms heap sort in most of the practical situations.
(D) All of the above.

l ed
n ow
 t e
Q Which of the following sorting algorithms has the lowest worst-case complexity?
(A) Merge Sort

a
(B) Bubble Sort

geG
l
(C) Quick Sort

ed
ow
(D) Selection Sort

n
Module

Algorithms

Topic
Sorting Algorithms

Subtopic
Heap Sort

Lesson

Heap Sort Notes

Lesson 11 of 26
 t e
Sorting Algorithms
a
eG
Heap Sort

g
l ed
n ow
 t e
Heap Sort

a
• Invention: Heap Sort was invented by J.W.J. Williams in 1964, introducing the heap data structure as a useful tool in its own

G
right.
• Process: Heap Sort divides the input into a sorted and unsorted region. It repeatedly extracts the largest element from the

e
unsorted region and inserts it into the sorted region.

g
• Efficiency: It avoids a linear-time scan by maintaining the unsorted region in a heap data structure, allowing for quicker
extraction of the largest element.

d
• Steps:
• First, a heap is built from the data (typically in an array with the layout of a complete binary tree).

e
• Then, elements are removed from the heap one by one (starting with the largest) and placed into a sorted array.

l
• Heap Property Maintenance: After each extraction of the largest element, the heap is updated to maintain its structure until
all elements are sorted.

n ow
Heap_Sort(A)
{

at e
Heap Sort(Algo)

1 2 3 4 5 6

G
Build_Max_heap(A)
for i 🡨 length[A] down to 2

e
{
do exchange (A[1] 🡨🡨A[i])

g
Heap-size[A] 🡨 Heap-size[A] – 1
Max-Heapify(A,1)

d
}
}

l e
Build_Max_Heap(A)
{ Max-Heapify(A, i)
Heap-size[A] 🡨 length[A] {

w
for i 🡨 ⌊ length[A]/2 ⌋ down to 1 L 🡨 Left[i]
R 🡨 Right[i]
{

o
if( L <= Heap_size[A] and A[L] > A[i])
do Max-Heapify (A, i) Largest 🡨 L
} Else

n
} Largest 🡨 i
if(R <= Heap_size[A] and A[r] > A[Largest])
Largest 🡨 R
if(Largest != i)
{
Exchange( A[i] 🡨🡨A[Largest])
Max-Heapify(A, Largest)
}
}
 at e
geG
led
n ow
 t e
Heap Sort(Analysis)

a
G
• Depends on structure or content ?
• Both

e
• Internal/External sort algorithm ?

g
• Internal

d
• Stable/Unstable sort algorithm ?
• Unstable

l e
• Best case time complexity ?
• O(nlogn)

w
• Worst case time complexity ?
• O(nlogn)

o
• Algorithmic Approach?

n
• Mixed Approach
Module

Algorithms

Topic
Sorting Algorithms

Subtopic
Quick Sort

Lesson

Quick Sort Notes

Lesson 12 of 26
 t e
Sorting Algorithms
a
eG
Quick Sort

g
l ed
n ow
 t e
Quick Sort

a
• Development: Quick Sort was developed by British computer scientist Tony Hoare and published in 1961. It

G
remains a widely used sorting algorithm today.
• Performance: When implemented efficiently, Quick Sort is faster than Merge Sort and approximately two to

e
three times faster than Heap Sort in practice.

g
• Recognition: Tony Hoare received the Turing Award in 1980, considered the highest distinction in computer
science, for his contributions.

d
• Algorithm Type: Quick Sort is a divide-and-conquer algorithm that selects a "pivot" element and partitions the

e
array into two sub-arrays—one with elements smaller than the pivot and the other with larger elements.

l
• In-Place Sorting: Quick Sort can be performed in-place, requiring minimal additional memory, and sorts
sub-arrays recursively.

n ow
 at e
geG
led
n ow
Quick_Sort(A, p, r)
{
if(p < r) 1 2

at e
3 4 5 6

G
{
q 🡨 partition (A, p, r)

e
quick_Sort(A, p, q - 1)
quick_Sort(A, q + 1, r)

g
}

d
}
Partition (A, p, r)

e
{

l
x 🡨 A[r]
i🡨p–1
for j 🡨 p to r – 1

w
{

o
if(A[j] <= x)
{

n
i🡨i+1
Exchange( A[i] 🡨🡨A[j])
}
}
Exchange( A[i + 1] 🡨🡨A[r])
return i+1
}
 t e
Quick Sort(Analysis)

a
G
• Depends on structure or content ?
• Both

e
• Internal/External sort algorithm ?

g
• Internal

d
• Stable/Unstable sort algorithm ?
• Unstable

l e
• Best case time complexity ?
• O(nlogn)

w
• Worst case time complexity ?
• O(n2)

o
• Algorithmic Approach?

n
• Divide and Conquer
 t e
Q Suppose we are sorting an array of eight integers using quicksort, and we have

a
just finished the first partitioning with the array looking like this:

G
2 5 1 7 9 12 11 10

e
Which statement is correct?

g
(A) The pivot could be either the 7 or the 9
(B) The pivot could be the 7, but it is not the 9

d
(C) The pivot is not the 7, but it could be the 9

l e
(D) Neither the 7 nor the 9 is the pivot.

n ow
 t e
Q What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?

a
(A) Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)

G
(B) Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)
(C) Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)

e
(D) Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)

ed g
wl
n o
Sorting Algorithm

at e
Best Case Worst Case

G
Selection O(n2) O(n2)

Bubble

d ge
O(n2) / O(n) O(n2)

l e
2
Insertion O(n) O(n )

n ow
Merge

Heap
O(nlogn)

O(nlogn)
O(nlogn)

O(nlogn)
2
Quick O(nlogn) O(n )
 t e
Q Which of the following is not a stable sorting algorithm in its typical
implementation.

a
G
(A) Insertion Sort

(B) Merge Sort

d ge
wl
(C) Quick Sort e
n o
(D) Bubble Sort
 t e
Q Which of the following sorting algorithms in its typical implementation gives best

a
performance when applied on an array which is sorted or almost sorted (maximum

G
1 or two elements are misplaced).

e
(A) Quick Sort

(B) Heap Sort

ed g
wl
(C) Merge Sort

n o
(D) Insertion Sort
 t e
Q Consider a situation where swap operation is very costly. Which of the following

a
sorting algorithms should be preferred so that the number of swap operations are

G
minimized in general?

e
(A) Heap Sort

(B) Selection Sort

ed g
wl
(C) Insertion Sort

n o
(D) Merge Sort
 t e
Q Which sorting algorithm will take least time when all elements of input array are

a
identical? Consider typical implementations of sorting algorithms.

G
(A) Insertion Sort

(B) Heap Sort

d ge
l
(C) Merge Sort

w e
n o
(D) Selection Sort
Module

Algorithms

Topic
Sorting Algorithms

Subtopic
Radix & Counting Sort

Lesson

Radix & Counting Sort Notes

Lesson 13 of 26
 t e
Sorting Algorithms
a
eG
Radix Sort

g
l ed
n ow
 t e
Non Comparison Based Sorting Algorithm

a
G
Counting Sort

d ge
Counting Sort is a non-comparison sorting algorithm used for sorting integer values.
It counts how many times each element appears in the array and then places the elements in sorted
order.

l e
Counting Sort works efficiently when the range of elements is small.

n ow
Algorithm :-
CountingSort(a, n, k)
{

at e
G
// Step 1: Initialize count array
for (i = 0; i <= k; i++)

e
c[i] = 0;

g
// Step 2: Count frequency

d
for (i = 1; i <= n; i++)
c[a[i]]++;

l e
// Step 3: Prefix sum (cumulative count)
for (i = 1; i <= k; i++)

w
c[i] = c[i - 1] + c[i];

o
// Step 4: Build output array (stable)
for (i = n; i >= 1; i--)

n
{
b[c[a[i]]] = a[i];
c[a[i]]--;
}

return b[1..n];
}
Time Complexity :-
Case Complexity

at e
G
Best Case O(n+k)

e
Average Case O(n+k)

g
Worst Case O(n+k)

Where:

l
● n = number of elements

ed
w
● k = range of input values

o
Space Complexity : -

n
O(n+k)
Stability
Counting Sort is a stable sorting algorithm.
Radix Sort using Queue : -

at e
G
Radix : -
Radix represents the number of unique digits or symbols used in a number system.

e
For decimal number system:

because digits range from 0 to 9.

ed g
l
Radix Sort using Queue is a non-comparison sorting algorithm in which queues are used to store elements

w
according to their digits.
Elements are distributed into multiple queues based on their digit values and then collected back into the

o
array.

n
If radix =10, then 10 queues are required for digits 0 to 9.
 at e
Each element is inserted into the corresponding queue according to its current digit.
After inserting all elements into queues, the elements are collected back into the array in order from Q 0
to Q9.

G
Multiple queues can also be implemented using a single array.

d ge
Time Complexity

wl
Case Complexity
e Where:

o
● n = number of elements

n
Best Case (O(dn)) ● d = number of digits
Average Case (O(dn))
Space Complexity
O(n+k)
Worst Case (O(dn))
Radix Sort using Counting Sort : -

at e
Radix Sort using Counting Sort is a non-comparison sorting algorithm in which Counting Sort is used to

G
sort elements digit by digit.

e
Digits are processed from Least Significant Digit (LSD) to Most Significant Digit (MSD).
Counting Sort is used as a stable sorting algorithm at each digit position.

ed g
wl
n o
Time Complexity :-

Case Complexity

at e
Best Case
Average Case

e
(O(d(n+k)))

g
(O(d(n+k)))
G
d
Worst Case (O(d(n+k)))

l e
Where:
● n = number of elements

w
● d = number of digits

o
● k = range of digits (0–9)

n
Space Complexity :-
O(n+k)
Stability
Radix Sort is a stable sorting algorithm.
 t e
Question. Consider sorting n integers that lie in the range (1,n4)

a
Which of the following algorithms will take the minimum time to sort the given integers?

G
A. Merge Sort

e
B. Quick Sort

g
C. Radix Sort
D. Counting Sort

l ed
n ow
Module

Algorithms

Topic
Sorting Algorithms

Subtopic
Comparisons & Searching

Lesson

Comparison & Searching Notes

Lesson 14 of 26
 t
Sorting Algorithms
a e
eG
Comparison & Searching

g
l ed
n ow
 t e
Linear Search (Sequential Search)

a
Check each element one by one until the key is found or the list ends.

G
It works on both sorted and unsorted arrays.

e
Algorithm : -

g
Given array A[1…n]

d
Steps

l e
1. Start from the first element.
2. Compare A[i] with key.
3. If equal → return index.

w
4. If end reached → element not present.

o
Pseudocode

n
LINEAR-SEARCH(A, n, key)
for i = 1 to n
if A[key] == x
return i
return -1
Linear Search Time Complexity Analysis:-

Best Case

at e
G
T(n) = O(1)

e
Worst case comparisons:

g
T(n) = n

d
Average comparisons:

l e
T(n) = n+1 / 2 ≈ n / 2

Therefore:

w
T(n) = Θ(n)

n o
 t e
Binary Search

a
Requirement : - Binary search works only on sorted arrays.

G
Instead of checking all elements, repeatedly divide the search space into half.

e
Every step eliminates 50% of elements. Iterative Pseudocode

g
Straight-BINARY-SEARCH(A, n, x)
Algorithm

d
1. Find middle element. low = 1
high = n

l e
2. If key = middle → found. while low ≤ high
mid = (low + high) / 2

w
3. If key < middle → search left half.
if A[mid] == x

o
return mid
4. If key > middle → search right half.

n
else if x < A[mid]
high = mid - 1

else
low = mid + 1

return -1
Binary Search Recursive Relation :-

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

at e
G
Solving:

e
n→n/2→n/4→n/8→⋯→1

g
Number of divisions:

d
k = log2n T(n) = Θ(logn)

l e
Time Complexity

w
Case Complexity

o
Best Case Θ(1)

Average Case Θ(log n)

n
Worst Case Θ(log n)
Algo: RecursiveBinarySearch(a, low, high, key)

t e
Recursive Binary Search

a
G
{
if (low >= high)

e
{
if (low == high)

g
{
if (a[low] == key)

d
return(low); // key is found
else

e
return(-1); // key is not found

l
}
}
else

w
{
mid = (low + high) / 2;

o
if (a[mid] < key)
return RecursiveBinarySearch(a, mid + 1, high, key);

n
else if (a[mid] > key)
return RecursiveBinarySearch(a, low, mid - 1, key);

else
return(mid);
}
}
Space Complexity :-

● Iterative → O(1)

at e
G
● Recursive → O(logn) (due to recursion stack)

e
Advantages

g
● Extremely fast

d
● Suitable for large datasets

l e
Disadvantages

● Requires sorted data

w
● Not efficient for linked list

n o
 t e
Min-Max Algorithm (Straight Method)

a
The Min-Max algorithm is used to find the minimum and maximum elements in an array using a linear

G
search approach.

e
In the Straight Method, each element of the array is compared with the current minimum and maximum

g
values. Algo: StraightMin-Max(a, n)
Input {

d
○ An array A[1 … n] min = max = a[1]

e
○ n = number of elements in the array

l
for i = 2 to n
● Example {

w
A = [12, 5, 8, 20, 3] if (a[i] > max)
n=5 max = a[i]

o
Output
else if (a[i] < min)

n
○ Minimum element in the array
min = a[i]
○ Maximum element in the array }
Example Output
Minimum = 3 return(min, max)
Maximum = 20 }
Best Case:

at e
Condition: Every new element is greater than the current maximum element.

G
● Number of Comparisons: (n−1)
● Explanation:

e
Only one comparison is required for each element because the condition a[i]>maxa[i] > maxa[i]>max becomes

g
true every time.

d
Worst Case:

e
● Condition: Every new element is smaller than the current minimum element.

l
● Number of Comparisons: 2(n−1)
● Explanation:

w
For every element, two comparisons are performed:
1. Comparison with maximum

o
2. Comparison with minimum

n
Average Case:

● Number of Comparisons: (3n / 2) - 1.5

t e
Min-Max Algorithm using Divide and Conquer Approach

a
G
The Divide and Conquer approach is an efficient method to find the minimum and maximum elements in an array.
In this method:

e
○ The array is divided into smaller subarrays.

g
○ Minimum and maximum values are found recursively.
○ The results are combined to obtain the final minimum and maximum.

d
● This method reduces the number of comparisons compared to the Straight Method.

e
Input

l
○ An array A[1 … n]
○ n = number of elements

w
● Example
A = [12, 5, 8, 20, 3, 15]

o
n=6

n
Output
○ Minimum element
○ Maximum element
Example Output
Minimum = 3
Maximum = 20
DACMINMAX(A, low, high)
{
if (low == high)
min = max = A[low]

at e
G
else if (low == high - 1)
{

e
if (A[low] < A[high])
{ min = A[low]

g
max = A[high]
}
else

d
{ min = A[high]
max = A[low]

e
}

l
}
else
{

w
mid = (low + high) / 2
(min1, max1) = DACMINMAX(A, low, mid)
(min2, max2) = DACMINMAX(A, mid + 1, high)

o
if (min1 < min2)
min = min1

n
else
min = min2
if (max1 > max2)
max = max1
else
max = max2
}
return(min, max)
}
Recurrence Relation for Time Complexity:

at e
geG
l ed
n ow
Recurrence Relation for Comparisons:

at e
geG
l ed
n ow
 t e
Straight Min-Max vs Divide and Conquer Min-Max (Comparisons)

a
geG
l ed
n ow
 t e
Q. How many comparisons are needed by an efficient algorithm to find the

a
minimum and maximum elements in an array of 250 elements?

geG
l ed
n ow
Module

Algorithms

Topic
Greedy Algorithms

Subtopic
Greedy Basics & Huffman

Lesson

Greedy Baics & Huffman Notes

Lesson 15 of 26
Greedy Algorithms
Greedy Basics & Huffman

[Link]
 Greedy Algorithm
• A greedy algorithm is a problem-solving approach like Subtract and conquer, divide and conquer
and dynamic programming, which is used for solving optimality problem(one Solution), out of all
feasible solution.

• Knapsack Problem
• Job sequencing with Deadline
• Huffman Coding
• Optimal Merge Pattern
• Minimum Spanning Tree
• Single source shortest path

[Link]
 लालच बुरी बला है ,
अगर बुरे काम के लए कया गया हो तो

[Link]
 Greedy Algorithm
• Definition: A greedy algorithm makes locally optimal choices at each stage with the hope of finding a global
optimum.
• Effectiveness: While a greedy strategy doesn't always produce the optimal solution, it often provides good
approximations in a reasonable amount of time.
• Example: In the Traveling Salesman Problem, a greedy strategy would involve visiting the nearest unvisited city at
each step. Though it doesn't guarantee the best solution, it finds a reasonable one quickly.
• Process: Greedy algorithms make one decision at a time and don't reconsider previous choices. This is different
from dynamic programming, which makes decisions based on previous stages and may revise earlier choices.
• Local vs Global Optimum: A greedy algorithm may reach a local maximum (e.g., "m") but miss the global
maximum (e.g., "M") if the local choice doesn't lead to the global best solution.

[Link]
 Huffman coding
• Definition: Huffman coding is an optimal prefix code used for lossless data
compression. It minimizes redundancy when encoding data, ensuring that no
code is a prefix of another.
• Development: The algorithm was developed by David A. Huffman while he
was a student at MIT in 1952, as a solution to a coding efficiency problem
presented by his professor.
• Process: Huffman’s algorithm builds a binary tree based on symbol
frequencies. The tree is built from the bottom up, ensuring an optimal coding
structure, unlike the top-down approach used in Shannon-Fano coding.
• Optimality: It generates a variable-length code table based on the frequency
of symbols. More frequent symbols get shorter codes, and less frequent
symbols get longer codes.
• Limitations: While Huffman coding is optimal for encoding symbols
separately, it is not always the most efficient method compared to other
advanced compression techniques that encode multiple symbols together.

[Link]
[Link]
[Link]
[Link]
Q Consider the following character with frequency and generate Huffman tree, find
Huffman code for each character, find the number of bits required for a message of
100 characters? Character Frequency
M1 12
M2 4
M3 45
M4 17
M5 23

[Link]
Q A networking company uses a compression technique to encode the message before
transmitting over the network. Suppose the message contains the following characters with their
frequency: If the compression technique used is Huffman Coding, how many bits will be saved in
the message?
(A) 24 (B) 800 (C) 76 (D) 324

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

[Link]
Q In question #2, which of the following represents the word “dead”?
(A) 1011111100101 (B) 0100000011010
(C) Both A and B (D) None of these
Character Frequency
a 5
b 9
c 12
d 13
e 16
f 45

[Link]
Q What is the time complexity of Huffman Coding?
(A) O(N) (B) O(NlogN) (C) O(N(logN)2) (D) O(N2)

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

[Link]
Module

Algorithms

Topic
Greedy Algorithms

Subtopic
Optimal Merge Pattern

Lesson

Optimal Merge Pattern Notes

Lesson 16 of 26
 t
Greedy Algorithms
a e
eG
Optimal Merge Pattern

g
l ed
n ow
 t e
Optimal Merge Pattern

a
Problem: Merging of two sorted list into a single sorted list.

A
1
4
2
9
3
13

geG
B
l
1
6 10
2 3
12
ed 4
17

C
n ow 1 2 3 4 5 6 7

Total time/Record movement =

a
G
A B C D A B C D A B C D
2 3 5 7 2 3

d ge5 7 2 3 5 7

wl e
n o
Case1: Total time/Record movement =
Case2: Total time/Record movement =
Case3:Total time/Record movement =
 t e
Optimal Merge Pattern

a
• Definition: An optimal merge pattern involves merging two or more sorted files into a single

G
sorted file using a two-way merge with the minimum number of record movements or

e
computations.

g
• Computation Time: If two files of size mmm and nnn are merged, the total computation time
will be m+nm + nm+n.

d
• Greedy Strategy: The greedy strategy is used by always merging the two smallest size files first,

e
ensuring the minimum total computation time.

l
• Conclusion: This method ensures an optimal solution by minimizing the overall number of

w
computations and movements during the merge process.

n o
 t e
Q Given a set of 8 files from F1 to F8 with following number of pages find the minimum number

a
of record movements to merge them into single file?

G
F1 F2 F3 F4 F5 F6 F7 F8
18 3 15 12

d ge 10 11 7 9

wl e
n o
Module

Algorithms

Topic
Greedy Algorithms

Subtopic
Fractional Knapsack

Lesson

KnapSack Problem Notes

Lesson 17 of 26
 t
Greedy Algorithms
a e
eG
Fractional Knapsack

g
l ed
n ow
•

at e
Knap Sack Problem
Definition: The knapsack problem is a combinatorial optimization problem where given a set of items

G
with specific weights and values, you need to determine the best combination of items to include in a

e
knapsack such that the total weight is within a given limit, and the total value is maximized.
• Versions: There are two versions of the problem:

g
• Fractional Knapsack: Items can be divided, meaning fractions of an item can be selected.

d
• 0/1 Knapsack: Items cannot be divided; you either take the whole item or none.
• History: The problem has been studied for over a century, with some of the earliest research dating

l e
back to 1897. The name is attributed to mathematician Tobias Dantzig.

n ow
 at e
geG
X1 X2

lX3

edX N-1 XN

n ow
one unit of each item.
t e
Q Consider the weights and values of items listed below. Note that there is only

a
Object O O O

G
1 2 3
Profit 25 24 15

e
Greedy by Profit

g
Weight 18 15 10

l ed
Object

n
Profit
Weighto
Solution
w O1
25
18
O2
24
15
O3
15
10
one unit of each item.
t e
Q Consider the weights and values of items listed below. Note that there is only

a
Object O O O

G
1 2 3
Profit 25 24 15

e
Greedy by Weight

g
Weight 18 15 10

l ed
Object

n
Profit
Weighto
Solution
w O1
25
18
O2
24
15
O3
15
10
one unit of each item.
t e
Q Consider the weights and values of items listed below. Note that there is only

a
Object O O O

G
1 2 3
Profit 25 24 15

e
Greedy by Profit/Weight

g
Weight 18 15 10

Object
l O1 O2
ed
O3
Profit
Weight

n ow 25 24
18 15
Profit/Weight 1.38 1.6
Solution
15
10
1.5
 t e
• Applications: The problem is commonly encountered in resource allocation

a
scenarios with financial constraints and has applications in fields like:

G
• Combinatorics

e
• Computer science
• Complexity theory
• Cryptography
• Applied mathematics

ed g
l
• Conclusion: The knapsack problem models real-life situations where a limited
capacity (e.g., knapsack) needs to be filled with the most valuable items,

w
maximizing utility while adhering to constraints.

n o
Module

Algorithms

Topic
Greedy Algorithms

Subtopic
Job & Activity Selection

Lesson

Job Scheduling Problem Notes

Lesson 18 of 26
Greedy Algorithms
at e
eG
Job and Activity Selection

g
l ed
n ow
• Problem Definition:

at e
Job sequencing with Deadline

G
• Given n jobs, each with a deadline Di and profit Pi if completed before the deadline.

e
• The goal is to schedule jobs on a single CPU with non-preemptive scheduling to maximize

g
profit.
• Assumptions:

d
• All jobs arrive at time 0.

e
• Each job takes exactly 1 time unit to complete (burst time = 1).

l
• Objective:
• Select a subset of jobs such that they can all be completed within their respective

w
deadlines and the total profit is maximized.

n o
 t e
Q if we have for task T1, T2, T3, T4, having Deadline D1 = 2, D2 =1, D3=2,

a
D4=1, and profit P1=100, P2=10, P3=27, P4=15, find the maximum profit

G
possible? Task T T T T

e
1 2 3 4

g
Profit 100 10 27 15

l
Deadline

ed
2 1 2 1

n ow
 Task T1 T2 T3

a
T4

t e T5 T6 T7

G
Profit 35 30 25 20 15 12 5
Deadline 3 4 4

d ge2 3 1 2

wl e
n o 1 2 3 4
• Solution Approach:

at e
• Step 1: Sort jobs in decreasing order of profit.
• Step 2: For each job in this order, find the latest available time slot iii such that i<Di and

G
the slot is empty.

e
• Step 3: Assign the job to the slot and mark the slot as filled.

g
• Step 4: If no such slot is available, ignore the job.

d
• Conclusion: The greedy strategy of scheduling the most profitable jobs first, within available

e
time slots, ensures the maximization of profit.

wl
n o
 at e
geG
led
n ow
Module

Algorithms

Topic
Dynamic Programming

Subtopic
Introduction to DP

Lesson

Introduction to DP Notes

Lesson 19 of 26
 Dynamic
at e
e
Programming
g G
ed
Introduction to DP
l
n ow
 t e
अगर आप अपने Past से कुछ सीख नहीं सकते तो

a
जीवनभर छोटे काम ही करते रहें गे I

geG -Dynamic Programming

l ed
n ow
 t e
Dynamic Programming

a
• Divide and conquer partition the problem into independent subproblem, solve the subproblems recursively and

G
then combine their solutions to solve the original problems.
• Dynamic programming is like the divide and conquer method, solve problems by combining the solutions to the

e
subproblems. In contrast, dynamic programming is applicable when the subproblems are not independent, i.e.

g
when subproblems share subsubproblems.
• A dynamic-programming algorithm solves every subsubproblems just one and then saves its answer in a table

d
there by avoiding the work of recomputing the answer every time the subproblem is encountered.
• Dynamic programming is typically applied to optimization problems. In such case there can be many possible

l e
solutions. Each solution has a value, and we wish to find a solution with the optimal value (minimum, maximum).

n ow
 n
F(n
0 1

at
2

e 3 4 5

G
)

d ge
wl e
n o O(N)
• There are four steps of dynamic programming

a
• Characterize the solution of an optimal solution.

t e
G
• Recursively define the value of an optimal solution.

e
• Compute the value of an optimal solution in a bottom-up-fashion.

d g
• Construct an optimal solution from computed information.

e
wl
o
भाई असली बात तो example से समझ आएगी

n
Module

Algorithms

Topic
Dynamic Programming

Subtopic
LCS & Subsequences

Lesson

LCS Notes

Lesson 20 of 26
 Dynamic
at e
e
Programming
g G
ed
LCS & Subsequences
l
n ow
 t e
Longest common subsequence

a
• The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to

G
all sequences in a set of sequences (often just two sequences).

e
• The longest common subsequence problem is a classic computer science problem, the basis of data

g
comparison programs such as the diff utility, and has applications in computational linguistics and bioinformatics.

d
• It is also widely used by revision control systems such as Git for reconciling multiple changes made to a
revision-controlled collection of files.

wl e
n o
 t e
Longest common subsequence

a
G
• Let there are two sequence X and Y, we say that a sequence Z is a common

e
subsequence of X and Y where

g
• Xm = {x1, x2, x3, ………. xm}

• Yn = {y1, y2, y3, ………. yn}

l ed
w
• we wish to find the maximum length of common of both X and Y,
Z = {z1, z2, z3, ………. zk}

n o
• Xm = {x1, x2, x3, ………. xm}
t e
STEP 1: Optimal Substructure

a
• Yn = {y1, y2, y3, ………. yn}
• Z = {z1, z2, z3, ………. zk}

geG
d
• if xm = yn

e
• then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1

wl
• if xm != yn, then zk != xm
• Implies that Zk is an LCS of Xm-1 and Yn

n o
• if xm != yn, then zk != yn
• Implies that Zk is an LCS of Xm and Yn-1
 t e
STEP 2: Recursive Solution

a
• Let us define C[i, j] to the length of L.C.S of sequence of Xi and Yj, if either i=0 or

G
j=0, so LCS has length 0.

• C[i, j] = {0

d ge
• The optimal substructure of LCS sub program gives the recursive formula
if i=0 or j=0}

e
• C[i, j] = {C[i-1, j-1] + 1 if i, j > 0 and xi = yj}

l
• C[i, j] = {max(C[i, j-1], C[i-1, j] if i, j > 0 and xi != yj}

n ow
LCS-Length (x, y)
{

at e
STEP 3: Computing the length of L.C.S

The running time of the procedure is O(mn), since

G
m 🡨 Length[x]
n 🡨 Length[y]
for i 🡨1 to m each table entry takes O(1) time to compute.

e
{
do C[i, 0] 🡨 0

g
}
for j 🡨0 to n
{
do C[0, j] 🡨 0

d
}
for i 🡨1 to m

e
{
for j 🡨1 to n

l
{
if (xi = yj)
{
c[i, j] 🡨 c[i-1, j-1] + 1

w
b[i, j] 🡨 ‘D_edge’
}
else if (C[i-1, j] >= C[i, j-1])

o
{
C[i, j] 🡨 C[i-1, j]
b[i, j] 🡨 ‘V_edge’

n
}
else
{
C[i, j] 🡨 C[i, j-1]
b[i, j] 🡨 ‘H_edge’
}
}
}
return b and C
}
Print_LCS (b, X, i, j)
{
if i=0 or j=0

at e
G
return
if (b[i, j] = ‘D_edge’)

e
{
then Print_LCS (b, X, i-1, j-1)

g
Print Xi

d
}
Else if (b[i, j] = ‘V_edge’)

e
{

l
Print_LCS (b, X, i-1, j)
}
Else

w
{

o
Print_LCS (b, X, i, j-1)
}

n
}

The procedure takes time O(m+n)

t e
Q Consider two strings X = “A, B, C, B, D, A, B” and Y = “B, D, C, A, B, A”. Find the longest common subsequence?

a
B A

G
0 1 2 3 4 5 6

e
0

g
A 1

d
B 2

B
3

wl e
o
D 5

n
A 6

B 7
Module

Algorithms

Topic
Dynamic Programming

Subtopic
Matrix Chain Order

Lesson

Matrix Chain Multiplication Notes

Lesson 21 of 26
 Dynamic
at e
e
Programming
g G
ed
Matrix Chain Order
l
n ow
•

at e
Matrix chain Multiplication
First lets understand what is the cost in terms of scalar multiplication for multiplying two

G
matrix of compatible order.

d ge
wl e
n o
 t e
• In matrix-chain multiplication problem, we are not actually multiplying matrix.

a
Our goal is only to determine an order for multiplying matrix that the lowest

G
cost.

e
A2X3 X A3X4 X A4X5 A2X3 X A3X4 X A4X5

ed g
wl
n o
 t e
STEP 1: The structure of an optimal paranthesization

a
• Suppose there are Ai, Ai+1……, Aj matrix to be multiplied

e
• Now let split the product chain Ai,……, AK ,AK+1……, Aj

g G
• Let Aij where i<=j for the matrix that results from evaluation of the product Ai,……, AK ,AK+1……, Aj

l d
• if i<=j then any paranthesization of product Ai,……, AK ,AK+1……, Aj must split the product between AK

e
& AK+1 in the range i <= k< j for the value of k. we first compute the matrix Ai,……, AK ,AK+1……, Aj. then
multiplying them to produce the final product Ai,…………, Aj.

w
• The cost of this paranthesization is the cost of computing the matrix Ai * AK and AK+1 to Aj and the cost of

o
multiplying them together.

n
• Suppose that the optimal paranthesization of Ai,……, Aj splits the product between Ak and Ak+1 then the
paranthesization of prefix sub chain. A1….Ak with in this optimal paranthesization of Ai….Aj must be optimal
paranthesization of A1 to Ak. A similar observation holds for the paranthesization of sub chain Ak+1 to Aj
 t e
STEP 2: Recursive Solution

a
• We define the cost of an optimal solution recursively in terms of the optimal solution to

G
subproblems.

e
• Let m[i, j] be the minimum number of scalar product needed to compute the matrix A i…j

g
• Let us assume that the optimal paranthesization splits the product Ai, Ai+1……, Aj between Ak

d
and Ak+1 . where i <= k < j. Then m[i, j] is equal to the minimum cost for computing the sub

e
products Ai,……, AK and AK+1……, Aj plus the cost of multiplying these two matrix together.

l
• Each matrix Ai is Pi-1 * Pi we see that commuting the matrix product Ai,……, AK ,AK+1……, Aj

w
takes Pi-1 Pk Pj scalar multiplication.

o
• m[i, j] = { 0 if(i=j)}

n
• m[i, j] = { min[m[i, k] + m[k+1, j] + Pi-1 Pk Pj] if(i < j)}
 • m[i, j] = { 0 if(i=j)}
t e
STEP 3: Computing the Optimal Cost

a
G
• m[i, j] = { min[m[i, k] + m[k+1, j] + Pi-1 Pk Pj] if(i < j)}

d ge
wl e
n o
A simple inspection of the nested loop structure of MATRIX-CHAIN-ORDER
yields a running time of O(n3) for the algorithm
STEP 4: Constructing an optimal Solution

at e
G
Print-Optimal Parenthesis (S, i, j)
{

e
if (i=j)

g
{

d
then print ‘Ai’
}

l e
Else
{

w
print “(”
Print-Optimal Parenthesis (S, i, S [i, j])

o
Print-Optimal Parenthesis (S, S [i, j] + 1, j)

n
print ‘)’
}
}
 t e
Q Let A1, A2, A3, A4 and A5 be five matrices of dimensions 30 x 35, 35 x 15, 15 x 5, 5 x 10, and

a
10 x 20 respectively. The minimum number of scalar multiplications required to find the

G
product A1A2A3A4A5 using the basic matrix multiplication method is?

e
m[i, j] = { min[m[i, k] + m[k+1, j] + Pi-1 Pk Pj]

ed g
wl
n o
 at e
geG
led
n ow
 at e
Q Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is
several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X
M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X

G
M3) X M4), the total number of scalar multiplications is pqr + prs + pst. If p = 10, q = 100, r = 20, s = 5 and t

e
= 80, then the number of scalar multiplications needed is:

g
a) 248000 b) 44000 c) 19000 d) 25000
m[i, j] = { min[m[i, k] + m[k+1, j] + Pi-1 Pk Pj]

l ed
n ow
Module

Algorithms

Topic
Dynamic Programming

Subtopic
Floyd & Subset Sum

Lesson

Floyd & Subset Sum Notes

Lesson 22 of 26
 Dynamic
at e
e
Programming
g G
ed
Floyd & Subset sum
l
n ow
 t e
All Pair Shortest Path-Floyd Warshall Algorithm

a
Q Consider a Directed weighted Graph and find all pair shortest path?

geG
l ed running time of O(n3) for the algorithm

n ow
 t e
Sum of subset problem

a
G
• Given a set of non-negative integers, and a value sum, determine if there is a subset of the

e
given set with sum equal to given sum.

g
Q Consider a set of non-negative integer S = {2, 3, 7, 8, 10}, find if there is a sub set of S with sum equal to 14?

d
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

e
2

l
3

w
7

o
10

n
Module

Algorithms

Topic
Minimum Spanning Trees

Subtopic
MST & Kruskal's Algo

Lesson

MST & Kruskal's Algo Notes

Lesson 23 of 26
Minimum Spanning
at e
Trees
geG
ed
MST & Kruskal’s Algo
l
n ow
 t e
Spanning tree

a
• A tree T is said to be spanning tree of a connected graph G, if T is a subgraph of
G and T contains all vertices of G.

geG
l ed
n ow
 t e
• A minimum spanning tree (MST) or minimum weight spanning tree is a subset

a
of the edges of a connected, edge-weighted undirected graph that connects all

G
the vertices together, without any cycles and with the minimum possible total

e
edge weight.

ed g
wl
n o
 t e
• Minimum spanning tree (MST) can be more than one

a
geG
l ed
n ow
 t e
• In general, a graph may have several spanning trees, but a graph that

a
is not connected will not contain a spanning tree (but see Spanning

G
forests below).

d ge
wl e
n o
• Any edge-weighted undirected graph (not necessarily connected) has a minimum spanning
forest, which is a union of the minimum spanning trees for its connected components.
•
Kruskal Algorithm
Joseph Bernard Kruskal, Jr. was an American

at e
G
mathematician, statistician, computer scientist and

e
psychometrician.
• Martin David Kruskal (September 28, 1925 – December

g
26, 2006) was an American mathematician and physicist.

d
He made fundamental contributions in many areas of
mathematics and science, ranging from plasma

l e
physics to general relativity and from nonlinear
analysis to asymptotic analysis. His most celebrated

w
contribution was in the theory of solitons.
• William Henry Kruskal (October 10, 1919 – April 21,

o
2005) was an American mathematician and statistician.

n
He is best known for having formulated the
Kruskal–Wallis one-way analysis of variance (together
with W. Allen Wallis), a widely used nonparametric
statistical method.
• Kruskal Algorithm Actual idea

at e
geG
l ed
n ow
Minimum_Spanning_Tree (G, w)

t
Kruskal

a e
G
{

e
A🡨ɸ
For each vertex v ϵ V(G)

g
{

d
do Make_Set(v)
}

l e
Sort the edges of E into non-decreasing order by weight w
for each edge (u, v) ϵ E, then in non-decreasing order by weights

w
{
if (Find_Set(u) != Find_Set(v))

o
{
A 🡨 A U {(u, v)}

n
UNION (u, v)
}
}
Return A
}
 at e
geG
led
n ow
Module

Algorithms

Topic
Minimum Spanning Trees

Subtopic
MST & Prim's Algo

Lesson

MST & Prim's Algo Notes

Lesson 24 of 26
 t
Minimum Spanning
a e
Trees
geG
ed
MST & Prim’s Algo
l
n ow
 Prim’s Algorithm

at e
• The algorithm was developed in 1930 by Czech mathematician

G
Vojtěch Jarník, later rediscovered and republished by computer

e
scientists Robert C. Prim in 1957 and Edsger W. Dijkstra in 1959.
Therefore, it is also sometimes called the Jarník's algorithm,

g
Prim–Jarník algorithm, Prim–Dijkstra algorithm or the DJP

d
algorithm.
• Vojtěch Jarník (1897–1970) was a Czech mathematician who

l e
worked for many years as a professor and administrator at
Charles University, and helped found the Czechoslovak

w
Academy of Sciences. He is the namesake of Jarník's
algorithm for minimum spanning trees.

o
• Robert Clay Prim (born September 25, 1921 in Sweetwater,
Texas) is an American mathematician and computer scientist.

n
• Edsger Wybe Dijkstra (11 May 1930 – 6 August 2002) was a
Dutch computer scientist, programmer, software engineer,
systems scientist, and science essayist. He received the
1972 Turing Award for fundamental contributions to
developing programming languages.
Minimum_Spanning_Tree (G, W, R)
{

for each u ϵ V(G)

at e
G
{

key[u] 🡨 ∞

e
∏[u] 🡨 NIL

g
}
Key[r] 🡨 0

d
Q 🡨V[G]
While (Q != ɸ) a b c d e f g

e
{

l
u 🡨 Extract-Min(Q)
For each v ϵ adj[u]

w
{

if (v ϵ Q and w(u, v) < key[v])

o
{

n
∏[v] 🡨 u
key[u] 🡨 w(u, v)

}
 at e
geG
led
n ow
Module

Algorithms

Topic
Shortest Path Algos

Subtopic
Dijkstra’s Algorithm

Lesson

Dijkstra's Algo Notes

Lesson 25 of 26
 t
Shortest Path Algos
a e
eG
Dijkastra’s Algorithm

g
l ed
n ow
 t e
Single Source Shortest Path

a
• In graph theory, the shortest path problem is the problem of finding a path between

G
two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is

e
minimized.

ed g
wl
n o
 at
prestigious Turing Award in 1972 for his work.

e
• One of his most famous inventions is Dijkstra's Algorithm, which he developed almost by
chance while sitting at a café in Amsterdam. The algorithm, created in just 20 minutes, solves

G
the shortest path problem, a fundamental concept in graph theory. This algorithm, published

e
in 1959, became widely influential and is still considered a cornerstone in computer science,

g
particularly in network routing protocols such as IS-IS and OSPF.
• Dijkstra’s algorithm is appreciated for its simplicity, which stems from his approach to

d
designing it without the aid of pencil and paper. This forced him to avoid unnecessary

e
complexities, making the algorithm highly efficient.

wl
n o
Dijkstra algorithm (G, W, S)
{
initialize-Single-source (G, S)
S🡨ɸ

at e
G
Q 🡨 V[G]
While (Q != ɸ)

e
{
u 🡨 extract-min (Q)
S 🡨 S U {u}

g
for each vertex v ϵ adj(u)
{

d
relax (u, v, w)

}
}
P Q R S T U

e
}

l
Relax (u, v, w)
{
if(d[v] > d[u] + w (u, v))

w
{
d[v] 🡨 d[u] + w (u, v)
∏[v] 🡨 u

o
}
}

n
Initialize_Single_Source (G, S)
{
for each vertex v ϵ V[G]
{
d[v] 🡨 ∞
∏[v] 🡨 NIL
}
d[S] 🡨 0
}
 at e
geG
led
n ow
 at e
geG
led
n ow
 t e
Dijkstra's algorithm (or Dijkstra's Shortest Path First algorithm, SPF algorithm)

a
∙ Guarantee to find optimal solution in a connected graph with positive weights.

G
∙ Can fail on graph with negative weights.

d ge
wl e
n o
Module

Algorithms

Topic
Shortest Path Algos

Subtopic
Bellman-Ford Algo

Lesson

Bellman-Ford Algo Notes

Lesson 26 of 26
 t
Shortest Path Algos
a e
eG
Bellman-Ford Algorithm

g
l ed
n ow
•

at e
Bellman–Ford Algorithm
The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of

G
the other vertices in a weighted digraph.
•

e
It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs
in which some of the edge weights are negative numbers.

g
• The algorithm was first proposed by Alfonso Shimbel (1955), but is instead named after Richard

d
Bellman and Lester Ford Jr., who published it in 1958 and 1956, respectively.

wl e
n o
Richard E. Bellman L. R. Ford Jr
Bellman_ford (G, W, S)
{
initialize-Single-Source (G, S)
for i 🡨 1 to |V(G)| - 1
{

at e
G
for each edge (u, v) ϵ E(G)
{

e
Relax(u, v, w)
}
}

g
for each edge (u, v) ϵ E(G)
{

d
if(d[v] > d[u] + w (u, v))
{
Return false

e
}
S T X Y Z

l
}
}
Initialize_Single_Source (G, S)
{

w
for each vertex v ϵ V[G]
{
d[v] 🡨 ∞

o
∏[v] 🡨 NIL
}
d[S] 🡨 0

n
}
Relax (u, v, w)
{
if(d[v] 🡨 d[u] + w (u, v))
{
d[v] 🡨 d[u] + w (u, v)
∏[v] 🡨 u
}
}
 at e
geG
led
n ow
 t e
Bellman–Ford algorithm with negative weight cycle

a
geG
l ed
n ow
Q Is the following statement valid?

at e
Given a weighted graph where weights of all edges are unique (no two

G
edge have same weights), there is always a unique shortest path from a

e
source to destination in such a graph.

g
(A) True (B) False

l ed
n ow
Q Is the following statement valid?

at e
Given a graph where all edges have positive weights, the shortest paths

G
produced by Dijkstra and Bellman Ford algorithm may be different but

e
path weight would always be same.

g
(A) True (B) False

l ed
n ow
 t e
Q Is the following statement valid about shortest paths?

a
Given a graph, suppose we have calculated shortest path from a source

G
to all other vertices. If we modify the graph such that weights of all

e
edges is becomes double of the original weight, then the shortest path

g
remains same only the total weight of path changes.

d
(A) True (B) False

wl e
n o
 t e
Q In a weighted graph, assume that the shortest path from a source ‘s’

a
to a destination ‘t’ is correctly calculated using a shortest path algorithm.

G
Is the following statement true?

e
If we increase weight of every edge by 1, the shortest path always

g
remains same.

d
(A) Yes (B) No

wl e
n o
(A) Dijkstra’s shortest path algorithm

at e
Q Which of the following standard algorithms is not a Greedy algorithm?
(B) Prim’s algorithm

G
(C) Kruskal algorithm (D) Huffman Coding

e
(E) Bellmen Ford Shortest path algorithm

ed g
wl
n o
 t e
Q Which of the following standard algorithms is not Dynamic Programming based.

a
(A) Bellman–Ford Algorithm for single source shortest path

G
(B) Floyd Warshall Algorithm for all pairs shortest paths

e
(C) 0-1 Knapsack problem

g
(D) Prim’s Minimum Spanning Tree

l ed
n ow