Introduction

January 2025

CSE201
 First things first!!

(January 2025) Introduction CSE201 2 / 68

Instructor Contacts

Instructor: Ayan Das

Email id: [email protected]
TAs
Tripti Kumari
Bharti
Akash Mishra
Mode of contact
Email or post in Google Classroom.
Classroom interaction.
Please do not call over the phone or send Whatsapp messages.

(January 2025) Introduction CSE201 3 / 68

Class timings

Wednesday: 3:00 PM - 3:50 PM

Thursday: 2:00 PM - 2:50 PM
Friday: 2:00 PM - 2:50 PM
Class rules:
Institute rule: 75% attendance is mandatory.

(January 2025) Introduction CSE201 4 / 68

Class timings

Wednesday: 3:00 PM - 3:50 PM

Thursday: 2:00 PM - 2:50 PM
Friday: 2:00 PM - 2:50 PM
Class rules:
Institute rule: 75% attendance is mandatory.
Class rule: Enter the class within 5 minutes of the commencement of
the class.
ATTENDANCE MEANS PHYSICAL PRESENCE IN THE CLASS!!

(January 2025) Introduction CSE201 4 / 68

Lecture basics

Classes will involve both Slides + Board

For the latest/updated slides, download them before each use.

(January 2025) Introduction CSE201 5 / 68

Lecture basics

Classes will involve both Slides + Board

For the latest/updated slides, download them before each use.
Use of laptops and smartphones is not allowed in the classroom.

(January 2025) Introduction CSE201 5 / 68

Evaluation plan

Evaluation plan
Quiz 1: 10 marks
Mid semester: 32 marks
Quiz 2: 10 marks
End semester: 48 marks

Textbooks and reference books

1 Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms,
Prentice Hall of India.
2 E. Horowitz, S. Sahni, and S. Rajasekaran, Fundamentals of
Computer Algorithms, Universities Press.

(January 2025) Introduction CSE201 6 / 68

Topics to be covered

Introduction (5 hours)
Definition and characteristics(1), Algorithm design and pseudocode(2),
Flowchart(2)
Analysis of Algorithms (5 hours)
Time and space complexity(1),Asymptotic notation(1.5),Recurrence relation(1.5)
Divide and Conquer paradigm (8 hours)
Strategy(1),Binary search(1),Quicksort(2),Mergesort(2),Order statistics(1),Matrix
multiplication(1)
Greedy Algorithms (8 hours)
Strategy(1),Fractional knapsack(1),Minimum Spanning Tree(2), Single source
shortest Path(1.5),Activity Selection(1.5),Optimal Merge Patterns(2)

(January 2025) Introduction CSE201 7 / 68

Topics to be covered (continued)

Dynamic Programming (8 hours)

Strategy(0.5),Fibonacci Numbers(0.5),0-1 knapsack problem(2),Edit
distance(1),Longest Common Subsequence(2),All pair shortest path(2)
Backtracking (4 hours)
Strategy(1),Depth First Search(1),4-Queen Problem(1),Graph Coloring(1)
Branch-and-Bound (4 hours)
Least Cost Search (2), 15-Puzzle Problem (2)

(January 2025) Introduction CSE201 8 / 68

Course Webpage

Google classroom link: Introduction to Algorithms (NCSE102)

https:
//classroom.google.com/c/Njk3NzYzMTQ4NDkz?cjc=vvexenn
Why do I need to check the webpage?
Lecture Notes
Misc. static information about the course.
Announcements, Quiz schedules, and marks.

(January 2025) Introduction CSE201 9 / 68

Data structures and Algorithms

Core issue
Problem solving by a computer.

(January 2025) Introduction CSE201 10 / 68

Data structures and Algorithms

Core issue
Problem solving by a computer.

Algorithms and data structures are very much integrated concepts

and go hand-in-hand in solving any problem for which a computer
program needs to be developed.

(January 2025) Introduction CSE201 10 / 68

Data structures and Algorithms

Core issue
Problem solving by a computer.

Algorithms and data structures are very much integrated concepts

and go hand-in-hand in solving any problem for which a computer
program needs to be developed.

(January 2025) Introduction CSE201 10 / 68

Points to remember

