Unit5

Noida Institute of Engineering and Technology, Greater
Noida
String Matching, Approximation Algorithms

and Theory of NP Completeness
Unit: 5
Design & Analysis of Algorithms

Ankita Sharma
ACSE0401
Assistant Professor
B.Tech 4th Sem cse Department
ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit

V 1
12/8/24
Evaluation Scheme
12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm 2

Unit V
Syllabus
ANKITA SHARMA ACSE0401 Design and analysis of Algorithm

12/8/24 Unit V 3
Branch wise Application
• In Data mining
• Image Processing
• Digital Signature.
• DNA Matching.
12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 4

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.
ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V

12/8/24 5
Course Outcome
At the end of the semester, the student will be able:

Description Bloom’s Taxonomy
CO To have knowledge of basic principles of algorithm design and Knowledge, analysis
1 Analysis, asymptotic notations and growth of functions for time And design
and space complexity analysis and applying the same in different
sorting algorithms
CO To apply different problem-solving approaches for advanced data Knowledge, analysis
2 structures And apply
CO To apply divide and conquer method for solving merge sort, Knowledge, analysis and
3 quick sort, matrix multiplication and Greedy Algorithm for Apply
solving different Graph Problem.
CO To analyze and apply different optimization techniques like Knowledge, Analysis And
4 dynamic programming, backtracking and Branch & Bound to Apply
solve the complex problems
CO To understand the advanced concepts like NP Completeness and Knowledge, Analysis and
5 Fast Fourier Transform, to analyze and apply String Matching, Apply
Approximation and Randomized Algorithms to solve the
complex problems

Program 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

CO-PO and PSO Mapping
Design and Analysis of Algorithm (kCS-502)
PO1
CO.K PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO12
1
ACSE0401.1 3 3 3 3 2 - - - 2 2 - 3
ACSE0401.2 3 3 3 3 2 2 - 1 1 1 - 3
ACSE0401.3 3 3 2 3 3 2 - 2 1 1 2 3
ACSE0401.4 3 3 3 3 2 2 - 2 2 1 3 3
ACSE0401.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

Program Educational Objectives(PEOs)
PEO1: To have an excellent scientific and engineering breadth so as to

comprehend, analyze, design and provide sustainable solutions for
real-life problems using state-of-the-art technologies.
PEO2:To have a successful career in industries, to pursue higher studies or
to support entrepreneurial endeavors and to face global challenges.
PEO3:To have an effective communication skills, professional attitude,
ethical values and a desire to learn specific knowledge in emerging
trends, technologies for research, innovation and product
development and contribution to society.
PEO4: To have life-long learning for up-skilling and re-skilling for
successful professional career as engineer, scientist, enterpreneur
and bureaucrat for betterment of society

12/8/24 9
V
End Semester Question Paper Template
B TECH
(SEM-V) THEORY EXAMINATION 20__-20__
COMPILER DESIGN
Time: 3 Hours Total
Marks: 100
Note: 1. Attempt all Sections. If require any missing data; then choose
suitably.
SECTION A
1.Q.No.
Attempt all questions in brief.
Question Marks 2 COx 10
1 = 20 2
2 2
. .
10 2

End Semester Question Paper Templates
SECTION B
2. Attempt any three of the following: 3 x 10 = 30
Q.No. Question Mark CO

s
1 10
2 10
. .
5 SECTION C 10
3. Attempt any one part of the following: 1 x 10 = 10
Q.No. Question Marks CO
1 10
2 10
ANKITA SHARMA 12/8/24
ACSE0401 Design and analysis of Algorithm Unit V 11
End Semester Question Paper Templates
1 10
2 10
1 10
2 10
Q.No. Question Mark CO
s
1 10
2 10

Prerequisite and Recap
• Prerequisite
• Basic concept of c programming language.
• Concept of stack, queue and link list.
• Recap
• Flow Chart
• Algorithm

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

Unit 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

Topic Objective
• This objective this topic is to make students understand about

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

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

Algebraic Structures
• Basic requirements
– precise representation of algebraic structures
– precise arithmetic with algebraic structures
– other analytical operations with these structures

(e.g., differentiation , integration )

• 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

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.

, 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.
12/8/24 21
Unit V
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.

12/8/24 22
Unit V
• 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.

12/8/24 23
Unit V
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)⁡.

12/8/24 24
Unit V
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

Prerequisite
• Algorithms
• Finite automata
Recap

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,2…9} or {A, B .....Z, a, b..... z}.

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.

• 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.

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

12/8/24 30
V
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.

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)

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


