CPS 616 TRANSFORM-AND-CONQUER 7-1

TRANSFORM AND CONQUER

Group of techniques to solve a problem by first transforming the problem into one
of:
1. a simpler/more convenient instance of the same problem
(instance simplification)
2. a different representation of the same instance
(representation change)
3. a different problem for which an algorithm is already available
(problem reduction)

INSTANCE SIMPLIFICATION - PRESORTING

Main idea:
• Many problems involving lists are easier when list is sorted:
 searching
 computing the median (selection problem)
 checking if all elements are distinct (element uniqueness)
• Also
 Topological sorting helps solving some problems for dags.
 Presorting is used in many geometric algorithms.

Efficiency of sorting
• Efficiency of algorithms with pre-sorts depends on efficiency of sorting
• Theorem (see Sec. 11.2): ⌈log2 n!⌉  n log2 n comparisons are necessary in
the worst case to sort a list of size n by any comparison-based algorithm.
• Note: About n log2 n comparisons are also sufficient to sort array of size n (by
mergesort, quicksort)
CPS 616 TRANSFORM-AND-CONQUER 7-2

Searching with presorting

• Problem: Search for a given K in A[0..n-1]
• Presorting-based algorithm:
 Stage 1 Sort the array by an efficient sorting algorithm
 Stage 2 Apply binary search
 Efficiency: Θ(nlog n) + O(log n) = Θ(nlog n)
• Linear search (without presorting):

Element uniqueness with presorting

• Problem: are all the elements of an array unique?
• Brute force algorithm : Compare all pairs of elements
Efficiency: O(n2)
• Presorting-based algorithm
 Stage 1: sort by efficient sorting algorithm (e.g. mergesort)
 Stage 2: scan array to check pairs of adjacent elements
• Efficiency: Θ(nlog n) + O(n) = Θ(nlog n)

Computing a mode with presorting

• Definition: a mode is a value that occurs most often in a given list of
numbers: e.g. for 2, 6, 7, 8, 6, 1, 6, 3, 6, 2 the mode is 6
• Brute force algorithm:
 Check the frequency of occurrence of each element and select element with
highest frequency
 Efficiency: O(n2)
• Presorting-based algorithm
 Stage 1: sort by efficient sorting algorithm (e.g. mergesort)
 Stage 2: scan array counting equal adjacent elements
 Efficiency: Θ(nlog n) + O(n) = Θ(nlog n)
CPS 616 TRANSFORM-AND-CONQUER 7-3

INSTANCE SIMPLIFICATION - GAUSSIAN ELIMINATION

Background
• To solve a set of equations:
a11x1 + a12x2 = b1
a21x1 + a22x2 = b2
 Transform the second equation as an equation with 1 variable:
a11x1 + a12x2 = b1
c22x2 = d2
 Then second equation can be solved as x2 = d2 / c22
 And this value can be substituted back into first:
a11x1 + a12(d2 / c22) = b1
 Which can be solved as: x1 = [ b1 - a12(d2 / c22) ] / a11
• How to transform: into:
a11x1 + a12x2 = b1 a11x1 + a12x2 = b1
a21x1 + a22x2 = b2 c22x2 = d2

 Multiply first equation by a21/ a11

a21x1 + (a12a21 / a11)x2 = b1 a21/ a11
 Subtract this equation from the second on both sides:
a22x2 - (a12a21 / a11)x2 = b2 - b1 a21/ a11
 We get: c22 = a22 - (a12a21 / a11)
d2 = b2 - b1 a21/ a11
• Note that the matrix equivalent of
a11x1 + a12x2 = b1
a21x1 + a22x2 = b2
is:
𝑎11 𝑎12 𝑥1 𝑏1
(𝑎 𝑎22 ) . (𝑥2 ) = ( )
21 𝑏2
• And the matrix equivalent of
a11x1 + a12x2 = b1
c22x2 = d2
is:
𝑎11 𝑎12 𝑥1 𝑏1
( 0 𝑐22 ) . (𝑥2 ) = ( )
𝑑2
CPS 616 TRANSFORM-AND-CONQUER 7-4

Generalization
• Given: A system of n linear equations in n unknowns with an arbitrary
coefficient matrix.
a11x1 + a12x2 + … + a1nxn = b1
a21x1 + a22x2 + … + a2nxn = b2
...
an1x1 + an2x2 + … + annxn = bn
• Transform to: An equivalent system of n linear equations in n unknowns with
an upper triangular coefficient matrix.
c11x1+ c12x2 + … + c1nxn = d1
c22x2 + … + c2nxn = d2
...
cnnxn = dn
• Solve the latter by substitutions starting with the last equation and moving up
to the first one.
• The transformation is accomplished by a sequence of elementary operations
on the system’s coefficient matrix (which don’t change the system’s
solution):

