TRANSFORM-AND-CONQUER
Module 3- Chapt 1
Mrs. Madhu Nagaraj
Assistant Professor
Dept of CSE-Data Science
ATMECE
It is a two-stage procedure:
1. Transformation - The problem’s instance is modified to be more
suitable to solution.
2. Conquering - It is solved
There are three major variations of this. They are:
Transformation to a simpler or more convenient instance of the same
problem— instance simplification.
Transformation to a different representation of the same instance—
representation change.
Transformation to an instance of a different problem for which an
algorithm is already available— problem reduction
Many algorithmic problems are easier to solve if their input is sorted.
Heaps and Heapsort
Definition A heap is a binary tree with keys at its nodes (one key per node) such
that:
• It is essentially complete, i.e., all its levels are full except possibly the last level,
where only some rightmost keys may be missing
• The key at each node is ≥ all keys in its children (and descendents)
Illustration of the heap’s definition
10 10 10
5 7 5 7 5 7
4 2 1 2 1 6 2 1
a heap not a heap not a heap
Note: Heap’s elements are ordered top down (along any path
down from its root), but they are not ordered left to right
Some Important Properties of a Heap
Given n, there exists exactly one unique binary tree (structure) with n nodes
that is essentially complete, with h = log2 n
The root contains the largest key
Every subtree rooted at every node of a heap is also a heap
A heap can easily be represented as an array (and usually is). By recording
its element in the top down approach.
Heap’s Array Representation
Store heap’s elements in an array (whose elements indexed, for convenience, 1 to n) in top-
down left-to-right order
Example:
9
1 2 3 4 5 6
5 3 9 5 3 1 4 2
1 4 2
Left child of node j is at 2j
Right child of node j is at 2j+1
Parent of node j is at j/2
Parental (ie interior) nodes are in the first n/2 locations
Heap Construction (bottom-up)
Step 1: Initialize structure (ie array) with keys in order given
Step 2: Starting with the last (rightmost) parental (ie interior) node, fix the heap rooted at it, if
it doesn’t satisfy the heap condition: keep exchanging it with its largest child until the
heap condition holds
Step 3: Repeat Step 1 for the preceding parental node
Bottom up: Adding nodes to heap from bottom to top, pushing elements up, as needed
Step 2 called Heapify:
Example of Heap Construction [Bottom Up]
Construct a heap for the list 2, 9, 7, 6, 5, 8 . Insert elements into the array. Process interior nodes R to L.
Why? Before and after each step? Heapify all the way down at each step. Bottom up?
2 2 2
9 7 > 9 8 9 8
6 5 8 6 5 7 6 5 7
2 9 9
9 8 > 2 8 > 6 8
6 5 7 6 5 7 2 5 7
Worst case? Number of comparisons for a node??
Pseudocode of bottom-up heap construction
Insert a New Element into a Heap
Basic operation in building heap in Top Down order
Insert the new element at last position in heap (size++)
Compare new element with its parent and, if it violates heap condition, exchange
them
Continue comparing the new element with nodes up the tree until the heap
condition is satisfied
Example: Insert key 10 into heap of size 6
9 9 10
6 8 > 6 10 > 6 9
2 5 7 10 2 5 7 8 2 5 7 8
What order is this? Efficiency: O(log n)
Heapsort
Stage 1: Construct a heap for a given list of n keys- Heap Construction
Max Heap - Descending order
Min Heap - Ascending order
Stage 2: Repeat operation of root removal n-1 times:
– Exchange keys in the root and in the last (rightmost) leaf
– Decrease heap size by 1
– If necessary, repeatedly swap new root (node) with larger child
until the heap condition again holds
Example of Sorting by Heapsort
Sort the list 2, 9, 7, 6, 5, 8 by heapsort
Analysis of Heapsort
Stage 1: Build heap for a given list of n keys (of height h)
worst-case h-1
C(n) = 2(h-i) 2i = 2 ( n – log2(n + 1)) (n)
i=0
# nodes at level i
Stage 2: Repeat operation of root removal n-1 times (fix heap)
worst-case
C(n) = n-1
2log2 i (nlogn)
i=1
Both worst-case and average-case efficiency: (nlogn)
In-place: yes
Balanced Search Trees
Attractiveness of binary search tree is marred by the bad /worst-case efficiency. Two ideas to
overcome it (i.e keep BST close to balanced) are:
to restructure BST to maintain balance, beacause an insertion makes the tree “too
unbalanced”
• AVL trees
• red-black trees
to allow more than one key per node of a search tree
• 2-3 trees
• 2-3-4 trees
Balanced trees: AVL trees
Definition : An AVL tree is a binary search tree in which, for every node, the difference
between the heights of its left and right subtrees, called the balance factor, is at most 1
(with the height of an empty tree defined as -1)
Tree (a) is an AVL tree; tree (b) is not an AVL tree
Rotations
If a key insertion violates the balance requirement at some node, the subtree rooted at that
node is transformed via one of the four rotations. (The rotation is always performed for a
subtree rooted at an “unbalanced” node closest to the new leaf.)
Single R-rotation Double LR-rotation
Construct an AVL tree for the list 5, 6, 8, 3, 2, 4, 7
AVL tree construction - an example [SKIP]
Construct an AVL tree for the list 5, 6, 8, 3, 2, 4, 7
AVL tree construction - example (cont.)
Analysis of AVL trees
average height: O(log n) (found empirically)
Search and insertion are O(log n)
Deletion is more complicated but is also O(log n)
Disadvantages:
• frequent rotations
• complexity
A similar idea: red-black trees (height of subtrees is allowed to differ by up to a factor
of 2)
2-3 Tree
Definition A 2-3 tree is a search tree that
may have 2-nodes and 3-nodes. 2 children, 1data element.
3 children, 2 data element
2-node 3-node
K K1, K2
<K >K < K1 (K1 , K 2 ) > K2
A 2-3 tree is constructed by successive insertions of keys given, with a new key always inserted
into a leaf of the tree. If the leaf is a 3-node, it’s split into two with the middle key promoted to
the parent. Splitting can be repeated up the tree, as needed.
2-3 Tree
Properties of 2-3 Trees
•Dats is in sorted manner
•It is a Balanced Tree
•All leaf at same level
•Each node can be a leaf, 2 node or 3 node.
•Always insertion done at leaf node.
2-3 tree construction – an example
Construct a 2-3 tree the list 9, 5, 8, 3, 2, 4, 7
8 8
>
9 5, 9 5, 8, 9 5 9 3, 5 9
8 3, 8 3, 8
>
2, 3, 5 9 2 5 9 2 4, 5 9
3, 8 > 3, 5, 8 >
3 8
2 4, 5, 7 9 2 4 7 9 2 4 7 9
LEAVES?
Analysis of 2-3 trees
Consider:
• Shortest tree with 8 nodes (add 1,4,10 to [3,8/2-5-9])
• Tallest tree with 7 nodes
Search, insertion, and deletion are in (log n)
The idea of 2-3 tree can be generalized by allowing more keys per node
• 2-3-4 trees
• B-trees
SPACE-TIME TRADEOFFS
Module 3- Chapt 3
Mrs. Madhu Nagaraj
Assistant Professor
Dept of CSE-Data Science
ATMECE
Space-for-time tradeoffs
Two varieties of space-for-time algorithms:
input enhancement — preprocess the input (or its part) to store some
info to be used later in solving the problem
• Comparision counting sorts
• string searching algorithms
prestructuring — preprocess the input to make accessing its elements
easier
• hashing
• indexing schemes (e.g., B-trees)
COMPARION COUNTING SORT
A sorting algorithm that stores, for each sortkey, the number of keys
less than the given key.
If Nj denotes the number of keys less than the jth key then (assuming
that keys are unique) the jth record should be in position Nj + 1 in a
file sorted into ascending order of the keys.
ALGORITHM ComparisonCountingSort(A[0..n − 1])
//Sorts an array by comparison counting
//Input: An array A[0..n − 1] of orderable elements
//Output: Array S[0..n − 1] of A’s elements sorted in nondecreasing order
for i ← 0 to n − 1 do Count[i]← 0
for i ← 0 to n − 2 do
for j ← i + 1 to n − 1 do
if A[i] < A[j ]
Count[j ]← Count[j ] + 1
else Count[i]← Count[i] + 1
for i ← 0 to n − 1 do S[Count[i]]← A[i]
return S
Review: String searching by brute force
pattern: a string of m characters to search for
text: a (long) string of n characters to search in
Brute force algorithm
Step 1 Align pattern at beginning of text
Step 2 Moving from left to right, compare each character of
pattern to the corresponding character in text until either all
characters are found to match (successful search) or a mismatch
is detected
Step 3 While a mismatch is detected and the text is not yet exhausted,
realign pattern one position to the right and repeat Step 2
String searching by preprocessing
Several string searching algorithms are based on the input enhancement idea of
preprocessing the pattern
Knuth-Morris-Pratt (KMP) algorithm preprocesses pattern left to right to get useful
information for later searching
Boyer -Moore algorithm preprocesses pattern right to left and store information into
two tables
Horspool’s algorithm simplifies the Boyer-Moore algorithm by using just one table
Horspool’s Algorithm
A simplified version of Boyer-Moore algorithm:
• preprocesses pattern to generate a shift table that determines how
much to shift the pattern when a mismatch occurs
• always makes a shift based on the text’s character c aligned with
the last character in the pattern according to the shift table’s entry
for c
How far to shift?
Look at first (rightmost) character in text that was compared:
The character is not in the pattern
.....c...................... (c not in pattern)
BAOBAB
The character is in the pattern (but not the rightmost)
.....O...................... (O occurs once in pattern)
BAOBAB
.....A...................... (A occurs twice in pattern)
BAOBAB
The rightmost characters do match
.....B......................
BAOBAB
Shift table
Shift sizes can be precomputed by the formula
distance from c’s rightmost occurrence in pattern
among its first m-1 characters to its right end
t(c) = pattern’s length m, otherwise by scanning pattern before search
begins and stored in a table called shift table
Shift table is indexed by text and pattern alphabet
Eg, for BAOBAB:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
1 2 6 6 6 6 6 6 6 6 6 6 6 6 3 6 6 6 6 6 6 6 6 6 6 6
ALGORITHM ShiftTable(P[0..m − 1])
//Fills the shift table used by Horspool’s and Boyer-Moore algorithms
//Input: Pattern P[0..m − 1] and an alphabet of possible characters
//Output: Table[0..size − 1] indexed by the alphabet’s characters and
// filled with shift sizes computed by formula (7.1)
for i ← 0 to size − 1 do Table[i]← m
for j ← 0 to m − 2 do Table[P[j ]]← m − 1 − j
return Table
Example of Horspool’s alg. application
_
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
1 2 6 6 6 6 6 6 6 6 6 6 6 6 3 6 6 6 6 6 6 6 6 6 6 6 6
BARD LOVED BANANAS
BAOBAB
BAOBAB
BAOBAB
BAOBAB (unsuccessful search)
Horspool’s algorithm
Step 1 For a given pattern of length m and the alphabet used in both the
pattern and text, construct the shift table.
Step 2 Align the pattern against the beginning of the text.
Step 3 Repeat the following until either a matching substring is found or the
pattern reaches beyond the last character of the text. Starting with the last character
in the pattern, compare the corresponding characters in the pattern and text until
either all m characters are matched (then stop) or a mismatching pair is encountered
ALGORITHM HorspoolMatching(P[0..m − 1], T [0..n − 1])
//Implements Horspool’s algorithm for string matching
//Input: Pattern P[0..m − 1] and text T [0..n − 1]
//Output: The index of the left end of the first matching substring
// or −1 if there are no matches
ShiftTable(P[0..m − 1]) //generate Table of shifts
i ← m − 1 //position of the pattern’s right end
while i ≤ n − 1 do
k ← 0 //number of matched characters
while k ≤ m − 1 and P[m − 1 − k] = T [i − k] do
k←k+1
if k = m
return i − m + 1
else i ← i + Table[T [i]] return −1