String Matching Algorithm (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.

Rabin Karp Matcher(T, P, d, q)
1. nßlength[T] //TEXT LENGTH

2. mßlength[P] //PATTERN LENGTH
3. hßdm-1 mod q
4. pß0 //HOLDS HASH VALUE OF PATTERN
5. t0 ß0 // HOLDS INITIAL HASH VALUE OF THE FIRST SUBSTRING T
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
13.If s< n-m
14. then ts+1 ß(d(ts – T[s+1]h) + T[s+m+1]) mod q

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 T.Length =11 so Q = 11
And P mod Q = 26 mod 11 = 4
Now find the exact match of P mod Q...

Solution:





• 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.)

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,(either in 0,1,2.. ;a,b.. Form)
• δ is a function from Q x ∑ into Q called the transition function of M.
• F is final state
• The finite automaton starts in state q0 and reads the characters of its input
string one at a time.(So time complexity O(n))
• 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.

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.

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.
**KMP uses concept of prefix and suffix for generation of Π table.

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
10. Return Π
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).


Example: Compute Π for the pattern 'p' below:
Solution:
Initially: m = length [p] = 7 Π [1] = 0 k = 0

Knuth- Morris and Pratt(KMP) algorithm


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.


• 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

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.

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.

NP Completeness(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

Prerequisite
• Different Problems like graph colouring
• Travelling Salesman Problem
Recap
• String Matching Algorithm
• Algorithms for solving real world problems

• In a deterministic algorithm, for a given

particular input, the computer will always
produce the same output going through the same
states.
• The target machine executes the same

instruction and gives the same results that does
not depend upon the way or process in which
the instruction gets executed.
• Deterministic algorithms can solve a problem in

polynomial time. (Polynomial time is if we produce an output a/o to
given in/p within specific amount of time )
• In the case of the non-deterministic algorithm,

for the same input, the compiler may produce
different output in different runs.
• Non-deterministic algorithms take multiple
execution paths, thus it is quite difficult to
determine the next state of the machine.
• non-deterministic algorithms can’t solve the
problem in polynomial time and can’t determine
what is the next step.
**Problems whose time complexity is in exponential form they are NP Hard
Problem.
(NP-Problem means Non deterministic Polynomial time)

• When researcher makes an algorithm for any

problem then it lies either in deterministic
category or non deterministic category.
• In computer science, there exist some problems
whose solutions are not yet found, the problems
are divided into classes known as Complexity
Classes.
• These classes help scientists to group problems
based on how much time and space they require
to solve problems and verify the solutions.
• Complexity classes are useful in organising
similar types of problems.
Types of Complexity Classes

• P Class (Polynomial time and deterministic algo)
• NP Class (Time complexity is Polynomial Time
and Algorithm will be non deterministic)
• NP-hard (time complexity is in exponential, non
polynomial so researcher tries to design algo it in
such a way that its time complexity will be
Polynomial)
• NP-complete(it is NP Hard Problem which gives
polynomial time but with non deterministic algo)
P is subset of
12/8/24 NP
ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 60

• 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.

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.

• 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

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.

12/8/24 65
Unit V
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

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

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

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)}

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.

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'.

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

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.

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

• 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.

Approximation Algorithm(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.

12/8/24 76
V
Randomized Algorithm(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

12/8/24 77
Unit V
Faculty Video Links, You tube & NPTEL Video Links and
Online Courses Details
• Self Made Video Link:
• Youtube/other Video Links

• https://www.youtube.com/watch?v=e2cF8a5aAhE
• https://www.youtube.com/watch?v=jFW7fwa0Zm8
• https://www.youtube.com/watch?v=MEz1J9wY2iM

Daily Quiz
• What does NP stands for in complexity classes theory?

• The hardest of NP problems are ____________.
• Travelling sales man problem belongs to which of the class?
• A problem which is both _______ and _________ is said to be NP
complete.
• In terms of NTIME, NP problems are the set of decision problems
which can be solved using a non deterministic machine in _______
time.
• Problems that can be solved in polynomial time are known as?
• The sum and composition of two polynomials are always
polynomials.(True/False).
• .... is the class of decision problems that can be solved by non-
deterministic polynomial algorithms?

Weekly Assignment
1.Write 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]
2.Define 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]

• FFT

MCQs
1. Which of the following can be used to define NP complexity

class?
a) Verifier
b) Polynomial time
c) Both (a) and (b)
d) None of the mentioned
2. Which of the following are not in NP?

a) All problems in P
b) Boolean Satisfiability problems
c) Integer factorization problem

MCQs
3. Which of the following contains NP?

a) PSPACE
b) EXPSPACE
c) Both (a) and (b)
4. State true or false?

Statement: If a problem X is in NP and a polynomial time
algorithm for X could also be used to solve problem Y in
polynomial time, then Y is also in NP.
a) true
b) false

