Module 1- Analysis & Design of Algorithms (BCS401)
CHAPTER 3: BRUTE FORCE APPROACHES
Chapter 3:
Transform and Conquer Technique
The Transform and conquer technique is a way of solving problems by breaking them down into smaller
subproblems, solving the smaller subproblems, and then combining the solutions to the subproblems to
solve the original problem. This technique can be used to solve problems in many different areas,
including mathematics, computer science, and engineering. This technique is often used when the original
problem is too difficult to solve directly, or when it is easier to solve the smaller sub-problems.
Heap and Heap Sort Algorithm
A heap can be defined as a binary tree with keys assigned to its nodes (one key per node) provided
the following two conditions are met:
1. The tree’s shape requirement—The binary tree is essentially complete (or simply complete), that is,
all its levels are full except possibly the last level, where only some rightmost leaves may be missing.
2. The parental dominance requirement—The key at each node is greater than or equal to the keys at
its children. (This condition is considered automatically satisfied for all leaves.)
Here is a list of important properties of heaps
1. There exists exactly one essentially complete binary tree with n nodes. Its height is equal to [log2 n] .
2. The root of a heap always contains its largest element.
3. A node of a heap considered with all its descendants is also a heap.
4. A heap can be implemented as an array by recording its elements in the topdown, left-to-right fashion. It
is convenient to store the heap’s elements in positions 1 though n of such an array, leaving H[0] either
unused or putting there a sentinel whose value is greater than every element in the heap. In such a
representation,
Dept. of AIML, GMIT, Davangere
Module 1- Analysis & Design of Algorithms (BCS401)
a. the parental node keys will be in the first [n/2] positions of the array, while the leaf keys will
occupy the last [n/2] positions.
b. the children of a key in the array’s parental position i (1≤ i ≤ [n/2]) will be in positions 2i and 2i
+ 1, and, correspondingly, the parent of a key in position i (2 ≤ i ≤ n) will be in position [i/2] .
How can we construct a heap for a given list of keys?
There are two principal alternatives for doing that. The first is the so-called bottom-up heap construction
algorithm. It initializes the essentially complete binary tree with n nodes by placing keys in the order given
and then “heapifies” the tree.
Dept. of AIML, GMIT, Davangere
Module 1- Analysis & Design of Algorithms (BCS401)
How can we delete an item from a heap?
We consider the most important case of deleting the root’s key, So deleting the root’s key from a heap can
be done with the following algorithm (illustrated in Figure 6.13).
Step 1 Exchange the root’s key with the last key K of the heap.
Step 2 Decrease the heap’s size by 1.
Step 3 “Heapify” the smaller tree by sifting K down the tree exactly in the same way we did it in the bottom-
up heap construction algorithm.That is, verify the parental dominance for K: if it holds, we are done; if not,
swap K with the larger of its children and repeat this operation until the parental dominance condition holds
for K in its new position.
Dept. of AIML, GMIT, Davangere
Module 1- Analysis & Design of Algorithms (BCS401)
Heap sort Algorithm
Q. Write the Heap sort Algorithm
Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to
the selection sort where we first find the minimum element and place the minimum element at the
beginning. Repeat the same process for the remaining elements.
This is a two-stage algorithm that works as follows.
Stage 1 (heap construction): Construct a heap for a given array.
Stage 2 (maximum deletions): Apply the root-deletion operation n − 1 times to the remaining heap.
First convert the array into heap data structure using heapify, then one by one delete the root node of the
Max-heap and replace it with the last node in the heap and then heapify the root of the heap. Repeat this
process until size of heap is greater than 1.
Build a heap from the given input array.
Repeat the following steps until the heap contains only one element:
Swap the root element of the heap (which is the largest element) with the last element of
the heap.
Remove the last element of the heap (which is now in the correct position).
Heapify the remaining elements of the heap.
The sorted array is obtained by reversing the order of the elements in the input array.
Dept. of AIML, GMIT, Davangere
Module 1- Analysis & Design of Algorithms (BCS401)
Problems on heap sort
Dept. of AIML, GMIT, Davangere
Module 1- Analysis & Design of Algorithms (BCS401)
Dept. of AIML, GMIT, Davangere
Module 1- Analysis & Design of Algorithms (BCS401)
Dept. of AIML, GMIT, Davangere
Module 1- Analysis & Design of Algorithms (BCS401)
Dept. of AIML, GMIT, Davangere
Module 1- Analysis & Design of Algorithms (BCS401)
Dept. of AIML, GMIT, Davangere
Module 1- Analysis & Design of Algorithms (BCS401)
Dept. of AIML, GMIT, Davangere
Module 1- Analysis & Design of Algorithms (BCS401)
Dept. of AIML, GMIT, Davangere
Module 1- Analysis & Design of Algorithms (BCS401)
SPACE-TIME TRADEOFFS:
A tradeoff is a situation where one thing increases and another thing decreases. It is a way to solve a
problem in:
Either in less time and by using more space, or
In very little space by spending a long amount of time.
The best Algorithm is that which helps to solve a problem that requires less space in memory and also
takes less time to generate the output. But in general, it is not always possible to achieve both of these
conditions at the same time. The most common condition is an algorithm using a lookup table. This means
that the answers to some questions for every possible value can be written down. One way of solving this
problem is to write down the entire lookup table, which will let you find answers very quickly but will
use a lot of space. Another way is to calculate the answers without writing down anything, which uses
very little space, but might take a long time. Therefore, the more time-efficient algorithms you have, that
would be less space-efficient.
Dept. of AIML, GMIT, Davangere
Module 1- Analysis & Design of Algorithms (BCS401)
Input enhancement Approach
The idea of this approach is to preprocess the problem's input, in whole or in part, and store the additional
information obtained to accelerate solving the problem afterward. Following algorithms are based on this
approach.
Counting methods for sorting (Section 7.1)
Boyer-Moore algorithm for string matching and its simplified version suggested by Horspool
Sorting by Counting:
Q. Write the algorithm for Sorting by counting method
As a first example of applying the input enhancement technique, we discuss its application to the sorting
problem. One idea is to count, for each element of a list to be sorted, the total number of elements smaller
than this element and record the results in a table. These numbers will indicate the positions of the
elements in the sorted list: e.g., if the count is 10 for some element, it should be in the 11th position (with
index 10, if we start counting with 0) in the sorted array. Thus, we will be able to sort the list by simply
copying its elements to their appropriate positions in a new, sorted list. This algorithm is called
comparison counting sort.
Example of sorting by comparison counting
Dept. of AIML, GMIT, Davangere
Module 1- Analysis & Design of Algorithms (BCS401)
The time efficiency of this algorithm
It should be quadratic because the algorithm considers all the different pairs of an n-element array. More
formally, the number of times its basic operation, the comparison A[i] < A[j], is executed is equal to the
sum we have encountered several times already:
Dept. of AIML, GMIT, Davangere
