Initializing A Max Heap

2 3

4 5 6 7

8 9 7
10 11
8

input array = [-, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

 Initializing A Max Heap
1

2 3

4 5 6 7

8 9 7
10 11
8

Start at rightmost array position that has a child.

Index is n/2.  Heapify
 Initializing A Max Heap
1

2 3

4 11 6 7

8 9 7
10 85

Move to next lower array position.

 Initializing A Max Heap
1

2 3

4 11 6 7

8 9 7
10 85

Heapify!
 Initializing A Max Heap
1

2 3

9 11 6 7

8 4 7
10 85
 Initializing A Max Heap
1

2 3

9 11 6 7

8 4 7
10 85

Move to next lower array position and Heapify.

 Initializing A Max Heap
1

2 7

9 11 6 3

8 4 7
10 85
 Initializing A Max Heap
1

2 7

9 11 6 3

8 4 7
10 85

Move to next lower array position and Heapify.

 Initializing A Max Heap
1

11 7

9 6 3

8 4 7
10 85

Find a home for 2.

 Initializing A Max Heap
1

11 7

9 10 6 3

8 4 8 75

Find a home for 2.

 Initializing A Max Heap
1

11 7

9 10 6 3

8 4 72 8
5

Done, move to next lower array position and Heapify.

 Initializing A Max Heap
1

11 7

9 10 6 3

8 4 72 8
5

Find home for 1.

 Initializing A Max Heap
11

9 10 6 3

8 4 72 8
5

Find home for 1.

 Initializing A Max Heap
11

10 7

9 6 3

8 4 72 8
5

Find home for 1.

 Initializing A Max Heap
11

10 7

9 5 6 3

8 4 72 8

Find home for 1.

 Initializing A Max Heap
11

10 7

9 5 6 3

8 4 72 8
1

Done.
Initializing a Max Heap*
 Time Complexity
11

9 7

8 5 6 3

1 4 7
10 8
2

Height of heap = h.
Number of subtrees with root at level j is <= 2 j-1.
Time for each subtree is O(h-j+1).
 Complexity
Time for level j subtrees is <= 2j-1(h-j+1) = t(j).
Total time is t(1) + t(2) + … + t(h-1) = O(n).
 Leftist Trees
Linked binary tree.
Can do everything a heap can do and in the
same asymptotic complexity.
Can meld two leftist tree priority queues in
O(log n) time.
 Extended Binary Trees

Start with any binary tree and add an

external node wherever there is an
empty subtree.
Result is an extended binary tree.
A Binary Tree
 An Extended Binary Tree

number of external nodes is n+1

 The Function s()

For any node x in an extended binary tree,

let s(x) be the length of a shortest path
from x to an external node in the subtree
rooted at x.
s() Values Example
 s() Values Example
2

2 1

2 1 1 0

1 1 0 0 1 0

0 0 0 0 0 0
 Properties Of s()

If x is an external node, then s(x) = 0.

Otherwise,
s(x) = min {s(leftChild(x)),
s(rightChild(x))} + 1
 Height Biased Leftist Trees

A binary tree is a (height biased) leftist tree

iff for every internal node x,
s(leftChild(x)) >= s(rightChild(x))

Tree Terminology
 A Leftist Tree
2

2 1

2 1 1 0

1 1 0 0 1 0

0 0 0 0 0 0
 Leftist Trees--Property 1

In a leftist tree, the rightmost path is a

shortest root to external node path and
the length of this path is s(root).
 A Leftist Tree
2

2 1

2 1 1 0

1 1 0 0 1 0

0 0 0 0 0 0

Length of rightmost path is 2.

 Leftist Trees—Property 2

The number of internal nodes is at least

2s(root) - 1
Because levels 1 through s(root) have no
external nodes.
So, s(root) <= log(n+1)
 A Leftist Tree
2

2 1

2 1 1 0

1 1 0 0 1 0

0 0 0 0 0 0

Levels 1 and 2 have no external nodes.

 Leftist Trees—Property 3

Length of rightmost path is O(log n), where

n is the number of nodes in a leftist tree.

Follows from Properties 1 and 2.

 Leftist Trees As Priority Queues

Min leftist tree … leftist tree that is a min tree.

Used as a min priority queue.
Max leftist tree … leftist tree that is a max tree.
Used as a max priority queue.
 A Min Leftist Tree
2

4 3

6 8 5

8 6 9
 Some Min Leftist Tree Operations
empty()
size()
top()
push()
pop()
meld()
initialize()
push() and pop() use meld().
 Push Operation
push(7) 2

4 3

6 8 5

8 6 9
 Push Operation
push(7) 2

4 3

6 8 5

8 6 9

Create a single node min leftist tree. 7

 Push Operation
push(7) 2

4 3

6 8 5

8 6 9

Create a single node min leftist tree. 7

Meld the two min leftist trees.

 Remove Min (pop)
2

4 3

6 8 5

8 6 9
 Remove Min (pop)
2

4 3

6 8 5

8 6 9

Remove the root.

 Remove Min (pop)
2

4 3

6 8 5

8 6 9

Remove the root.

Meld the two subtrees.
 Meld Two Min Leftist Trees

4 3

6 8 5 6

8 6 9

Traverse only the rightmost paths so as to get

logarithmic performance.
 Meld Two Min Leftist Trees
4 3

6 8 5 6

8 6 9

Meld right subtree of tree with smaller root and

all of other tree.
 Meld Two Min Leftist Trees
4 3

6 8 5 6

8 6 9

Meld right subtree of tree with smaller root and all of

other tree.
 Meld Two Min Leftist Trees
4 6

6 8

8 6

Meld right subtree of tree with smaller root and all of

other tree.
 Meld Two Min Leftist Trees
8 6

Meld right subtree of tree with smaller root and all of

other tree.
Right subtree of 6 is empty. So, result of melding right
subtree of tree with smaller root and other tree is the
other tree.
 Meld Two Min Leftist Trees
8 6

Make melded subtree right subtree of smaller root.

6

Swap left and right subtree if s(left) < s(right). 6

8
 Meld Two Min Leftist Trees
4
4
6

6 6
6
8

8 6 8
8 6

Make melded subtree right subtree of smaller root.

Swap left and right subtree if s(left) < s(right).

 Meld Two Min Leftist Trees
3

5 4

9 6 6

8 6 8

Make melded subtree right subtree of smaller root.

Swap left and right subtree if s(left) < s(right).

 Meld Two Min Leftist Trees
3

4
5

6 6
9

8 6 8
 Initializing In O(n) Time
• create n single node min leftist trees
and place them in a FIFO queue
• repeatedly remove two min leftist trees
from the FIFO queue, meld them, and
put the resulting min leftist tree into the
FIFO queue
• the process terminates when only 1 min
leftist tree remains in the FIFO queue
• analysis is the same as for heap
initialization
 Tournament Trees

Winner trees.
Loser Trees.
 Winner Trees
Complete binary tree with n external
nodes and n - 1 internal nodes.
External nodes represent tournament
players.
Each internal node represents a match
played between its two children;
the winner of the match is stored at
the internal node.
Root has overall winner.
Winner Tree For 16 Players

player match node

 Winner Tree For 16 Players
1

1
2

3 1 2 2

3 6 1 3 2 4 2 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

Smaller element wins => min winner tree.

 Winner Tree For 16 Players
1

1
2

3 1 2 2

3 6 1 3 2 4 2 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

height is log2 n (excludes player level)

 Complexity Of Initialize

• O(1) time to play match at each match node.

• n - 1 match nodes.
• O(n) time to initialize n player winner tree.
 Applications

Sorting.

Insert elements to be sorted into a

winner tree.
Repeatedly extract the winner and
replace by a large value.
 Sort 16 Numbers
1

1
2

3 1 2 2

3 6 1 3 2 4 2 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8
 Sort 16 Numbers
1

1
2

3 1 2 2

3 6 1 3 2 4 2 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8
 Sort 16 Numbers
1

1
2

3 1 2 2

3 6 1 3 2 4 2 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

Sorted array.
 Sort 16 Numbers
1

1
2

3 1 2 2

3 6 5 3 2 4 2 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

Sorted array.
 Sort 16 Numbers
1

1
2

3 3 2 2

3 6 5 3 2 4 2 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

Sorted array.
 Sort 16 Numbers
1

3
2

3 3 2 2

3 6 5 3 2 4 2 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

Sorted array.
 Sort 16 Numbers
2

3
2

3 3 2 2

3 6 5 3 2 4 2 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

Sorted array.
 Sort 16 Numbers
2

3
2

3 3 2 2

3 6 5 3 2 4 2 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

1 2

Sorted array.
 Sort 16 Numbers
2

3
2

3 3 2 2

3 6 5 3 6 4 2 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

1 2

Sorted array.
 Sort 16 Numbers
2

3
2

3 3 4 2

3 6 5 3 6 4 2 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

1 2

Sorted array.
 Sort 16 Numbers
2

3
2

3 3 4 2

3 6 5 3 6 4 2 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

1 2

Sorted array.
 Sort 16 Numbers
2

3
2

3 3 4 2

3 6 5 3 6 4 2 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

1 2

Sorted array.
 Sort 16 Numbers
2

3
2

3 3 4 2

3 6 5 3 6 4 2 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

1 2 2

Sorted array.
 Sort 16 Numbers
2

3
2

3 3 4 2

3 6 5 3 6 4 5 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

1 2 2

Sorted array.
 Sort 16 Numbers
2

3
2

3 3 4 5

3 6 5 3 6 4 5 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

1 2 2

Sorted array.
 Sort 16 Numbers
2

3
4

3 3 4 5

3 6 5 3 6 4 5 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

1 2 2

Sorted array.
 Sort 16 Numbers
3

3
4

3 3 4 5

3 6 5 3 6 4 5 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

1 2 2

Sorted array.
 Sort 16 Numbers
3

3
4

3 3 4 5

3 6 5 3 6 4 5 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

1 2 2 3

Sorted array.
 Time To Sort

• Initialize winner tree.

 O(n) time
• Remove winner and replay.
 O(log n) time
• Remove winner and replay n times.
 O(n log n) time
• Total sort time is O(n log n).
• Actually Theta(n log n).
 Winner Tree Operations

• Initialize
 O(n) time
• Get winner
 O(1) time
• Remove/replace winner and replay
 O(log n) time
 more precisely Theta(log n)
 Replace Winner And Replay
1

1
2

3 1 2 2

3 6 1 3 2 4 2 5

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8

Replace winner with 6.

 Replace Winner And Replay
1

1
2

3 1 2 2

3 6 1 3 2 4 2 5

4 3 6 8 6 5 7 3 2 6 9 4 5 2 5 8

Replay matches on path to root.

 Replace Winner And Replay
1

1
2

3 1 2 2

3 6 1 3 2 4 2 5

4 3 6 8 6 5 7 3 2 6 9 4 5 2 5 8

Replay matches on path to root.

 Replace Winner And Replay
1

1
2

3 1 2 2

3 6 1 3 2 4 2 5

4 3 6 8 6 5 7 3 2 6 9 4 5 2 5 8

Opponent is player who lost last match played at this node.

 Loser Tree

Each match node stores the match

loser rather than the match winner.
 Min Loser Tree For 16 Players

4 8

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8
 Min Loser Tree For 16 Players

6 1

4 8 5 7

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8
 Min Loser Tree For 16 Players
1

6 3 2

4 8 5 7 6 9

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8
 Min Loser Tree For 16 Players
1

3
2

6 3 4 2

4 8 5 7 6 9 5 8

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8
 Min Loser Tree For 16 Players
1

3
2

6 3 4 5

4 8 5 7 6 9 5 8

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8
 Min Loser Tree For 16 Players
1

3
2

6 3 4 5

4 8 5 7 6 9 5 8

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8
 Min Loser Tree For 16 Players
2

3
2

6 3 4 5

4 8 5 7 6 9 5 8

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8
 1 Winner

3
2

6 3 4 5

4 8 5 7 6 9 5 8

4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8
 Complexity Of Loser Tree
Initialize

• One match at each match node.

• One store of a left child winner.
• Total time is O(n).
• More precisely Theta(n).
 21 Winner

32

3
2

6 53 4 5

4 8 95 7 6 9 5 8

4 3 6 8 91 5 7 3 2 6 9 4 5 2 5 8

Replace winner with 9 and replay matches.

 Complexity Of Replay

• One match at each level that has a match

node.
• O(log n)
• More precisely Theta(log n).
 More Tournament Tree
Applications

• k-way merging of runs during an external

merge sort
• Truck loading
 Truck Loading

 n packages to be loaded into trucks

 each package has a weight
 each truck has a capacity of c tons
 minimize number of trucks
 Truck Loading

n = 5 packages
weights [2, 5, 6, 3, 4]
truck capacity c = 10

Load packages from left to right. If a package

doesn’t fit into current truck, start loading a
new truck.
 Truck Loading

n = 5 packages
weights [2, 5, 6, 3, 4]
truck capacity c = 10

truck1 = [2, 5]
truck2 = [6, 3]
truck3 = [4]
uses 3 trucks when 2 trucks suffice
 Truck Loading

n = 5 packages
weights [2, 5, 6, 3, 4]
truck capacity c = 10

truck1 = [2, 5, 3]
truck2 = [6, 4]
 Bin Packing

• n items to be packed into bins

• each item has a size
• each bin has a capacity of c
• minimize number of bins
 Bin Packing

Truck loading is same as bin packing.

Truck is a bin that is to be packed (loaded).
Package is an item/element.
Bin packing to minimize number of bins is NP-hard.
Several fast heuristics have been proposed.
 Bin Packing Heuristics

• First Fit.
 Bins are arranged in left to right order.
 Items are packed one at a time in given order.
 Current item is packed into leftmost bin into
which it fits.
 If there is no bin into which current item fits,
start a new bin.
 First Fit

n=4
weights = [4, 7, 3, 6]
capacity = 10

Pack red item into first bin.

 First Fit

n=4
weights = [4, 7, 3, 6]
capacity = 10

Pack blue item next.

Doesn’t fit, so start a new bin.
 First Fit

n=4
weights = [4, 7, 3, 6]
capacity = 10
 First Fit

n=4
weights = [4, 7, 3, 6]
capacity = 10

Pack yellow item into first

bin.
 First Fit

n=4
weights = [4, 7, 3, 6]
capacity = 10

Pack green item.

Need a new bin.
 First Fit

n=4
weights = [4, 7, 3, 6]
capacity = 10

Not optimal.
2 bins suffice.
 Bin Packing Heuristics

• First Fit Decreasing.

 Items are sorted into decreasing order.
 Then first fit is applied.
 Bin Packing Heuristics

• Best Fit.
 Items are packed one at a time in given order.
 To determine the bin for an item, first
determine set S of bins into which the item fits.
 If S is empty, then start a new bin and put item
into this new bin.
 Otherwise, pack into bin of S that has least
available capacity.
 Bin Packing Heuristics

• Best Fit Decreasing.

 Items are sorted into decreasing order.
 Then best fit is applied.
 Performance

• For first fit and best fit:

Heuristic Bins <= (17/10)(Minimum Bins) + 2

• For first fit decreasing and best fit

decreasing:
Heuristic Bins <= (11/9)(Minimum Bins) + 4
 Complexity Of First Fit

Use a max tournament tree in which

the players are n bins and the value
of a player is the available capacity
in the bin.

O(n log n), where n is the number of

items.
 Binary Search Trees

• Dictionary Operations:
 find(key)
 insert(key, value)
 erase(key)
• Additional operations:
 ascend()
 get(index) (indexed binary search tree)
 delete(index) (indexed binary search tree)
Complexity Of Dictionary Operations
find(), insert() and erase()

Data Structure Worst Case Expected

Hash Table O(n) O(1)

Binary Search O(n) O(log n)

Tree
Balanced O(log n) O(log n)
Binary Search
Tree
n is number of elements in dictionary
 Complexity Of Other Operations
ascend(), get(index), delete(index)

Data Structure ascend get and delete

Hash Table O(D + n log n) O(D + n log n)

Indexed BST O(n) O(n)

Indexed O(n) O(log n)

Balanced BST

D is number of buckets
 Definition Of Binary Search Tree

• A binary tree.
• Each node has a (key, value) pair.
• For every node x, all keys in the left
subtree of x are smaller than that in x.
• For every node x, all keys in the right
subtree of x are greater than that in x.
 Example Binary Search Tree
20

10 40

6 15 30

2 8 25

Only keys are shown.

 The Operation ascend()
20

10 40

6 15 30

2 8 25

Do an inorder traversal. O(n) time.

 The Operation find()
20

10 40

6 15 30

2 8 25

Complexity is O(height) = O(n), where n is

number of nodes/elements.
 The Operation insert()
20

10 40

6 15 30

2 8 25 35

Insert a pair whose key is 35.

 The Operation insert()
20

10 40

6 15 30

2 8 25 35

Insert a pair whose key is 7.

 The Operation insert()
20

10 40

6 15 30

18 25 35
2 8

Insert a pair whose key is 18.

 The Operation insert()
20

10 40

6 15 30

18 25 35
2 8

Complexity of insert() is O(height).

 The Operation erase()

Three cases:
 Element is in a leaf.
 Element is in a degree 1 node.
 Element is in a degree 2 node.
 Erase From A Leaf
20

10 40

6 15 30

18 25 35
2 8

Erase a leaf element. key = 7

 Erase From A Leaf (contd.)
20

10 40

6 15 30

18 25 35
2 8

Erase a leaf element. key = 35

 Erase From A Degree 1 Node
20

10 40

6 15 30

18 25 35
2 8

Erase from a degree 1 node. key = 40

 Erase From A Degree 1 Node (contd.)
20

10 40

6 15 30

18 25 35
2 8

Erase from a degree 1 node. key = 15

 Erase From A Degree 2 Node
20

10 40

6 15 30

18 25 35
2 8

Erase from a degree 2 node. key = 10

 Erase From A Degree 2 Node
20

10 40

6 15 30

18 25 35
2 8

Replace with largest key in left subtree (or

smallest in right subtree).
 Erase From A Degree 2 Node
20

10 40

6 15 30

18 25 35
2 8

Replace with largest key in left subtree (or

smallest in right subtree).
 Erase From A Degree 2 Node
20

8 40

6 15 30

18 25 35
2 8

Replace with largest key in left subtree (or

smallest in right subtree).
 Erase From A Degree 2 Node
20

8 40

6 15 30

18 25 35
2 8

Largest key must be in a leaf or degree 1 node.

Another Erase From A Degree 2 Node
20

10 40

6 15 30

18 25 35
2 8

Erase from a degree 2 node. key = 20

 Erase From A Degree 2 Node
20

10 40

6 15 30

18 25 35
2 8

Replace with largest in left subtree.

 Erase From A Degree 2 Node
20

10 40

6 15 30

18 25 35
2 8

Replace with largest in left subtree.

 Erase From A Degree 2 Node
18

10 40

6 15 30

18 25 35
2 8

Replace with largest in left subtree.

 Erase From A Degree 2 Node
18

10 40

6 15 30

2 8 25 35

Complexity is O(height).
 Indexed Binary Search Tree

• Binary search tree.

• Each node has an additional field.
 leftSize = number of nodes in its left subtree
Example Indexed Binary Search Tree
7
20

4 3
10 40

1 0 1
6 15 30

0 0 0 0
1 18
2 8 25 35

0
7

leftSize values are in red

 leftSize And Rank
Rank of an element is its position in inorder
(inorder = ascending key order).
[2,6,7,8,10,15,18,20,25,30,35,40]
rank(2) = 0
rank(15) = 5
rank(20) = 7
leftSize(x) = rank(x) with respect to elements in
subtree rooted at x
 leftSize And Rank
7
20

4 3
10 40

1 0 1
6 15 30

0 0 0 0
1 18
2 8 25 35

0
7

sorted list = [2,6,7,8,10,15,18,20,25,30,35,40]

 get(index) And delete(index)
7
20

4 3
10 40

1 0 1
6 15 30

0 0 0 0
1 18
2 8 25 35

0
7

sorted list = [2,6,7,8,10,15,18,20,25,30,35,40]

 get(index) And delete(index)

• if index = x.leftSize desired element is

x.element
• if index < x.leftSize desired element is
index’th element in left subtree of x
• if index > x.leftSize desired element is
(index - x.leftSize-1)’th element in right
subtree of x
 Applications
(Complexities Are For Balanced Trees)

Best-fit bin packing in O(n log n) time.

Representing a linear list so that get(index),
insert(index, element), and erase(index)
run in O(log(list size)) time (uses an
indexed binary tree, not indexed binary
search tree).
Can’t use hash tables for either of these
applications.
 Linear List As Indexed Binary Tree
7
h

4 3
e l

1 0 1
b f j

0 0 0 0
1 g
a d i k

0
c

list = [a,b,c,d,e,f,g,h,i,j,k,l]
 insert(5,’m’)
7
h

4 3
e l

1 0 1
b f j

0 0 0 0
1 g
a d i k

0
c

list = [a,b,c,d,e,f,g,h,i,j,k,l]
 insert(5,’m’)
7
h

4 3
e l

1 0 1
b f j

0 0 0 0
1 g
a d i k

0
c

list = [a,b,c,d,e, m,f,g,h,i,j,k,l]

find node with element 4 (e)
 insert(5,’m’)
7
h

4 3
e l

1 0 1
b f j

0 0 0 0
1 g
a d i k

0
c

list = [a,b,c,d,e, m,f,g,h,i,j,k,l]

find node with element 4 (e)
 insert(5,’m’)
7
h

4 3
e l

1 m 0 1
b f j

0 0 0 0
1 g
a d i k

0
c

add m as right child of e; former right

subtree of e becomes right subtree of m
 insert(5,’m’)
7
h

4 3
e l

1 0 1
b f j

0 0 0 0
1 g
a d m i k

0
c

add m as leftmost node in right subtree

of e
 insert(5,’m’)

• Other possibilities exist.

• Must update some leftSize values on path
from root to new node.
• Complexity is O(height).
 Balanced Binary Search Trees

• height is O(log n), where n is the

number of elements in the tree
• AVL (Adelson-Velsky and Landis)
trees
• red-black trees
• find, insert, and erase take O(log n)
time
 Balanced Binary Search Trees
• Indexed AVL trees
• Indexed red-black trees
• Indexed operations also take
O(log n) time
 Balanced Search Trees
• weight balanced binary search trees
• 2-3 & 2-3-4 trees
• AA trees
• B-trees
• BBST
• etc.
 AVL Tree
• binary tree
• More specifically it’s a “self-balancing
binary search tree”
• for every node x, define its balance factor
balance factor of x = height of left subtree of x
- height of right subtree of x
• balance factor of every node x is -1, 0, or 1
• rebalancing if necessary
 Balance Factors
-1

1 1

0 1 -1
0

0
0 0 -1 0

This is an AVL tree.

 Height

The height of an AVL tree that has n nodes is

at most 1.44 log2 (n+2).

The height of every n node binary tree is

at least log2 (n+1).
 AVL Search Tree
-1
10

1 1
7 40
0 1 -1
0 45
3 8 30
0
0 0 -1 0 60
35
1 5 20
0
25
 insert(9)
-1
10

0 1 1
7 40
0 1 -1
0 -1 45
3 8 30
0
0 0 0 -1 0 60
35
1 5 9 20
0
25
 insert(29)
-1
10

1 1
7 40
0 1 -1
0 45
3 8 30
0
0 0 -2 -1 35
0 60
1 5 20
0 -1
RR imbalance => new node is in 25
right subtree of right subtree of 0

blue node (node with bf = -2) 29

 insert(29)
-1
10

1 1
7 40
0 1 -1
0 45
3 8 30
0
0 0 0 0 60
35
1 5 25
0 0
20 29

RR rotation.
 AVL Rotations

• RR
• LL
• RL
• LR
 Red Black Trees

Colored Nodes Definition

• Binary search tree.
• Each node is colored red or black.
• Root and all external nodes are black.
• No root-to-external-node path has two
consecutive red nodes.
• All root-to-external-node paths have the
same number of black nodes
 Example Red Black Tree
10

7 40

45
3 8 30

35 60
1 5 20

25
 Red Black Trees

Colored Edges Definition

• Binary search tree.
• Child pointers are colored red or black.
• Pointer to an external node is black.
• No root to external node path has two
consecutive red pointers.
• Every root to external node path has the
same number of black pointers.
 Example Red Black Tree
10

7 40

45
3 8 30

35 60
1 5 20

25
 Red Black Tree

• The height of a red black tree that has n

(internal) nodes is between log2(n+1) and
2log2(n+1).
• C++ STL Class map => red black tree
• Java standard library TreeMap => red-black tree
 Graphs

• G = (V,E)
• V is the vertex set.
• Vertices are also called nodes and points.
• E is the edge set.
• Each edge connects two different vertices.
• Edges are also called arcs and lines.
• Directed edge has an orientation (u,v).
u v
 Graphs

• Undirected edge has no orientation (u,v).

u v

• Undirected graph => no oriented edge.

• Directed graph => every edge has an
orientation.
 Undirected Graph

2
3
8
1 10

4
5
9
11

6
7
Directed Graph (Digraph)

2
3
8
1 10

4
5
9
11

6
7
Applications—Communication Network

2
3
8
1 10

4
5
9
11

6
7

• Vertex = city, edge = communication link.

 Driving Distance/Time Map

2
4 3
8 8
1 6 10
2 4 5
4 4 3
5
9
11
5 6

6 7
7

• Vertex = city, edge weight = driving

distance/time.
 Street Map

2
3
8
1 10

4
5
9
11

6
7

• Some streets are one way.

 Complete Undirected Graph

Has all possible edges.

n=1 n=2 n=3 n=4

Number Of Edges—Undirected Graph

• Each edge is of the form (u,v), u != v.

• Number of such pairs in an n vertex graph is
n(n-1).
• Since edge (u,v) is the same as edge (v,u),
the number of edges in a complete
undirected graph is n(n-1)/2.
• Number of edges in an undirected graph is
<= n(n-1)/2.
Number Of Edges—Directed Graph

• Each edge is of the form (u,v), u != v.

• Number of such pairs in an n vertex graph is
n(n-1).
• Since edge (u,v) is not the same as edge
(v,u), the number of edges in a complete
directed graph is n(n-1).
• Number of edges in a directed graph is <=
n(n-1).
 Vertex Degree

2
3
8
1 10

4
5
9
11

6
7

Number of edges incident to vertex.

degree(2) = 2, degree(5) = 3, degree(3) = 1
 Sum Of Vertex Degrees

8
10

9
11

Sum of degrees = 2e (e is number of edges)

 In-Degree Of A Vertex

2
3
8
1 10

4
5
9
11

6
7

in-degree is number of incoming edges

indegree(2) = 1, indegree(8) = 0
 Out-Degree Of A Vertex

2
3
8
1 10

4
5
9
11

6
7

out-degree is number of outbound edges

outdegree(2) = 1, outdegree(8) = 2
 Sum Of In- And Out-Degrees

each edge contributes 1 to the in-degree of

some vertex and 1 to the out-degree of some
other vertex

sum of in-degrees = sum of out-degrees = e,

where e is the number of edges in the
digraph
Graph Operations And
Representation
 Sample Graph Problems

• Path problems.
• Connectedness problems.
• Spanning tree problems.
• Graph coloring problems.
• Flow network problems.
 Path Finding
Path between 1 and 8.
2
4 3
8 8
1 6 10
2 4 5
4 4 3
5
9
11
5 6

6 7
7

Path length is 20.

Another Path Between 1 and 8

2
4 3
8 8
1 6 10
2 4 5
4 4 3
5
9
11
5 6

6 7
7

Path length is 28.

 Example Of No Path

2
3
8
1 10

4
5
9
11

6
7

No path between 2 and 9.

 Connected Graph

• Undirected graph.
• There is a path between every pair of
vertices.
Example Of Not Connected

2
3
8
1 10

4
5
9
11

6
7
Connected Graph Example

2
3
8
1 10

4
5
9
11

6
7
 Connected Components

• A subgraph in which any two vertices are

connected to each other by paths
• It is connected to no additional vertices in
the supergraph
• A vertex with no incident edges is itself a
connected component
Connected Components
Connected Components

2
3
8
1 10

4
5
9
11

6
7
 Connected Component

• A maximal subgraph that is connected.

 Cannot add vertices and edges from original
graph and retain connectedness.
• A connected graph has exactly 1
component.
 Not A Component

2
3
8
1 10

4
5
9
11

6
7
 Connected Components

• Several algorithms exists

• A straightforward approach:
– To find all the connected components of a
graph, loop through its vertices, starting a new
breadth first or depth first search whenever the
loop reaches a vertex that has not already been
included in a previously found connected
component.
Connected Components
Connected Components
Connected Components
Connected Components
 Communication Network

2
3
8
1 10

4
5
9
11

6
7

Each edge is a link that can be constructed

(i.e., a feasible link).
Communication Network Problems

• Is the network connected?

 Can we communicate between every pair of
cities?
• Find the components.
• Want to construct smallest number of
feasible links so that resulting network is
connected.
 Cycles And Connectedness

2
3
8
1 10

4
5
9
11

6
7

Removal of an edge that is on a cycle does not affect

connectedness.
 Cycles And Connectedness

2
3
8
1 10

4
5
9
11

6
7

Connected subgraph with all vertices and

minimum number of edges has no cycles.
 Tree

• Connected graph that has no cycles.

• n vertex connected graph with n-1 edges.
 Spanning Tree

• Subgraph that includes all vertices of the

original graph.
• Subgraph is a tree.
 If original graph has n vertices, the spanning
tree has n vertices and n-1 edges.
 Minimum Cost Spanning Tree

2
4 3
8 8
1 6 10
2 4 5
4 4 3
5
9
8 11
5 6
2

6 7
7

• Tree cost is sum of edge weights/costs.

 A Spanning Tree

2
4 3
8 8
1 6 10
2 4 5
4 4 3
5
9
8 11
5 6
2

6 7
7

Spanning tree cost = 51.

 Minimum Cost Spanning Tree

2
4 3
8 8
1 6 10
2 4 5
4 4 3
5
9
8 11
5 6
2

6 7
7

Spanning tree cost = 41.

 A Wireless Broadcast Tree

2
4 3
8 8
1 6 10
2 4 5
4 4 3
5
9
8 11
5 6
2

6 7
7

Source = 1, weights = needed power.

Cost = 4 + 8 + 5 + 6 + 7 + 8 + 3 = 41.
 Graph Representation

• Adjacency Matrix
• Adjacency Lists
 Linked Adjacency Lists
 Array Adjacency Lists
 Adjacency Matrix
• 0/1 n x n matrix, where n = # of vertices
• A(i,j) = 1 iff (i,j) is an edge

1 2 3 4 5
2
3 1 0 1 0 1 0
2 1 0 0 0 1
1
3 0 0 0 0 1
4 4 1 0 0 0 1
5
5 0 1 1 1 0
 Adjacency Matrix Properties
1 2 3 4 5
2
3 1 0 1 0 1 0
2 1 0 0 0 1
1
3 0 0 0 0 1
4 4 1 0 0 0 1
5
5 0 1 1 1 0
•Diagonal entries are zero.
•Adjacency matrix of an undirected graph is
symmetric.
A(i,j) = A(j,i) for all i and j.
 Adjacency Matrix (Digraph)
1 2 3 4 5
2
3 1 0 0 0 1 0
2 1 0 0 0 1
1
3 0 0 0 0 0
4 4 0 0 0 0 1
5
5 0 1 1 0 0
•Diagonal entries are zero.
•Adjacency matrix of a digraph need not be
symmetric.
 Adjacency Matrix

• n2 bits of space
• For an undirected graph, may store only
lower or upper triangle (exclude diagonal).
 (n-1)n/2 bits
• O(n) time to find vertex degree and/or
vertices adjacent to a given vertex.
 Adjacency Lists
• Adjacency list for vertex i is a linear list of
vertices adjacent from vertex i.
• An array of n adjacency lists.
aList[1] = (2,4)
2 aList[2] = (1,5)
3
aList[3] = (5)
1
aList[4] = (5,1)
4
5
aList[5] = (2,4,3)
 Linked Adjacency Lists
• Each adjacency list is a chain.
2 aList[1] 2 4
3
[2] 1 5
1 [3] 5
[4] 5 1
4
5 aList[5] 2 4 3

Array Length = n
# of chain nodes = 2e (undirected graph)
# of chain nodes = e (digraph)
 Array Adjacency Lists
• Each adjacency list is an array list.
2 aList[1] 2 4
3
[2] 1 5
1 [3] 5
[4] 5 1
4
5 aList[5] 2 4 3

Array Length = n
# of list elements = 2e (undirected graph)
# of list elements = e (digraph)
 Weighted Graphs

• Cost adjacency matrix.

 C(i,j) = cost of edge (i,j)
• Adjacency lists => each list element is a
pair (adjacent vertex, edge weight)
Number Of C++ Classes Needed
• Graph representations
 Adjacency Matrix
 Adjacency Lists
Linked Adjacency Lists
Array Adjacency Lists
 3 representations
• Graph types
 Directed and undirected.
 Weighted and unweighted.
 2 x 2 = 4 graph types
• 3 x 4 = 12 C++ classes
 Abstract Class Graph
template<class T>
class graph
{
public:
// ADT methods come here

// implementation independent methods come here

};
 Abstract Methods Of Graph

// ADT methods
virtual ~graph() {}
virtual int numberOfVertices() const = 0;
virtual int numberOfEdges() const = 0;
virtual bool existsEdge(int, int) const = 0;
virtual void insertEdge(edge<T>*) = 0;
virtual void eraseEdge(int, int) = 0;
virtual int degree(int) const = 0;
virtual int inDegree(int) const = 0;
virtual int outDegree(int) const = 0;
 Abstract Methods Of Graph

// ADT methods (continued)

virtual bool directed() const = 0;
virtual bool weighted() const = 0;
virtual vertexIterator<T>* iterator(int) = 0;
virtual void output(ostream&) const = 0;
 Graph Search Methods
• A vertex u is reachable from vertex v iff there is a
path from v to u.

2
3
8
1

4
5
9
10

6
7 11
 Graph Search Methods
• A search method starts at a given vertex v and
visits/labels/marks every vertex that is reachable
from v.
2
3
8
1

4
5
9
10

6
7 11
 Graph Search Methods
• Many graph problems solved using a search
method.
 Path from one vertex to another.
 Is the graph connected?
 Find a spanning tree.
 Etc.
• Commonly used search methods:
 Breadth-first search. (BFS)
 Depth-first search. (DFS)
 Breadth-First Search

• Visit start vertex and put into a FIFO queue.

• Repeatedly remove a vertex from the queue, visit
its unvisited adjacent vertices, put newly visited
vertices into the queue.
 Breadth-First Search Example

2
3
8
1

4
5
9
10

6
7 11

Start search at vertex 1.

 Breadth-First Search Example

2
3
FIFO Queue
8
1 1
4
5
9
10

6
7 11

Visit/mark/label start vertex and put in a FIFO queue.

 Breadth-First Search Example

2
3
FIFO Queue
8
1 1
4
5
9
10

6
7 11

Remove 1 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 2 4
1

4
5
9
10

6
7 11

Removed 1 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 2 4
1

4
5
9
10

6
7 11

Remove 2 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 4 5 3 6
1

4
5
9
10

6
7 11

Removed 2 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 4 5 3 6
1

4
5
9
10

6
7 11

Remove 4 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 5 3 6
1

4
5
9
10

6
7 11

Removed 4 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 5 3 6
1

4
5
9
10

6
7 11

Remove 5 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 3 6 9 7
1

4
5
9
10

6
7 11

Removed 5 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 3 6 9 7
1

4
5
9
10

6
7 11

Remove 3 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 6 9 7
1

4
5
9
10

6
7 11

Removed 3 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 6 9 7
1

4
5
9
10

6
7 11

Remove 6 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 9 7
1

4
5
9
10

6
7 11

Removed 6 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 9 7
1

4
5
9
10

6
7 11

Remove 9 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 7 8
1

4
5
9
10

6
7 11

Removed 9 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 7 8
1

4
5
9
10

6
7 11

Remove 7 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 8
1

4
5
9
10

6
7 11

Removed 7 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 8
1

4
5
9
10

6
7 11

Remove 8 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8
1

4
5
9
10

6
7 11

Queue is empty. Search terminates.

 Breadth-First Search Property

• All vertices reachable from the start vertex

(including the start vertex) are visited.
 Time Complexity
• Each visited vertex is put on (and so
removed from) the queue exactly once.
• When a vertex is removed from the queue,
we examine its adjacent vertices.
 O(n) if adjacency matrix used
 O(vertex degree) if adjacency lists used
• Total time
 O(mn), where m is number of vertices in the
component that is searched (adjacency matrix)
 Time Complexity

 O(n + sum of component vertex degrees) (adj.

lists)
= O(n + number of edges in component)

In other words:
O( |V| + |E| )
 Path From Vertex v To Vertex u

• Start a breadth-first search at vertex v.

• Terminate when vertex u is visited or when
Q becomes empty (whichever occurs first).
• Time
 O(n2) when adjacency matrix used
 O(n+e) when adjacency lists used (e is number
of edges)
 Finds the shortest hop-count path
(unweighted graph)
 Is The Graph Connected?
• Start a breadth-first search at any vertex of
the graph.
• Graph is connected iff all n vertices get
visited.
• Time
 O(n2) when adjacency matrix used
 O(n+e) when adjacency lists used (e is number
of edges)
 Connected Components
• Start a breadth-first search at any as yet
unvisited vertex of the graph.
• Newly visited vertices (plus edges between
them) define a component.
• Repeat until all vertices are visited.
 Connected Components

2
3
8
1

4
5
9
10

6
7 11
 Time Complexity
 O(n2) when adjacency matrix used
 O(n+e) when adjacency lists used (e
is number of edges)
 Spanning Tree

2
3
8
1

4
5
9

6
7

Breadth-first search from vertex 1.

Breadth-first spanning tree.
 Spanning Tree
• Start a breadth-first search at any vertex of
the graph.
• If graph is connected, the n-1 edges used to
get to unvisited vertices define a spanning
tree (breadth-first spanning tree).
• Time
 O(n2) when adjacency matrix used
 O(n+e) when adjacency lists used (e is number
of edges)
 Depth-First Search

depthFirstSearch(v)
{
Label vertex v as reached.
for (each unreached vertex u
adjacenct from v)
depthFirstSearch(u);
}
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Start search at vertex 1.

Label vertex 1 and do a depth first search
from either 2 or 4.
Suppose that vertex 2 is selected.
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Label vertex 2 and do a depth first search

from either 3, 5, or 6.
Suppose that vertex 5 is selected.
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Label vertex 5 and do a depth first search

from either 3, 7, or 9.
Suppose that vertex 9 is selected.
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Label vertex 9 and do a depth first search

from either 6 or 8.
Suppose that vertex 8 is selected.
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Label vertex 8 and return to vertex 9.

From vertex 9 do a dfs(6).
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Label vertex 6 and do a depth first search from

either 4 or 7.
Suppose that vertex 4 is selected.
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Label vertex 4 and return to 6.

From vertex 6 do a dfs(7).
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Label vertex 7 and return to 6.

Return to 9.
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Return to 5.
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Do a dfs(3).
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Label 3 and return to 5.

Return to 2.
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Return to 1.
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Return to invoking method.

 Depth-First Search Properties
• Same complexity as BFS.
• Same properties with respect to path
finding, connected components, and
spanning trees.
• Edges used to reach unlabeled vertices
define a depth-first spanning tree when the
graph is connected.
• There are problems for which bfs is better
than dfs and vice versa.
 Algorithm Design Methods

• Greedy method.
• Divide and conquer.
• Dynamic Programming.
• Backtracking.
• Branch and bound.
 Some Methods Not Covered

• Linear Programming.
• Integer Programming.
• Simulated Annealing.
• Neural Networks.
• Genetic Algorithms.
• Tabu Search.
 Optimization Problem

A problem in which some function (called the

optimization or objective function) is to be
optimized (usually minimized or
maximized) subject to some constraints.
 Machine Scheduling

Find a schedule that minimizes the finish time.

• optimization function … finish time
• constraints
 each job is scheduled continuously on a single machine
for an amount of time equal to its processing requirement
 no machine processes more than one job at a time
 Bin Packing

Pack items into bins using the fewest number of

bins.
• optimization function … number of bins
• constraints
 each item is packed into a single bin
 the capacity of no bin is exceeded
 Min Cost Spanning Tree

Find a spanning tree that has minimum cost.

• optimization function … sum of edge costs
• constraints
 must select n-1edges of the given n vertex graph
 the selected edges must form a tree
 Feasible And Optimal Solutions
A feasible solution is a solution that satisfies
the constraints.

An optimal solution is a feasible solution that

optimizes the objective/optimization
function.
e.g. Earliest finish time, fewest number of
bins, lowest cost, etc.
 Greedy Method

• Solve problem by making a sequence of

decisions.
• Decisions are made one by one in some
order.
• Each decision is made using a greedy
criterion.
• A decision, once made, is (usually) not
changed later.
 Greedy Method
• Make locally optimal choice at each stage
– Greedy algorithms are “short-sighted”
• Hoping to find the global optimum
• Can result in locally optimal solutions:

Start1 end1 Start2 end2

 Greedy Method
• Optimal substructure:
– A problem exhibits optimal substructure if an
optimal solution to the problem contains
optimal solutions to the sub-problems. *

• Greedy algorithms usually fail to find the

optimal solution
– But still Useful:
• Usually fast and simple
• Often produce good approximations
 Machine Scheduling
LPT Scheduling.
• Schedule jobs one by one and in decreasing order
of processing time.
• Each job is scheduled on the machine on which it
finishes earliest.
• Scheduling decisions are made serially using a
greedy criterion (minimize finish time of this job).
• LPT scheduling is an application of the greedy
method.
 LPT Schedule
• LPT rule does not guarantee minimum finish
time schedules.
• (LPT Finish Time)/(Minimum Finish Time) <= 4/3 - 1/(3m)
where m is number of machines
• Minimum finish time scheduling is NP-hard.
• In this case, the greedy method does not work.
• The greedy method does, however, give us a
good heuristic for machine scheduling.
 Container Loading

• Ship has capacity c.

• m containers are available for loading.
• Weight of container i is wi.
• Each weight is a positive number.
• Sum of container weights > c.
• Load as many containers as is possible
without sinking the ship.
 Greedy Solution

• Load containers in increasing order of

weight until we get to a container that
doesn’t fit.
• Does this greedy algorithm always load the
maximum number of containers?
• Yes. May be proved using a proof by
induction (see text).
 Container Loading With 2 Ships

Can all containers be loaded into 2 ships whose

capacity is c (each)?
• Same as bin packing with 2 bins.
 Are 2 bins sufficient for all items?
• Same as machine scheduling with 2 machines.
 Can all jobs be completed by 2 machines in c time
units?
• NP-hard.
0/1 Knapsack Problem
 0/1 Knapsack Problem
• Hiker wishes to take n items on a trip.
• The weight of item i is wi.
• The items are to be carried in a knapsack whose
weight capacity is c.
• When sum of item weights <= c, all n items can
be carried in the knapsack.
• When sum of item weights > c, some items must
be left behind.
• Which items should be taken/left?
 0/1 Knapsack Problem
• Hiker assigns a profit/value pi to item i.
• All weights and profits are positive numbers.
• Hiker wants to select a subset of the n items to take.
 The weight of the subset should not exceed the
capacity of the knapsack. (constraint)
 Cannot select a fraction of an item. (constraint)
 The profit/value of the subset is the sum of the
profits of the selected items. (optimization function)
 The profit/value of the selected subset should be
maximum. (optimization criterion)
 0/1 Knapsack Problem
Let xi = 1 when item i is selected and let xi = 0
when item i is not selected.
n
maximize pi xi
i=1
n
subject to wi xi <= c
i=1
and xi = 0 or 1 for all i
 Greedy Attempt 1
Be greedy on capacity utilization.
 Select items in increasing order of weight.
n = 2, c = 7
w = [3, 6]
p = [2, 10]
only item 1 is selected
profit (value) of selection is 2
not best selection!
 Greedy Attempt 2
Be greedy on profit earned.
 Select items in decreasing order of profit.
n = 3, c = 7
w = [7, 3, 2]
p = [10, 8, 6]
only item 1 is selected
profit (value) of selection is 10
not best selection!
 Greedy Attempt 3
Be greedy on profit density (p/w).
 Select items in decreasing order of profit density.
n = 2, c = 7
w = [1, 7]
p = [10, 20]
only item 1 is selected
profit (value) of selection is 10
not best selection!
 Greedy Attempt 3
Be greedy on profit density (p/w).
 Works when selecting a fraction of an item is
permitted
 Select items in decreasing order of profit density, if
next item doesn’t fit take a fraction so as to fill
knapsack.
n = 2, c = 7
w = [1, 7]
p = [10, 20]
item 1 and 6/7 of item 2 are selected
 0/1 Knapsack Greedy Heuristics

• Select a subset with <= k items.

• If the weight of this subset is > c, discard
the subset.
• If the subset weight is <= c, fill as much of
the remaining capacity as possible by being
greedy on profit density.
• Try all subsets with <= k items and select
the one that yields maximum profit.
 0/1 Knapsack Greedy Heuristics
• (best value - greedy value)/(best value) <=
1/(k+1)
k 0% 1% 5% 10% 25%

0 239 390 528 583 600

1 360 527 598 600

2 483 581 600

Number of solutions (out of 600) within x% of best.

 0/1 Knapsack Greedy Heuristics

• First sort into decreasing order of profit density.

• There are O(nk) subsets with at most k items.
• Trying a subset takes O(n) time.
• Total time is O(nk+1) when k > 0.
• (best value - greedy value)/(best value) <=
1/(k+1)
 Shortest Path Problems

• Directed weighted graph.

• Path length is sum of weights of edges on path.
• The vertex at which the path begins is the
source vertex.
• The vertex at which the path ends is the
destination vertex.
 Optimal Substructure
• If the shortest route from Seattle to Los
Angeles passes through Portland and then
Sacramento, then the shortest route from
Portland to Los Angeles must pass through
Sacramento too
• The problem of how to get from Portland to
Los Angeles is nested inside the problem of
how to get from Seattle to Los Angeles.
 Example
8 6
1
2 3
3 1
16
6 7 4 5 10
4
2 4 7
5 3

14

A path from 1 to 7.
Path length is 14.
 Example
8 6
1
2 3
3 1
16
6 7 4 5 10
4
2 4 7
5 3

14

Another path from 1 to 7.

Path length is 11.
 Shortest Path Problems

• Single source single destination.

• Single source all destinations.
• All pairs (every vertex is a source
and destination).
 Single Source Single Destination

Possible greedy algorithm:

 Leave source vertex using cheapest/shortest edge.
 Leave new vertex using cheapest edge subject to the
constraint that a new vertex is reached.
 Continue until destination is reached.
 Greedy Shortest 1 To 7 Path
8 6
1
2 3
3 1
16
6 7 4 5 10
4
2 4 7
5 3

14

Path length is 12.

Not shortest path. Algorithm doesn’t work!
 Single Source All Destinations
Need to generate up to n (n is number of vertices)
paths (including path from source to itself).
Greedy method:
 Construct these up to n paths in order of increasing
length.
 Assume edge costs (lengths) are >= 0.
 So, no path has length < 0.
 First shortest path is from the source vertex to itself.
The length of this path is 0.
 Greedy Single Source All Destinations
8 6
1
2 3
3 1
16
6 7 4 5 10
4
2 4 7
5 3
14
Path Length 1 2 6
1 0
1 3 5 4 9
1 3 2
1 3 6 10
1 3 5 5 1 3 6 7 11
 Greedy Single Source All Destinations
Path Length
1 0 • Each path (other than
first) is a one edge
1 3 2 extension of a previous
path.
1 3 5 5
6 •Next shortest path is
1 2
the shortest one edge
1 3 5 4 9 extension of an already
generated shortest path.
1 3 6 10

1 3 6 7 11
 Greedy Single Source All Destinations

• Let d(i) (distanceFromSource(i)) be the length of

a shortest one edge extension of an already
generated shortest path, the one edge extension
ends at vertex i.
• The next shortest path is to an as yet unreached
vertex for which the d() value is least.
• Let p(i) (predecessor(i)) be the vertex just before
vertex i on the shortest one edge extension to i.
 Greedy Single Source All Destinations
8 6
1
2 3
3 1
16
6 7 4 5 10
4
2 4 7
5 3
1 14
[1] [2] [3] [4] [5] [6] [7]
d 0 6 2 16 - - 14
p - 1 1 1 - - 1
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
 Greedy Single Source All Destinations
8 6
1
2 3
3 1
16
6 7 4 5 10
4
2 4 7
5 3
1 14
1 3 [1] [2] [3] [4] [5] [6] [7]
d 0 6 2 16 55- 10 - 14
p - 1 1 1 3- 3- 1
 Greedy Single Source All Destinations
8 6
1
2 3
3 1
16
6 7 4 5 10
4
2 4 7
5 3
1 14
1 3 [1] [2] [3] [4] [5] [6] [7]
1 3 5 d 0 66 2 16 9 5- 10 - 14
p - 1 1 51 3- 3- 1
 Greedy Single Source All Destinations
8 6
1
2 3
3 1
16
6 7 4 5 10
4
2 4 7
5 3
1 14
1 3 [1] [2] [3] [4] [5] [6] [7]
1 3 5 d 0 6 2 9 5- 10 - 14
p - 1 1 5 3- 3- 1
1 2
 Greedy Single Source All Destinations
8 6
1
2 3
3 1
16
6 7 4 5 10
4
2 4 7
5 3
1 14
1 3 [1] [2] [3] [4] [5] [6] [7]
1 3 5 d 0 6 2 9 5- 10 - 14
12
p - 1 1 5 3- -3 41
1 2

1 3 5 4
 Greedy Single Source All Destinations
8 6
1
2 3
3 1
16
6 7 4 5 10
4
2 4 7
5 3
14
1 3 6 [1] [2] [3] [4] [5] [6] [7]
d 0 6 2 9 5- 10 - 14
12
11
p - 1 1 5 3- 3- 416
 Greedy Single Source All Destinations
Path Length
1 0
1 3 2
1 3 5 5
1 2 6
[1] [2] [3] [4] [5] [6] [7]
1 3 5 4 9
0 6 2 9 5- 10 - 14
12
11
- 1 1 5 3- 3- 416
1 3 6 10

1 3 6 7 11
Single Source Single Destination

Terminate single source all destinations

greedy algorithm as soon as shortest path to
desired vertex has been generated.
Data Structures For Dijkstra’s Algorithm
• The greedy single source all destinations
algorithm is known as Dijkstra’s algorithm.
• Implement d() and p() as 1D arrays.
• Keep a linear list L of reachable vertices to
which shortest path is yet to be generated.
• Select and remove vertex v in L that has smallest
d() value.
• Update d() and p() values of vertices adjacent to
v.
 Note on Dijkstra’s
• Directed weighted graph.
• Does not work with negative cycle
• In fact, Dijkstra’s prohibits negative edges!
• Shortest path on a graph with a negative
cycle is undefined:
 Complexity
• O(n) to select next destination vertex.
• O(out-degree) to update d() and p() values
when adjacency lists are used.
• O(n) to update d() and p() values when
adjacency matrix is used.
• Selection and update done once for each
vertex to which a shortest path is found.
• Total time is O(n2 + e) = O(n2).
 Complexity
• When a min heap of d() values is used in place of
the linear list L of reachable vertices, total time is
O((n+e) log n), because O(n) remove min
operations and O(e) change key (d() value)
operations are done.
• When e is O(n2), using a min heap is worse than
using a linear list.
• When a Fibonacci heap is used, the total time is
O(n log n + e).
– This is asymptotically the fastest known single-source
shortest-path algorithm for arbitrary directed graphs
with unbounded non-negative weights. *
 Minimum-Cost Spanning Tree

• weighted connected undirected graph

• spanning tree
• cost of spanning tree is sum of edge costs
• find spanning tree that has minimum cost
 Example

8 10 14
1 3 5 7
7 4 12 6 3
2
2 4 6 8
9

• Network has 10 edges.

• Spanning tree has only n - 1 = 7 edges.
• Need to either select 7 edges or discard 3.
Edge Selection Greedy Strategies
• Start with an n-vertex 0-edge forest.
Consider edges in ascending order of cost.
Select edge if it does not form a cycle
together with already selected edges.
 Kruskal’s method.
• Start with a 1-vertex tree and grow it into an
n-vertex tree by repeatedly adding a vertex
and an edge. When there is a choice, add a
least cost edge.
 Prim’s method.
Edge Selection Greedy Strategies
• Start with an n-vertex forest. Each
component/tree selects a least cost edge to
connect to another component/tree.
Eliminate duplicate selections and possible
cycles. Repeat until only 1 component/tree
is left.
 Sollin’s method.
Edge Rejection Greedy Strategies
• Start with the connected graph. Repeatedly
find a cycle and eliminate the highest cost
edge on this cycle. Stop when no cycles
remain.
• Consider edges in descending order of cost.
Eliminate an edge provided this leaves
behind a connected graph.
 Kruskal’s Method
8 10 14
1 3 5 7 1 3 5 7
7 4 12 6 3
2
2 4 6 8 2 4 6 8
9

• Start with a forest that has no edges.

• Consider edges in ascending order of cost.

• Edge (1,2) is considered first and added to
the forest.
 Kruskal’s Method
8 10 14
1 3 5 7 1 3 5 7
7 3 7 4 6 3
2 4 12 6 2
2 4 6 8 2 4 6 8
9

• Edge (7,8) is considered next and added.

• Edge (3,4) is considered next and added.
• Edge (5,6) is considered next and added.
• Edge (2,3) is considered next and added.
• Edge (1,3) is considered next and rejected
because it creates a cycle.
 Kruskal’s Method
8 10 14 10 14
1 3 5 7 1 3 5 7
7 3 7 4 6 3
2 4 12 6 2
2 4 6 8 2 4 6 8
9

• Edge (2,4) is considered next and rejected

because it creates a cycle.
• Edge (3,5) is considered next and added.
• Edge (3,6) is considered next and rejected.
• Edge (5,7) is considered next and added.
 Kruskal’s Method
8 10 14 10 14
1 3 5 7 1 3 5 7
7 3 7 4 6 3
2 4 12 6 2
2 4 6 8 2 4 6 8
9

• n - 1 edges have been selected and no cycle

formed.
• So we must have a spanning tree.
• Cost is 46.
• Min-cost spanning tree is unique when all
edge costs are different.
 Prim’s Method
8 10 14 10 14
1 3 5 7 1 3 5 7
7 3 7 4 6 3
2 4 12 6 2
2 4 6 8 2 4 6 8
9

• Start with any single vertex tree.

• Get a 2-vertex tree by adding a cheapest edge.
• Get a 3-vertex tree by adding a cheapest edge.
• Grow the tree one edge at a time until the tree
has n - 1 edges (and hence has all n vertices).
 Sollin’s Method
8 10 14
1 3 5 7 1 3 5 7
7 12 6 3 4 6 3
2 4 2
2 4 6 8 2 4 6 8
9

• Start with a forest that has no edges.

• Each component selects a least cost edge
with which to connect to another component.
• Duplicate selections are eliminated.
• Cycles are possible when the graph has
some edges that have the same cost.
 Sollin’s Method
8 10 14 10 14
1 3 5 7 1 3 5 7
7 3 7 4 6 3
2 4 12 6 2
2 4 6 8 2 4 6 8
9

• Each component that remains selects a

least cost edge with which to connect to
another component.
• Beware of duplicate selections and cycles.
Greedy Minimum-Cost Spanning Tree Methods

• Can prove that all result in a minimum-cost

spanning tree.
• Prim’s method is fastest.
 O(n2) using an implementation similar to that of
Dijkstra’s shortest-path algorithm.
 O(e + n log n) using a Fibonacci heap.
• Kruskal’s uses union-find trees to run in
O(n + e log e) time.
 Pseudocode For Kruskal’s Method

Start with an empty set T of edges.

while (E is not empty && |T| != n-1)
{
Let (u,v) be a least-cost edge in E.
E = E - {(u,v)}. // delete edge from E
if ((u,v) does not create a cycle in T)
Add edge (u,v) to T.
}
if (| T | == n-1) T is a min-cost spanning tree.
else Network has no spanning tree.
Data Structures For Kruskal’s Method

Edge set E.
Operations are:
 Is E empty?
 Select and remove a least-cost edge.
Use a min heap of edges.
 Initialize. O(e) time.
 Remove and return least-cost edge. O(log e) time.
Data Structures For Kruskal’s Method

Set of selected edges T.

Operations are:
 Does T have n - 1 edges?
 Does the addition of an edge (u, v) to T result in a
cycle?
 Add an edge to T.
Data Structures For Kruskal’s Method
Use an array linear list for the edges of T.
 Does T have n - 1 edges?
• Check size of linear list. O(1) time.
 Does the addition of an edge (u, v) to T result in a
cycle?
• Not easy.
 Add an edge to T.
• Add at right end of linear list. O(1) time.
Just use an array rather than arrayList.
Data Structures For Kruskal’s Method
Does the addition of an edge (u, v) to T result in
a cycle?
1 3 5 7
7 4 6 3
2
2 4 6 8

• Each component of T is a tree.

• When u and v are in the same component, the
addition of the edge (u,v) creates a cycle.
• When u and v are in the different components,
the addition of the edge (u,v) does not create a
cycle.
Data Structures For Kruskal’s Method
1 3 5 7
7 4 6 3
2
2 4 6 8

• Each component of T is defined by the

vertices in the component.
• Represent each component as a set of
vertices.
 {1, 2, 3, 4}, {5, 6}, {7, 8}
• Two vertices are in the same component iff
they are in the same set of vertices.
Data Structures For Kruskal’s Method
1 3 5 7
7 4 6 3
2
2 4 6 8

• When an edge (u, v) is added to T, the two

components that have vertices u and v
combine to become a single component.
• In our set representation of components, the
set that has vertex u and the set that has vertex
v are united.
 {1, 2, 3, 4} + {5, 6} => {1, 2, 3, 4, 5, 6}
Data Structures For Kruskal’s Method
• Initially, T is empty.
1 3 5 7

2 4 6 8

• Initial sets are:

 {1} {2} {3} {4} {5} {6} {7} {8}
• Does the addition of an edge (u, v) to T result
in a cycle? If not, add edge to T.
s1 = find(u); s2 = find(v);
if (s1 != s2) union(s1, s2);
Data Structures For Kruskal’s Method
• Use fastUnionFind.
• Initialize.
 O(n) time.
• At most 2e finds and n-1 unions.
 Very close to O(n + e).
• Min heap operations to get edges in
increasing order of cost take O(e log e).
• Overall complexity of Kruskal’s method is
O(n + e log e).
 Divide And Conquer

• Distinguish between small and large instances.

• Small instances solved differently from large ones.
 Small And Large Instance

• Small instance.
 Sort a list that has n <= 10 elements.
 Find the minimum of n <= 2 elements.
• Large instance.
 Sort a list that has n > 10 elements.
 Find the minimum of n > 2 elements.
 Solving A Small Instance
• A small instance is solved using some
direct/simple strategy.
 Sort a list that has n <= 10 elements.
• Use count, insertion, bubble, or selection sort.
 Find the minimum of n <= 2 elements.
• When n = 0, there is no minimum element.
• When n = 1, the single element is the minimum.
• When n = 2, compare the two elements and
determine which is smaller.
 Solving A Large Instance
• A large instance is solved as follows:
 Divide the large instance into k >= 2 smaller instances.
 Solve the smaller instances somehow.
 Combine the results of the smaller instances to obtain
the result for the original large instance.
 Sort A Large List

• Sort a list that has n > 10 elements.

 Sort 15 elements by dividing them into 2 smaller lists.
One list has 7 elements and the other has 8.
 Sort these two lists using the method for small lists.
 Merge the two sorted lists into a single sorted list.
 Find The Min Of A Large List

• Find the minimum of 20 elements.

 Divide into two groups of 10 elements each.
 Find the minimum element in each group somehow.
 Compare the minimums of each group to determine
the overall minimum.
 Recursion In Divide And Conquer
• Often the smaller instances that result from the
divide step are instances of the original problem
(true for our sort and min problems). In this case,
 If the new instance is a small instance, it is solved
using the method for small instances.
 If the new instance is a large instance, it is solved using
the divide-and-conquer method recursively.
• Generally, performance is best when the smaller
instances that result from the divide step are of
approximately the same size.
 Recursive Find Min

• Find the minimum of 20 elements.

 Divide into two groups of 10 elements each.
 Find the minimum element in each group
recursively. The recursion terminates when the
number of elements is <= 2. At this time the
minimum is found using the method for small
instances.
 Compare the minimums of the two groups to
determine the overall minimum.
Tiling A Defective Chessboard
Our Definition Of A Chessboard
A chessboard is an n x n grid, where n is a
power of 2.

1x1 2x2 4x4 8x8

A defective chessboard is a chessboard that
has one unavailable (defective) position.

1x1 2x2 4x4 8x8

 A Triomino
A triomino is an L shaped object that can
cover three squares of a chessboard.

A triomino has four orientations.

 Tiling A Defective Chessboard
Place (n2 - 1)/3 triominoes on an n x n
defective chessboard so that all n2 - 1
nondefective positions are covered.

1x1 2x2 4x4 8x8

 Tiling A Defective Chessboard

Divide into four smaller chessboards. 4 x 4

One of these is a defective 4 x 4 chessboard.

 Tiling A Defective Chessboard

Make the other three 4 x 4 chessboards defective

by placing a triomino at their common corner.
Recursively tile the four defective 4 x 4
chessboards.
Tiling A Defective Chessboard
 Complexity

• Let n = 2k.
• Let t(k) be the time taken to tile a 2k x 2k
defective chessboard.
• t(0) = d, where d is a constant.
• t(k) = 4t(k-1) + c, when k > 0. Here c is a
constant.
• Recurrence equation for t().
 Substitution Method
t(k) = 4t(k-1) + c
= 4[4t(k-2) + c] + c
= 42 t(k-2) + 4c + c
= 42[4t(k-3) + c] + 4c + c
= 43 t(k-3) + 42c + 4c + c
=…
= 4k t(0) + 4k-1c + 4k-2c + ... + 42c + 4c + c
= 4k d + 4k-1c + 4k-2c + ... + 42c + 4c + c
= Theta(4k)
= Theta(number of triominoes placed)
 Min And Max
Find the lightest and heaviest of n elements
using a balance that allows you to compare
the weight of 2 elements.

Minimize the number of comparisons.

 Max Element
• Find element with max weight from
w[0:n-1].

maxElement = 0;
for (int i = 1; i < n; i++)
if (w[maxElement] < w[i]) maxElement = i;

• Number of comparisons of w values is n-1.

 Min And Max

• Find the max of n elements making n-1

comparisons.
• Find the min of the remaining n-1 elements
making n-2 comparisons.
• Total number of comparisons is 2n-3.
 Divide And Conquer

• Small instance.
 n <= 2.
 Find the min and max element making at most
one comparison.
Large Instance Min And Max
 n > 2.
 Divide the n elements into 2 groups A and B
with floor(n/2) and ceil(n/2) elements,
respectively.
 Find the min and max of each group
recursively.
 Overall min is min{min(A), min(B)}.
 Overall max is max{max(A), max(B)}.
 Min And Max Example
• Find the min and max of {3,5,6,2,4,9,3,1}.
• Large instance.
• A = {3,5,6,2} and B = {4,9,3,1}.
• min(A) = 2, min(B) = 1.
• max(A) = 6, max(B) = 9.
• min{min(A),min(B)} = 1.
• max{max(A), max(B)} = 9.
 Dividing Into Smaller Instances
{8,2,6,3,9,1,7,5,4,2,8}

{8,2,6,3,9} {1,7,5,4,2,8}

{8,2} {6,3,9} {1,7,5} {4,2,8}

{6} {3,9} {1} {7,5} {4} {2,8}

Solve Small Instances And Combine
{1,9}

{2,9} {1,8}

{8,2} {3,9} {1,7} {2,8}

{2,8} {6} {3,9} {1} {7,5} {4} {2,8}

{6,6} {3,9} {1,1} {5,7} {4,4} {2,8}

 Time Complexity
• Let c(n) be the number of comparisons made
when finding the min and max of n elements.
• c(0) = c(1) = 0.
• c(2) = 1.
• When n > 2,
c(n) = c(floor(n/2)) + c(ceil(n/2)) + 2
• To solve the recurrence, assume n is a power of 2
and use repeated substitution.
• c(n) = ceil(3n/2) - 2.
 Interpretation Of Recursive Version

• The working of a recursive divide-and-conquer algorithm

can be described by a tree—recursion tree.
• The algorithm moves down the recursion tree dividing large
instances into smaller ones.
• Leaves represent small instances.
• The recursive algorithm moves back up the tree combining
the results from the subtrees.
• The combining finds the min of the mins computed at
leaves and the max of the leaf maxs.
 Iterative Version

• Start with n/2 groups with 2 elements each

and possibly 1 group that has just 1element.
• Find the min and max in each group.
• Find the min of the mins.
• Find the max of the maxs.
 Iterative Version Example

• {2,8,3,6,9,1,7,5,4,2,8 }
• {2,8}, {3,6}, {9,1}, {7,5}, {4,2}, {8}
• mins = {2,3,1,5,2,8}
• maxs = {8,6,9,7,4,8}
• minOfMins = 1
• maxOfMaxs = 9
 Comparison Count
• Start with n/2 groups with 2 elements each
and possibly 1 group that has just 1element.
 No compares.
• Find the min and max in each group.
 floor(n/2) compares.
• Find the min of the mins.
 ceil(n/2) - 1 compares.
• Find the max of the maxs.
 ceil(n/2) - 1 compares.
• Total is ceil(3n/2) - 2 compares.
 Initialize A Heap
• n > 1:
 Initialize left subtree and right subtree recursively.
 Then do a trickle down operation at the root.
• t(n) = c, n <= 1.
• t(n) = 2t(n/2) + d * height, n > 1.
• c and d are constants.
• Solve to get t(n) = O(n).
• Implemented iteratively in Chapter 12.
 Initialize A Loser Tree
• n > 1:
 Initialize left subtree.
 Initialize right subtree.
 Compare winners from left and right subtrees.
 Loser is saved in root and winner is returned.
• t(n) = c, n <= 1.
• t(n) = 2t(n/2) + d, n > 1.
• c and d are constants.
• Solve to get t(n) = O(n).
• Implemented iteratively in Chapter 13.
 Divide-And-Conquer Sorting
• Small instance.
 n <= 1 elements.
 n <= 10 elements.
 We’ll use n <= 1 for now.
• Large instance.
 Divide into k >= 2 smaller instances.
 k = 2, 3, 4, … ?
 What does each smaller instance look like?
 Sort smaller instances recursively.
 How do you combine the sorted smaller instances?
 Insertion Sort
a[0] a[n-2] a[n-1]

• k=2
• First n - 1 elements (a[0:n-2]) define one of the
smaller instances; last element (a[n-1]) defines
the second smaller instance.
• a[0:n-2] is sorted recursively.
• a[n-1] is a small instance.
 Insertion Sort
a[0] a[n-2] a[n-1]

• Combining is done by inserting a[n-1] into the

sorted a[0:n-2] .
• Complexity is O(n2).
• Usually implemented nonrecursively.
 Divide And Conquer
• Divide-and-conquer algorithms generally have
best complexity when a large instance is divided
into smaller instances of approximately the same
size.
• When k = 2 and n = 24, divide into two smaller
instances of size 12 each.
• When k = 2 and n = 25, divide into two smaller
instances of size 13 and 12, respectively.
 Merge Sort
• k=2
• First ceil(n/2) elements define one of the smaller
instances; remaining floor(n/2) elements define
the second smaller instance.
• Each of the two smaller instances is sorted
recursively.
• The sorted smaller instances are combined using
a process called merge.
• Complexity is O(n log n).
• Usually implemented nonrecursively.
 Merge Two Sorted Lists
• A = (2, 5, 6)
B = (1, 3, 8, 9, 10)
C = ()
• Compare smallest elements of A and B and
merge smaller into C.
• A = (2, 5, 6)
B = (3, 8, 9, 10)
C = (1)
 Merge Two Sorted Lists
• A = (5, 6)
B = (3, 8, 9, 10)
C = (1, 2)
• A = (5, 6)
B = (8, 9, 10)
C = (1, 2, 3)
• A = (6)
B = (8, 9, 10)
C = (1, 2, 3, 5)
 Merge Two Sorted Lists
• A = ()
B = (8, 9, 10)
C = (1, 2, 3, 5, 6)
• When one of A and B becomes empty, append
the other list to C.
• O(1) time needed to move an element into C.
• Total time is O(n + m), where n and m are,
respectively, the number of elements initially in
A and B.
 Merge Sort

[8, 3, 13, 6, 2, 14, 5, 9, 10, 1, 7, 12, 4]

[8, 3, 13, 6, 2, 14, 5] [9, 10, 1, 7, 12, 4]

[8, 3, 13, 6] [2, 14, 5] [9, 10, 1] [7, 12, 4]

[8, 3] [13, 6] [2, 14] [5] [9, 10] [1] [7, 12] [4]
[8] [3] [13] [6] [2] [14] [9] [10] [7] [12]
 Merge Sort

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13,14]