Problem solving is not merely programming.

We are solving a problem using a computer that has a specific
architecture and structure.
Problem is posed in human language.
If it is possible for a computer to understand human language and
solve a problem, then the concepts of algorithms and data structures
are already automated.
Our task is to convert the problem described in a human language to
a description in a programming language so that a computer can
solve it efficiently.

(January 2025) Introduction CSE201 11 / 68

Basic Components in a Computer

(January 2025) Introduction CSE201 12 / 68

Programming

A computer needs to be
programmed to do tasks.
Program: sequence of
instructions to do a task,
computer processes the
instructions sequentially one
after the other.
Programming is the process of
writing instructions in a
language that can be
understood by the computer so
that a desired task can be
performed by it.

(January 2025) Introduction CSE201 13 / 68

Example

Problem
Find the maximum of N integers.

The problem statement does not give us the steps for solving it.
Why steps?
Because the computer does not understand a visual expression! Given
a snap of a series of numbers, the computer cannot determine the
maximum by inspection.
The notion of steps is inherent to the structure/architecture of a
computer.
Similarly the notion of efficiently organizing the data in computer
memory for efficient access and manipulation is also inherent to the
construct of the computer.
Our task is to design the steps and plan the organization of the data
for efficient implementation of the solution to a problem.
(January 2025) Introduction CSE201 14 / 68
Array in memory

(January 2025) Introduction CSE201 15 / 68

Array

(January 2025) Introduction CSE201 16 / 68

Example

Problem
Find the maximum of N integers.

READ(n) // Read the number of integers

READ(value) // Value of the first number
MAX=value
LOOP: 2 to n, 1
READ(value)
IF MAX < value:
THEN MAX = value
PRINT(MAX)

These are the generic steps for solving the problem.

These steps can be implemented in a programming language and run
on a computer as a program.
(January 2025) Introduction CSE201 17 / 68
Data structures and Algorithms

Algorithms: A recipe for solving a problem; a step-by-step procedure

to solve a problem.
Program: An implementation of an algorithm in a programming
language.
Data structure: Organization of the data in the memory needed to
solve a problem.

(January 2025) Introduction CSE201 18 / 68

 Algorithm basics

(January 2025) Introduction CSE201 19 / 68

Algorithmic problem

Specification of input defines the domain of the input. There can be

infinitely many input instances satisfying the specification of the input
e.g. A sequence of positive integers of finite length
1: 5, 11232456, 12, 771, 49, 34245,
2: 65535, 2124, 6, 98, 323178, 435

(January 2025) Introduction CSE201 20 / 68

Algorithmic problem

An algorithm describes the sequence of actions taken on the input to

convert it to an output such that it is a solution to the instance of the
problem corresponding to the input.

(January 2025) Introduction CSE201 21 / 68

Properties of an algorithm

Correctness: It should correctly transform any instance from the

input domain to the output domain.
Finiteness: The algorithm must terminate after a finite number of
steps on input of finite size.
Definiteness: The statements of the algorithm must be unambiguous
and it must always produce the same output for a given input.
Effectiveness: Every step in the algorithm must be effective i.e.
every step should do some work.

(January 2025) Introduction CSE201 22 / 68

Good algorithm

Efficient
Running time
Space used
Efficiency as a function of input size
The number of bits in an input.
Number of data elements.
In this course, we shall focus on efficiency in terms of running time.

(January 2025) Introduction CSE201 23 / 68

Measuring the running time

How do you measure the running time

of an algorithm?

(January 2025) Introduction CSE201 24 / 68

Measuring the running time

How do you measure the running time

of an algorithm?
It should be done by measuring the
running time of the implementation of
the algorithm.

Implement the algorithm in a programming language.

Run the program over inputs of different sizes.
Measure the running time of the program e.g. clock() in < time.h >.
The runtime of an implementation may vary due to the choice of
programming language, system load, implementation details, etc.
We are interested in the variation of runtime as a function of input
size.
(January 2025) Introduction CSE201 24 / 68
Beyond experimental studies

We have to develop a general methodology for analyzing the running

time of the algorithms.
The approach
1 Develop a high-level description of the algorithm instead of
implementation.
2 Take inputs of all possible but finite sizes into account.
3 Hardware and software environment independent efficiency evaluation
technique for algorithms.