MCQs
5. Which of the following is incorrect for the given phrase

Phrase :’solvable by non deterministic algorithms in polynomial
time’
a) NP Problems
b) During control flow, non deterministic algorithm may have
more than one choice
c) If the choices that non deterministic algorithm makes are
correct, the amount of time it takes is bounded by polynomial time.
6. Which of the following can be used to define NP complexity class?

a) Verifier
b) Polynomial time
c) Both (a) and (b)

MCQs
7. Which of the following does not belong to the closure properties

of NP class?
a) Union
b) Concatenation
c) Reversal
d) Complement
8. The worst-case efficiency of solving a problem in polynomial time

is?
a) O(p(n))
b) O(p( n log n))
c) O(p(n2))
d) O(p(m log n))

12/8/24 V 84
MCQs
9. Halting problem is an example for?

a) decidable problem
b) undecidable problem
c) complete problem
d) trackable problem
10. A non-deterministic algorithm is said to be non-deterministic

polynomial if the time-efficiency of its verification stage is
polynomial.
a) true
b) false

12/8/24 Unit V 85
Glossary Question
Q.1 ________worst-case efficiency of solving a problem in polynomial time.

a) O(p(n))
b) O(p( n log n))
c) O(p(n2))
d) O(p(m log n))
Q.2 Problems that can be solved in polynomial time are known as____________.
a) intractable
b) tractable
c) decision
d) complete
Q.3 _________ is the class of decision problems that can be solved by non-
deterministic polynomial algorithms.
a) NP
b) P
c) Hard
d) Complete

12/8/24 V 86
Glossary Question
Q.4 Problems that cannot be solved by any algorithm are called _________.
a) tractable problems
b) intractable problems
c) undecidable problems
d) decidable problems
Q.5 Halting problem is an example for___________.
a) decidable problem
b) undecidable problem
c) complete problem
d) trackable problem.
Q.6 __________conditions have to be met if an NP- complete problem is
polynomially reducible?
a) 1
b) 2
c) 3
d) 4
12/8/24 Unit V 87
Glossary Question
Q.7 A CNF-satisfiability problem belong to______

a) NP class
b) P class
c) NP complete
d) NP hard
Q.8 The choice of polynomial class has led to the development of an extensive theory
called ________
a) computational complexity
b) time complexity
c) problem complexity
d) decision complexity
Q.9 A randomized algorithm uses random bits as input in order to achieve a
_____________ good performance over all possible choice of random bits.
a) worst case
b) best case
c) average case
d) none of the mentioned

Old Question Papers(2022-2023)


12/8/24 Unit V 90

12/8/24 Unit V 91

12/8/24 V 92

12/8/24 Unit V 93

12/8/24 Unit V 94

12/8/24 V 95

12/8/24 V 96

12/8/24 V 97

12/8/24 Unit V 98

12/8/24 V 99

12/8/24 101
V
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.
[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.
Recap Of Unit
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.
Unit 5
Thank You

Unit5

Uploaded by

Copyright:

Available Formats

Unit5

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit5

Uploaded by

Copyright:

Available Formats

Noida Institute of Engineering and Technology, Greater

String Matching, Approximation Algorithms

Design & Analysis of Algorithms

ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm 2

ANKITA SHARMA ACSE0401 Design and analysis of Algorithm

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 4

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

ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V

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

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 6

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

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 7

Design and Analysis of Algorithm (kCS-502)

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 8

PEO1: To have an excellent scientific and engineering breadth so as to

ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 10

Q.No. Question Mark CO

4. Attempt any one part of the following: 1 x 10 = 10

Q.No. Question Marks CO

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 12

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 13

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 14

• This. objective this unit is to make students understand about

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 15

• This objective this topic is to make students understand about

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 16

• In computational mathematics, computer algebra, also called

• Although , computer algebra should be a subfield of scientific

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 17

– precise arithmetic with algebraic structures

– other analytical operations with these structures

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 18

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

• Representation is very important because often the effectiveness of

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 19

Fast Fourier transformation

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

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

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 20

Fast Fourier transformation

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

• An FFT rapidly computes such transformations by factorizing the

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

Discrete Fourier transformation

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

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

ANKITA SHARMA ACSE0401 Design and analysis of Algorithm

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

• We divide the coefficient vector of the polynomial into two vectors,

ANKITA SHARMA ACSE0401 Design and analysis of Algorithm

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

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

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

ANKITA SHARMA ACSE0401 Design and analysis of Algorithm

This objective this topic is to make students understand about

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 25

12/8/24 ANKITA SHARMA ACSE0401 Design and analysis of Algorithm Unit V 26

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