[2, 3, 5, 6, 8, 13, 14] [1, 4, 7, 9, 10,12]

[3, 6, 8, 13] [2, 5, 14] [1, 9, 10] [4, 7, 12]

[3, 8] [6, 13] [2, 14] [5] [9, 10] [1] [7, 12] [4]
[8] [3] [13] [6] [2] [14] [9] [10] [7] [12]
 Time Complexity
• Let t(n) be the time required to sort n elements.
• t(0) = t(1) = c, where c is a constant.
• When n > 1,
t(n) = t(ceil(n/2)) + t(floor(n/2)) + dn,
where d is a constant.
• To solve the recurrence, assume n is a power of 2
and use repeated substitution.
• t(n) = O(n log n).
 Nonrecursive Version

• Eliminate downward pass.

• Start with sorted lists of size 1 and do
pairwise merging of these sorted lists as in
the upward pass.
 Nonrecursive Merge Sort

[8] [3] [13] [6] [2] [14] [5] [9] [10] [1] [7] [12] [4]

[3, 8] [6, 13] [2, 14] [5, 9] [1, 10] [7, 12] [4]

[3, 6, 8, 13] [2, 5, 9, 14] [1, 7, 10, 12] [4]

[2, 3, 5, 6, 8, 9, 13, 14] [1, 4, 7, 10, 12]

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14]

 Complexity