(January 2025) Introduction CSE201 25 / 68

Pseudocode

A stepwise description of the generic ideas of a data structure or

algorithm using a combination of natural language and high-level
programming concepts.
A pseudo-code need not necessarily run in a computer but must obey
the properties of an algorithm.
It is more structured than standard text but less formal than a
program.
Expressions:
Standard mathematical symbols and expressions.
Use ’←’ for assignment
Use ’=’ for equality relationship.
Method declaration:
Procedure FindMax(N)
Algorithm LinearSearch(parameter1, parameter2)

(January 2025) Introduction CSE201 26 / 68

Analysis of algorithms

Primitive operations: Programming language independent low-level

operations e.g.
1 Data movement. (Assignment, Reading input)
2 Control (Conditionals, Loops, Function call, return)
3 arithmetic and logical operations.
Count the number of such primitive operations in the pseudocode.
Express the count as a function of the input size.

(January 2025) Introduction CSE201 27 / 68

Time complexity (Example 1)
Find the sum of n numbers

Code 1
READ(n)
sum <- 0
LOOP: i <- 1 to n, 1
READ(value)
sum <- sum + value
PRINT(sum)

(January 2025) Introduction CSE201 28 / 68

Time complexity (Example 1)
Find the sum of n numbers
Code 2: With a count variable
READ(n)
Code 1 sum <- 0
count <- 0
READ(n)
LOOP: i <- 1 to n, 1
sum <- 0
READ(value)
LOOP: i <- 1 to n, 1
sum <- sum + value
READ(value)
count <- count + 1
sum <- sum + value
PRINT(sum)
PRINT(sum)
count <- count + 1
// For PRINT stmt
PRINT (count)

(January 2025) Introduction CSE201 28 / 68

Time complexity (Example 1)
Find the sum of n numbers
Code 2: With a count variable
READ(n)
Code 1 sum <- 0
count <- 0
READ(n)
LOOP: i <- 1 to n, 1
sum <- 0
READ(value)
LOOP: i <- 1 to n, 1
sum <- sum + value
READ(value)
count <- count + 1
sum <- sum + value
PRINT(sum)
PRINT(sum)
count <- count + 1
n count (= n + 1) // For PRINT stmt
1 2 PRINT (count)
2 3
3 4
.. ..
. .
(January 2025) Introduction CSE201 28 / 68
Time complexity (Example 2)

Generate the multiplication tables of n numbers with first n integers

READ(n) // Number of multiplicands

READ(n) // Number of multipliers
LOOP: i <- 1 to n, 1
READ(mcand)
LOOP: j <- 1 to n, 1
prod <- mcand * j
PRINT(mcand, j, prod)

(January 2025) Introduction CSE201 29 / 68

Time complexity (Example 2)

Generate the square multiplication tables of n numbers with first n

integers
READ(n) // Number of multiplicands and multipliers
count <- 0
LOOP: i <- 1 to n, 1
READ(mcand)
LOOP: j <- 1 to n, 1
prod <- mcand * j
PRINT(mcand, j, prod)
count <- count + 1
PRINT(count)
Value of count = n2

(January 2025) Introduction CSE201 30 / 68

Time complexity (Example 2)

Generate the multiplication tables of n numbers with first n integers

READ(n) // Number of multiplicands and multipliers
count <- 0
LOOP: i <- 1 to n, 1
READ(mcand)
count <- count + 1
LOOP: j <- 1 to n, 1
prod <- mcand * j
PRINT(mcand, j, prod)
count <- count + 1
PRINT(count)
Value of count = n2 + n

(January 2025) Introduction CSE201 31 / 68

Time complexity (Example 2)

Generate the multiplication tables of n numbers with first n integers

READ(n) // Number of multiplicands and multipliers
count <- 2
LOOP: i <- 1 to n, 1
READ(mcand)
count <- count + 1
LOOP: j <- 1 to n, 1
prod <- mcand * j
PRINT(mcand, j, prod)
count <- count + 2
PRINT(count)
Value of count = 2n2 + n + 2

(January 2025) Introduction CSE201 32 / 68

