10/31/16

CSC 8301- Design and Analysis of Algorithms

Lecture 7

Transform and Conquer I

Algorithm Design Technique

Transform and Conquer

This group of techniques solves a problem by a transformation to

q  a simpler/more convenient instance of the same problem (instance

simplification)

q  a different representation of the same instance (representation

change)

q  a different problem for which an algorithm is already available

(problem reduction)

1  
 10/31/16  

Transform and Conquer

q  Instance simplification

–  Presorting
–  Gaussian Elimination

q  Representation change

–  Binary Search Trees
–  Heaps
–  Horner’s rule for polynomial evaluation

q  Problem reduction

–  Example: compute lcm(a,b) by computing gcd(a,b)

Instance simplification - Presorting

Presorting
q  sorting ahead of time, to make repetitive solutions faster

Many problems involving lists are easier when list is sorted, e.g.,
q  searching

q  computing the median (selection problem)

q  checking if all elements are distinct (element uniqueness)

Also:
q  Topological sorting helps solving some problems for dags

q  Presorting is used in many geometric algorithms

2  
 10/31/16  

How fast can we sort ?

Efficiency of algorithms involving presorting depends on
efficiency of the sorting algorithm used

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 nlog2 n comparisons are also sufficient to sort array of

size n (by mergesort)

Searching with presorting

Problem: Search for a given K in A[0..n-1]

Presorting-based algorithm:
Stage 1 Sort the array by, say, mergesort
Stage 2 Apply binary search

Efficiency: Θ(nlog n) + O(log n) = Θ(nlog n)

Good or bad?
Why do we have our dictionaries, telephone directories, etc. sorted?

3  
 10/31/16  

Instance Simplification – Element Uniqueness

q  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)

q  Brute force algorithm

Compare all pairs of elements

Efficiency: O(n2)

Instance simplification – Gaussian Elimination

You are familiar with systems of two linear equations:

a11x1 + a12x2 = b1
a21x1 + a22x2 = b2
Unless a11/a21 = a12/a22, the system has a unique solution:

q  Multiply the first equation by –a21/a11

-a21x1 – (a21a12/a11) x2 = –a21b1/a11

q  Add the above equation to the 2nd one in the system
(a22-a21a12/a11)x2 = b2–a21b1/a11

q  Extract x2 from this equation, substitute in the 1st

4  
 10/31/16  

Instance simplification – Gaussian Elimination

Given: A system of n linear equations in n unknowns with an

arbitrary coefficient matrix.

Transform to: An equivalent system of n linear equations in n

unknowns with an upper triangular coefficient matrix.

Solve the latter by substitutions starting with the last equation and
moving up to the first one.

a11x1 + a12x2 + … + a1nxn = b1 a11x1+ a12x2 + … + a1nxn = b1

a21x1 + a22x2 + … + a2nxn = b2 a22x2 + … + a2nxn = b2

an1x1 + an2x2 + … + annxn = bn annxn = bn

Gaussian Elimination (cont.)

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

5  
 10/31/16  

Example of Gaussian Elimination

Solve 2x1 - 4x2 + x3 = 6

3x1 - x2 + x3 = 11
x1 + x2 - x3 = -3
Gaussian elimination
2 -4 1 6 2 -4 1 6
3 -1 1 11 row2 – (3/2)*row1 0 5 -1/2 2 Repeat
1 1 -1 -3 row3 – (1/2)*row1 0 3 -3/2 -6 row3–(3/5)*row2

2 -4 1 6
0 5 -1/2 2
0 0 -6/5 -36/5
Backward substitution
x3 = (-36/5) / (-6/5) = 6
x2 = (2+(1/2)*6) / 5 = 1
x1 = (6 – 6 + 4*1)/2 = 2

Pseudocode & Efficiency of Gaussian Elimination

Stage 1: Reduction to the upper-triangular matrix

for i ← 1 to n-1 do
for j ← i+1 to n do
temp ← A[j, i] / A[i, i]
for k ← i to n+1 do
A[j, k] ← A[j, k] - A[i, k] * temp

Stage 2: Backward substitution

for j ← n downto 1 do
t←0
for k ← j +1 to n do
t ← t + A[j, k] * x[k]
x[j] ← (A[j, n+1] - t) / A[j, j]

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

6  
 10/31/16  

Transform and Conquer

Representation Change

Searching Problem
Problem: Given a (multi)set S of keys and a search
key K, find an occurrence of K in S, if any

❂  There is no single algorithm that fits all situations best

❂  Searching must be considered in the context of:
–  file size (internal or external)
–  dynamics of data (static vs. dynamic)