• Sorted segment size is 1, 2, 4, 8, …
• Number of merge passes is ceil(log2n).
• Each merge pass takes O(n) time.
• Total time is O(n log n).
• Need O(n) additional space for the merge.
• Merge sort is slower than insertion sort when n
<= 15 (approximately). So define a small instance
to be an instance with n <= 15.
• Sort small instances using insertion sort.
• Start with segment size = 15.
 Natural Merge Sort
• Initial sorted segments are the naturally ocurring
sorted segments in the input.
• Input = [8, 9, 10, 2, 5, 7, 9, 11, 13, 15, 6, 12, 14].
• Initial segments are:
[8, 9, 10] [2, 5, 7, 9, 11, 13, 15] [6, 12, 14]
• 2 (instead of 4) merge passes suffice.
• Segment boundaries have a[i] > a[i+1].
 Quick Sort
• Small instance has n <= 1. Every small instance is a
sorted instance.
• To sort a large instance, select a pivot element from out
of the n elements.
• Partition the n elements into 3 groups left, middle and
right.
• The middle group contains only the pivot element.
• All elements in the left group are <= pivot.
• All elements in the right group are >= pivot.
• Sort left and right groups recursively.
• Answer is sorted left group, followed by middle group
followed by sorted right group.
 Example

6 2 8 5 11 10 4 1 9 7 3