Time complexity
Among all the values of count the leading term is n2 .
If we take the number of operations into account it will simply
multiply the leading by a constant (i.e. the number of operations).
For a very large value of n the value of the lower order terms will be
insignificant.
The constant term will depend on the implementation and will affect
the value of the step count uniformly for the different values of n.

n n2 n2 + n 2n2 + n + 2
5 25 30 57
50 2500 2550 5052
500 250000 250500 500502
5000 25000000 25005000 50005002
50000 2500000000 2500050000 5000050002
.. .. .. ..
. . . .

(January 2025) Introduction CSE201 33 / 68

Different time complexity functions

(January 2025) Introduction CSE201 34 / 68

Time complexity (Example 3)

Linear search in an one-dimensional array

READ(key) // Element to be found
A[n] // Array of n numbers
LOOP: j <- 1 to n, 1
IF A[j] = key // key found
THEN PRINT (j)
EXIT // Exit the program
PRINT(0)

(January 2025) Introduction CSE201 35 / 68

Time complexity (Example 3)

Linear search in an one-dimensional array

READ(key) // Element to be found
A[n] // Array of n numbers
count <- 0
LOOP: j <- 1 to n, 1
count <- count + 1
IF A[j] = key // key found
THEN PRINT (j)
EXIT // Exit the program
PRINT(0)
PRINT (count)

(January 2025) Introduction CSE201 36 / 68

Best/Worst/Average case
Best case: The first element matches the key. A[1] = key count = 1
Worst case: The last element matches the key or none of the
elements match the key. A[n] = key count = f (n)
Average case:
1 In the best case you compare with just one element.
2 In the worst case you compare with all the n elements.
3 So on average, over several runs, you may have to compare the key
with all the elements in the array, and without any further information
all the elements are equally likely.
1 1 1
time complexity = ∗ 1 + ∗ 2 + · · · + ∗ n
n n n
1
= (1 + 2 + 3 + · · · + n)
n
n+1
=
2

(January 2025) Introduction CSE201 37 / 68

Best/Worst/Average case
Best case: The first element matches the key. A[1] = key count = 1
Worst case: The last element matches the key or none of the
elements match the key. A[n] = key count = f (n)
Average case:
1 In the best case you compare with just one element.
2 In the worst case you compare with all the n elements.
3 So on average, over several runs, you may have to compare the key
with all the elements in the array, and without any further information
all the elements are equally likely.
1 1 1
time complexity = ∗ 1 + ∗ 2 + · · · + ∗ n
n n n
1
= (1 + 2 + 3 + · · · + n)
n
n+1
=
2
This analysis is for successful searches. What will happen if we
consider unsuccessful searches??
(January 2025) Introduction CSE201 37 / 68
Best/Worst/Average case
For a specific size of input n, investigate running times for different input
instances

Best case is the smallest possible time your algorithm will take on an
input of size n.
Worst case is the maximum possible time your algorithm will take on
an input of size n.
Average case is the average of all the possible run times of your
algorithm on any input of size n.
(January 2025) Introduction CSE201 38 / 68
Best/Worst/Average case

For inputs of all sizes

(January 2025) Introduction CSE201 39 / 68

Best/Worst/Average case

Worst case is usually used: It is an upper-bound and in certain

application domains (e.g., air traffic control, surgery) knowing the
worst-case time complexity is of crucial importance.
For some algorithms worst case occurs fairly often.
Average case is often as bad as the worst case.
Finding average case may be very difficult.

(January 2025) Introduction CSE201 40 / 68

Asymptotic analysis

Goal: To simplify the analysis of running time by getting rid of

factors that may be implementation or hardware-specific.
Eliminating the lower order terms e.g. 50000021 ≈ 50000000
Avoiding the constant factors. 3n2 ≈ n2
Capturing the essence: How the running time of an algorithm
increases with the size of the input in the limit.
Asymptotically more efficient algorithms are best for large inputs.

(January 2025) Introduction CSE201 41 / 68

Asymptotic notation (Big-O notation)

Used for worst case analysis.

