Module 2

Amruthasree V M, Assistant Professor, NIE 1

 2.1 Brute-Force String Matching
• A string of n characters called the text and a string of m characters (m ≤ n)
called the pattern.
• We need to find a substring of the text that matches the pattern and find i—the
index of the leftmost character of the first matching substring in the text.
• Align the pattern against the first m characters of the text and start matching the
corresponding pairs of characters from left to right until either all the m pairs of
the characters match or a mismatching pair is encountered.
• If all the m pairs of the characters match then the algorithm can stop.
• If mismatching pair is encountered then subsequently shift the pattern one
position to the right and resume the character comparisons, starting again with
the first character of the pattern and its counterpart in the text.
Amruthasree V M, Assistant Professor, NIE 2
• Note: The last position in the text that can still be a beginning of a matching
substring is n-m.
• Beyond that position, there are not enough characters to match the entire pattern.
Hence the algorithm need not make any comparison here.

Algorithm:

Amruthasree V M, Assistant Professor, NIE 3

Example:

Amruthasree V M, Assistant Professor, NIE 4

1. Worst case : The algorithm may have to make all m comparisons before shifting the
pattern, and this can happen for each of the n − m + 1 tries. Thus, in the worst case, the
algorithm makes m(n − m + 1) character comparisons, which puts it in the O(nm) class.
Text: a a a a a a a a
Pattern : a a b
a a b
a a b
a a b
a a b
a a b
• Here n is 8 and m is 3.
• The number of iteration is 6. So we can write total number of iteration as n-m+1.
• In each iteration we are performing m comparisons ie, 3, So the total num of comparison is
m(n-m+1)= mn-m^2+m ie, O(nm) Class.
5
2. Best Case: Ω(m) : Number of comparison will be m. (Here the
pattern matches with first m characters of the text)
Text: a b c d e f
Pattern: a b c

3. Average case : This efficiency should be considerably better than the

worst-case efficiency. It has been shown to be linear, i.e., Ɵ(n).

Amruthasree V M, Assistant Professor, NIE 6

 Exhaustive Search
• Exhaustive search is simply a brute-force approach to combinatorial
problems.
• That generate each and every element of the problem domain, selecting
those of them that satisfy all the constraints, and then finding a desired
element (e.g., the one that optimizes some objective function).
• Note that although the idea of exhaustive search is quite straightforward.
• Its implementation typically requires an algorithm for generating certain
combinatorial objects such as permutation, combination and subset of a
given set..

Amruthasree V M, Assistant Professor, NIE 7

Exhaustive Search - Travelling Salesman problem
• The traveling salesman problem (TSP) find the shortest tour through a given set of
n cities that visits each city exactly once before returning to the city where it started.
• The problem can be modeled by a weighted graph, with vertices representing the
cities and the edge weights specifying the distances.
• Then the problem can be stated as the problem of finding the shortest Hamiltonian
circuit of the graph. (A Hamiltonian circuit is defined as a cycle that passes through
all the vertices of the graph exactly once)
• Hamiltonian circuit can also be defined as a sequence of n + 1 adjacent vertices vi0,
vi1, . . . , vin−1, vi0, where the first vertex of the sequence is the same as the last one
and all the other n − 1 vertices are distinct.
• Solution to a TSP can be found by generating all the tours by generating
permutations of n − 1 intermediate cities and then compute the tour lengths, and find
the shortest among them. 8
 • There are two optimal solutions with length
of tour=10
• NOTE: Total number of permutation
needed=1/2(n-1)!
• Impractical for all but very small values of n.

Amruthasree V M, Assistant Professor, NIE 9

 Exhaustive Search - Knapsack Problem
• Given n items of known weights w1, w2, . . . , wn and values v1, v2, . . . , vn and a
knapsack of capacity W.
• The problem is to find the most valuable subset of the items that fit into the
knapsack.
• Example: Cargo transport plane that has to deliver the most valuable set of items to
a remote location without exceeding the plane’s capacity.
• Use exhaustive-search approach to this problem leads to generating all the subsets
of the set of n items given, computing the total weight of each subset in order to
identify feasible subsets (i.e., the ones with the total weight not exceeding the
knapsack capacity), and finding a subset of the largest value among them.
10
Amruthasree V M, Assistant Professor, NIE
Amruthasree V M, Assistant Professor, NIE 11
• The number of subsets of an n-element set is 2^n, the exhaustive search
leads to a Ω (2^n) algorithm, no matter how efficiently individual
subsets are generated.
• Both the traveling salesman and knapsack problems based on exhaustive
search are extremely inefficient on every input.
• These two problems are the best-known examples of NP-hard
problems(No polynomial time).
• Thus alternative approaches like backtracking and branch-and-bound can
be used to solve some instance of problem but not all.