for i ←1 to n-1 do
replace each of the subsequent rows (i.e., rows i+1, …, n) by
a difference between that row and an appropriate multiple
of the i-th row to make the new coefficient in the i-th column
of that row 0
Pseudocode
• Stage 1: Reduction to an upper-triangular matrix
for i ← 1 to n-1 do // remove multiple of row i from others below
for j ← i+1 to n do // rows j from which row i is removed
factor ← A[j, i] / A[i, i]
for k ← i to n+1 do // columns of row j
A[j, k] ← A[j, k] - A[i, k] * factor
• Stage 2: Back substitutions
for j ← n downto 1 do //go from bottom row j to top
t←0
for k ← j +1 to n do //substitute solved x’s into equation
t ← t + A[j, k] * x[k]
x[j] ← (A[j, n+1] - t) / A[j, j] // solve equation for row
CPS 616 TRANSFORM-AND-CONQUER 7-5

Efficiency
• Θ(n3) + Θ(n2) = Θ(n3)

Example
• Solve 2x1 - 4x2 + x3 = 6 2 -4 1 6
3x1 - x2 + x3 = 11 3 -1 1 11
x1 + x2 - x3 = -3 1 1 -1 -3
• Gaussian Elimination
2 -4 1 6
row2 – (3/2)*row1: 0 5 -1/2 2
row3 – (1/2)*row1: 0 3 -3/2 -6

2 -4 1 6
0 5 -1/2 2
row3–(3/5)*row2 : 0 0 -6/5 -36/5
• Which represents:
2x1 - 4x2 + x3 = 6
5x2 -1/2 x3 = 2
-6/5x3 = -36/5
• Backward substitution
x3 = (-36/5) / (-6/5) = 6
x2 = (2+(1/2)*6) / 5 = 1
x1 = (6 – 6 + 4*1)/2 = 2
CPS 616 TRANSFORM-AND-CONQUER 7-6

INSTANCE SIMPLIFICATION - BALANCED SEARCH TREES

Review: Searching with BSTs
• Linear search for a key through an array is O(n)
• Instead arrange keys in a binary tree with the binary search tree property:

• If the tree is balanced, search for key is O(log n)

• Bonus: inorder traversal produces sorted list
Review: Operations on BSTs
• Searching – straightforward
• Insertion – search for key, insert at leaf where search terminated
• Deletion – 3 cases:
 deleting key at a leaf
 deleting key at node with single child
 deleting key at node with two children
• Efficiency depends of the tree’s height: ⌊log2 n⌋  h  n-1,
with height average (random files) be about 3log2 n
• Thus all three operations have
 worst case efficiency: (n)
 average case efficiency: (log n)
CPS 616 TRANSFORM-AND-CONQUER 7-7

Balanced Search Trees

• Attractiveness of binary search tree is marred by the bad (linear) worst-case
efficiency. Two ideas to overcome it are:
• Instance simplification: rebalance binary search tree when a new insertion
makes the tree “too unbalanced”
 AVL trees: diff. between heights of L and R subtrees  1
 red-black trees: height of 1 subtree  2* height of the other (see later)
• Representation change: allow more than one key per node of a search tree
 2-3 trees
 2-3-4 trees
 B-trees
AVL Trees
• Definitions:
 The height of a tree is the number of edges between the root and the lowest
leaf. The height of an empty tree is -1.
 The balance factor of the node of a tree is the difference between the
heights of its left and right subtrees.
 An AVL tree is a binary search tree in which the absolute value of the
balance factor of any node is at most 1
CPS 616 TRANSFORM-AND-CONQUER 7-8

Degenerate Trees
Degenerate Degenerate AVL Tree
BST (half of the levels are fully balanced)
1

100 100
1 1
45
50 140
30 1 1 1 1

40 60 120 150
18
1 1 1 0 1 0 0

15 25 43 55 65 112 123 144

0 0 0 0

10 18 33 41 52 105
0

10

• Analysis of Efficiency
 height  1.4404 log2 (n + 2) - 1.3277 i.e. O(log n)
 average height: 1.01 log2n + 0.1 for large n (found empirically)
 Search and insertion are O(log n)
 Deletion is more complicated but is also O(log n)

• Disadvantages:
 frequent rotations (see later)
 complexity
CPS 616 TRANSFORM-AND-CONQUER 7-9

