Analysis & Design of Algorithms Module 3 BCS401

Transform-and-Conquer

This general technique work as two-stage procedures.

First, in the transformation stage, the problem’s instance is modified to be, for one reason or
another, more amenable to solution.

Then, in the second or conquering stage, it is solved.

It is, in fact, a group of techniques based on the idea of transformation to a problem that is
easier to solve.

There are three major variations of this idea that differ by what we transform a given instance to
(Figure):

 Transformation to a simpler or more convenient instance of the same problem—we call it

instance simplification. (Ex: List presorting, Gaussian elimination, and rotations in AVL
trees are good examples of this strategy.)
 Transformation to a different representation of the same instance—we call it
representation change. (Ex: representation of a set by a 2-3 tree, heaps and heapsort)
 Transformation to an instance of a different problem for which an algorithm is already
available—we call it problem reduction.

Dept. of AI & ML, KIT, Tiptur Page 1

Analysis & Design of Algorithms Module 3 BCS401

Balanced Search Trees

It is a binary tree whose nodes contain elements of a set of orderable items, one element per
node, so that all elements in the left subtree are smaller than the element in the subtree’s root,
and all the elements in the right subtree are greater than it.

AVL Trees

AVL trees were invented in 1962 by two Russian scientists, G. M. Adelson-Velsky and E. M.
Landis, after whom this data structure is named.

DEFINITION: An AVL tree is a binary search tree in which the balance factor of every node,
which is defined as the difference between the heights of the node’s left and right subtrees, is
either 0 or +1 or −1. (The height of the empty tree is defined as−1.)

For example, the binary search tree in Figure a is an AVL tree but the one in Figure b is not.

If an insertion of a new node makes an AVL tree unbalanced, we transform the tree by a
rotation. A rotation in an AVL tree is a local transformation of its subtree rooted at a node whose
balance has become either +2 or −2. If there are several such nodes, we rotate the tree rooted at
the unbalanced node that is the closest to the newly inserted leaf. There are only four types of
rotations; in fact, two of them are mirror images of the other two. In their simplest form, the four
rotations are shown in Figure below.

Dept. of AI & ML, KIT, Tiptur Page 2

Analysis & Design of Algorithms Module 3 BCS401

Dept. of AI & ML, KIT, Tiptur Page 3

Analysis & Design of Algorithms Module 3 BCS401

The first rotation type is called the single right rotation, or R-rotation: Note that this rotation is
performed after a new key is inserted into the left subtree of the left child of a tree whose root
had the balance of +1 before the insertion.

The symmetric single left rotation, or L-rotation, is the mirror image of the single R-rotation. It
is performed after a new key is inserted into the right subtree of the right child of a tree whose
root had the balance of −1 before the insertion.

The second rotation type is called the double left-right rotation (LR rotation). It is, in fact, a
combination of two rotations:

 we perform the L-rotation of the left subtree of root r followed by the R-rotation of the
new tree rooted at r.
 It is performed after a new key is inserted into the right subtree of the left child of a tree
whose root had the balance of +1 before the insertion.

The double right-left rotation (RL-rotation) is the mirror image of the double LR-rotation.

Dept. of AI & ML, KIT, Tiptur Page 4

Analysis & Design of Algorithms Module 3 BCS401

Construction of an AVL tree for the list 5, 6, 8, 3, 2, 4, 7

Dept. of AI & ML, KIT, Tiptur Page 5

Analysis & Design of Algorithms Module 3 BCS401

2-3 Trees

The second idea of balancing a search tree is to allow more than one key in the same node of
such a tree. The simplest implementation of this idea is 2-3 trees, introduced by the U.S.
computer scientist John Hopcroft in 1970.

A 2-3 tree is a tree that can have nodes of two kinds: 2-nodes and 3-nodes. A 2-node contains a
single key K and has two children: the left child serves as the root of a subtree whose keys are
less than K, and the right child serves as the root of a subtree whose keys are greater than K. (In
other words, a 2-node is the same kind of node we have in the classical binary search tree.)

