MODULE 2

EXHAUSTIVE SEARCH: A search process in which every item of a set is checked before a
decision is made about the presence or absence of a target item.
The brute force approach used to solve combinatorial problems is called exhaustive search. The
solutions to these problems consume more time.
The goal of the exhaustive search method is to search all possible solutions and obtain an optimal
solution.
Some of the problems that involve exhaustive search are-
 Traveling Salesman Problem
 Knapsack problem
 Assignment problem

TRAVELING SALESMAN PROBLEM (TSP):

The problem can be stated as the problem of finding the shortest Hamiltonian circuit of the graph. It is
easy to see that a 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. Further, we can assume, with no loss of generality that all circuits start and end at
one particular vertex. Thus, we can get all the tours by generating all the permutations of n – 1
intermediate cities, compute the tour lengths, and find the shortest among them.
Given n cities, a salesperson starts at a specified city (source), visit all n-1 cities only once and return
to the city from where he has started. The objective of this problem is to find a route through the cities
that minimizes the cost and by maximizing the profit.

Here, the cities are represented as a, b, c and d and the distance between various cities are represented
as numbers in each of the edge.
If we assume that the sales person starts from city a, the various routes using which he can visit each
and every city exactly once and returns back to the start city a along with the cost incurred for each
route are-

Route with minimum cost are:

abdca cost=11
acdba cost=11

Analysis: Let us find out the possible routes taken by the sales person by assuming he has
started from the city a. Let n denote the number of cities to visit.
 a b a b a b

c d c

Figure: a Figure: b Figure: c

When n=2: from a it is clear that, aba i.e. n=1 [(2-1)! = 1] (Here, n= number of routes)
When n=3: from b it is clear that, abca and acba i.e. n=2 [(3-1)! = 2]
When n=4: from c it is clear that, abcda
acbda
adbca
acdba
abdca
adcba i.e. n=6 [(4-1)! = 6]
In general, for n cities number of routes = (n-1)! I.e. f(n) = (n-1)!.
Therefore, time complexity is f(n)ϵO(n!)

NOTE: This method is very inefficient since the optimal solution is selected out of (n-1)! Possible
routes. So, TSP consumes too much time to find the optimal route.

KNAPSACK PROBLEM:
Given a knapsack (bag/container) of capacity M and n objects of weights w1, w2, w3….wn with profits
p1, p2, p3….pn. Let x1, x2, x3….xn be the fractions of the objects that are supposed to be added into the
knapsack.
The main objective is to place the objects into the knapsack so that maximum profit is obtained and
the weights of objects chosen should not exceed the capacity of knapsack.
The problem is stated as,

Example: Solve the following knapsack problem using brute – force method given, M =40, n=3, (w1,
w2, w3) = {20, 25, 10} represents weight of 3 objects and (p1, p2, p3) = {30, 40, 35} represents
profits of 3 objects.

Solution: The various feasible solutions for this problem are shown below-
Objects selected Total weight of objects Feasible or not Profit earned
selected feasible solution
{} 0 Feasible 0
{1} 20 Feasible 30
{2} 25 Feasible 40
{3} 10 Feasible 35
{1,2} 20+25=45 Not Feasible -
{1,3} 20+10=30 Feasible 65
{2,3} 25+10=35 Feasible 75
{1,2,3} 20+25+10=55 Not Feasible -

The combination of objects {1, 2} and {1, 2, 3} are not feasible because, the total weight of the
objects selected will exceed the capacity of the knapsack 40. A feasible solution is the one that
satisfies the given constraint.
Out of feasible solutions, we have to select the subset which leads to maximum profit which in this
case is 75 by selecting the objects {2, 3}.

Analysis: The total number of subsets obtained for 3 elements is 8. In general, given n objects, the
total number of subsets obtained will be 2n. Even in the best case and worst case, the total number of
subsets generated will be 2n.
Therefore the time complexity is f(n)ϵθ(2n).