• 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.)
CPS 616 TRANSFORM-AND-CONQUER 7 - 10
CPS 616 TRANSFORM-AND-CONQUER 7 - 11

• AVL Tree Construction

CPS 616 TRANSFORM-AND-CONQUER 7 - 12

REPRESENTATION CHANGE - 2-3 TREES

Multiway Search Trees

• Definition: A multiway search tree is a search tree that allows more than
one key in the same node of the tree.
• Definition A node of a search tree is called an n-node if it contains n-1
ordered keys (which divide the entire key range into n intervals pointed to by
the node’s n links to its children):

• Note: Every node in a classical binary search tree is a 2-node

2-3 Trees
• Definition A 2-3 tree is a search tree that
 may have 2-nodes and 3-nodes
 is height-balanced (all leaves are on the same level)
CPS 616 TRANSFORM-AND-CONQUER 7 - 13

• Extreme 2-3 Trees

Max height when all nodes are 2-nodes

50
ℎ𝑒𝑖𝑔ℎ𝑡
𝑛=∑ 2𝑖
𝑖=0
40 60
(2ℎ𝑒𝑖𝑔ℎ𝑡+1 − 1)
=
2−1
25 43 55 65
= (2ℎ𝑒𝑖𝑔ℎ𝑡+1 − 1)

18 33 41 47 52 58 63 70 So height = log2(n+1)-1

Min height when all nodes are 3-nodes

50 100

20 40 150 200
5 10 45 48 110 130 210 215
25 30 65 85 160 180
55 60 90 95
70 75

ℎ𝑒𝑖𝑔ℎ𝑡
𝑖
(3ℎ𝑒𝑖𝑔ℎ𝑡+1 − 1)
𝑛 = 2. ∑ 3 = 2. = (3ℎ𝑒𝑖𝑔ℎ𝑡+1 − 1)
𝑖=0 3−1

So height = log3(n+1)-1

• Efficiency
 log3 (n + 1) - 1  height  log2 (n + 1) - 1
 Search, insertion, and deletion are in (log n)
CPS 616 TRANSFORM-AND-CONQUER 7 - 14

• Construction:

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.

• The idea of 2-3 tree can be generalized by allowing more keys per node
 2-3-4 trees
 B-trees
• However, 2-3 tree implementation is complicated. These trees can instead be
implemented as red-black BSTs
CPS 616 TRANSFORM-AND-CONQUER 7 - 15

RED-BLACK TREES
Definition
2-3 Trees can be represented as special BSTs using rules:
• Nodes and edges are either red or black
• A node is the same colour as its upper edge
• On any path from the root to a leaf the number of black edges is the same
• A red node that is not a leaf has 2 black children
• A black node that is not a leaf has either
 Two black children, or
 One child of each colour, or
 A single child which is a red leaf
Conversion:
A 3-node: is converted into one of the two red-black trees
50 100 50 100

100 50
or

Examples
A 2-3 Tree: Is converted into:
M S M

D F Q V F S

D H Q V
A E H N O R T X Z
A E O R T X

N Z

Properties
• The height of the red-black tree is at most twice the height of the
corresponding 2-3 tree.
• Therefore the logarithmic-time operations on 2-3 trees will be logarithmic
time on the red-black implementations of those trees provided that each
conversion operation (like splitting) can be done in constant time.
CPS 616 TRANSFORM-AND-CONQUER 7 - 16

REPRESENTATION CHANGE :
POLYNOMIAL EVALUATION USING HORNER'S RULE
Problem: (Handout 4)
Find the value of polynomial
p(x) = anxn + an-1xn-1 +… + a1x1 + a0
at a point x = x0
Horner's Rule
p(x) = anxn + an-1xn-1 +… + a1x1 + a0
= [(((anx + an-1)x + an-2)x + an-3)x + … + a1] x + a0
Algorithm:
p  a[n]
for i  n-1 downto 0 do
p  p  x + a[i]
return p
Efficiency
#multiplications = #additions = n
Example
p(x) = 2x4 - x3 + 3x2 + x - 5
= (2x3 - x2 + 3x + 1) x - 5
= ((2x2 - x + 3) x + 1) x - 5
= (((2x - 1) x + 3) x + 1) x – 5
Arrange coefficients in table:
2 -1 3 1 -5
x=3
2x - 1 = 5
(2x - 1) x + 3 = 18
((2x - 1) x + 3) x + 1) = 55
(((2x - 1) x + 3) x + 1) x – 5 = 160
CPS 616 TRANSFORM-AND-CONQUER 7 - 17

REPRESENTATION CHANGE : SYNTHETIC DIVISION

