Selected Topics

Unit: V

Design & Analysis of Algorithms

N
KCS502
Assistant Professor
IT Department
B Tech 5th Sem

1
11/30/2025
 Contents

• Algebraic Computation
• Fast Fourier Transform
• String Matching
• Theory of NP-completeness
• Approximation algorithms
• Randomized algorithms.

11/30/2025 2
 Course Objective

• Upon completion of this course, students will be able to do the

following:
• Analyze the asymptotic performance of algorithms.
• Write rigorous correctness proofs for algorithms.
• Demonstrate a familiarity with major algorithms and data
structures.
• Apply important algorithmic design paradigms and methods of
analysis.
• Synthesize efficient algorithms in common engineering design
situations.

11/30/2025 3
 Unit 5-Objective

This objective this unit is to make students understand about

• Different classes of problems , P Class, NP class, NPC.
• Different string matching algorithms.
• The Approximation algorithm and Randomized algorithm

11/30/2025 4
 Course Outcome
At the end of the semester, the student will be able:
Description Bloom’s Taxonomy
CO1 To have knowledge of basic principles of algorithm design and Knowledge, analysis
Analysis, asymptotic notations and growth of functions for time And design
and space complexity analysis and applying the same in
different sorting algorithms
CO2 To apply different problem-solving approaches for advanced Knowledge, analysis
data structures And apply
CO3 To apply divide and conquer method for solving merge sort, Knowledge, analysis and
quick sort, matrix multiplication and Greedy Algorithm for Apply
solving different Graph Problem.

CO4 To analyze and apply different optimization techniques like Knowledge, Analysis And
dynamic programming, backtracking and Branch & Bound to Apply
solve the complex problems
CO5 To understand the advanced concepts like NP Completeness and Knowledge, Analysis and
Fast Fourier Transform, to analyze and apply String Matching, Apply
Approximation and Randomized Algorithms to solve the
complex problems

11/30/2025 5
 Programme Outcome

At the end of the semester, the student will be able:

POs Engineering Graduates will be able to
PO1 Engineering Knowledge
PO2 Problem Analysis
PO3 Design & Development of solutions
PO4 Conduct Investigation of complex problems
PO5 Modern Tool Usage
PO6 The Engineer and Society
PO7 Environment and sustainability
PO8 Ethics
PO9 Individual & Team work
PO10 Communication
PO11 Project management and Finance
PO12 Life Long Learning

11/30/2025 6
 CO-PO and PSO Mapping

Design and Analysis of Algorithm (KCS-502)

CO.K PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12

RCS-502.1 3 3 3 3 2 - - - 2 2 - 3

RCS-502.2 3 3 3 3 2 2 - 1 1 1 - 3

RCS-502.3 3 3 2 3 3 2 - 2 1 1 2 3

RCS-502.4 3 3 3 3 2 2 - 2 2 1 3 3

RCS-502.5 2 2 2 2 2 2 - 2 1 1 1 2

Average 2.8 2.8 2.6 2.8 2.2 1.6 - 1.8 1.4 1.2 1.2 2.8

11/30/2025 7
 CO-PO and PSO Mapping

Design & Analysis of Algorithms(KCS-502)

CO.K PSO1 PSO2 PSO3 PSO4

RCS-501.1 3 1 3 1

RCS-501.2 3 1 3 1

RCS-501.3 3 1 3 1

RCS-501.4 3 1 3 1

RCS-501.5 3 1 3 1

Average 3 1 3 1

11/30/2025 8
 Algebraic Computation(CO5)
Objective

This objective this topic is to make students understand about

• Computational Mathematics.
• Algebraic Structures
• Representation
• FFT & DFT

11/30/2025 9
 Prerequisite and Recap

• Prerequisite
• Mathematical concepts of Limits and differentiation

• Recap
• Techniques of solving real world problems like dynamic,
backtracking and branch & bound.

11/30/2025 10
 Algebraic Computation(CO5)

• In computational mathematics, computer algebra, also called

symbolic computation or algebraic computation, is a scientific area
that refers to the study and development of algorithms and
software for manipulating mathematical expressions and other
mathematical objects.