Amruthasree V M, Assistant Professor, NIE 12

 DECREASE-AND-CONQUER
• The decrease-and-conquer technique is based on exploiting the relationship
between a solution to a given instance of a problem and a solution to its
smaller instance.
• Once such a relationship is established, it can be exploited either top down or
bottom up.
• Here we decrease the size of the problem instance to get the solution to the
actual problem.
• There are three major variations of decrease-and-conquer:
1. Decrease by a constant
2. Decrease by a constant factor
3. Variable size decrease: Here the size reduction pattern varies from one
iteration of an algorithm to another. Euclid’s algorithm for computing the
greatest common divisor provides a good example of such a situation. 13
1. Decrease by a constant :
• In the decrease-by-a-constant, the size of an
instance is reduced by the same constant on
each iteration of the algorithm. Typically, this
constant is equal to one.
• Consider, as an example, the exponentiation
problem of computing an where a != 0 and n
is a nonnegative integer.
• The relationship between a solution to an
instance of size n and an instance of size n−1
is obtained by the obvious formula
an = an-1 * a.

14
[Link] by a constant factor
• Here the size of the instance is reduced by the same constant
factor on each iteration of the algorithm. In most applications,
this constant factor is equal to two.
• For an example, Consider, an example, the exponentiation
problem of computing an. If the instance of size n is to compute
an, the instance of half its size is to compute an/2 with the
obvious relationship between the two:
an = (an/2)2.
• But since we consider here instances with integer exponents
only, the former does not work for odd n.
• If n is odd, we have to compute an -1 by using the rule for even-
valued exponents and then multiply the result by a.

15
2.4 Topological Sorting (Topological Ordering)
• Topological ordering of a directed acyclic graph(DAG) is a linear ordering
of all the nodes in the graph, such that there is an edge from node x to node
y, x should be placed before y.
• (Directed graph : It is a graph with directions specified for all its edges. The
adjacency matrix and adjacency lists are the two ways of representing a
digraph)
• Two methods to obtain topological ordering
1. DFS (Depth first search)
2. Vertex deletion method (Source removal method)

Amruthasree V M, Assistant Professor, NIE 16

• Consider a set of five required courses {C1, C2, C3, C4,
C5} a part-time student has to take in some degree
program. The courses can be taken in any order as long
as the following course prerequisites are met:
• C1 and C2 have no prerequisites, C3 requires C1 and
C2, C4 requires C3, and C5 requires C3 and C4. The Digraph representing the
student can take only one course per term. prerequisite structure of five
courses.
• In which order should the student take the courses?
• The situation can be modeled by a digraph in which vertices represent courses
and directed edges indicate prerequisite requirements (Figure).
• In terms of this digraph, the question is whether we can list its vertices in such
an order that for every edge in the graph, the vertex where the edge starts is
listed before the vertex where the edge ends. This problem is called
topological sorting.
Amruthasree V M, Assistant Professor, NIE 17
 1. DFS Method (depth-first search):
• Traverse the graph using depth-first search and note the order in which vertices
become dead-ends (i.e., popped off the traversal stack).
• Reversing the popping order yields a solution to the topological sorting problem.
• The algorithm work in such a way
that when a vertex v is popped off a
DFS stack, no vertex u with an edge
from u to v can be among the vertices
popped off before v. (Otherwise, (u,
v) would have been a back edge.)
Hence, any such vertex u will be
listed after v in the popped-off order
list, and before v in the reversed list.
Amruthasree V M, Assistant Professor, NIE 18
• Popping order: c d b a
b
• Topological order: a b d c
Procedure: a c
• Starting from any node, here starting at node 'a'.
• After visiting node 'a' push it onto the stack and then alphabetically visit the adjacent nodes of 'a' which haved
a direct edge from 'a'.
• ‘a’ is having outgoing edge to ‘b’ . ‘b’ is unvisited , visit ‘b’ and push into stack.
• ‘b’ is having outgoing edge to ‘d’. ‘d’ is unvisited, vsit the node ‘d’ and push into stack. c
d
• ‘d’ is having outgoing edge to ‘c’. ‘c’ is unvisited, visit the node ‘c’ and push into stack.
b
• ‘c’ is not having any outgoing edge . Then pop ‘c’ from the stack and add it into the popping order. Then a
backtrack into the previously visited node ie, ‘d’.
• There is no unvisited outgoing edge from ‘d’. Then pop ‘d’ from the stack and add it into the popping order.
• Then backtrack into the previously visited node ie, ‘b’.
• There is no unvisited outgoing edge from ‘b’. Then pop ‘b’ from the stack and add into popping order. Then
backtrack into the previously visited node ie, ‘a’.
• ‘a’ is not having any unvisited node , pop ‘a’ from the stack and add it into popping order.
• At last reverse the popping order will get the Topological order.
Amruthasree V M, Assistant Professor, NIE 19
 c