The “big-Oh” notation
Used to measure the
asymptotic upper bound.
f (n) is O(g (n)) if there exists
constant c and n0 such that
0 ≤ f(n) ≤ cg(n) for n ≥ n0
f (n) and g (n) are functions
over non-negative integers.

(January 2025) Introduction CSE201 42 / 68

Example

For functions f (n) and g (n) there are positive constants c and n0 such
that: 0 ≤ f (n) ≤ cg (n) for n ≥ n0

Conclusion:
2n + 6 is O(n)

(January 2025) Introduction CSE201 43 / 68

Another Example

(January 2025) Introduction CSE201 44 / 68

Another Example

n2 is not O(n).
There is no c and n0 such that:
n2 ≤ cn for n ≥ n0
The graph to the left shows that
no matter how large a c you
choose, there is always an n big
enough that n2 > cn

(January 2025) Introduction CSE201 44 / 68

Asymptotic Notation

Estimate the worst-case running time from the algorithm steps.

Simple rule: Drop the lower order terms and constant factors.
50n is O(n)
7n − 3 is O(n)
8n2 log n + 5n2 + n is O(n2 log n)
Even though 100nlog n is O(n10 ), it is expected that such an
approximation is of as small an order as possible.

(January 2025) Introduction CSE201 45 / 68

Asymptotic Analysis of Running Time
Use O-notation to express the number of primitive operations
executed as a function of input size.
Comparing asymptotic running times
An algorithm that runs in O(n) time is better than one that runs in
O(n2 ) time.
Similarly, O(log n) is better than O(n).
Hierarchy of functions: log n < n < n log n < n2 < n3 < 2n
Caveat: Beware of very large constant factors !!
An algorithm running in time 1,000,000 n is still O(n) but might be
less efficient than one running in time 2n2 , which is O(n2 ).

(January 2025) Introduction CSE201 46 / 68

Example of Asymptotic Analysis

Procedure prefixAverages(A)
Input: An n-element array X of numbers.
Output: An n-element array A of numbers such that A[i]
is the average of elements X[0], ..., X[i].
for i <- 1 to n do
a <- 0
for j <- 1 to i do
a <- a + X[j]
A[i] <- a / j
return array A

(January 2025) Introduction CSE201 47 / 68

Example of Asymptotic Analysis

(January 2025) Introduction CSE201 48 / 68

Example of Asymptotic Analysis

Homework: Propose an O(n) algorithm for this problem.

Analyze the generation of nth Fibonacci number.

(January 2025) Introduction CSE201 48 / 68

Asymptotic Notation (terminology )

Special classes of algorithms:

1 Logarithmic: O(log n)
2 Linear: O(n)
3 Quadratic: O(n2 )
4 Polynomial: O(nk ), k ≥ 1
5 Exponential: O(an ), a > 1
Other related notations to Big-Oh
1 Ω(f (n)): Big Omega- asymptotic lower bound
2 Θ(f (n)): Big Theta- asymptotic tight bound

(January 2025) Introduction CSE201 49 / 68

Asymptotic Notation (The “Big-Omega” Ω notation.)

Used to describe asymptotic lower bounds for algorithmic problems

e.g. lower-bound for searching in an unsorted array is Ω(n).

Used to describe the

best-case running times or
lower bounds of algorithmic
problems.
lower bound for searching an
unsorted array is Ω(n)
f (n) is Ω(g (n)) if there exist
constants c and n0 s.t.
cg(n) ≤ f(n) for n ≥ n0 .

(January 2025) Introduction CSE201 50 / 68

Asymptotic Notation (The “big-Theta” Θ-Notation)

Used to describe asymptotic tight bound.

f (n) = Θ(g (n)) if there exists constants c1 , c2 and n0 such that
c1 g(n) ≤ f(n) ≤ c2 g(n) for n ≥ n0

f (n) is Θ(g (n)) if and only if

1 f (n) is O(g (n))
2 f (n) is Ω(g (n))

(January 2025) Introduction CSE201 51 / 68

Abuse of asymptotic notations

Abuse of notation: f (n) = O(g (n)) actually means f (n) ∈ O(g (n)).
Analogy with real numbers
f (n) = O(g (n)) ∼
=f ≤g
f (n) = Ω(g (n)) ∼
=f ≥g
f (n) = Θ(g (n)) ∼
=f =g