NOTE: The exhaustive search for TSP problem and knapsack problems are extremely inefficient on
every input.

DECREASE- AND –CONQUER

It is a technique used to solve problems by reducing the size of the input data at each step of the
solution process.
This technique is used to solve the smaller version of the problem, and the solution to the smaller
problem can be used to find the solution to the original problem.
Examples: Problems that can be solved using the decrease and conquer technique include-
(1) Binary Search
(2) Finding the max/min element in an array
(3) Finding the closet pair of points in a set of points.
The main advantage of decrease and conquer is that it often leads to efficient algorithms, as the size of
the input size is reduced at each step, reducing the time and space complexity of the solution.
Implementation: This approach can be either implemented as top-down or bottom-up.
Top-down approach: It is the recursive implementation of the problem.
Bottom-up approach: It is usually implemented in iterative way, starting with a solution to the
smallest instance of the problem.
Three major variations of decrease and conquer are-
1. Decrease by a constant(one)
2. Decrease by a constant factor
3. Variable size decrease
Decrease by one: In this variation, the size of an instance is reduced by the same constant on each
iteration of the algorithm.
Example: Insertion sort, DFS, BFS, Topological sorting.

Advantages and Disadvantages:

Advantages:
1. Simplicity: Decrease-and-conquer is often simpler to implement compared to other techniques
like dynamic programming or divide-and-conquer.
2. Efficient Algorithms: The technique often leads to efficient algorithms as the size of the input
data is reduced at each step, reducing the time and space complexity of the solution.
3. Problem-Specific: The technique is well-suited for specific problems where it’s easier to solve a
smaller version of the problem.
Disadvantages:
1. Problem-Specific: The technique is not applicable to all problems and may not be suitable for
more complex problems.
2. Implementation Complexity: The technique can be more complex to implement when compared
to other techniques like divide-and-conquer, and may require more careful planning.

INSERTION SORT:
It is an application of the decrease by one technique used to sort an array A [0….n-1]. It is more
efficient to implement this algorithm using bottom-up i.e. iteratively.
Example:

Steps in insertion sort:

 We have to start with 2nd element of the array as 1st element in the array is assumed to be
sorted.
 Compare second element with the 1st element and check if the 2nd element is smaller, than
swap them.
 Move to the 3rd element and compare it with the 2nd element, then the 1st element and swap as
necessary to put it in the correct position among the first three elements.
 Continue this process, comparing each element with the ones before it and swapping as
needed to place it in the correct position among the sorted elements.
 Repeat until the entire array is sorted.

Analysis:
Basic Operation: The key comparison: A[j]>v
Summation Relation: The number of key comparisons in this algorithm obviously depends on the
nature of the input.
 In the worst case, A[j]>v is executed the largest number of times, i.e. for every j = i-
1…0. Therefore,

 In the best case, A[j]>v is executed only once on every iteration of the outer loop. It
happens if and only if A[i-1]<=A[i] for every i=1,….n-1, i.e. if the input array is already
sorted in non-decreasing order.

 It shows that on randomly ordered arrays, insertion sort makes an average half as many
comparisons as on decreasing arrays i.e.
TOPOLOGICAL SORTING:
The topological sort algorithm takes a directed graph and returns an array of the nodes where each
node appears before all the nodes it points to. The ordering of the nodes in the array is called a
topological ordering.
Directed graph/digraph: It is a graph with directions specified for all edges. The adjacency matrix and
adjacency lists are still two principal means of representing a digraph.

Example:

The topological ordering or sorting of the graph is A, B, C, D, E, F. That means to visit vertex B,
vertex A should be visited first. To visit vertex C, vertex A, B must be visited, and so on.

The following two conditions will be used for sorting an array using the topological method:

 The graph should be acyclic and directed.

 In a topological graph, the vertex should be a vertex with no incoming edges.