A 3-node contains two ordered keys K1 and K2 (K1<K2) and has three children. The leftmost
child serves as the root of a subtree with keys less than K1, the middle child serves as the root of
a subtree with keys between K1 and K2, and the rightmost child serves as the root of a subtree
with keys greater than K2 (Figure).

The last requirement of the 2-3 tree is that all its leaves must be on the same level. In other
words, a 2-3 tree is always perfectly height-balanced: the length of a path from the root to a leaf
is the same for every leaf.

Searching for a given key K in a 2-3 tree is quite straightforward. We start at the root.

 If the root is a 2-node, we act as if it were a binary search tree: we either stop if K is
equal to the root’s key or continue the search in the left or right subtree if K is,
respectively, smaller or larger than the root’s key.
 If the root is a 3- node, we know after no more than two key comparisons whether the
search can be stopped (if K is equal to one of the root’s keys) or in which of the root’s
three subtrees it needs to be continued.

Inserting a new key in a 2-3 tree is done as follows.

First of all, we always insert a new key K in a leaf, except for the empty tree. The appropriate
leaf is found by performing a search for K. If the leaf in question is a 2-node, we insert K there
as either the first or the second key, depending on whether K is smaller or larger than the node’s
old key.

Dept. of AI & ML, KIT, Tiptur Page 6

Analysis & Design of Algorithms Module 3 BCS401

If the leaf is a 3-node, we split the leaf in two: the smallest of the three keys (two old ones and
the new key) is put in the first leaf, the largest key is put in the second leaf, and the middle key is
promoted to the old leaf’s parent. (If the leaf happens to be the tree’s root, a new root is created
to accept the middle key.) Note that promotion of a middle key to its parent can cause the
parent’s overflow (if it was a 3-node) and hence can lead to several node splits along the chain of
the leaf’s ancestors.

An example of a 2-3 tree construction is given in Figure below.

Dept. of AI & ML, KIT, Tiptur Page 7

Analysis & Design of Algorithms Module 3 BCS401

Heaps and Heapsort

DEFINITION 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 shape property—the binary tree is essentially complete (or simply complete), i.e., all
its levels are full except possibly the last level, where only some rightmost leaves may be
missing.
2. The parental dominance or heap property—the key in each node is greater than or equal
to the keys in its children.

For example, consider the trees of Figure.

 The first tree is a heap.

 The second one is not a heap, because the tree’s shape property is violated. And
 the third one is not a heap, because the parental dominance fails for the node with key
5.

Note that key values in a heap are ordered top down; i.e., a sequence of values on any path from
the root to a leaf is decreasing (nonincreasing, if equal keys are allowed).

However, there is no left-to-right order in key values; i.e., there is no relationship among key
values for nodes either on the same level of the tree or, more generally, in the left and right
subtrees of the same node.

Dept. of AI & ML, KIT, Tiptur Page 8

Analysis & Design of Algorithms Module 3 BCS401

Here is a list of important properties of heaps

Dept. of AI & ML, KIT, Tiptur Page 9

Analysis & Design of Algorithms Module 3 BCS401

Heap Construction:
There are two principal alternatives for doing this.

The first is the bottom-up heap construction algorithm illustrated in Figure below.

 It initializes the essentially complete binary tree with n nodes by placing keys in the order
given and then “heapifies” the tree as follows.
 Starting with the last parental node, the algorithm checks whether the parental
dominance holds for the key in this node. If it does not, the algorithm exchanges the
node’s key K with the larger key of its children and checks whether the parental
dominance holds for K in its new position.
 This process continues until the parental dominance for K is satisfied.
 After completing the “heapification” of the subtree rooted at the current parental node,
the algorithm proceeds to do the same for the node’s immediate predecessor.
 The algorithm stops after this is done for the root of the tree.

Dept. of AI & ML, KIT, Tiptur Page 10

Analysis & Design of Algorithms Module 3 BCS401

The alternative (and less efficient) algorithm constructs a heap by successive insertions of a
new key into a previously constructed heap; some people call it the top-down heap construction
algorithm.