f
g
e
b
a
• Popping order: e f g b c a d
• Topological order: d a c b g f

Amruthasree V M, Assistant Professor, NIE 20

2. Vertex deletion method (Source removal method)
• Repeatedly, identify in a remaining digraph a source, which is a vertex with
no incoming edges, and delete it along with all the edges outgoing from it.
(If there are several sources, break the tie arbitrarily. If there are none, stop
because the problem cannot be solved)
• The order in which the vertices are deleted yields a solution to the
topological sorting problem.
• Note: Solution obtained by the source-removal algorithm is different from
the one obtained by the DFS-based algorithm. Both of them are correct, of
course; the topological sorting problem may have several alternative
solutions.

Amruthasree V M, Assistant Professor, NIE 21

Amruthasree V M, Assistant Professor, NIE 22
 DIVIDE AND CONQUER
• Divide-and-conquer is the best-known
algorithm design technique.
• This algorithms work according to the following
general plan:
1. A given problem of size n is divided into two
sub problems of size n/2 .
2. The sub problems of size n/2 is further divided
into two sub problems and so (typically
recursively)
3. This process continue until the problem can’t
be divided into further.
4. Then solutions to the sub problems are
combined to get a solution to the original
problem. 23
Amruthasree V M, Assistant Professor, NIE
• Recursive algorithms are solved by using recurrence relations.
T (n) = aT (n/b) + f (n)

Amruthasree V M, Assistant Professor, NIE 24

1. T (n) = 4T (n/2) + n2
for this example, a = 4, b = 2, and d = 2 (power of f(n)), bd =4; hence, since
a = b d,
Case 2: T(n) ∈ (n dlogn) = θ(n 2 logn)
2. T (n) = 4T (n/2) + n3
for this example, a = 4, b = 2, and d = 3 (power of f(n)), bd =8; hence, since
a < b d,
Case 3: T(n) ∈ (n d) = θ(n 3 )

***More Problems : refer your note book

Amruthasree V M, Assistant Professor, NIE 25

 2.5 Merge Sort
• Merge sort is an example of an
application of the divide-and conquer
technique.

• It sorts a given array A[0..n − 1] by

dividing it into two halves

A[0..n/2 − 1] and A[n/2..n − 1],

sorting each of them recursively, and
then merging the two smaller sorted
arrays into a single sorted one.
Amruthasree V M, Assistant Professor, NIE 26
Pseudo code:
ALGORITHM Mergesort(A[l……r],l,r)
//Sorts array A[0..n − 1] by recursive merge sort
//Input: An array A[0..n − 1] of orderable elements
//Output: Array A[0..n − 1] sorted in non decreasing order
if l<r
m=(l+r)/2
Mergesort(A,l,m)
Mergesort(A,m+1,r)
Merge(A,l,m,r)

Amruthasree V M, Assistant Professor, NIE 27

 Pseudo code:
The merging of two sorted arrays can be
ALGORITHM Merge(A,l,m,r)
done as follows.
//Merges two sorted arrays into one sorted array
• Two pointers (array indices) are
//Input: Two sorted arrays A[l…m] & A[m+1….r]
initialized to point to the first elements of
the arrays being merged. //Output: A single sorted array A[0…….r]
• The elements pointed to are compared, i ←l; j ←m+1; k←l
and the smaller of them is added to a while i <=m and j <=r do
new array being constructed; after that, if A[i]< A[j ]
the index of the smaller element is B[k++]←A[i++]
incremented to point to its immediate else
successor in the array it was copied from.
B[k++]←A[j++]
• This operation is repeated until one of
while i<=m
the two given arrays is exhausted, and
B[k++]←A[i++]
then the remaining elements of the other
while j<=r
array are copied to the end of the new
B[k++]←A[j++]
array.
Copy all elements of B to A 28
Amruthasree V M, Assistant Professor, NIE
Amruthasree V M, Assistant Professor, NIE 29
Time Complexity:
• Input size: n
• Basic Operation: Comparison
• Since it is recursive algorithm we have to come up with a recurrence relation
If n=1, need not do any comparisons so
C(1)=0
• Let C(n) denotes the number of comparison made
• Cmerge(n): It is a function which denotes the number of comparisons made to merge two
sorted array of size n/2.
• In the worst case, neither of the two arrays becomes empty before the other one contains
just one element (e.g., smaller elements may come from the alternating arrays). Therefore,
for the worst case, Cmerge(n) = n − 1, and we have the recurrence