❂  Dictionary operations (dynamic data):

–  find (search)
–  insert
–  delete

7  
 10/31/16  

Taxonomy of Searching Algorithms

q  List searching
–  sequential search
–  binary search

q  Tree searching

–  binary search tree
–  binary balanced trees: AVL trees, red-black trees
–  multiway balanced trees: 2-3 trees, 2-3-4 trees, B trees

q  Hashing
–  open hashing (separate chaining)
–  closed hashing (open addressing)

Binary Search Tree

Arrange keys in a binary tree with the binary search tree

property:
K  

<K   >K  

Example: 5, 3, 1, 10, 12, 7, 9

8  
 10/31/16  

Dictionary Operations on Binary Search Trees

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)

Bonus: inorder traversal produces sorted list

Balanced Search Trees

Attractiveness of binary search tree is marred by the bad (linear)

worst-case efficiency. Two ideas to overcome it are:

q  to rebalance binary search tree when a new insertion

makes the tree “too unbalanced”
–  AVL trees
–  red-black trees

q  to allow more than one key per node of a search tree
–  2-3 trees
–  2-3-4 trees
–  B-trees

9  
 10/31/16  

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)
1 2

10 10
0 1 0 0
5 20 5 20

1 -1 0 1 -1

4 7 12 4 7

0 0 0 0
2 8 2 8

(a) (b)

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.)
2 0 2 0
3 2 3 2

1 0 0 -1 0 0
R LR
2 > 1 3 1 > 1 3

0 0
1 2
(a) (c)

Single R-rotation Double LR-rotation

10  
 10/31/16  

Unbalanced Cases (after insertion)

Left-Left: R-rotation(r) Right-Right: L-rotation(r)

(Left subtree of Left child) (Right subtree of Right child)

Right-Left: LR-rotation(r) Left-Right: RL-rotation(r)

(Right subtree of Left child) (Left subtree of Right child)

General case: Single R-rotation

11  
 10/31/16  

General case: Double LR-rotation

AVL tree construction - an example

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

0 -1 -2 0
L(5)
5 5 5 6
0 -1 > 0 0
6 6 5 8

0
8

1 2 1
6 6 6
1 0 2 0 R (5) 0 0
5 8 5 8 > 3 8

0 1 0 0
3 3 2 5

0
2

12  
 10/31/16  

AVL tree construction - an example (cont.)

5, 6, 8, 3, 2, 4, 7 2 0
6 5
-1 0 LR (6) 0 -1
3 8 > 3 6

0 1 0 0 0
2 5 2 4 8

0
4

-1 0
5 5
0 -2 0 0
3 6 3 7
RL (6)
0 0 1 > 0 0 0 0
2 4 8 2 4 6 8

0
7

Analysis of AVL trees

q  h ≤ 1.4404 log2 (n + 2) - 1.3277

average height: 1.01 log2n + 0.1 for large n (found empirically)

q  Search and insertion are O(log n)

q  Deletion is more complicated but is also O(log n)

q  Disadvantages:
–  frequent rotations
–  complexity

q  A similar idea: red-black trees (height of subtrees is allowed to

differ by up to a factor of 2)

13  
 10/31/16  

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):

k1    <    k2    <  …  <    kn-­‐1  

<  k1   [k1,  k2  )   ≥  kn-­‐1  

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

2-3 Tree
Definition A 2-3 tree is a search tree that
q  may have 2-nodes and 3-nodes

q  height-balanced (all leaves are on the same level)

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.

14  
 10/31/16  

2-3 tree construction – an example

Construct a 2-3 tree for the list 9, 5, 8, 3, 2, 4, 7
8
8 8
8
>
9 5,
9 5, 9
9 5,
5, 8,
8, 9
9 5
5 9
9 3,
3, 5
5 9
9

8
8 3,
3, 8
8 3,
3, 8
8
>
2,
2, 3,
3, 5
5 9
9 2
2 5
5 9
9 2
2 4,
4, 5
5 9
9

5
5

3,
3, 8
8 > 3,
3, 5,
5, 8
8 >
3
3 8
8

2
2 4,
4, 5,
5, 7
7 9
9 2
2 4
4 7
7 9
9 2
2 4
4 7
7 9
9

Analysis of 2-3 trees

❂  log3 (n + 1) - 1 ≤ h ≤ log2 (n + 1) - 1

❂  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

15  
 10/31/16  

Homework

Read Sections 6.1, 6.2, 6.3 and 7.4

Exercises 6.1: 2, 4, 7, 11a
Exercises 6.2: 1, 4
Exercises 6.3: 2, 3, 4, 7

Next time: Heaps and Heapsort

16