So how can we insert a new key K into a heap? First, attach a new node with key K in it after the
last leaf of the existing heap. Then sift K up to its appropriate place in the new heap as follows.

Compare K with its parent’s key: if the latter is greater than or equal to K, stop (the structure is a
heap); otherwise, swap these two keys and compare K with its new parent. This swapping
continues until K is not greater than its last parent or it reaches the root (illustrated in Figure
below).

Dept. of AI & ML, KIT, Tiptur Page 11

Analysis & Design of Algorithms Module 3 BCS401

Heapsort

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.

Maximum Key Deletion from a heap

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 AI & ML, KIT, Tiptur Page 12

Analysis & Design of Algorithms Module 3 BCS401

Space and Time Trade-Offs

Space and time trade-offs in algorithm design are a well-known issue for both theoreticians and
practitioners of computing.

In somewhat more general terms, the idea is to preprocess the problem’s input, in whole or in
part, and store the additional information obtained to accelerate solving the problem
afterward.

We call this approach input enhancement and discuss the following algorithms based on it:

 counting methods for sorting

 Boyer-Moore algorithm for string matching and its simplified version suggested by
Horspool.

Sorting by Counting
 Applying the input-enhancement technique, we discuss its application to the sorting
problem. One rather obvious 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 (Figure
below).

Dept. of AI & ML, KIT, Tiptur Page 13

Analysis & Design of Algorithms Module 3 BCS401

Dept. of AI & ML, KIT, Tiptur Page 14

Analysis & Design of Algorithms Module 3 BCS401

Distribution Counting Sort:

The counting idea does work productively in a situation in which elements to be sorted belong to
a known small set of values.

More generally, if element values are integers between some lower bound l and upper bound u,
we can compute the frequency of each of those values and store them in array F[0..u − l].

Then the first F[0] positions in the sorted list must be filled with l, the next F[1] positions with l
+ 1, and so on.

All this can be done, of course, only if we can overwrite the given elements.

Let us consider a more realistic situation of sorting a list of items with some other information
associated with their keys so that we cannot overwrite the list’s elements.

Then we can copy elements into a new array S[0..n−1]to hold the sorted list as follows.

The elements of A whose values are equal to the lowest possible value l are copied into the first
F[0] elements of S, i.e., positions 0 through F[0]− 1; the elements of value l + 1 are copied to
positions from F[0] to (F[0]+ F[1]) − 1; and so on.

Since such accumulated sums of frequencies are called a distribution in statistics, the method
itself is known as distribution counting.

Dept. of AI & ML, KIT, Tiptur Page 15

Analysis & Design of Algorithms Module 3 BCS401

Dept. of AI & ML, KIT, Tiptur Page 16

Analysis & Design of Algorithms Module 3 BCS401

Input Enhancement in String Matching

The problem of string matching requires finding an occurrence of a given string of m characters
called the pattern in a longer string of n characters called the text.

Most of them exploit the input-enhancement idea: preprocess the pattern to get some information
about it, store this information in a table, and then use this information during an actual search
for the pattern in a given text. This is exactly the idea behind the two best known algorithms of
this type: the Knuth-Morris-Pratt algorithm and the Boyer-Moore algorithm.

The principal difference between these two algorithms lies in the way they compare characters of
a pattern with their counterparts in a text: the Knuth-Morris-Pratt algorithm does it left to right,
whereas the Boyer-Moore algorithm does it right to left.

Although the underlying idea of the Boyer-Moore algorithm is simple, its actual implementation
in a working method is less so. Therefore, we start our discussion with a simplified version of the
Boyer-Moore algorithm suggested by R. Horspool.

Dept. of AI & ML, KIT, Tiptur Page 17

Analysis & Design of Algorithms Module 3 BCS401

Dept. of AI & ML, KIT, Tiptur Page 18

Analysis & Design of Algorithms Module 3 BCS401

Dept. of AI & ML, KIT, Tiptur Page 19

Analysis & Design of Algorithms Module 3 BCS401

Dept. of AI & ML, KIT, Tiptur Page 20