• Although , computer algebra should be a subfield of scientific

computing is generally based on numerical computation with
inexact floating point number, while representation computation
emphasize exact computation with terminology contain variables
that have no given value and are manipulated as symbols, hence
the representation computation

11/30/2025 11
 Algebraic Computation(CO5)
Algebraic Structures

• Basic requirements
– precise representation of algebraic structures

– precise arithmetic with algebraic structures

– other analytical operations with these structures

(e.g., differentiation , integration )

11/30/2025 12
 Algebraic Computation(CO5)

• To work on a computer with algebraic structures, we need to

represent them by some sort of data structures

• Representation is very important because often the effectiveness of

an algorithm will depend on the representation that is used.

• Can be represented by
– Representation of integers
– Representation of polynomials
– Representation of expressions

11/30/2025 13
, Algebraic Computation(CO5)

Fast Fourier transformation

• The discovery of the Fast Fourier transformation (FFT) is attributed to
Cooley and Tukey, who published an algorithm in 1965.

• A fast Fourier transform (FFT) is an algorithm that computes

the Discrete Fourier Transform (DFT) of a sequence, or its inverse
(IDFT).

• Fourier analysis converts a signal from its original domain (often time
or space) to a representation in the frequency domain and vice versa.

• The DFT is obtained by decomposing a sequence of values into

components of different frequencies.

11/30/2025 14
, Algebraic Computation(CO5)
Fast Fourier transformation

• This operation is useful in many fields, but computing it directly from

the definition is often too slow to be practical.

• An FFT rapidly computes such transformations by factorizing the DFT

matrix into a product of sparse (mostly zero) factors.

• It manages to reduce the complexity of computing the DFT from

O(N2), which arises if one simply applies the definition of DFT , to
O(NlogN), where N is the size of data.

• The difference in speed can be enormous, especially for long data sets
where N may be in the thousands or millions.
11/30/2025 15
 Algebraic Computation(CO5)

• Discrete Fourier transformation