Use 6 as the pivot.

2 5 4 1 3 6 7 9 10 11 8

Sort left and right groups recursively.

 Choice Of Pivot

• Pivot is leftmost element in list that is to be sorted.

 When sorting a[6:20], use a[6] as the pivot.
 Text implementation does this.
• Randomly select one of the elements to be sorted
as the pivot.
 When sorting a[6:20], generate a random number r in
the range [6, 20]. Use a[r] as the pivot.
 Choice Of Pivot
• Median-of-Three rule. From the leftmost, middle,
and rightmost elements of the list to be sorted,
select the one with median key as the pivot.
 When sorting a[6:20], examine a[6], a[13] ((6+20)/2),
and a[20]. Select the element with median (i.e., middle)
key.
 If a[6].key = 30, a[13].key = 2, and a[20].key = 10,
a[20] becomes the pivot.
 If a[6].key = 3, a[13].key = 2, and a[20].key = 10, a[6]
becomes the pivot.
 Choice Of Pivot

 If a[6].key = 30, a[13].key = 25, and a[20].key = 10,

a[13] becomes the pivot.
• When the pivot is picked at random or when the
median-of-three rule is used, we can use the quick
sort code of the text provided we first swap the
leftmost element and the chosen pivot.
swap

pivot
 Partitioning Example Using