= POLYNOMIAL DIVISION USING HORNER'S RULE
Problem:
Divide p(x) = anxn + an-1xn-1 +… + a1x1 + a0 by (x - x0)
Result: p(x) = (x - x0) q(x) + remainder
where q(x) = bn-1xn-1 +… + b1x1 + b0
Remainder Theorem:
If the polynomial p(x) is divided by x - x0, then the remainder is p(x0).
Application (substitution of remainder): p(x) = (x - x0) q(x) + p(x0)
Find coefficients bi's of q(x)
p(x) = (x - x0) (bn-1xn-1 +… + b1x1 + b0 ) + p(x0)
= x .(bn-1xn-1 +… + b1x1 + b0 ) - x0 . (bn-1xn-1 +… + b1x1 + b0 ) + p(x0)
= x .(bn-1xn-1 +… + b1x1 + b0 ) - x0 . (bn-1xn-1 +… + b1x1 ) - b0 x0+ p(x0)
= anxn + an-1xn-1 +… + a1x1 + a0
So a0 = p(x0) - b0 x0
So b0 = (p(x0) - a0 )/x0
Apply Horner's Rule to p(x0):
p(x0) = an x0n + an-1 x0n-1 +… + a1 x01 + a0
= [(((an x0 + an-1) x0 + an-2) x0 + an-3) x0 + … + a1] x0+ a0
Substitute back into formula for b0:
b0 = (p(x0) - a0 )/x0
=([[(((an x0 + an-1) x0 + an-2) x0 + an-3) x0 + … + a1] x0+ a0] - a0 )/x0
=([[(((an x0 + an-1) x0 + an-2) x0 + an-3) x0 + … + a1] x0 )/x0
=[[(((an x0 + an-1) x0 + an-2) x0 + an-3) x0 + … + a1]
This is the one before last step in the calculation of p(x0) using Horner's rule!
Example:
divide p(x) = 2x4 - x3 + 3x2 + x - 5 by x-3
The steps to calculate p(3) were: 2 (times 30), 5, 18, 55, 160
Result: 2x4 - x3 + 3x2 + x - 5= (x-3)(2x3 + 5x2 + 18x + 55)+160
Algorithm
p  a[n]
for i  n-1 downto 0 do
b[i]  p
p  p  x + a[i]
remainder p
CPS 616 TRANSFORM-AND-CONQUER 7 - 18

PROBLEM REDUCTION - EXPLANATION

• This variation of transform-and-conquer solves a problem by a transforming it
into different problem for which an algorithm is already available.
• To be of practical value, the combined time of the transformation and solving
the other problem should be smaller than solving the problem as given by
another method.

PROBLEM REDUCTION - LEAST COMMON MULTIPLE

• The least common multiple of two positive integers m and n, denoted
lcm(m,n), is the smallest integer that is divisible by both m and n,
• E.g. lcm(25,60) = 300
𝒎 .𝒏
• Theorem: m.n = gcd(m,n).lcm(m,n) and so 𝒍𝒄𝒎(𝒎, 𝒏) =
𝐠𝐜𝐝(𝒎,𝒏)

• Algorithm:
 Calculate gcd(m,n) first using Euclidian Algorithm
 Apply formula above

PROBLEM REDUCTION - COUNTING PATHS IN A GRAPH

• Problem: given a graph, how many paths of size n does it have?
• Represent graph by adjacency matrix A
• Theorem: the number of paths of length n from vertex i to j is An[i,j]
• Algorithm: take the power of A n times - answers are in matrix An
CPS 616 TRANSFORM-AND-CONQUER 7 - 19

PROBLEM REDUCTION - REDUCTION TO GRAPHS

River crossing puzzle:
• Peasant must take cabbage, goat, and wolf across river using one boat which
can only take one passenger other than himself. In his absence, the wolf
might eat the goat and the goat might eat the cabbage. Is there a way for the
peasant to transport all 3 safely to the other side?
• http://www.transum.org/software/River_Crossing/Level1.asp
Reduction to graph:
• Draw a state-space graph: vertices are possible states of the problem, edges
indicate how to move from one state to the other. This is the same as a state-
transition diagram.

Solution:
• find a minimal path from Pwgc|| to ||Pwgc using BFS
CPS 616 TRANSFORM-AND-CONQUER 7 - 20

PROBLEM REDUCTION - OPTIMISATION PROBLEMS

• Problem: Find min (or max) of a function

• How to find either of them in calculus? solve for f'(x)=0

• This is a problem reduction as well: min of a graph reduced to solving an
equation