➢ Robin karp algorithm .

Ans. The Robin-Karp algorithm is a pattern matching algorithm that uses hashing to
find occurrences of a pattern within a larger text. It works by comparing the hash
values of the pattern and substrings of the text.

Here's how it works:

1. First, calculate the hash value of the pattern you want to find.
2. Then, calculate the hash values of all possible substrings of the same length in the
text.
3. Compare the hash values. If they match, it means there's a potential match.
4. If the hash values match, compare the actual characters of the pattern and
substring to confirm the match.

The Robin-Karp algorithm is efficient because it uses hashing to quickly compare

substrings.

➢ Classify all pairs -shortest path problem .

Ans. The all pair shortest path algorithm is also known as Floyd-Warshall algorithm is used
to find all pair shortest path problem from a given weighted graph. As a result of
this algorithm, it will generate a matrix, which will represent the minimum distance from
any node to all other nodes in the graph.

At first the output matrix is same as given cost matrix of the graph. After that the output
matrix will be updated with all vertices k as the intermediate vertex.

The time complexity of this algorithm is O(V3), here V is the number of vertices in the graph.

Input − The cost matrix of the graph.

036∞∞∞∞
3021∞∞∞
620142∞
∞1102∞4
∞∞42021
∞∞2∞201
∞∞∞4110

Output − Matrix of all pair shortest path.

0345677
3021344
4201323
5110233
6332021
7423201
7433110

➢ Classify single source shortest paths algorithm.

Ans. Dijkstra’s Algorithm

The dijkstra’s algorithm is designed to find the shortest path between two
vertices of a graph. These two vertices could either be adjacent or the
farthest points in the graph. The algorithm starts from the source. The
inputs taken by the algorithm are the graph G {V, E}, where V is the set of
vertices and E is the set of edges, and the source vertex S. And the output
is the shortest path spanning tree.

Examples

To understand the dijkstra’s concept better, let us analyze the algorithm

with the help of an example graph −

Step 1

Initialize the distances of all the vertices as ∞, except the source node S.

Vertex S A B C D E
 Distance 0 ∞ ∞ ∞ ∞ ∞

Now that the source vertex S is visited, add it into the visited array.

visited = {S}

Step 2

The vertex S has three adjacent vertices with various distances and the
vertex with minimum distance among them all is A. Hence, A is visited and
the dist[A] is changed from ∞ to 6.

S→A=6
S→D=8
S→E=7
Vertex S A B C D E

Distance 0 6 ∞ ∞ 8 7

Visited = {S, A}

Step 3

There are two vertices visited in the visited array, therefore, the adjacent
vertices must be checked for both the visited vertices.

Vertex S has two more adjacent vertices to be visited yet: D and E. Vertex
A has one adjacent vertex B.

Calculate the distances from S to D, E, B and select the minimum distance

−

S → D = 8 and S → E = 7.
S → B = S → A + A → B = 6 + 9 = 15
Vertex S A B C D E
 Distance 0 6 15 ∞ 8 7

Visited = {S, A, E}

Step 4

Calculate the distances of the adjacent vertices – S, A, E – of all the visited

arrays and select the vertex with minimum distance.

S→D=8
S → B = 15
S → C = S → E + E → C = 7 + 5 = 12
Vertex S A B C D E

Distance 0 6 15 12 8 7

Visited = {S, A, E, D}

Step 5

Recalculate the distances of unvisited vertices and if the distances minimum

than existing distance is found, replace the value in the distance array.
S → C = S → E + E → C = 7 + 5 = 12
S → C = S → D + D → C = 8 + 3 = 11

dist[C] = minimum (12, 11) = 11

S → B = S → A + A → B = 6 + 9 = 15
S → B = S → D + D → C + C → B = 8 + 3 + 12 = 23

dist[B] = minimum (15,23) = 15

Vertex S A B C D E

Distance 0 6 15 11 8 7

Visited = { S, A, E, D, C}

Step 6

The remaining unvisited vertex in the graph is B with the minimum distance
15, is added to the output spanning tree.

Visited = {S, A, E, D, C, B}

The shortest path spanning tree is obtained as an output using the dijkstra’s
algorithm.
 ➢ Explain the representation of graph in the memory of a computer? Campare the
graph representation method.

Ans. Graph Representations

In graph theory, a graph representation is a technique to store graph into the memory of computer.