Additional Array
a 6 2 8 5 11 10 4 1 9 7 3

b 2 5 4 1 3 6 7 9 10 11 8

Sort left and right groups recursively.

 In-Place Partitioning Example
a 6 2 8 5 11 10 4 1 9 7 3

a 6 2 3 5 11 10 4 1 9 7 8

a 6 2 3 5 1 10 4 11 9 7 8

a 6 2 3 5 1 4 10
10 11 9 7 8

bigElement is not to left of smallElement,

terminate process. Swap pivot and smallElement.
a 4 2 3 5 1 64 10 11 9 7 8
 Complexity
• O(n) time to partition an array of n elements.
• Let t(n) be the time needed to sort n elements.
• t(0) = t(1) = c, where c is a constant.
• When t > 1,
t(n) = t(|left|) + t(|right|) + dn,
where d is a constant.
• t(n) is maximum when either |left| = 0 or |right| =
0 following each partitioning.
 Complexity
• This happens, for example, when the pivot is
always the smallest element.
• For the worst-case time,
t(n) = t(n-1) + dn, n > 1
• Use repeated substitution to get t(n) = O(n2).
• The best case arises when |left| and |right| are
equal (or differ by 1) following each partitioning.
• For the best case, the recurrence is the same as
for merge sort.
 Complexity Of Quick Sort
• So the best-case complexity is O(n log n).
• Average complexity is also O(n log n).
• To help get partitions with almost equal size,
change in-place swap rule to:
 Find leftmost element (bigElement) >= pivot.
 Find rightmost element (smallElement) <= pivot.
 Swap bigElement and smallElement provided
bigElement is to the left of smallElement.
• O(n) space is needed for the recursion stack. May
be reduced to O(log n) (see Exercise 18.22).
 Complexity Of Quick Sort

• To improve performance, define a small instance

to be one with n <= 15 (say) and sort small
instances using insertion sort.
 C++ STL sort Function

• Quick sort.
 Switch to heap sort when number of subdiviions
exceed some constant times log2n.
 Switch to insertion sort when segment size becomes
small.
 C++ STL stable_sort Function

• Merge sort is stable (relative order of elements

with equal keys is not changed).
• Quick sort is not stable.
• STL’s stable_sort is a merge sort that switches to
insertion sort when segment size is small.
 Rank
Rank of an element is its position in ascending key
order.
[2,6,7,8,10,15,18,20,25,30,35,40]
rank(2) = 0
rank(15) = 5
rank(20) = 7
 Selection Problem
• Given n unsorted elements, determine the
k’th smallest element. That is, determine the
element whose rank is k-1.
• Applications
 Median score on a test.
• k = ceil(n/2).
 Median salary of Computer Scientists.
 Identify people whose salary is in the bottom
10%. First find salary at the 10% rank.
 Selection By Sorting

• Sort the n elements.

• Pick up the element with desired rank.
• O(n log n) time.
 D&C Selection Example
Find kth element of:
a 3 2 8 0 11 10 1 2 9 7 1

Use 3 as the pivot and partition.

a 1 2 1 0 2 34 10 11 9 7 8

rank(pivot) = 5. So pivot is the 6’th

smallest element.
 D&C Selection Example
a 1 2 1 0 2 34 10 11 9 7 8

• If k = 6 (k-1 = rank(pivot)), pivot is the

element we seek.
• If k < 6 (k-1 < rank(pivot)), find k’th
smallest element in left partition.
• If k > 6 (k-1 > rank(pivot)), find (k-
rank(pivot)-1)’th smallest element in right
partition.
 Time Complexity
• Worst case arises when the partition to be
searched always has all but the pivot.
 O(n2)
• Expected performance is O(n).
• Worst case becomes O(n) when the pivot is
chosen carefully.
 Partition into n/9 groups with 9 elements each
(last group may have a few more)
 Find the median element in each group.
 pivot is the median of the group medians.
 This median is found using select recursively.
 Closest Pair Of Points
• Given n points in 2D, find the pair that are
closest.
 Applications

• We plan to drill holes in a metal sheet.

• If the holes are too close, the sheet will tear during
drilling.
• Verify that no two holes are closer than a
threshold distance (e.g., holes are at least 1 inch
apart).
 Air Traffic Control

• 3D -- Locations of airplanes flying in the

neighborhood of a busy airport are known.
• Want to be sure that no two planes get closer than
a given threshold distance.
 Simple Solution

• For each of the n(n-1)/2 pairs of points,

determine the distance between the points in
the pair.
• Determine the pair with the minimum
distance.
• O(n2) time.
 Divide-And-Conquer Solution
• When n is small, use simple solution.
• When n is large
 Divide the point set into two roughly equal parts A
and B.
 Determine the closest pair of points in A.
 Determine the closest pair of points in B.
 Determine the closest pair of points such that one
point is in A and the other in B.
 From the three closest pairs computed, select the one
with least distance.
 Example

A B
• Divide so that points in A have x-coordinate
<= that of points in B.
 Example

d1

A B
• Find closest pair in A.
• Let d1 be the distance between the points in
this pair.
 Example

d1

d2

A B
• Find closest pair in B.
• Let d2 be the distance between the points in
this pair.
 Example

d1

d2

A B
• Let d = min{d1, d2}.
• Is there a pair with one point in A, the other in
B and distance < d?
 Example

A RA RB B
• Candidates lie within d of the dividing line.
• Call these regions RA and RB, respectively.
 Example

A RA RB B
• Let q be a point in RA.
• q need be paired only with those points in RB that are
within d of q.y.
 Example

q 2d
d

A RA RB B
• Points that are to be paired with q are in a d x 2d
rectangle of RB (comparing region of q).
• Points in this rectangle are at least d apart.
 Example

q 2d
d

A RA RB B
• So the comparing region of q has at most 6 points.
• So number of pairs to check is <= 6| RA | = O(n).
 Time Complexity

• Create a sorted by x-coordinate list of points.

 O(n log n) time.
• Create a sorted by y-coordinate list of points.
 O(n log n) time.
• Using these two lists, the required pairs of points
from RA and RB can be constructed in O(n) time.
• Let n < 4 define a small instance.
 Time Complexity
• Let t(n) be the time to find the closest pair (excluding the
time to create the two sorted lists).
• t(n) = c, n < 4, where c is a constant.
• When n >= 4,
t(n) = t(ceil(n/2)) + t(floor(n/2)) + an,
where a is a constant.
• To solve the recurrence, assume n is a power of 2
and use repeated substitution.
• t(n) = O(n log n).
 Dynamic Programming

• Sequence of decisions.
• Problem state.
• Principle of optimality.
• Dynamic Programming Recurrence
Equations.
• Solution of recurrence equations.
 Sequence Of Decisions

• As in the greedy method, the solution to a

problem is viewed as the result of a
sequence of decisions.
• Unlike the greedy method, decisions are not
made in a greedy and binding manner.
 0/1 Knapsack Problem
Let xi = 1 when item i is selected and let xi = 0
when item i is not selected.
n
maximize pi xi
i=1
n
subject to wi xi <= c
i=1
and xi = 0 or 1 for all i
All profits and weights are positive.
 Sequence Of Decisions

• Decide the xi values in the order x1, x2, x3, …, xn.

• Decide the xi values in the order xn, xn-1, xn-2, …,
x1.
• Decide the xi values in the order x1, xn, x2, xn-1, …
• Or any other order.
 Problem State
• The state of the 0/1 knapsack problem is given by
 the weights and profits of the available items
 the capacity of the knapsack
• When a decision on one of the xi values is made,
the problem state changes.
 item i is no longer available
 the remaining knapsack capacity may be less
 Problem State