• Apply masters theorem, a=2,b=2,d=1, b^d=2

so a= b^d (Case 2 of masters theorem)
• The number of comparisons made by this algorithm in the average case also is θ(n log n)
30
Amruthasree V M, Assistant Professor, NIE
 2.6 Quick Sort
• Quick sort is the sorting algorithm that is based on the divide-and conquer approach.
• Unlike merge sort, which divides its input elements according to their position in the array,
quick sort divides them according to their value.
• This use the idea of an array partition
• First we need to select a pivot element, it can be either the first or the last element in an
array. Next compare the pivot element with the remaining elements in an array.
• After doing some comparisons at the end of the partition, place pivot element in its actual
position in the sorted array. and we can continue sorting the two subarrays to the left and to
the right of A[P] independently
• A partition is an arrangement of the array’s elements so that all the elements to the left of
pivot are less than or equal to pivot element, and all the elements to the right of pivot are
greater than or equal to it:

31
Amruthasree V M, Assistant Professor, NIE
Pseudo code:
ALGORITHM Quicksort(A,l,r)
//Sorts a set of elements recursively using Quick sort
//Input: An array A indexed from l and r
//Output: A sorted array A
if l < r
s ←Partition(A,l,r) //s is a split position
Quicksort(A,l,s-1)
Quicksort(A,s+1,r)

Amruthasree V M, Assistant Professor, NIE 32

ALGORITHM Partition(A[l..r])
//Partitions a subarray by Hoare’s algorithm, using the first element as a pivot
//Input: Subarray of array A[0..n − 1], defined by its left and right indices l and r (l<r)
//Output: Partition of A[l..r], with the split position returned as this function’s value
pivot←A[l]
i ←l+1; j ←r
while True
while pivot>=A[i] and i<=r increment i
while pivot<A[j] decrement j
if(i<j)
swap(A[i], A[j ])
else
swap(A[l], A[j ]) //undo last swap when i ≥ j
return j Amruthasree V M, Assistant Professor, NIE 33
Amruthasree V M, Assistant Professor, NIE 34
Amruthasree V M, Assistant Professor, NIE 35
Amruthasree V M, Assistant Professor, NIE 36
Best case scenario of Quick sort
• If all the splits happen in the middle of corresponding sub arrays, we will
have the best case.
• The number of key comparisons in the best case satisfies the recurrence
Cbest(n) = 2Cbest(n/2) + n for n > 1, Cbest(1) = 0.
• Apply masters theorem, a=2,b=2,d=1,b^d=2
• Here, a= = b^d case 2 of masters theorem Cbest(n) ∈ θ(n log2 n);
• Cbest(n) = n log2 n

Amruthasree V M, Assistant Professor, NIE 37

Worst case scenario of Quick sort
• In the worst case, all the splits will be skewed to the extreme: one of the two sub
arrays will be empty, and the size of the other will be just 1 less than the size of the
sub array being partitioned.
• This unfortunate situation will happen, in particular, for increasing arrays, i.e., for
inputs for which the problem is already solved! Indeed, if A[0..n − 1] is a strictly
increasing array and we use A[0] as the pivot, the left-to-right scan will stop on A[1]
while the right-to-left scan will go all the way to reach A[0], indicating the split at
position 0:
• So, after making n + 1 comparisons to get to this partition and exchanging the pivot
A[0] with itself, the algorithm will be left with the strictly increasing array A[1..n −
1] to sort. This sorting of strictly increasing arrays of diminishing sizes will

Amruthasree V M, Assistant Professor, NIE 38

Amruthasree V M, Assistant Professor, NIE 39
Average case scenario of Quick sort

Amruthasree V M, Assistant Professor, NIE 40

 2.7 Strassen’s Matrix Multiplication.
• An algorithm was published by V. Strassen in 1969 [Str69]. The principal
insight of the algorithm lies in the discovery that we can find the product C
of two 2 × 2 matrices A and B with just seven multiplications as opposed to
the eight required by the brute-force algorithm.
• This multiplication is based on divide and conquer technique in which the
time complexity is reduced to n 2.81
• This is accomplished by using the following formulas:

41
Amruthasree V M, Assistant Professor, NIE
 • Thus, to multiply two 2 × 2
matrices, Strassen’s algorithm
makes seven multiplications
and 18 additions/subtractions,
whereas the brute-force
algorithm required eight
multiplications and four
additions.

Amruthasree V M, Assistant Professor, NIE 42

Time Complexity

Amruthasree V M, Assistant Professor, NIE 43