• The discrete fourier transform (DFT) of the polynomial A(x) (or

equivalently the vector of coefficients (a0,a1,…,a n−1) is defined as
the values of the polynomial at the points x=wn,k i.e. it is the
vector:

DFT(a0,a1,…,an−1) =(y0,y1,…,yn−1)
=(A(wn,0),A(wn,1),…,A(wn,n−1)
=(A(w0n),A(w1n),…,A(wn−1n))

• Thus, if a direct DFT computes the values of the polynomial at the

points at the n-th roots, the inverse DFT can restore the
coefficients of the polynomial using those values.
11/30/2025 16
 Algebraic Computation(CO5)

• The fast Fourier transform is a method that allows computing the

DFT in O(nlogn) time.

• The basic idea of the FFT is to apply divide and conquer.

• We divide the coefficient vector of the polynomial into two

vectors, recursively compute the DFT for each of them, and
combine the results to compute the DFT of the complete
polynomial.

11/30/2025 17
 Algebraic Computation(CO5)
Inverse DFT

• The inverse DFT of values of the polynomial (y0,y1,…,yn-1) are

the coefficients of the polynomial (a0,a1,…,a n−1) .

InverseDFT(y0,y1,…,yn−1) = (a0,a1,…,an−1)

• Thus, if a direct DFT computes the values of the polynomial at

the points at the n-th roots, the inverse DFT can restore the
coefficients of the polynomial using those values.

• The computation of the inverse DFT is almost the same as the

calculation of the direct DFT, and it also can be performed
in O(nlogn).

11/30/2025 18
 String Matching(CO5)
Objective

This objective this topic is to make students understand about

• Concepts of String Matching
• Naïve String Matching
• Rabin Karp Algorithm
• Knuth Morris Pratt
• String Matching with automata
• Boyer Moore Algorithm

11/30/2025 19
 Prerequisite and Recap

Prerequisite
• Algorithms
• Finite automata

Recap
• Algebraic Computation

11/30/2025 20
 String Matching (CO5)

• String Matching Algorithm is also called "String Searching Algorithm”

are an important class of string algorithm that try to find a place
where one or several strings(also called patterns) are found within a
larger string or text.

• Given a text array, T [1.....n], of n character and a pattern array, P

[1......m], of m characters. The problems are to find an integer s,
called valid shift where 0 ≤ s < n-m and T [s+1......s+m] = P [1......m].

• In other words, to find even if P in T, i.e., where P is a substring of T.

• The item of P and T are character drawn from some finite alphabet
such as {0, 1} or {A, B .....Z, a, b..... z}.

11/30/2025 21
 String Matching (CO5)

• Given a string T [1......n], the substrings are represented as T

[i......j] for some 0≤i ≤ j≤n-1, the string formed by the
characters in T from index i to index j, inclusive. This process
that a string is a substring of itself (take i = 0 and j =m).

• The proper substring of string T [1......n] is T [1......j] for some

0<i ≤ j≤n-1. That is, we must have either i>0 or j < m-1.

11/30/2025 22
 String Matching(CO5)

• Using these descriptions, we can say given any string T [1......n], the
substrings are
T [i.....j] = T [i] T [i +1] T [i+2]......T [j] for some 0≤i ≤ j≤n-1.

And proper substrings are

T [i.....j] = T [i] T [i +1] T [i+2]......T [j] for some 0≤i ≤ j≤n-1.

• Note: If i>j, then T [i.....j] is equal to the empty string or null, which
has length zero.

11/30/2025 23
 String Matching(CO5)

Algorithms used for String Matching:

There are different types of method is used to finding the string

• The Naive String Matching Algorithm

• The Rabin-Karp-Algorithm

• Finite Automata

• The Knuth-Morris-Pratt Algorithm

• The Boyer-Moore Algorithm

11/30/2025 24
 String Matching(CO5)

Naïve String Matching Algorithm

 The naïve approach tests all the possible placement of Pattern P

[1.......m] relative to text T [1......n]. We try shift s = 0, 1.......n-m,
successively and for each shift s. Compare T [s+1.......s+m] to P
[1......m].

 The naïve algorithm finds all valid shifts using a loop that checks the
condition P [1.......m] = T [s+1.......s+m] for each of the n - m +1
possible value of s.

11/30/2025 25
 String Matching(CO5)

NAIVE-STRING-MATCHER (T, P)
• 1. n ← length [T]
• 2. m ← length [P]
• 3. for s ← 0 to n -m
• 4. do if P [1.....m] = T [s + 1....s + m]
• 5. then print "Pattern occurs with shift" s

Analysis: This for loop from 3 to 5 executes for n-m + 1(we need at
least m characters at the end) times and in iteration we are doing m
comparisons. So the total complexity is O (n-m+1)

11/30/2025 26
 String Matching(CO5)

• Example:
Suppose T = 1011101110 , P = 111 . Find all the Valid Shift
Solution:
•

11/30/2025 27
 String Matching(CO5)

11/30/2025 28
 String Matching Algorithm (CO5)

11/30/2025 29
 String Matching(CO5)

Rabin- Karp- Algorithm

• The Rabin-Karp string matching algorithm calculates a hash value for
the pattern, as well as for each M-character subsequences of text to
be compared.

• If the hash values are unequal, the algorithm will determine the
hash value for next M-character sequence.

• If the hash values are equal, the algorithm will analyze the pattern
and the M-character sequence.

• In this way, there is only one comparison per text subsequence, and
character matching is only required when the hash values match.

11/30/2025 30
 String Matching(CO5)
Rabin Karp Matcher(T, P, d, q)

1. nlength[T]
2. mlength[P]
3. hdm-1 mod q
4. p0
5. t0 0
6. For i1 to m (preprocessing)
7. do p(dp +P[i])modq
8. t0 (d t0 +T[i])modq
9. For s0 to n-m (matching)
10. do if p = ts
11. then if P[1…..m] = T[s +1,……..s+m]
12. then “Pattern occurs with shift” s
[Link] s< n-m
14. then ts+1 (d(ts – T[s+1]h) + T[s+m+1]) mod q
11/30/2025 31
 String Matching(CO5)
Rabin- Karp- Algorithm
Complexity: The running time of RABIN-KARP-MATCHER in the worst
case scenario O ((n-m+1) m but it has a good average case running time.
If the expected number of strong shifts is small O (1) and prime q is
chosen to be quite large, then the Rabin-Karp algorithm can be
expected to run in time O (n+m) plus the time to require to process
spurious hits.

Example: For string matching, working module q = 11, how many

spurious hits does the Rabin-Karp matcher encounters in Text T =
31415926535.......

T = 31415926535.......
P = 26
Here [Link] =11 so Q = 11
And P mod Q = 26 mod 11 = 4
Now find the exact match of P mod Q...

11/30/2025 32
 String Matching(CO5)

Rabin- Karp- Algorithm

Solution:

11/30/2025 33
 String Matching(CO5)

Rabin- Karp- Algorithm

11/30/2025 34
 String Matching(CO5)

Rabin- Karp- Algorithm

11/30/2025 35
 String Matching(CO5)

Rabin- Karp- Algorithm

11/30/2025 36
 String Matching(CO5)
Rabin- Karp- Algorithm
• The string-matching automaton is a very useful tool which is used in
string matching algorithm.

• It examines every character in the text exactly once and reports all
the valid shifts in O (n) time.

• The goal of string matching is to find the location of specific text

pattern within the larger body of text (a sentence, a paragraph, a
book, etc.)

11/30/2025 37
 String Matching(CO5)
String Matching With Finite Automata

A finite automaton M is a 5-tuple (Q, q0,A,∑δ), where

• Q is a finite set of states,
• q0 ∈ Q is the start state,
• A ⊆ Q is a notable set of accepting states,
• ∑ is a finite input alphabet,
• δ is a function from Q x ∑ into Q called the transition function of M.

• The finite automaton starts in state q0 and reads the characters of its
input string one at a time.
• If the automaton is in state q and reads input character a, it moves
from state q to state δ (q, a).
• Whenever its current state q is a member of A, the machine M has
accepted the string read so far. An input that is not allowed
is rejected.

11/30/2025 38
 String Matching(CO5)

Knuth-Morris and Pratt Algorithm

• Knuth-Morris and Pratt introduce a linear time algorithm for the

string matching problem.

• A matching time of O (n) is achieved by avoiding comparison with an

element of 'S' that have previously been involved in comparison
with some element of the pattern 'p' to be matched. i.e.,
backtracking on the string 'S' never occurs.

11/30/2025 39
 String Matching(CO5)

Components of KMP Algorithm:

1. The Prefix Function (Π): The Prefix Function, Π for a pattern

encapsulates knowledge about how the pattern matches against the
shift of itself. This information can be used to avoid a useless shift of
the pattern 'p.' In other words, this enables avoiding backtracking of
the string 'S.’

2. The KMP Matcher: With string 'S,' pattern 'p' and prefix function 'Π'
as inputs, find the occurrence of 'p' in 'S' and returns the number of
shifts of 'p' after which occurrences are found.

11/30/2025 40
 String Matching(CO5)
The Prefix Function (Π)
Following pseudo code compute the prefix function, Π:
Compute-Prefix-function(P)
1. nlength[P]
2. Π[1]0
3. K0
4. for q2 to m
5. do while k > 0 and P[k+1] ≠ P[q]
6. do k Π[k]
7. if P[k+1] = P[q]
8. then k k+1
9. Π[q]k
[Link] Π

In the above pseudo code for calculating the prefix function, the for
loop from step 4 to step 10 runs 'm' times. Step1 to Step3 take constant
time. Hence the running time of computing prefix function is O (m).

11/30/2025 41
 String Matching(CO5)

Knuth-Morris and Pratt Algorithm

Example: Compute Π for the pattern 'p' below:

Solution:
Initially: m = length [p] = 7 Π [1] = 0 k = 0

11/30/2025 42
 String Matching(CO5)

Knuth- Morris and Pratt(KMP) algorithm

11/30/2025 43
 String Matching(CO5)

Knuth-Morris and Pratt Algorithm

11/30/2025 44
 String Matching(CO5)

Boyer and Moore Algorithm

• Robert Boyer and J Strother Moore established it in 1977. The B-M
String search algorithm is a particularly efficient algorithm and has
served as a standard benchmark for string search algorithm ever
since.

• The B-M algorithm takes a 'backward' approach: the pattern string

(P) is aligned with the start of the text string (T), and then compares
the characters of a pattern from right to left, beginning with
rightmost character.

• If a character is compared that is not within the pattern, no match

can be found by analyzing any further aspects at this position so the
pattern can be changed entirely past the mismatching character.

11/30/2025 45
 String Matching(CO5)

Boyer and Moore Algorithm

• For deciding the possible shifts, B-M algorithm uses two
preprocessing strategies simultaneously. Whenever a mismatch
occurs, the algorithm calculates a variation using both approaches
and selects the more significant shift thus, if make use of the most
effective strategy for each case.

• The two strategies are called heuristics of B - M as they are used to

reduce the search. They are
• Bad Character Heuristics
• Good Suffix Heuristics

11/30/2025 46
 String Matching(CO5)
Boyer and Moore Algorithm
Bad Character Heuristics

This Heuristics has two implications:

• Suppose there is a character in a text in which does not occur in a

pattern at all. When a mismatch happens at this character (called as
bad character), the whole pattern can be changed, begin matching
form substring next to this 'bad character.’

• On the other hand, it might be that a bad character is present in the

pattern, in this case, align the nature of the pattern with a bad
character in the text.

• Thus in any case shift may be higher than one.

11/30/2025 47
 String Matching(CO5)

Boyer and Moore Algorithm

Good Suffix Heuristics:

• A good suffix is a suffix that has matched successfully.

• After a mismatch which has a negative shift in bad character

heuristics, look if a substring of pattern matched till bad character
has a good suffix in it, if it is so then we have an onward jump equal
to the length of suffix found.

11/30/2025 48
 NPCompleteness(CO5)
Objective

This objective this topic is to make students understand about

• Different Class of problems
• P Class
• NP Class
• NPC
• Hard Problems
• Approximation and Randomized algorithm

11/30/2025 49
 Prerequisite and Recap

Prerequisite
• Different Problems like graph colouring
• Travelling Salesman Problem

Recap
• String Matching Algorithm
• Algorithms for solving real world problems

11/30/2025 50
 NPCompleteness(CO5)

• A problem is in the class NPC if it is in NP and is as hard as any

problem in NP. A problem is NP-hard if all problems in NP are
polynomial time reducible to it, even though it may not be in NP
itself.

• If a polynomial time algorithm exists for any of these problems, all

problems in NP would be polynomial time solvable. These problems
are called NP-complete. The phenomenon of NP-completeness is
important for both theoretical and practical reasons.

11/30/2025 51
 NPCompleteness(CO5)

A language B is NP-complete if it satisfies two conditions

1. B is in NP
2. Every A in NP is polynomial time reducible to B.

• If a language satisfies the second property, but not necessarily the

first one, the language B is known as NP-Hard. Informally, a search
problem B is NP-Hard if there exists some NP-
Complete problem A that Turing reduces to B.

• The problem in NP-Hard cannot be solved in polynomial time, until P

= NP. If a problem is proved to be NPC, there is no need to waste
time on trying to find an efficient algorithm for it. Instead, we can
focus on design approximation algorithm.

11/30/2025 52
 NPCompleteness(CO5)

• NP-Complete Problems
Following are some NP-Complete problems, for which no polynomial
time algorithm is known.
• Determining whether a graph has a Hamiltonian cycle
• Determining whether a Boolean formula is satisfiable, etc.

• NP-Hard Problems
The following problems are NP-Hard
• The circuit-satisfiability problem
• Set Cover
• Vertex Cover
• Travelling Salesman Problem

11/30/2025 53
 NPCompleteness(CO5)
Circuit Satisfiability
According to given decision-based NP problem, we can design the
CIRCUIT and verify a given mentioned output also within the P time.
The CIRCUIT is provided below:-

Although we can design a circuit and verified the mentioned output

within Polynomial time but remember we can never predict the
number of gates which produces the high output against the set of
inputs/high inputs within a polynomial time. So we verified the
production and conversion had been done within polynomial time. So it
is NPC.

11/30/2025 54
 NPCompleteness(CO5)
Set Cover Problem

• Given a universe U of n elements, a collection of subsets of U say S

= {S1, S2…,Sm} where every subset Si has an associated cost.

• Find a minimum cost subcollection of S that covers all elements of

U.

• There is no polynomial time solution available for this problem as

the problem is a known NP-Hard problem

11/30/2025 55
 NPCompleteness(CO5)

Example:
U = {1,2,3,4,5}, S = {S1,S2,S3}

S1 = {4,1,3}, Cost(S1) = 5
S2 = {2,5}, Cost(S2) = 10
S3 = {1,4,3,2}, Cost(S3) = 3

Output: Minimum cost of set cover is 13 and set cover is {S2, S3}
There are two possible set covers {S1, S2} with cost 15 and {S2, S3} with
cost 13

11/30/2025 56
 NPCompleteness(CO5)
Vertex Cover problem

The minimum vertex cover problem is the optimization problem of

finding a smallest vertex cover in a given graph. The vertex cover
problem is an NP-complete problem.
A vertex-cover of an undirected graph G = (V, E) is a subset of
vertices V' ⊆ V such that if edge (u, v) is an edge of G, then
either u in V or v in V' or both.

APPROX-VERTEX_COVER (G: Graph) c ← { } E' ← E[G]

1. while E' is not empty do
2. Let (u, v) be an arbitrary edge of E' c ← c U {u, v}
3. Remove from E' every edge incident on either u or v
4. return c

11/30/2025 57
 NPCompleteness(CO5)

Example:
The set of edges of the given graph is −
{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,8),(3,5),(8,5)}

11/30/2025 58
 NPCompleteness(CO5)

Now, we start by selecting an In the next step, we have chosen

arbitrary edge (1,6). We eliminate another edge (2,3) at random
all the edges, which are either
incident to vertex 1 or 6 and we
add edge (1,6) to cover.

11/30/2025 59
 NPCompleteness(CO5)

Now we select another edge (4,7). We select another edge (8,5).

Hence, the vertex cover of this graph is {1,2,4,5}.

Analysis
It is easy to see that the running time of this algorithm is O(V + E), using
adjacency list to represent E'.

11/30/2025 60
 NPCompleteness(CO5)
Travelling Salesman Problem

• The traveling salesman problem consists of a salesman and a set

of cities.

• The salesman has to visit each one of the cities starting from a
certain one and returning to the same city.

• The challenge of the problem is that the traveling salesman wants

to minimize the total length of the trip

11/30/2025 61
 NPCompleteness(CO5)

Proof

1. To prove TSP is NP-Complete, first we have to prove that TSP

belongs to NP.

• In TSP, we find a tour and check that the tour contains each vertex
once.

• Then the total cost of the edges of the tour is calculated.

• Finally, we check if the cost is minimum.

• This can be completed in polynomial time.

• Thus TSP belongs to NP

11/30/2025 62
 NPCompleteness(CO5)
2. Secondly, we have to prove that TSP is NP-hard.

• To prove this, one way is to show that Hamiltonian cycle ≤p TSP (as
we know that the Hamiltonian cycle problem is NPcomplete).
Assume G = (V, E) to be an instance of Hamiltonian cycle.
Hence, an instance of TSP is constructed. We create the complete
graph G' = (V, E'), where
E′={(i,j):i,j ∈ V and i≠j
E′={(i,j):i,j ∈V and i≠j
Thus, the cost function is defined as follows −
t(i,j)= 0 if (i,j) ∈ E
=1 otherwise

11/30/2025 63
 NPCompleteness(CO5)

• Now, suppose that a Hamiltonian cycle h exists in G. It is clear that

the cost of each edge in h is 0 in G' as each edge belongs to E.
Therefore, h has a cost of 0 in G'. Thus, if graph G has a
Hamiltonian cycle, then graph G' has a tour of 0 cost.

• Conversely, we assume that G' has a tour h' of cost at most 0. The
cost of edges in E' are 0 and 1 by definition. Hence, each edge
must have a cost of 0 as the cost of h' is 0. We therefore conclude
that h' contains only edges in E.

• We have thus proven that G has a Hamiltonian cycle, if and only

if G' has a tour of cost at most 0. TSP is NP-complete.

11/30/2025 64
 NPCompleteness(CO5)

• An Approximate Algorithm is a way of approach NP-

COMPLETENESS for the optimization problem.

• This technique does not guarantee the best solution.

• The goal of an approximation algorithm is to come as close as

possible to the optimum value in a reasonable amount of time
which is at the most polynomial time

• A simple example of an approximation algorithm is one for the

Minimum Vertex Cover problem, where the goal is to choose the
smallest set of vertices such that every edge in the input graph
contains at least one chosen vertex.

11/30/2025 65
 NPCompleteness(CO5)

• An algorithm that uses random numbers to decide what to do next

anywhere in its logic is called Randomized Algorithm.. For example,
in Randomized Quick Sort, we use random number to pick the next
pivot (or we randomly shuffle the array). And in Karger's algorithm,
we randomly pick an edge..
For example:
• Select a random number from stream, with O(1) space.
• Birthday Paradox
• Linearity of Expectation
• Random Number generator in arbitrary probability distribution
fashion

11/30/2025 66
 Weekly Assignment

[Link] Rabin-Karp algorithm. For string matching working modulo q =

11, how many spurious hits does the Rabin-Karp matcher encounter
in the text T = 3141592653589793 when looking for pattern P = 26?
[CO5]
[Link] NP, NP hard and NP complete. Give example of each. [CO5]

3. Explain Approximation and Randomized algorithms. [CO5]

4. Explain Rabin Karp algorithm. For the text 2359023141526739921

and for the pattern 31415 and working modulo q=13 how many valid
match and spurious hits does the Rabin matcher encounter. [CO5]

5. Write short notes on [CO5]

• Algebraic Computation
• FFT

11/30/2025 67
 Old Question Papers(2019-2020)

11/30/2025 68
 Old Question Papers(2019-2020)

11/30/2025 69
 Old Question Papers(2019-2020)

11/30/2025 70
 Old Question Papers(2019-2020)

11/30/2025 71
 Old Question Papers(2019-2020)

11/30/2025 72
 Old Question Papers(2018-2019)

11/30/2025 73
 Old Question Papers(2018-2019)

11/30/2025 74
 Old Question Papers(2018-2019)

11/30/2025 75
 Old Question Papers(2018-2019)

11/30/2025 76
 Old Question Papers(2018-2019)

11/30/2025 77
 Old Question Papers(2017-2018)

11/30/2025 78
 Old Question Papers(2017-2018)

11/30/2025 79
 Old Question Papers(2017-2018)

11/30/2025 80
 Old Question Papers(2017-2018)

11/30/2025 81
 Old Question Papers(2017-2018)

11/30/2025 82
 Expected Questions for University Exam

1. What are the different applications of DFT and FFT? [CO5]

2. Discuss the string matching algorithms along with an example.e
[CO5]
3. How is approximation algorithm different from randomized
algorithm? [CO5]
4. Explain Naive string matching algorithm. [CO5]
5. Discuss the problem classes, NP, P, NPC along with their [CO5]
relationship.

11/30/2025 83
 Summary

This unit gives the insights of different classes of problems , P

Class, NP class, NPC. The different string matching algorithms
have been discussed. The Approximation algorithm and
Randomized algorithm have also been explained.

11/30/2025 84
 References

1. Thomas H. Coreman, Charles E. Leiserson and Ronald L. Rivest,

“Introduction to Algorithms”, Printice Hall of India.
2. E. Horowitz & S Sahni, "Fundamentals of Computer Algorithms",
3. Aho, Hopcraft, Ullman, “The Design and Analysis of Computer
Algorithms” Pearson Education, 2008.
4. LEE “Design & Analysis of Algorithms(POD)”, McGraw Hill
5. Richard [Link] ‘Foundations of Algorithms” Jones & Bartlett
Learning.
6. Gilles Brassard and Paul Bratley, Algorithmics: Theory and Practice,
Prentice Hall, 1995.

11/30/2025 85
 Unit 5

Thank You

11/30/2025 86