MODULE-2
BRUTE FORCE
APPROACHES(conti…)
Exhaustive Search
• a brute-force approach to combinatorial problems.
• It suggests generating each and every element of the problem's
domain, selecting those of them that satisfy all the constraints, and
then finding a desired element.
• Examples for the Exhaustive Search
[Link] salesman problem
2. The knapsack problem
Traveling Salesman Problem
(TSP)
Problem Statement: 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.
• Modeled by a weighted graph, with the graph's vertices representing the cities
and the edge weights specifying the distances.
• 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
• A Hamiltonian circuit can also be defined as a sequence of 𝑛+1
the graph exactly once.
adjacent vertices 𝑣𝑖0,𝑣𝑖1,…,𝑣𝑖(𝑛−1),𝑣𝑖0 where the first vertex of
the sequence is the same as the last one, and all the other 𝑛−1
vertices are distinct.
Example problem
Knapsack Problem
• Given n items of known weights w1 , ... , Wn and values v1, ... , vn
and a knapsack of capacity W , find the most valuable subset of the
does not exceed 𝑊and the total value is
items that fit into the knapsack, such that the total weight
maximized.
• 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 to identify feasible subsets
Decrease-and-Conquer
• Technique is based on exploiting the relationship between a solution
to a given instance of a problem and a solution to a smaller instance
of the same problem.
• Once such a relationship is established, it can be exploited either top
down (recursively) or bottom up (without a recursion).
• There are three major variations of decrease-and-conquer
1. Decrease by a constant
2. Decrease by a constant factor
3. Variable size Decrease
Decrease by CONSTANT(ONE)
• The size of an instance is reduced by the same constant on each
iteration of the algorithm. Typically, this constant is equal to one
Ex: n! ,,Topological sorting
Decrease-by-a-constant-factor
• Technique suggests reducing a problem's instance by the same
constant factor on each iteration of the algorithm.
variable-size-decrease
• variety of decrease-and-conquer, a size reduction pattern varies from
one iteration of an algorithm to another.
ex: Euclid's algorithm for computing the greatest common divisor
INSERTION SORT
• we consider sorting an array 𝐴[0..𝑛−1] using the
decrease-by-one technique.
𝐴[0..𝑛−2] has already been solved, giving us a sorted
• We assume the smaller problem of sorting the array
array of size 𝑛−1: 𝐴[0]≤...≤𝐴[𝑛−2]
appropriate position for 𝐴[𝑛−1] in the sorted subarray
• To solve the original problem, we need to find the
and insert it there.
𝐴[𝑛−1] among the sorted elements and inserting it into
• This involves locating the correct insertion point for
its correct position.
To insert 𝐴[𝑛−1]] into its correct position in the sorted
subarray 𝐴[0..𝑛−2] ,we have three reasonable alternatives:
[Link]-to-Right Scan:
[Link]: Scan the sorted subarray from left to right.
[Link]: Start at the beginning of the sorted subarray and move
equal to 𝐴[𝑛−1]
rightward until you find the first element that is greater than or
[Link]: Insert 𝐴[𝑛−1] right before this element.
[Link]-to-Left Scan:
• Method: Scan the sorted subarray from right to left.
• Process: Start at the end of the sorted subarray and move
or equal to 𝐴[𝑛−1].
leftward until you find the first element that is smaller than
• Insertion: Insert 𝐴[𝑛−1] right after this element.
[Link] Search:
• Method: Use binary search to find the correct insertion
point.
subarray to find the position where 𝐴[𝑛−1] should be
• Process: Perform a binary search on the sorted
inserted.
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
for i <- 1 to n-1 do
v <- A[i]
j <- i-1
while j >= 0 and A[j] > v do
A[j + 1] <- A[j]
j <- j-1
A[j + 1] <- v
Topological Sorting
• . A directed graph( digraph) is a graph with directions specified for all
its edges
• There are only two notable differences between undirected and
directed graphs in representing them:
(1) the adjacency matrix of a directed graph does not have to be
symmetric
(2) An edge in a directed graph has just one corresponding nodes in
the digraph's adjacency lists.
• Topological sorting(ordering) for Directed Acyclic Graph (DAG) G = (V,
E), is a linear ordering of vertices such that for every directed
edge( u ,v), vertex u comes before v in the ordering.
• Topological sorting(ordering) can be done by using 2 algorithms
1. DFS traversal
2. Source removal method
Topological ordering by DFS
traversal
• perform a DFS traversal and note the order in which vertices become
dead ends (i.e., are popped off the traversal stack). Reversing this
order yields a solution to the topological sorting problem
Source removal method
• The second algorithm is based on a direct implementation of the
decrease (by one )-and-conquer technique
1. Repeatedly ,Identify in a digraph a source, which is a vertex with no
incoming edges
2. delete it along with all the edges outgoing from it.
3. The order in which the vertices are deleted yields a solution to the
topological sorting problem.
Binary Tree Traversals and
Related Properties
• A binary tree T is defined as a finite set of nodes that is either empty
or consists of a root and two disjoint binary trees TL and TR
called,respectively,the left and right subtree of the root.
Height of a binary tree.
• The height is defined as the length of the longest path from the root
to a leaf.
• it can be computed as the maximum of the heights of the root's left
and right subtrees plus 1.
• the height of the empty tree as -1.
ALGORITHM Height(T)
// Computes recursively the height of a binary tree
// Input: A binary tree T
// Output: The height of T
if T = ø
return -1
else
return max(Height(TL), Height(TR)) + 1
• We measure the problem's instance size by the number of nodes n(T) in a
given binary tree T.
𝐴(0)=0
A(n(T))=A(n(TL))+A(n(TR))+1 form (T)>0
• 𝐴(𝑛(𝑇))- is the number of additions made by the algorithm
Where:
for a binary tree 𝑇.
• 𝑇𝐿and 𝑇𝑅are the left and right subtrees of 𝑇, respectively.
• 𝑛(𝑇) is the number of nodes in tree 𝑇.
• The analysis of tree algorithms to draw the tree's extension by
replacing the empty subtrees by special nodes.
• The extra nodes ( little squares ) are called External.
• The original nodes (little circles) are called Internal.
• it is easy to hypothesize that the number of external nodes x is always
one more than the number of internal nodes
X=n+1
• The total number of nodes, both internal and external. Since every
node, except the root, is one of the two children of an internal node,
we have the equation
2n + 1=x +n
• n and x denote the numbers of parental nodes and leaves,
respectively.
• Returning to algorithm Height, the number of comparisons to check
whether the tree is empty is
C(n)=n+x=2n+1
• while the number of additions is
A(n) = n
Multiplication of Large Integers
• The conventional pen-and-pencil algorithm for multiplying two n-digit
integers
• Each digit of the first number (there are n such digits) is multiplied by
each digit of the second number (again, n digits).
• Therefore, the total number of digit multiplications is n×n=N^2 TIMES
Divide-and-Conquer Concept
• Given two n-digit integers a and b where n is a positive even number.
• divide both numbers in the middle(the divide-and-conquer technique)
• We denote the
first half of the a’s digits by a1 and the second half by a0
for b, the notations are b1 and b0,
C
ALGORITHM
MatrixMultiplication(A[0..n−1,
0..n−1], B[0..n−1, 0..n−1])
// Multiplies two square matrices of order n using the definition-based method
//input: two n x n matrices A & B
//output : Matric C=AB
for i ← 0 to n − 1 do
for j ← 0 to n − 1 do
C[i, j] ← 0.0
for k ← 0 to n − 1 do
C[i, j] ← C[i, j] + (A[i, k] * B[k, j])
return C
M(n)=O(n³)
Strassen’s Matrix Multiplication