• Suppose that decisions are made in the order x1, x2, x3,
…, xn.
• The initial state of the problem is described by the pair
(1, c).
 Items 1 through n are available (the weights, profits and n are
implicit).
 The available knapsack capacity is c.
• Following the first decision the state becomes one of the
following:
 (2, c) … when the decision is to set x1= 0.
 (2, c-w1) … when the decision is to set x1= 1.
 Problem State
• Suppose that decisions are made in the order xn, xn-1, xn-2,
…, x1.
• The initial state of the problem is described by the pair
(n, c).
 Items 1 through n are available (the weights, profits and first
item index are implicit).
 The available knapsack capacity is c.
• Following the first decision the state becomes one of the
following:
 (n-1, c) … when the decision is to set xn= 0.
 (n-1, c-wn) … when the decision is to set xn= 1.
 Principle Of Optimality
• An optimal solution satisfies the following
property:
 No matter what the first decision, the remaining
decisions are optimal with respect to the state that
results from this decision.

• Dynamic programming may be used only when

the principle of optimality holds.
 0/1 Knapsack Problem
• Suppose that decisions are made in the order x1,
x2, x3, …, xn.
• Let x1= a1, x2 = a2, x3 = a3, …, xn = an be an
optimal solution.
• If a1 = 0, then following the first decision the state
is (2, c).
• a2, a3, …, an must be an optimal solution to the
knapsack instance given by the state (2,c).
 x 1 = a1 = 0
n
maximize pi xi
i=2
n
subject to wi xi <= c
i=2
and xi = 0 or 1 for all i

• If not, this instance has a better solution b2, b3,

…, bn.
n n
pi bi > pi ai
i=2 i=2
 x 1 = a1 = 1
n
maximize pi xi
i=2
n
subject to wi xi <= c- w1
i=2
and xi = 0 or 1 for all i

• If not, this instance has a better solution b2, b3,

…, bn.
n n
pi bi > pi ai
i=2 i=2
 0/1 Knapsack Problem
• Therefore, no matter what the first decision, the
remaining decisions are optimal with respect to
the state that results from this decision.
• The principle of optimality holds and dynamic
programming may be applied.
Dynamic Programming Recurrence
• Let f(i,y) be the profit value of the optimal solution to
the knapsack instance defined by the state (i,y).
 Items i through n are available.
 Available capacity is y.
• For the time being assume that we wish to determine
only the value of the best solution.
 Later we will worry about determining the xis that yield this
maximum value.
• Under this assumption, our task is to determine f(1,c).
Dynamic Programming Recurrence
• f(n,y) is the value of the optimal solution to the
knapsack instance defined by the state (n,y).
 Only item n is available.
 Available capacity is y.
• If wn <= y, f(n,y) = pn.
• If wn > y, f(n,y) = 0.
Dynamic Programming Recurrence
• Suppose that i < n.
• f(i,y) is the value of the optimal solution to the
knapsack instance defined by the state (i,y).
 Items i through n are available.
 Available capacity is y.
• Suppose that in the optimal solution for the state
(i,y), the first decision is to set xi= 0.
• From the principle of optimality (we have
shown that this principle holds for the knapsack
problem), it follows that f(i,y) = f(i+1,y).
Dynamic Programming Recurrence
• The only other possibility for the first decision
is xi= 1.
• The case xi= 1 can arise only when y >= wi.
• From the principle of optimality, it follows that
f(i,y) = f(i+1,y-wi) + pi.
• Combining the two cases, we get
 f(i,y) = f(i+1,y) whenever y < wi.
 f(i,y) = max{f(i+1,y), f(i+1,y-wi) + pi}, y >= wi.
 Recursive Code
int f(int i, int y)
{// Return f(i, y).
if (i == n) return (y < w[n]) ? 0 : p[n];
if (y < w[i]) return f(i + 1, y);
return max(f(i + 1, y), f(i + 1, y - w[i]) + p[i]);
}
 Recursion Tree

f(1,c)

f(2,c) f(2,c-w1)

f(3,c) f(3,c-w2) f(3,c-w1) f(3,c-w1 –w2)

f(4,c) f(4,c-w3) f(4,c-w2) f(4,c-w1 –w3)

f(5,c)
f(5,c-w1 –w3 –w4)
 Time Complexity
• Let t(n) be the time required when n items are
available.
• t(0) = t(1) = a, where a is a constant.
• When t > 1,
t(n) <= 2t(n-1) + b,
where b is a constant.
• t(n) = O(2n).

Solving dynamic programming recurrences

recursively can be hazardous to run time.
 Reducing Run Time

f(1,c)

f(2,c) f(2,c-w1)

f(3,c) f(3,c-w2) f(3,c-w1) f(3,c-w1 –w2)

f(4,c) f(4,c-w3) f(4,c-w2) f(4,c-w1 –w3)

f(5,c)
f(5,c-w1 –w3 –w4)
 Integer Weights Dictionary

• Use an array fArray[][] as the dictionary.

• fArray[1:n][0:c]
• fArray[i][y] = -1 iff f(i,y) not yet computed.
• This initialization is done before the recursive method
is invoked.
• The initialization takes O(cn) time.
 No Recomputation Code
int f(int i, int y)
{
if (fArray[i][y] >= 0) return fArray[i][y];
if (i == n) {fArray[i][y] = (y < w[n]) ? 0 : p[n];
return fArray[i][y];}
if (y < w[i]) fArray[i][y] = f(i + 1, y);
else fArray[i][y] = max(f(i + 1, y),
f(i + 1, y - w[i]) + p[i]);
return fArray[i][y];
}
 Time Complexity
• t(n) = O(cn).
• Analysis done in text.
• Good when cn is small relative to 2n.
• n = 3, c = 1010101
w = [100102, 1000321, 6327]
p = [102, 505, 5]
• 2n = 8
• cn = 3030303
 Dynamic Programming
• Steps.
View the problem solution as the result of a sequence
of decisions.
Obtain a formulation for the problem state.
Verify that the principle of optimality holds.
Set up the dynamic programming recurrence
equations.
Solve these equations for the value of the optimal
solution.
 Perform a traceback to determine the optimal
solution.
 Dynamic Programming

• When solving the dynamic programming

recurrence recursively, be sure to avoid the
recomputation of the optimal value for the
same problem state.
• To minimize run time overheads, and hence
to reduce actual run time, dynamic
programming recurrences are almost always
solved iteratively (no recursion).
 0/1 Knapsack Recurrence
• If wn <= y, f(n,y) = pn.
• If wn > y, f(n,y) = 0.
• When i < n
 f(i,y) = f(i+1,y) whenever y < wi.
 f(i,y) = max{f(i+1,y), f(i+1,y-wi) + pi}, y >= wi.
• Assume the weights and capacity are integers.
• Only f(i,y)s with 1 <= i <= n and 0 <= y <= c
are of interest.
 Iterative Solution Example
• n = 5, c = 8, w = [4,3,5,6,2], p = [9,7,10,9,3]

0 1 2 3 4 5 6 7 8
f[i][y]
5
4 i
3
2
1
y
 Compute f[5][*]
• n = 5, c = 8, w = [4,3,5,6,2], p = [9,7,10,9,3]

0 1 2 3 4 5 6 7 8
f[i][y]
5 0 0 3 3 3 3 3 3 3
4 i
3
2
1
y
 Compute f[4][*]
• n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]

0 1 2 3 4 5 6 7 8
f[i][y]
5 0 0 3 3 3 3 3 3 3
4 0 0 3 3 3 3 9 9 12 i
3
2
1
y
f(i,y) = max{f(i+1,y), f(i+1,y-wi) + pi}, y >= wi
 Compute f[3][*]
• n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]

0 1 2 3 4 5 6 7 8
f[i][y]
5 0 0 3 3 3 3 3 3 3
4 0 0 3 3 3 3 9 9 12 i
3 0 0 3 3 3 10 10 13 13
2
1
y
f(i,y) = max{f(i+1,y), f(i+1,y-wi) + pi}, y >= wi
 Compute f[2][*]
• n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]

0 1 2 3 4 5 6 7 8
f[i][y]
5 0 0 3 3 3 3 3 3 3
4 0 0 3 3 3 3 9
9 12 i
3 0 0 3 3 3 10 10 13 13
2 0 0 3 8 8 11 11 13 18
1
y
f(i,y) = max{f(i+1,y), f(i+1,y-wi) + pi}, y >= wi
 Compute f[1][c]
• n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]

0 1 2 3 4 5 6 7 8
f[i][y]
5 0 0 3 3 3 3 3 3 3
4 0 0 3 3 3 3 9
9 12 i
3 0 0 3 3 3 10 10 13 13
2 0 0 3 8 8 11 11 13 18
1 18
y
f(i,y) = max{f(i+1,y), f(i+1,y-wi) + pi}, y >= wi
 Traceback
• n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]

0 1 2 3 4 5 6 7 8
f[i][y]
5 0 0 3 3 3 3 3 3 3
4 0 0 3 3 3 3 9
9 12 i
3 0 0 3 3 3 10 10 13 13
2 0 0 3 8 8 11 11 13 18
1 18
y
f[1][8] = f[2][8] => x1 = 0
 Traceback
• n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]

0 1 2 3 4 5 6 7 8
f[i][y]
5 0 0 3 3 3 3 3 3 3
4 0 0 3 3 3 3 9
9 12 i
3 0 0 3 3 3 10 10 13 13
2 0 0 3 8 8 11 11 13 18
1 18
y
f[2][8] != f[3][8] => x2 = 1
 Traceback
• n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]

0 1 2 3 4 5 6 7 8
f[i][y]
5 0 0 3 3 3 3 3 3 3
4 0 0 3 3 3 3 9
9 12 i
3 0 0 3 3 3 10 10 13 13
2 0 0 3 8 8 11 11 13 18
1 18
y
f[3][5] != f[4][5] => x3 = 1
 Traceback
• n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]

0 1 2 3 4 5 6 7 8
f[i][y]
5 0 0 3 3 3 3 3 3 3
4 0 0 3 3 3 3 9
9 12 i
3 0 0 3 3 3 10 10 13 13
2 0 0 3 8 8 11 11 13 18
1 18
y
f[4][0] = f[5][0] => x4 = 0
 Traceback
• n = 5, c = 8, w = [4,3,5,6,2], p = [9,8,10,9,3]

0 1 2 3 4 5 6 7 8
f[i][y]
5 0 0 3 3 3 3 3 3 3
4 0 0 3 3 3 3 9
9 12 i
3 0 0 3 3 3 10 10 13 13
2 0 0 3 8 8 11 11 13 18
1 18
y
f[5][0] = 0 => x5 = 0
 Complexity Of Traceback

• O(n)
 Matrix Multiplication Chains
• Multiply an m x n matrix A and an n x p matrix
B to get an m x p matrix C.
n
C(i,j) = A(i,k) * B(k,j)
k=1
• We shall use the number of multiplications as
our complexity measure.
• n multiplications are needed to compute one
C(i,j).
• mnp multiplicatons are needed to compute all
mp terms of C.
 Matrix Multiplication Chains
• Suppose that we are to compute the product X*Y*Z of
three matrices X, Y and Z.
• The matrix dimensions are:
 X:(100 x 1), Y:(1 x 100), Z:(100 x 1)
• Multiply X and Y to get a 100 x 100 matrix T.
 100 * 1 * 100 = 10,000 multiplications.
• Multiply T and Z to get the 100 x 1 answer.
 100 * 100 * 1 = 10,000 multiplications.
• Total cost is 20,000 multiplications.
• 10,000 units of space are needed for T.
 Matrix Multiplication Chains
• The matrix dimensions are:
 X:(100 x 1)
 Y:(1 x 100)
 Z:(100 x 1)
• Multiply Y and Z to get a 1 x 1 matrix T.
 1 * 100 * 1 = 100 multiplications.
• Multiply X and T to get the 100 x 1 answer.
 100 * 1 * 1 = 100 multiplications.
• Total cost is 200 multiplications.
• 1 unit of space is needed for T.
 Product Of 5 Matrices

• Some of the ways in which the product of 5 matrices

may be computed.
 A*(B*(C*(D*E))) right to left
 (((A*B)*C)*D)*E left to right
 (A*B)*((C*D)*E)
 (A*B)*(C*(D*E))
 (A*(B*C))*(D*E)
 ((A*B)*C)*(D*E)
 Find Best Multiplication Order

• Number of ways to compute the product of q

matrices is O(4q/q1.5).

• Evaluating all ways to compute the product

takes O(4q/q0.5) time.
 An Application
• Registration of pre- and post-operative 3D brain
MRI images to determine volume of removed
tumor.
3D Registration
 3D Registration
• Each image has 256 x 256 x 256 voxels.
• In each iteration of the registration algorithm, the
product of three matrices is computed at each
voxel … (12 x 3) * (3 x 3) * (3 x 1)
• Left to right computation => 12 * 3 * 3 + 12 * 3*1
= 144 multiplications per voxel per iteration.
• 100 iterations to converge.
 3D Registration
• Total number of multiplications is about 2.4 *
1011.
• Right to left computation => 3 * 3*1 + 12 * 3 * 1
= 45 multiplications per voxel per iteration.
• Total number of multiplications is about 7.5 *
1010.
• With 108 multiplications per second, time is 40
min vs 12.5 min.
 Matrix Multiplication Chains
• Determine the best way to compute the
matrix product M1x M2 x M3 x … x Mq.
• Let the dimensions of Mi be rix ri+1.
• q-1 matrix multiplications are to be done.
• Decide the matrices involved in each of
these multiplications.
 Decision Sequence

• M1x M2 x M3 x … x Mq
• Determine the q-1 matrix products in
reverse order.
 What is the last multiplication?
 What is the next to last multiplication?
 And so on.
 Problem State
• M1x M2 x M3 x … x Mq
• The matrices involved in each multiplication are a
contiguous subset of the given q matrices.
• The problem state is given by a set of pairs of the
form (i, j), i <= j.
 The pair (i,j) denotes a problem in which the matrix
product Mix Mi+1 x … x Mj is to be computed.
 The initial state is (1,q).
 If the last matrix product is (M1x M2 x … x Mk) x (Mk+1x
Mk+2 x … x Mq), the state becomes {(1,k), (k+1,q)}.
 Verify Principle Of Optimality
• Let Mij= Mi x Mi+1 x … x Mj, i <= j.
• Suppose that the last multiplication in the
best way to compute Mijis Mikx Mk+1,j for
some k, i <= k < j.
• Irrespective of what k is, a best computation
of Mijin which the last product is Mikx
Mk+1,j has the property that Mikand Mk+1,j
are computed in the best possible way.
• So the principle of optimality holds and
dynamic programming may be applied.
 Recurrence Equations
• Let c(i,j) be the cost of an optimal (best) way to
compute Mij, i <= j.
• c(1,q) is the cost of the best way to multiply the
given q matrices.
• Let kay(i,j) = k be such that the last product in
the optimal computation of Mij is Mikx Mk+1,j.
• c(i,i) = 0, 1 <= i <= q. (Mii= Mi)
• c(i,i+1) = riri+1ri+2, 1 <= i < q. (Mii+1= Mix Mi+1)
• kay(i,i+1) = i.
 c(i, i+s), 1 < s < q
• The last multiplication in the best way to
compute Mi,i+s is Mikx Mk+1,i+s for some k, i <= k
< i+s.
• If we knew k, we could claim:
c(i,i+s) = c(i,k) + c(k+1,i+s) + rirk+1ri+s+1
• Since i <= k < i+s, we can claim
c(i,i+s) = min{c(i,k) + c(k+1,i+s) + rirk+1ri+s+1}, where
the min is taken over i <= k < i+s.
• kay(i,i+s) is the k that yields above min.
 Recurrence Equations

• c(i,i+s) =
min i <= k < i+s{c(i,k) + c(k+1,i+s) +
rirk+1ri+s+1}
• c(*,*) terms on right side involve fewer matrices
than does the c(*,*) term on the left side.
• So compute in the order s = 2, 3, …, q-1.
 Recursive Implementation

• See text for recursive codes.

• Code that does not avoid recomputation of
already computed c(i,j)s runs in Omega(2q)
time.
• Code that does not recompute already computed
c(i,j)s runs in O(q3) time.
• Implement nonrecursively for best worst-case
efficiency.
 Example
