MODULE-2 Analysis and Design of Algorithms (BCS401-22 SCHEME)

BRUTE FORCE APPROACHES (contd...): Exhaustive Search (Travelling Salesman problem and Knapsack Problem).
DECREASE-AND-CONQUER: Insertion Sort, Topological Sorting.
DIVIDE AND CONQUER: Merge Sort, Quick Sort, Binary Tree Traversals, Multiplication of Large Integers and Strassen’s Matrix
Multiplication.
Chapter 3(Section 3.4), Chapter 4 (Sections 4.1, 4.2), Chapter 5 (Section 5.1, 5.2, 5.3, 5.4)
2.1. Brute Force Approaches
2.1.1. Exhaustive Search
[Link]. Travelling Salesman Problem
 Hamiltonian circuit
 Hamiltonian circuit is defined as a cycle that passes through all the vertices of the graph exactly
once.
 TSP
 Hamiltonian circuit can also be defined as a sequence of n + 1 adjacent vertices vi0, vi1… vin-1, vi0.
 The first vertex of the sequence is the same as the last one and all the other n - 1 vertices are
distinct.
 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.

 Consider two intermediate vertices, say and c, and then only permutations in which b precedes c.
(This trick implicitly defines a tour’s direction.).
 An inspection of above figure reveals three pairs of tours that differ only by their direction. Hence,
we could cut the number of vertex permutations by half because cycle total lengths in both
directions are same.
 The total number of permutations needed is still 1/2(n - 1)!, which makes the exhaustive- search
approach impractical for large n. It is useful for very small values of n.
[Link]. Knapsack Problem
 Given n items of known weight w1, w2 … wn and values v1, v2 … vn, and a knapsack of capacity
W, find the most valuable subset of the items that fit into the knapsack.
 The 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 and
finding a subset of the largest value among them.
 The number of subsets of an n-element set is 2n.
 The time complexity of this algorithm is Ω(2n)

[Link] Page 1
 MODULE-2 Analysis and Design of Algorithms (BCS401-22 SCHEME)

2.2. 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.
It can be exploited either top down or bottom up.
The bottom-up variation is usually implemented iteratively, starting with a solution to the
smallest instance of the problem; it is called sometimes the incremental approach.
There are three major variations of decrease-and-conquer:
 decrease by a constant
 decrease by a constant factor
 variable size decrease
Decrease by a Constant
 The size of an instance is reduced by the same constant on each iterations of the algorithm.

[Link] Page 2
 MODULE-2 Analysis and Design of Algorithms (BCS401-22 SCHEME)

 Example:

The exponentiation problem of computing an (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 formula an = an-1. a. So the function f (n) = an using its recursive definition can be computed
either “top down” by using its recursive definition.

Decrease by a Constant factor

 Reducing a problem instance by the same constant factor on each iteration of the algorithm.
 Example:
 Let the exponentiation problem.
 The input size is n then compute an.
 The instance of half its size is to compute an/2.
 Then the relationship between the two: an = (an/2)2.
 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.
 The recursive formula is

 Then the algorithm efficiency is Θ(log n).

[Link] Page 3
 MODULE-2 Analysis and Design of Algorithms (BCS401-22 SCHEME)

variable size decrease

 The size-reduction pattern varies from one iteration of an algorithm to another.
 Example:
 Euclid’s algorithm for computing the greatest common divisor (GCD)
 gcd(m, n) = gcd(n, m mod n).
 The value of the second argument is always smaller on the right-hand side.
 Than on the left-hand side, it decreases neither by a constant nor by a constant factor.

2.2.1. Insertion Sort

 It is based on recursive idea.
 It is more efficient to implement this algorithm bottom up, i.e., iteratively.
 Starting with A[1] and ending with A[n - 1],A[i] is inserted in its appropriate place among the first i elements of
the array that have been already sorted.
 Example:

 Algorithm:
ALGORITHM InsertionSort(A[0..n - 1])
//Sorts a given array by insertion sort
//Input: An array A[0..n - 1] of n orderable elements
//Output: Array A[0..n - 1] sorted in nondecreasing order

[Link] Page 4
 MODULE-2 Analysis and Design of Algorithms (BCS401-22 SCHEME)

for i ←1 to n - 1 do
v ←A[i]
j ←i - 1
while j = 0 and A[j ] >vdo
A[j + 1] ←A[j ]
j ←j - 1
A[j + 1] ←v
 Algorithm Analysis:
 The input size is n.
 The basic operation is the key comparison A[j ] >v.
 The number of key comparisons is depends on the nature of the input.
 Worst case:
 The basic comparison operation takes a largest time.

 Best Case:
 The comparison 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 nondecreasing order.

 Average Case:
 It is based on investigating the number of element pairs that are out of order.
 It shows that on randomly ordered arrays, insertion sort makes on average half as many
comparisons as on decreasing arrays, i.e.,

2.2.2. Topological Sorting:

A linear ordering of vertices in a directed acyclic graph (DAG) called topological sort.
 Directed graph:
 A directed graph consists of a set of vertices (nodes) and a set of directed edges (arcs) that connect
them.
 Digraph is a short form of directed graph.
 Representation of graph
 Adjacency matrix and adjacency lists
 Differences between undirected and directed graphs
 The adjacency matrix of a directed graph does not have to be symmetric.
 An edge in a directed graph has just one (not two) corresponding nodes in the digraph’s adjacency
lists.
 Tree Traversals
 Depth-first search (DFS) and breadth-first search (BFS)
 DFS forest of a directed graph:
 The following figures exhibits all four types of edges possible in a DFS forest of a directed graph:

[Link] Page 5
 MODULE-2 Analysis and Design of Algorithms (BCS401-22 SCHEME)

o tree edges:
 ab, bc, de
o back edges:
 (ba) from vertices to their ancestors.
 A back edge in a DFS forest of a directed graph can connect a vertex to
its parent. Whether or not it is the case, the presence of a back edge
indicates that the digraph has a directed cycle.
o forward edges:
 (ac) from vertices to their descendants in the tree other than their
children.
o cross edges:
 (dc), which are none of the aforementioned types.
o Directed cycle:
 A sequence of three or more of its vertices that starts and ends with the
same vertex.
 Topological Sort:
 There are two types of topological sort are DFS method and Resource removal method.
 Topological Sort : DFS Algorithm
Here’s a step-by-step algorithm for topological sorting using Depth First Search (DFS):
o Create a graph with n vertices and m-directed edges.
o Initialize a stack and a visited array of size n.
o For each unvisited vertex in the graph, do the following:
 Call the DFS function with the vertex as the parameter.
 In the DFS function, mark the vertex as visited and recursively call the
DFS function for all unvisited neighbors of the vertex.
 Once all the neighbors have been visited, push the vertex onto the
stack.
 After all, vertices have been visited, pop elements from the stack and append them to the
 Output list until the stack is empty.
 The resulting list is the topologically sorted order of the graph.

[Link] Page 6
 MODULE-2 Analysis and Design of Algorithms (BCS401-22 SCHEME)

 Topological Sort: Source Removal Methods

 This is a direct implementation of the decrease and conquers method.
 From a given graph find a vertex with no incoming edges. Delete it along with all the
edges outgoing from it. If there is more than one such vertex then break the tie randomly.
 Note the vertices that are deleted.
 All these recorded vertices give a topologically sorted list.

2.3. Divide and Conquer

2.3.1. Working principle of Divide and conquer
 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.
 Divide and conquer technique as shown in the diagram.

 Example:
o Consider the sum of n numbers (a0… an-1). If n>1,
o Divide the problem into two instances of the same problem.
o To compute the sum of the first numbers remaining numbers. (if n = 1, return a0 as
the answer).

[Link] Page 7
 MODULE-2 Analysis and Design of Algorithms (BCS401-22 SCHEME)

o Once each of these two sums is computed by applying the same method recursively, we can add their
values to get the sum in question:

 Master Theorem
 If f(n) ∈Θ(nd) where d ≥ 0 in recurrence T (n) = aT (n/b) + f (n), then

Analogous results hold for the O and Ω notations, too.

[Link] Page 8