To represent a graph, we just need the set of vertices, and for each vertex the neighbors of the vertex
(vertices which is directly connected to it by an edge). If it is a weighted graph, then the weight will
be associated with each edge.

There are different ways to optimally represent a graph, depending on the density of its edges, type
of operations to be performed and ease of use.

1. Adjacency Matrix

o Adjacency matrix is a sequential representation.

o It is used to represent which nodes are adjacent to each other. i.e. is there any edge connecting nodes
to a graph.

o In this representation, we have to construct a nXn matrix A. If there is any edge from a vertex i to
vertex j, then the corresponding element of A, a i,j = 1, otherwise ai,j= 0.

Note, even if the graph on 100 vertices contains only 1 edge, we still have to have a 100x100
matrix with lots of zeroes.

o If there is any weighted graph then instead of 1s and 0s, we can store the weight of the edge.

Example
Consider the following undirected graph representation:

Backward Skip 10sPlay VideoForward Skip 10s

Undirected graph representation

Directed graph represenation

See the directed graph representation:

In the above examples, 1 represents an edge from row vertex to column vertex, and 0 represents no
edge from row vertex to column vertex.

Undirected weighted graph represenation

Pros: Representation is easier to implement and follow.

Cons: It takes a lot of space and time to visit all the neighbors of a vertex, we have to traverse all the
vertices in the graph, which takes quite some time.

2. Adjacency List

o Adjacency list is a linked representation.

o In this representation, for each vertex in the graph, we maintain the list of its neighbors. It means,
every vertex of the graph contains list of its adjacent vertices.

o We have an array of vertices which is indexed by the vertex number and for each vertex v, the
corresponding array element points to a singly linked list of neighbors of v.
Example
Let's see the following directed graph representation implemented using linked list:

We can also implement this representation using array as follows:

Pros:

o Adjacency list saves lot of space.

o We can easily insert or delete as we use linked list.

o Such kind of representation is easy to follow and clearly shows the adjacent nodes of node.

Cons:

o The adjacency list allows testing whether two vertices are adjacent to each other but it is slower to
support this operation.
 ➢ Kmp string matching algorithm.

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

Example: Given a string 'T' and pattern 'P' as follows:

Let us execute the KMP Algorithm to find whether 'P' occurs in 'T.'

For 'p' the prefix function, ? was computed previously and is as follows:

Solution:

Initially: n = size of T = 15
m = size of P = 7
Pattern 'P' has been found to complexity occur in a string 'T.' The total number of shifts that took
place for the match to be found is i-m = 13 - 7 = 6 shifts.

1, Identify string.

Ans. Given a string str, the task is to check if the string is a valid identifier or not. In order to
qualify as a valid identifier, the string must satisfy the following conditions:
1.It must start with an either underscore(_) or any of the characters from the ranges [‘a’,
‘z’] and [‘A’, ‘Z’].
2.There must not be any white space in the string.
3.And, all the subsequent characters after the first character must not consist of any special
characters like $, #, % etc.

2. identify minimum spanning tree.

Ans . Minimum Spanning Tree

A Minimum Spanning Tree (MST) is a subset of edges of a connected weighted
undirected graph that connects all the vertices together with the minimum possible total
edge weight. To derive an MST, Prim’s algorithm or Kruskal’s algorithm can be used. Hence,
we will discuss Prim’s algorithm in this chapter.

As we have discussed, one graph may have more than one spanning tree. If there
are n number of vertices, the spanning tree should have n - 1 number of edges. In this
context, if each edge of the graph is associated with a weight and there exists more than
one spanning tree, we need to find the minimum spanning tree of the graph.

Moreover, if there exist any duplicate weighted edges, the graph may have multiple
minimum spanning tree.

In the above graph, we have shown a spanning tree though it’s not the minimum spanning
tree. The cost of this spanning tree is (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38.
3. Define string cantentation.

Ans.

4. Maximum flow.

Ans. The Ford-Fulkerson algorithm is used to detect maximum flow from start vertex to
sink vertex in a given graph. In this graph, every edge has the capacity. Two vertices are
provided named Source and Sink. The source vertex has all outward edge, no inward edge,
and the sink will have all inward edge no outward edge.
There are some constraints:

• Flow on an edge doesn’t exceed the given capacity of that graph.

• Incoming flow and outgoing flow will also equal for every edge, except the source and the sink.

5.Boyce moor string matching.

Ans.