(January 2025) Introduction CSE201 52 / 68

 Recurrence relations

(January 2025) Introduction CSE201 53 / 68

Recurrence relations

Recurrence relations are an essential tool in the analysis of recursive

algorithms.
Tool to mathematically express the time complexity of algorithms in
terms of their recursive structure and input size.
Recurrence relations require one or more base cases that define the
time complexity for the smallest instances of the problem.
These base cases
1 act as termination conditions for the recursion
2 provide a starting point for analyzing the time complexity of larger
instances.

(January 2025) Introduction CSE201 54 / 68

Recursive linear search

LIN_SEARCH(A,k,key,n) // k is an index
IF k > n:
RETURN -1
IF A[k] = key:
THEN RETURN k
ELSE
LIN_SEARCH(A,k+1,key)
What will be the complexity for an input array A of size n for the call
LIN SEARCH(A, 1, key , n)?

(January 2025) Introduction CSE201 55 / 68

Recursive linear search

LIN_SEARCH(A,k,key,n) // k is an index
IF k > n:
RETURN -1
IF A[k] = key:
THEN RETURN k
ELSE
LIN_SEARCH(A,k+1,key)
What will be the complexity for an input array A of size n for the call
LIN SEARCH(A, 1, key , n)?
Let the number of comparisons for an input size n be T (n).
If n = 1, the number of comparisons is 1 or T (1) = 1.
If n = 2, the number of comparisons is T (2) = 1 + T (1) = 2.
...

(January 2025) Introduction CSE201 55 / 68

Recursive linear search

If n = 3, the number of comparisons is

T (3) = 1 + T (2) ≡ 1 + 1 + T (1) = 3.
T (n) = 1 + T (n − 1)
The expression has two components
1 The complexity of non-recursive operations within the function call.
2 The complexity of the call to the sub-problem.
T (n) = O(n), meaning that the time complexity of recursive linear
search grows linearly with the size of the array n.

(January 2025) Introduction CSE201 56 / 68

Recursive binary search

INPUT: A sorted array of size n and a key to be searched.

OUTPUT: The position of the search key in the array.

(January 2025) Introduction CSE201 57 / 68

Recursive binary search

INPUT: A sorted array of size n and a key to be searched.

OUTPUT: The position of the search key in the array.
BIN_SEARCH(A,low,high,key)
mid = (low+high)/2
IF low > high:
RETURN -1
IF A[mid] = key:
RETURN mid
ELSE IF key < A[mid]:
BIN_SEARCH(A,low,mid-1,key)
ELSE IF key > A[mid]:
BIN_SEARCH(A,mid+1,high,key)

(January 2025) Introduction CSE201 57 / 68

Recursive binary search

(January 2025) Introduction CSE201 58 / 68

Recursive binary search
If n = 1, T (1) = c
Non-recursive operations within a function call = c
Number of recursive calls = 1
Input size of the recursive call w.r.t. to current input size n = n/2
T (n) = T (n/2) + c
Assuming n = 2m

T (n) = T (n/2) + c
= c + c + T (n/4)
...
= c + c + c + · · · + c (log2 n times)
= clog2 n
= O(log2 n)

(January 2025) Introduction CSE201 59 / 68

Recurrence relation: Example

Find the time complexity for the following recurrence relation

T (n) = 2T (n − 1) + 1, where T (1) = 1

(January 2025) Introduction CSE201 60 / 68

Recurrence relation: Example

Find the time complexity for the following recurrence relation

T (n) = 2T (n − 1) + 1, where T (1) = 1
T (n) = 2n−1 T (1) + 2n−2 + 2n−3 + · · · + 22 + 2 + 1

(January 2025) Introduction CSE201 60 / 68

Recurrence relation: Example

Find the time complexity for the following recurrence relation

T (n) = 2T (n − 1) + 1, where T (1) = 1
T (n) = 2n−1 T (1) + 2n−2 + 2n−3 + · · · + 22 + 2 + 1
Solution: T (n) = O(2n )

(January 2025) Introduction CSE201 60 / 68

Recurrence relation: Example

√
T (n) = 2T (⌊ n⌋) + log n and T (1) = 1 for n = 2m