• q = 4, (10 x 1) * (1 x 10) * (10 x 1) * (1 x 10)
• r = [r1,r2 ,r3,r4,r5] = [10, 1, 10, 1, 10]
1 2 3 4
1
2
3
4

c(i,j), i <= j kay(i,j), i <= j

 s=0
c(i,i) and kay(i,i) , 1 <= i <= 4 are to be computed.

0 0
0 0
0 0
0 0

c(i,j), i <= j kay(i,j), i <= j

 s=1
c(i,i+1) and kay(i,i+1) , 1 <= i <= 3 are to be
computed.

0 0
0 0
0 0
0 0

c(i,j), i <= j kay(i,j), i <= j

 s=1
• c(i,i+1) = riri+1ri+2, 1 <= i < q. (Mii+1= Mix Mi+1)
• kay(i,i+1) = i.
• r = [r1,r2 ,r3,r4,r5] = [10, 1, 10, 1, 10]

0 100 0 1
0 10 0 2
0 100 0 3
0 0

c(i,j), i <= j kay(i,j), i <= j

 s=2
• c(i,i+2) = min{c(i,i) + c(i+1,i+2) + riri+1ri+3,
c(i,i+1) + c(i+2,i+2) + riri+2ri+3}
• r = [r1,r2 ,r3,r4,r5] = [10, 1, 10, 1, 10]

0 100 0 1
0 10 0 2
0 100 0 3
0 0

c(i,j), i <= j kay(i,j), i <= j

 s=2
• c(1,3) = min{c(1,1) + c(2,3) + r1r2r4,
c(1,2) + c(3,3) + r1r3r4}
• r = [r1,r2 ,r3,r4,r5] = [10, 1, 10, 1, 10]
• c(1,3) = min{0 + 10 + 10, 100 + 0 + 100}
0 100 20 0 1 1
0 10 0 2
0 100 0 3
0 0

c(i,j), i <= j kay(i,j), i <= j

 s=2
• c(2,4) = min{c(2,2) + c(3,4) + r2r3r5,
c(2,3) + c(4,4) + r2r4r5}
• r = [r1,r2 ,r3,r4,r5] = [10, 1, 10, 1, 10]
• c(2,4) = min{0 + 100 + 100, 10 + 0 + 10}
0 100 20 0 1 1
0 10 20 0 2 3
0 100 0 3
0 0

c(i,j), i <= j kay(i,j), i <= j

 s=3
• c(1,4) = min{c(1,1) + c(2,4) + r1r2r5,
c(1,2) + c(3,4) + r1r3r5, c(1,3) + c(4,4) + r1r4r5}
• r = [r1,r2 ,r3,r4,r5] = [10, 1, 10, 1, 10]
• c(1,4) = min{0+20+100, 100+100+1000, 20+0+100}
0 100 20 120 0 1 1 1
0 10 20 0 2 3
0 100 0 3
0 0

c(i,j), i <= j kay(i,j), i <= j

 Determine The Best Way To Compute M14
• kay(1,4) = 1.
• So the last multiplication is M14 = M11 x M24.
• M11 involves a single matrix and no multiply.
• Find best way to compute M24.
0 100 20 120 0 1 1 1
0 10 20 0 2 3
0 100 0 3
0 0

c(i,j), i <= j kay(i,j), i <= j

 Determine The Best Way To Compute M24
• kay(2,4) = 3 .
• So the last multiplication is M24 = M23 x M44.
• M23 = M22 x M33.
• M44 involves a single matrix and no multiply.
0 100 20 120 0 1 1 1
0 10 20 0 2 3
0 100 0 3
0 0

c(i,j), i <= j kay(i,j), i <= j

 The Best Way To Compute M14

• The multiplications (in reverse order) are:

 M14 = M11 x M24
 M24 = M23 x M44
 M23 = M22 x M33
 Time Complexity
1 2 3 4
1 0 100 20 120
2 0 10 20 c(i,j), i <= j
3 0 100
0
4
• O(q2) c(i,j) values are to be computed, where q is the
number of matrices.
• c(i,i+s) = min i <= k < i+s{c(i,k) + c(k+1,i+s) + rirk+1ri+s+1}.
• Each c(i,j) is the min of O(q) terms.
• Each of these terms is computed in O(1) time.
• So all c(i,j) are computed in O(q3) time.
 Time Complexity
1 2 3 4
1 0 1 1 1
2 0 2 3 kay(i,j), i <= j
3 0 3
0
4

• The traceback takes O(1) time to determine

each matrix product that is to be done.
• q-1 products are to be done.
• Traceback time is O(q).
 Dynamic Programming
1. Characterize the structure (problem state) of
optimal solution
2. Recursively define the value of optimal
solution
3. Compute the value of optimal solution
• Usually done in a bottom-up manner
 All-Pairs Shortest Paths
• Given an n-vertex directed weighted graph,
find a shortest path from vertex i to vertex j
for each of the n2 vertex pairs (i,j).
2
9 6
1
5 3
9 1
1 2
7 7 4 5 1
4 8 4
2 4 7
5 16
Dijkstra’s Single Source Algorithm
• Use Dijkstra’s algorithm n times, once with
each of the n vertices as the source vertex.
2
9 6
1
5 3
9 1
1 2
7 7 4 5 1
4 8 4
2 4 7
5 16
 Performance

• Time complexity is O(n3) time.

• Works only when no edge has a cost < 0.
 Dynamic Programming Solution
• Time complexity is Q(n3) time.
• Works so long as there is no cycle whose length is <
0.
• When there is a cycle whose length is < 0, some
shortest paths aren’t finite.
 If vertex 1 is on a cycle whose length is -2, each time you
go around this cycle once you get a 1 to 1 path that is 2
units shorter than the previous one.
• Simpler to code, smaller overheads.
• Known as Floyd-Warshall’s shortest path algorithm.
 Decision Sequence

i j

• First decide the highest intermediate vertex (i.e.,

largest vertex number) on the shortest path from i
to j.
• If the shortest path is i, 2, 6, 3, 8, 5, 7, j the first
decision is that vertex 8 is an intermediate vertex
on the shortest path and no intermediate vertex is
larger than 8.
• Then decide the highest intermediate vertex on the
path from i to 8, and so on.
 Problem State
i j

• (i,j,k) denotes the problem of finding the shortest

path from vertex i to vertex j that has no
intermediate vertex larger than k. (i.e. using the set
{1, …, k} of vertices as intermediate vertices)
• (i,j,n) denotes the problem of finding the shortest
path from vertex i to vertex j (with no restrictions
on intermediate vertices).
 Cost Function
i j

• Let c(i,j,k) be the length of a shortest path from

vertex i to vertex j that has no intermediate vertex
larger than k.
 c(i,j,n)
• c(i,j,n) is the length of a shortest path from
vertex i to vertex j that has no intermediate
vertex larger than n.
• No vertex is larger than n.
• Therefore, c(i,j,n) is the length of a shortest
path from vertex i to vertex j.
2
9 6
1
5 3
9 1
1 2
7 7 4 5 1
4 8 4
2 4 7
5 16
 c(i,j,0)
• c(i,j,0) is the length of a shortest path from vertex i
to vertex j that has no intermediate vertex larger
than 0.
 Every vertex is larger than 0.
 Therefore, c(i,j,0) is the length of a single-edge path
from vertex i to vertex j.
2
9 6
1
5 3
9 1
1 2
7 7 4 5 1
4 8 4
2 4 7
5 16
 Recurrence For c(i,j,k), k > 0
• The shortest path from vertex i to vertex j that has
no intermediate vertex larger than k may or may
not go through vertex k.
• If this shortest path does not go through vertex k,
the largest permissible intermediate vertex is k-1.
So the path length is c(i,j,k-1).

<k
i j
 Recurrence For c(i,j,k) ), k > 0
• Shortest path goes through vertex k.
k
i j

• We may assume that vertex k is not repeated

because no cycle has negative length.
• Largest permissible intermediate vertex on i to k
and k to j paths is k-1.
 Recurrence For c(i,j,k) ), k > 0

k
i j

• i to k path must be a shortest i to k path that

goes through no vertex larger than k-1.
• If not, replace current i to k path with a shorter
path from i to k to get an even shorter i to j path.
 Recurrence For c(i,j,k) ), k > 0

k
i j

• Similarly, k to j path must be a shortest k to j

path that goes through no vertex larger than k-1.
• Therefore, length of i to k path is c(i,k,k-1), and
length of k to j path is c(k,j,k-1).
• So, c(i,j,k) = c(i,k,k-1) + c(k,j,k-1).
 Recurrence For c(i,j,k) ), k > 0

i j

• Combining the two equations for c(i,j,k), we get

• c(i, j, k-1) if shortest i to j path doesn’t pass through k
• c(i, k, k-1)+ c(k, j, k-1) if shortest i to j path passes through k
• c(i,j,k) = min{c(i,j,k-1), c(i,k,k-1) + c(k,j,k-1)}.
• Reminder: c(i,j,0) is the length of a single-edge path from vertex i to vertex j.

• We may compute the c(i,j,k)s in the order k = 1,

2, 3, …, n.
 Floyd’s Shortest Paths Algorithm
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
c(i,j,k) = min{c(i,j,k-1),
c(i,k,k-1) + c(k,j,k-1)};
• Time complexity is O(n3).
 More precisely Q(n3).
 Q(n3) space is needed for c(*,*,*).
 Space Reduction
• c(i,j,k) = min{c(i,j,k-1), c(i,k,k-1) + c(k,j,k-1)}
• When neither i nor j equals k, c(i,j,k-1) is used
only in the computation of c(i,j,k).
column k

(i,j)

row k

• So c(i,j,k) can overwrite c(i,j,k-1).

 Space Reduction
• c(i,j,k) = min{c(i,j,k-1), c(i,k,k-1) + c(k,j,k-1)}
• When i equals k, c(i,j,k-1) equals c(i,j,k).
 c(k,j,k) = min{c(k,j,k-1), c(k,k,k-1) + c(k,j,k-1)}
= min{c(k,j,k-1), 0 + c(k,j,k-1)}
= c(k,j,k-1)
• So, when i equals k, c(i,j,k) can overwrite
c(i,j,k-1).
• Similarly when j equals k, c(i,j,k) can overwrite
c(i,j,k-1).
• So, in all cases c(i,j,k) can overwrite c(i,j,k-1).
 Floyd’s Shortest Paths Algorithm
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
c(i,j) = min{c(i,j), c(i,k) + c(k,j)};

 Initially, c(i,j) = c(i,j,0).

 Upon termination, c(i,j) = c(i,j,n).
 Time complexity is Q(n3).
 Q(n2) space is needed for c(*,*).
 Building The Shortest Paths
• Let kay(i,j) be the largest vertex on the shortest
path from i to j.
• Initially, kay(i,j) = 0 (shortest path has no
intermediate vertex).

for (int k = 1; k <= n; k++)

for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (c(i,j) > c(i,k) + c(k,j))
{kay(i,j) = k; c(i,j) = c(i,k) + c(k,j);}
 Example
2
9 6
1
5 3
9 1
1 2
7 7 4 5 1
4 8 4
2 4 7
5 16
- 7 5 1 - - - -
- - - - 4 - - -
- 7 - - 9 9 - -
- 5 - - - - 16 - Initial Cost Matrix
- - - 4 - - - 1 c(*,*) = c(*,*,0)
- - - - - - 1 -
2 - - - - - - 4
- - - - - 2 4 -
Final Cost Matrix c(*,*) = c(*,*,n)
0 6 5 1 10 13 14 11
10 0 15 8 4 7 8 5
12 7 0 13 9 9 10 10
15 5 20 0 9 12 13 10
6 9 11 4 0 3 4 1
3 9 8 4 13 0 1 5
2 8 7 3 12 6 0 4
5 11 10 6 15 2 3 0
kay Matrix
04004885
80850885
70050065
80802885
84800880
77777007
04114800
77777060
 Shortest Path

2
9 6
1
5 3
9 1
1 2
7 7 4 5 1
4 8 4
2 4 7
5 16

Shortest path from 1 to 7.

Path length is 14.
 Build A Shortest Path
04004885 • The path is 1 4 2 5 8 6 7.
80850885 • kay(1,7) = 8
70050065
1 8 7
80802885
• kay(1,8) = 5
84800880 1 5 8 7
77777007 • kay(1,5) = 4
04114800
1 4 5 8 7
77777060
 Build A Shortest Path
04004885 • The path is 1 4 2 5 8 6 7.
80850885 1 4 5 8 7
70050065 • kay(1,4) = 0
80802885 14 5 8 7
84800880 • kay(4,5) = 2
77777007 14 2 5 8 7
04114800 • kay(4,2) = 0
77777060 14 2 5 8 7
 Build A Shortest Path
04004885 • The path is 1 4 2 5 8 6 7.
80850885 14 2 5 8 7
70050065 • kay(2,5) = 0
80802885 14 25 8 7
84800880 • kay(5,8) = 0
77777007 14 258 7
• kay(8,7) = 6
04114800
14 258 6 7
77777060
 Build A Shortest Path
04004885 • The path is 1 4 2 5 8 6 7.
80850885 14 258 6 7
70050065
• kay(8,6) = 0
80802885
14 2586 7
84800880
• kay(6,7) = 0
77777007
14 25867
04114800
77777060
 Output A Shortest Path

void outputPath(int i, int j)

{// does not output first vertex (i) on path
if (i == j) return;
if (kay[i][j] == 0) // no intermediate vertices on path
cout << j << " ";
else {// kay[i][j] is an intermediate vertex on the path
outputPath(i, kay[i][j]);
outputPath(kay[i][j], j);
}
}
 Time Complexity Of outputPath
O(number of vertices on shortest path)
 To-do challenges
• https://www.hackerrank.com/challenges/
fibonacci-modified
• https://www.hackerrank.com/challenges/
maxsubarray
• A handbook by a fellow gator on some
problems that can be solved using DP:
– https://github.com/chelseametcalf/DP
 Single-Source All-Destinations
Shortest Paths With Negative Costs

• Directed weighted graph.

• Edges may have negative cost.
• No cycle whose cost is < 0.
• Find a shortest path from a given source vertex
s to each of the n vertices of the digraph.
 Single-Source All-Destinations
Shortest Paths With Negative Costs

• Dijkstra’s O(n2) single-source greedy algorithm

doesn’t work when there are negative-cost
edges.
• Floyd’s Q(n3) all-pairs dynamic-programming
algorithm does work in this case.
 Bellman-Ford Algorithm

• Single-source all-destinations shortest paths in

digraphs with negative-cost edges.
• Uses dynamic programming.
• Runs in O(n3) time when adjacency matrices
are used.
• Runs in O(ne) time when adjacency lists are
used.
 Decision Sequence
s w v

• To construct a shortest path from the source to

vertex v, decide on the max number of edges on the
path and on the vertex that comes just before v.

• Since the digraph has no cycle whose length is < 0,

we may limit ourselves to the discovery of cycle-
free (acyclic) shortest paths.
• A path that has no cycle has at most n-1 edges.
 Problem State
s w v

• Problem state is given by (u,k), where u is the

destination vertex and k is the max number of
edges.
• (v,n-1) is the state in which we want the shortest
path to v that has at most n-1 edges.
 Cost Function
s w v

• Let d(v,k) be the length of a shortest path from the

source vertex to vertex v under the constraint that
the path has at most k edges.
• d(v,n-1) is the length of a shortest unconstrained
path from the source vertex to vertex v.
• We want to determine d(v,n-1) for every vertex v.
 Value Of d(*,0)
• d(v,0) is the length of a shortest path from the
source vertex to vertex v under the constraint that
the path has at most 0 edges.

• d(s,0) = 0.
• d(v,0) = infinity for v != s.
 Recurrence For d(*,k), k > 0

• d(v,k) is the length of a shortest path from the

source vertex to vertex v under the constraint that
the path has at most k edges.
• If this constrained shortest path goes through no
edge, then d(v,k) = d(v,0).
 Recurrence For d(*,k), k > 0
• If this constrained shortest path goes through at
least one edge, then let w be the vertex just before v
on this shortest path (note that w may be s).

s w v

• We see that the path from the source to w must be

a shortest path from the source vertex to vertex w
under the constraint that this path has at most k-1
edges.
• d(v,k) = d(w,k-1) + length of edge (w,v).
 Recurrence For d(*,k), k > 0