Directed acyclic graph: A directed acyclic graph is a directed graph with no directed cycles. That is,
it consists of vertices and edges, with each edge directed from one vertex to another, such that
following those directions will never form a closed loop.

Example: 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 [Link] student can take only one course per term. In which order should the student
take the courses?

Solution: The situation can be modelled by a digraph in which vertices represent courses and directed
edges indicates prerequisite requirements. 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.

Note: The problem cannot have a solution if a digraph has a directed cycle. Thus, for topological sorting
to be possible, a digraph in question must be a dag.

There are two efficient algorithms that both verify whether a digraph is a dag and if it is, produce an
ordering of vertices that solves the topological sorting problems.

First algorithm: It is a simple application of Depth First Search (DFS)

 Perform a DFS traversal and note the order in which vertices become dead ends.
 Reversing this order yields a solution to the topological sorting problem.
  If a back edge has been encountered, the digraph is not a dag, and topological sorting of its
vertices is impossible.

Example:

Second algorithm: It is called as Source removal algorithm.

 It is based on a direct implementation of the decrease (by one)-and-conquer technique.
 It identifies a vertex with no incoming edges, and delete it along with all the edges outgoing
from it.
 The order in which the vertices are deleted yields a solution to the topological sorting
problem.
Example: The application of this algorithm to the same digraph representing the 5 courses is shown in
the diagram.

DIVIDE AND CONQUER:

These algorithms work according to the following general plan:
 A problem is divided into several sub problems of the same type, ideally of about equal size.
 The sub problems are solved.
 If necessary, the solutions to the sub problems are combined to get a solution to the original
problem.
The divide and conquer technique is diagrammed in figure below,
The divide – and – conquer approach yields some of the most important and efficient algorithms in
computer science.

Running time analysis: Consider a problem’s instance of size n is divided into 2 instances of size
n/2. More generally, an instance of size n can be divided into b instances of size n/b, with a of them
needing to be solved.
Here, a and b are constants where, a>=1 and b>1.
Assuming that size n is a power of b (ab) to simplify our analysis, we get the following recurrence for
the running time T(n).
T(n) = aT(n/b) + f(n)  1
where, f(n) is a function that accounts for the time spent on dividing an instance of size n into
instances of size n/b and combining their solutions.
The recurrence 1 is called general divide and conquer recurrence.
The order of growth of its solution T(n) depends on the values of the constants a and b and the order
of growth of the function f(n).
Master Theorem: If f(n) ϵ ϴ(nd) where, d>=0 and by applying this on 1 (recurrence relation) we
get,

Example: The recurrence of the number of additions A(n) made by divide and conquer on input of
size n=2k is,

MERGE SORT: Merge sort is a perfect example of a successful 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
B [n/2….n-1], sorting each of them recursively and then merging the 2 smaller sorted arrays into a
single sorted one.

The merging of two sorted arrays can be done as follows-

 Two pointers are initialized to point to the first elements of the arrays being merged.
 The elements pointed to are compared, and the smaller of them is added to a new array
being constructed.
 After that, the index of the smaller element is incremented to point to its immediate
successor in the array it was copied from.
 This operation is repeated until one of the 2 given arrays is exhausted, and then the
remaining elements of the other array are copied to the end of the array.

The operation of the algorithm on the list 8, 3, 2, 9, 7, 1, 5, 4 is illustrated in the below example.
Example:

At each step, exactly one comparison is made, after which the total number of elements in the 2 arrays
still needing to be processed is reduced by 1.
In the worst case, neither of the two arrays become empty before the other one contains just one
element.
Therefore, for the worst case, Cmerge(n) = n − 1, and we have the recurrence,
Cworst(n) = 2Cworst(n/2) + n − 1 for n > 1, Cworst(1) = 0.
Hence, according to the Master Theorem, Cworst(n) ∈ ϴ (n log n).
For large n, the number of comparisons made by this algorithm in the average case turns out to be
about 0.25n.