(January 2025) Introduction CSE201 61 / 68

Master Theorem

The master method is a formula for solving recurrence relations of the

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

where T (n) is the time complexity of the algorithm for an input of size
n.
a = number of sub-problems in the recursion
n/b = size of each subproblem
f (n) represents the time complexity of combining the solutions of the
subproblems and any additional work done outside the recursive calls.
It provides a simple way to determine the time complexity based on
the values of ’a’, ’b’, and the complexity of ’f (n)’.
It has three cases, depending on how ’f (n)’ compares with nlogb a

(January 2025) Introduction CSE201 62 / 68

Recurrence relation: Master theorem

(January 2025) Introduction CSE201 63 / 68

Recurrence relation: Example

(January 2025) Introduction CSE201 64 / 68

Goals of the course

How to devise algorithms?

How to analyze algorithms?

(January 2025) Introduction CSE201 65 / 68

 Data structure basics

(January 2025) Introduction CSE201 66 / 68

Data structuring

Given a problem, we try to solve that computationally by

1 developing the steps for solving the problem.
2 analyzing the solution.
3 improving the solution.

(January 2025) Introduction CSE201 67 / 68

Data structuring

Given a problem, we try to solve that computationally by

1 developing the steps for solving the problem.
2 analyzing the solution.
3 improving the solution.
Improvement can be done in two major ways
1 Redesigning the algorithm to reduce the runtime complexity.
2 Data structuring: Efficient organization of data for faster access and
manipulation.
3 Data structuring is a very important component of algorithm design.

(January 2025) Introduction CSE201 67 / 68

Data structures

Data structuring consists of two major components,

1 Organization of data elements.
2 Efficient procedures for data manipulation.
and both are interlinked.
Every programming language provides in-built some data
structure/datatypes and provision to create other data structures.
We shall address data structuring by discussing the arrays in this
course.

(January 2025) Introduction CSE201 68 / 68

 Temperature Converter
• converts temperatures from Celsius to Fahrenheit and vice
versa.
• Input:
• The temperature value.
• The unit of the input temperature (Celsius or Fahrenheit).
• Output:
• The converted temperature.

08/01/2025 1
 Student Grade Calculation
• Input:
• Scores for exams and assignments.

• Output:
• The final grade.

08/01/2025 2
 FlowChart/Algorithm
• Flow chart/ Algorithm:
• A step-by-step procedure for solving a particular problem.
• Should be independent of the programming language.

• Program
• A translation of the algorithm/flowchart into a form that can be processed by a
computer.
• Typically written in a high-level language like C, C++, Java, etc.

08/01/2025 3
 Flowchart Symbols

Start/Stop Control Flow

Input/ Output
Condition / Decision Box

Computation

08/01/2025 4
 Adding two numbers
Start

Read A, B

S= A+B

Print S

Stop

08/01/2025 5
 Celsius to Fahrenheit
Start

Read C

F=C*(9/5)+32

Print F

Stop

08/01/2025 6
 Greatest of two numbers
Start

Read A, B

If
A>B

Print A Print B

Stop

08/01/2025 7
 Greatest of 3 Numbers
Start

Read A, B, C

If A > B

If A > C
If B > C

Print B Print A
Print A Print C

Stop Stop Stop Stop

08/01/2025 8
 Sum of first N natural numbers
Start

Read N

SUM=0
Count=1

SUM=SUM+count
Count=Count+1

NO Is Output
YES
Count> SUM
N?

Stop

08/01/2025 9
 SUM = 12+ 22+ 32+ N2
Start Start

Read N Read N

SUM=0 SUM=0
Count=1 Count=n

SUM=SUM+(count*count) SUM=SUM+(count*count)
Count=Count+1 Count=Count-1

Is NO Is YES Output
NO YES Output
Count> Count<= 0 SUM
SUM ?
N?

Stop Stop

08/01/2025 10
 SUM =1.2 +2.3+3.4 to N terms
Start

Read N

SUM=0
Count=1

SUM=SUM+count*(count+1)
Count=Count+1

NO Is Output
YES
Count> SUM
N?

Stop

08/01/2025 11
 Computing Factorial
Start

Read N