• d(v,k) = d(w,k-1) + length of edge (w,v).
s w v
• We do not know what w is.
• We can assert
 d(v,k) = min{d(w,k-1) + length of edge (w,v)}, where
the min is taken over all w such that (w,v) is an edge of
the digraph.
• Combining the two cases considered yields:
 d(v,k) = min{d(v,0),
min{d(w,k-1) + length of edge (w,v)}}
 Pseudocode To Compute d(*,*)
// initialize d(*,0)
d(s,0) = 0;
d(v,0) = infinity, v != s;
// compute d(*,k), 0 < k < n
for (int k = 1; k < n; k++)
{
d(v,k) = d(v,0), 1 <= v <= n;
for (each edge (u,v))
d(v,k) = min{d(v,k), d(u,k-1) + cost(u,v)}
}
 p(*,*)

• Let p(v,k) be the vertex just before vertex v

on the shortest path for d(v,k).
• p(v,0) is undefined.
• Used to construct shortest paths.
 Example
1
-6 6
1
3 2
4 6
7
5 3
3
4 5
9

Source vertex is 1.
 Example
1
-6 6
1
3 2
4 6
7
5 3
3
4 5
9
1 2 3 4 5 6 v
0 0 - - - - - - - - - - - k
1 0 3 - 7 - - - 1 - 1 - -
2 0 3 7 7 16 8 - 1 2 1 4 4
3 0 2 7 7 10 8 - 6 2 1 3 4
4 0 2 6 7 10 8 - 6 2 1 3 4
d(v,k) p(v.k)
 Example
1
-6 6
1
3 2
4 6
7
5 3
3
4 5
9
1 2 3 4 5 6 v
4 0 2 6 7 10 8 - 6 2 1 3 4 k
5 0 2 6 7 9 8 - 6 2 1 3 4

d(v,k) p(v.k)
 Shortest Path From 1 To 5
1
-6 6
1
3 2
4 6
7
5 3
3
4 5
9

1 2 3 4 5 6 1 2 3 4 5 6
5 0 2 6 7 9 8 - 6 2 1 3 4
d(v,5) p(v,5)
 Observations
• d(v,k) = min{d(v,0),
min{d(w,k-1) + length of edge (w,v)}}
• d(s,k) = 0 for all k.
• If d(v,k) = d(v,k-1) for all v, then d(v,j) = d(v,k-1),
for all j >= k-1 and all v.
– i.e. the shortest path uses k-1 edges
• If we stop computing as soon as we have a d(*,k)
that is identical to d(*,k-1) the run time becomes
 O(n3) when adjacency matrix is used.
 O(ne) when adjacency lists are used.
 Observations
• The computation may be done in-place.
d(v) = min{d(v), min{d(w) + length of edge (w,v)}}
instead of
d(v,k) = min{d(v,0),
min{d(w,k-1) + length of edge (w,v)}}
• Following iteration k, d(v,k+1) <= d(v) <= d(v,k)
• On termination d(v) = d(v,n-1).
• Space requirement becomes O(n) for d(*) and
p(*).
 Applications

• Distance-vector routing protocols

– Routing Information Protocol (RIP)
– Interior Gateway Routing Protocol (IGRP)
 Edit Distance*
• How similar are two strings?
– Applications in Spell correction, computational
biology, Machine Translation, etc.
• For example:
– The user type “Graffe”
– Which is closest?
• Graf
• Graft
• Grail
• Giraffe
 Edit Distance*
• The minimum edit distance between two strings
• Editing operations are:
– Insertion
– Deletion
– Substitution

 Minimum number of editing operations to

transform one string into another
 Edit Distance*
• Sequence of edits from one string to another
 Edit Distance*
• Initial state: the word we’re transforming
• Operations: insert, delete, substitute
• Goal state: the word we’re trying to get to
• Path cost (target function to be minimized):
the number of edits
 Edit Distance*
• All edit sequences are too many
– We cannot explore all of them (brute force)
• Many paths wind up at the same state
– Keep the shortest path to each of those revisited
states
 Edit Distance*
• All edit sequences are too many
– We cannot explore all of them (brute force)
• Many paths wind up at the same state
– Keep the shortest path to each of those revisited
states
 Edit Distance*
• For two strings
– X of length n
– Y of length m
• Define d(i,j)
– The edit distance between X[1…i] and Y[1..j]
• i.e. the edit distance concerning the first i characters of X
and the first j characters of Y
– The goal state is d(n,m)
• i.e. the edit distance concerning all characters of X and all
characters of Y
 Edit Distance*
• Initialization:
– d(i,0) = i
– d(0,j) = j
• Recurrence:
For each i = 1 … N
For each j = 1 … M
d(i,j) = min { d(i-1,j) + 1,
d(i,j-1) + 1,
if X(i)==Y(j) { d(i-1,j-1) }
else {d(i-1,j-1) + 1 }
 Hard Problems

• Some problems are hard to solve.

 No polynomial time algorithm is known.
 E.g., NP-hard problems such as machine scheduling,
bin packing, 0/1 knapsack.
• Is this necessarily bad?
• Data encryption relies on difficult to solve
problems.
 Reminder: NP-hard Problems
• Infamous class of problems for which no one
has developed a polynomial time algorithm.
• That is, no algorithm whose complexity is
O(nk) for any constant k is known for any NP-
hard problem.
• The class includes thousands of real-world
problems.
• Highly unlikely that any NP-hard problem can
be solved by a polynomial time algorithm.
 Reminder: NP-hard Problems
• Since even polynomial time algorithms with
degree k > 3 (say) are not practical for large n,
we must change our expectations of the
algorithm that is used.
• Usually develop fast heuristics for NP-hard
problems.
 Algorithm that gives a solution close to best.
 Approximation algorithms
 Runs in acceptable amount of time.
• LPT rule is a good heuristic for minimum finish
time scheduling.
NP (non-deterministic polynomial-time)
 Cryptography

encryption
message encryption key
algorithm

Transmission
Channel

decryption
decryption key message
algorithm
 Public Key Cryptosystem (RSA)

• A public encryption method that relies on a public

encryption algorithm, a public decryption algorithm, and
a public encryption key.
• Using the public key and encryption algorithm, everyone
can encrypt a message.
• The decryption key is known only to authorized parties.
• Asymmetric method.
– Encryption and decryption keys are different; one is not easily
computed from the other.
 Public Key Cryptosystem (RSA)
• p and q are two prime numbers.
• n = pq
• m = (p-1)(q-1)
• a is such that 1 < a < m and gcd(m,a) = 1.
• b is such that (ab) mod m = 1.
• a is computed by generating random positive
integers and testing gcd(m,a) = 1 using the
extended Euclid’s gcd algorithm.
• The extended Euclid’s gcd algorithm also
computes b when gcd(m,a) = 1.
 RSA Encryption And Decryption

• Message M < n.
• Encryption key = (a,n).
• Decryption key = (b,n).
• Encrypt => E = Ma mod n.
• Decrypt => M = Eb mod n.
 Breaking RSA

• Factor n and determine p and q, n = pq.

• Now determine m = (p-1)(q-1).
• Now use Euclid’s extended gcd algorithm to
compute gcd(m,a). b is obtained as a byproduct.
• The decryption key (b,n) has been determined!
• No polynomial-time method for factoring large integers
on a classical computer has yet been found, but it has not
been proven that none exists. *
 Security Of RSA

• Relies on the fact that prime factorization is

computationally very hard.
• Let q be the number of bits in the binary
representation of n.
• No algorithm, polynomial in q, is known to find
the prime factors of n.
• Try to find the factors of a 100 bit number.
 Elliptic Curve Cryptography
(ECC)
• Asymmetric Encryption Method
– Encryption and decryption keys are different; one is not
easily computed from the other.
• Relies on difficulty of computing the discrete
logarithm problem for the group of an elliptic
curve over some finite field.
– Galois field of size a power of 2.
– Integers modulo a prime.
• 1024-bit RSA ~ 200-bit ECC (cracking difficulty).
• Faster to compute than RSA?
Data Encryption Standard (DES)

• Used for password encryption.

• Encryption and decryption keys are the same,
and are secret. (Symmetric encryption)
• Relies on the computational difficulty of the
satisfiability problem.
• The satisfiability problem is NP-hard.
 Satisfiability Problem

• F = (x1+ x2 + x3)( x4+ x7 + x8)(x2+ x5)

• F is true when x1, x2, and x4 (for e.g.) are true.

 Other Problems

• Partition
 Partition n positive integers s1, s2, s3, …, sn into
two groups A and B such that the sum of the
numbers in each group is the same.
 [9, 4, 6, 3, 5, 1,8]
 A = [9, 4, 5] and B = [6, 3, 1, 8]
• NP-hard.
 Subset Sum Problem

• Does any subset of n positive integers s1, s2,

s3, …, sn have a sum exactly equal to c?
• [9, 4, 6, 3, 5, 1,8] and c = 18
• A = [9, 4, 5]
• NP-hard.
Traveling Salesperson Problem (TSP)
• Let G be a weighted directed graph.
• A tour in G is a cycle that includes every vertex
of the graph.
• TSP => Find a tour of shortest length.
• Problem is NP-hard.
 Applications Of TSP

Home city
Visit city
Applications Of TSP

Robot Station
 Applications Of TSP
• Manufacturing.
• A robot arm is used to drill n holes in a metal
sheet.
Robot Station

n+1 vertex TSP.

 n-Queens Problem
A queen that is placed on an n x n chessboard,
may attack any piece placed in the same
column, row, or diagonal.

8x8 Chessboard
 n-Queens Problem
Can n queens be placed on an n x n
chessboard so that no queen may attack
another queen?

4x4
n-Queens Problem

8x8
 Difficult Problems

• Many require you to find either a subset or

permutation that satisfies some constraints
and (possibly also) optimizes some
objective function.
• May be solved by organizing the solution
space into a tree and systematically
searching this tree for the answer.
 Subset Problems
• Solution requires you to find a subset of n
elements.
• The subset must satisfy some constraints and
possibly optimize some objective function.
• Examples.
 Partition.
 Subset sum.
 0/1 Knapsack.
 Satisfiability (find subset of variables to be set to true
so that formula evaluates to true).
 Scheduling 2 machines.
 Packing 2 bins.
 Permutation Problems
• Solution requires you to find a permutation of n
elements.
• The permutation must satisfy some constraints and
possibly optimize some objective function.
• Examples.
 TSP.
 n-queens.
Each queen must be placed in a different row and different
column.
Let queen i be the queen that is going to be placed in row i.
Let ci be the column in which queen i is placed.
c1, c2, c3, …, cn is a permutation of [1,2,3, …, n] such that no
two queens attack.
 Solution Space
• Set that includes at least one solution to the
problem.
• Subset problem.
 n = 2, {00, 01, 10, 11}
 n = 3, {000, 001, 010, 100, 011, 101, 110, 111}
• Solution space for subset problem has 2n members.
• Nonsystematic search of the space for the answer
takes O(p2n) time, where p is the time needed to
evaluate each member of the solution space.
 Solution Space
• Permutation problem.
 n = 2, {12, 21}
 n = 3, {123, 132, 213, 231, 312, 321}
• Solution space for a permutation problem has n!
members.
• Nonsystematic search of the space for the answer
takes O(pn!) time, where p is the time needed to
evaluate a member of the solution space.
Backtracking And Branch And Bound
 Subset & Permutation Problems
• Subset problem of size n.
 Nonsystematic search of the space for the answer takes
O(p2n) time, where p is the time needed to evaluate
each member of the solution space.
• Permutation problem of size n.
 Nonsystematic search of the space for the answer takes
O(pn!) time, where p is the time needed to evaluate
each member of the solution space.
• Backtracking and branch and bound perform a
systematic search; often taking much less time
than taken by a nonsystematic search.
Reminder: Complexity
 Tree Organization Of Solution Space
• Set up a tree structure such that the leaves
represent members of the solution space.
• For a size n subset problem, this tree structure has
2n leaves.
• For a size n permutation problem, this tree
structure has n! leaves.
• The tree structure is too big to store in memory; it
also takes too much time to create the tree
structure.
• Portions of the tree structure are created by the
backtracking and branch and bound algorithms as
needed.
 Subset Problem

• Use a full binary tree that has 2n leaves.

• At level i the members of the solution space
are partitioned by their xi values.
• Members with xi = 1 are in the left subtree.
• Members with xi = 0 are in the right subtree.
• Could exchange roles of left and right
subtree.
 Subset Tree For n = 4

x1=1 x1= 0

x2=1 x2= 0 x2=1 x 2= 0

x3=1 x3= 0

x4=1 x4=0

1110 1011 0111 0001

 Permutation Problem

• Use a tree that has n! leaves.

• At level i the members of the solution space
are partitioned by their xi values.
• Members (if any) with xi = 1 are in the first
subtree.
• Members (if any) with xi = 2 are in the next
subtree.
• And so on.
 Permutation Tree For n = 3

x1=1 x1= 3
x1=2

x2= 2 x2= 3 x2= 1 x2= 3 x2= 1 x 2= 2

x3=3 x3=2 x3=3 x3=1 x3=2 x3=1

123 132 213 231 312 321

 Backtracking

• Search the solution space tree in a depth-

first manner.
• May be done recursively or use a stack to
retain the path from the root to the current
node in the tree.
• The solution space tree exists only in your
mind, not in the computer.
 Backtracking
• The backtracking algorithm enumerates a
set of partial candidates that, in principle,
could be completed in various ways to give
all the possible solutions to the given
problem.
• Backtracking is a Swiss army knife
– Most problems where you can't find another
solution for, are solved by backtracking
 Backtracking Depth-First Search

x1=1 x1= 0

x2=1 x2= 0 x2=1 x 2= 0

 Backtracking Depth-First Search

x1=1 x1= 0

x2=1 x2= 0 x2=1 x 2= 0

 Backtracking Depth-First Search

x1=1 x1= 0

x2=1 x2= 0 x2=1 x 2= 0

 Backtracking Depth-First Search

x1=1 x1= 0

x2=1 x2= 0 x2=1 x 2= 0

 Backtracking Depth-First Search

x1=1 x1= 0

x2=1 x2= 0 x2=1 x 2= 0

 O(2n) Subet Sum & Bounding Functions
{10, 5, 2, 1}, c = 14

x1=1 x1= 0

x2=1 x2= 0 x2=1 x 2= 0

Each forward and backward move takes O(1) time.

 Bounding Functions
• When a node that represents a subset whose sum
equals the desired sum c, terminate.
• When a node that represents a subset whose sum
exceeds the desired sum c, backtrack. I.e., do not
enter its subtrees, go back to parent node.
• Keep a variable r that gives you the sum of the
numbers not yet considered. When you move to a
right child, check if current subset sum + r >= c.
If not, backtrack.
 Backtracking
• Space required is O(tree height).
• With effective bounding functions, large instances
can often be solved.
• For some problems (e.g., 0/1 knapsack), the
answer (or a very good solution) may be found
quickly but a lot of additional time is needed to
complete the search of the tree.
• Run backtracking for as much time as is feasible
and use best solution found up to that time.
 Branch And Bound
• Search the tree using a breadth-first search (FIFO
branch and bound).
• Search the tree as in a bfs, but replace the FIFO
queue with a stack (LIFO branch and bound).
• Replace the FIFO queue with a priority queue
(least-cost (or max priority) branch and bound).
The priority of a node p in the queue is based on
an estimate of the likelihood that the answer node
is in the subtree whose root is p.
 Branch And Bound
• Space required is O(number of leaves).
• For some problems, solutions are at different
levels of the tree (e.g., 16 puzzle).

4 14 1 1 2 3 4
13 2 3 12 5 6 7 8
6 11 5 10 9 10 11 12
9 8 7 15 13 14 15
 Branch And Bound
 FIFO branch and bound finds solution closest to root.
 Backtracking may never find a solution because tree
depth is infinite (unless repeating configurations are
eliminated).
• Least-cost branch and bound directs the search to
parts of the space most likely to contain the
answer. So it could perform better than
backtracking.
 Branch And Bound
• maintain provable lower and upper bounds on
global objective value
– terminate with certificate proving epsilon–sub
optimality
• rely on two subroutines that (efficiently) compute
a lower and an upper bound on the optimal value
over a given region of search space
• often slow; exponential worst case performance