Prod=1
Count=1

Prod=Prod*count
Count=Count+1

NO Is Output
YES
Count> SUM
N?

Stop

08/01/2025 12
 Practice
• Prime number
• Even and odd
• Any other series like exponential series
• Fibonacci series

08/01/2025 13
 Divide and Conquer

Dr. Ayan Das

Department of Computer Science & Engineering
Indian Institute of Technology (ISM), Dhanbad
Jharkhand-826004
E-mail: [email protected]

Data Structures and Algorithms Dept. of CSE, IIT(ISM) Dhanbad 30/06/24 1

 Outline
Introduction
Minmax Algorithm
Binary Search
Mergesort
Matrix Multiplication

Data Structures and Algorithms Dept. of CSE, IIT(ISM) Dhanbad 30/06/24 2

 Introduction
A divide-and-conquer algorithm divides the problem instance
into a number of sub-instances (in most cases 2)
Each of these sub-instances is solved recursively, using the
same divide-and-conquer approach.
Recursive methods are applied until the sub-problems reach a
base case, which is a simple enough problem to solve directly.
Once the sub-instances have been solved, their solutions are
combined or integrated to obtain the final solution to the
original, larger problem.
This process often leads to an efficient and elegant way of
solving complex problems.

Data Structures and Algorithms Dept. of CSE, IIT(ISM) Dhanbad 30/06/24 3

 Example: Minmax Algorithm
Problem Statement: Finding both the minimum and maximum in an
array of integers A[1:n] and assume for simplicity that n is a power of 2.
A straightforward algorithm might look like the one below.

The number of element comparisons performed by this method is 2n-2.

By employing the divide-and-conquer (D&C) strategy, it's possible to identify
both the minimum and maximum using only (3n/2) - 2 element comparisons.

Data Structures and Algorithms Dept. of CSE, IIT(ISM) Dhanbad 30/06/24 4

 Minmax Algorithm based on D&C
Value 22 13 -5 -8 15 60 17 31 47
Index 1 2 3 4 5 6 7 8 9

Data Structures and Algorithms Dept. of CSE, IIT(ISM) Dhanbad 30/06/24 5

 Contd…

Data Structures and Algorithms Dept. of CSE, IIT(ISM) Dhanbad 30/06/24 6

 Contd…
This leads to the subsequent recurrence relation for the
number of comparisons done by the algorithm:

Data Structures and Algorithms Dept. of CSE, IIT(ISM) Dhanbad 30/06/24 7

 Binary Search

The time complexity of Algorithm is O(log n).

Data Structures and Algorithms Dept. of CSE, IIT(ISM) Dhanbad 30/06/24 8

Data Structures and Algorithms
 Merge Sort

Data Structures and Algorithms Dept. of CSE, IIT(ISM) Dhanbad 30/06/24 10

 Example

Data Structures and Algorithms Dept. of CSE, IIT(ISM) Dhanbad 30/06/24 11

 Matrix Multiplication
In this section, we show how to apply the divide
and conquer strategy to this problem to obtain an
efficient algorithm.
In the traditional method, Matrix multiplication is
computed using the formula:

To compute C(i,j), we need n multiplications, again

as the matrix C has n2 elements . The complexity
will be O(n3)

Data Structures and Algorithms Dept. of CSE, IIT(ISM) Dhanbad 30/06/24 12

 The traditional algorithm

Data Structures and Algorithms Dept. of CSE, IIT(ISM) Dhanbad 30/06/24 13

 Strassen's algorithm
The idea behind this algorithm consists in
reducing the number of multiplications at the
expense of increasing the number of additions
and subtractions.
In short, this algorithm uses 7 multiplications
and 18 additions of n/2 × n/2 matrices.

Data Structures and Algorithms Dept. of CSE, IIT(ISM) Dhanbad 30/06/24 14

 Contd…

Data Structures and Algorithms Dept. of CSE, IIT(ISM) Dhanbad 30/06/24 15

 Contd…

Data Structures and Algorithms Dept. of CSE, IIT(ISM) Dhanbad 30/06/24 16

 Thank You
Data Structures and Algorithms Dept. of CSE, IIT(ISM) Dhanbad 30/06/24 17