KECE208

Data Structures and Algorithms

- Algorithm Design Techniques -

담당교수: 황 인준

School of Electrical Engineering

Korea University

2020-11-25 Weiss, Data Structures & Alg's 1

 Algorithm Design Types
1. Greedy Algorithms

2. Divide and Conquer

3. Dynamic Programming

4. Randomized Algorithms

5. Backtracking Algorithms

2
 Extended Binary Tree
• Augment binary tree with a special “square”
node at every place there is a null link: external
node
• Every binary tree with n nodes has n+1 null links.
• Every binary tree with n nodes has n+1 external
nodes.
• External (Internal) path length E(I)of a binary
tree is the sum of the lengths of the paths from
the root to all external (internal) nodes

3
 Extended Binary Tree

internal node
I=0+1+1+2+3=7
E = 2 + 2 + 2 + 3 + 4 + 4 = 17 external node

4
 Properties
• The internal and external path lengths I and E of
a binary tree with n internal nodes are related by
the formula E = I +2n.

• It follows that binary trees with the maximum E

also have maximum I.

• Question: Over all binary trees with n internal

nodes, what is the maximum and minimum
possible values for I ?

5
 Properties
• The worst case is when the tree is
n-1
I = ∑ i = n*(n-1) / 2
i=0

6
 Properties
• For minimum I, put as many internal nodes
as close to the root as possible.

0 + 2 * 1 + 4 * 2 + 8 * 3 + ...
n
→ ∑ |log k| = O(n*logn)
1

• One such example: Complete binary tree

7
 Weighted External Path Length
• From a set of n +1 positive weights q1,q2,...,
qn+1, each of the n +1 external nodes in a
binary tree is associated with one of the weights.

• Weighted External Path Length

n+1
WE = ∑ qi * ki
1

where ki is the distance from the root node to

the external node with weight qi

8
 Example

15

5 2 4 5 15

2 4

WE = 2*3 +4*3+5*2+15*1 WE = 2*2 +4*2+5*2+15*2

= 43 = 52

9
 Application
• An optimal set of codes for messages M1,...,
Mn+1 to transmit the corresponding messages.
• At the receiving end, the code will be decoded
using a decode tree.
• A decode tree is a binary tree in which external
nodes represent messages
• The binary bits in the codes determine the
branching needed at each level of the decode
tree to reach the correct external node.

10
 Decode tree
• Codes for messages
M1 : 000
0 1 M2 : 001
M3 : 01 Huffman codes
M4
0 1 M4 : 1

M3 • The cost of decoding a code word

0 1
is proportional to the number of
bits in the code
M1 M2
• Is equal to the distance of the
corresponding external node from
the root node.

11
 Problem Formalism
• Assume qi is the relative frequency with which
message Mi will be transmitted, then the
expected decode time is
n+1
T = ∑ qi * di
1

where di is the distance of the external node

for the message Mi from the root node
• The expected decode time is minimized by
choosing code words resulting in a decode tree
with minimal weighted external path length

12
 Algorithm
procedure HUFFMAN (L, n) {
//L is a list of n single node binary trees
for i = 1 to n-1 do {
GETNODE(T); //create a new binary tree by
LCHILD(T) ← LEAST(L); //combining the trees with
RCHILD(T) ← LEAST(L); //the two smallest weights
WT(T) ← WT(LCHILD(T)) + WT(RCHILD(T));
INSERT (L, T)
}
}

13
 Example
q1 = 2, q2 = 3, q3 = 5, q4 = 7, q5 = 9, and q6 = 13

5 10 16 23

2 3 5 5 7 9 10 13

2 3 5 5

2 3

14
 Approximate Bin Packing
• Solve the bin packing problem
• Run quickly but will not necessarily produce
optimal solutions
• The solutions are not too far from optimal

2020-11-25 Weiss, Data Structures & Alg's 15

 Approximate Bin Packing
• Input
N items of size s1, s2, …, sN where 0<si≤ 1

• Goal
Pack the items in the fewest no. of bins.

2020-11-25 Weiss, Data Structures & Alg's 16

 Optimal Packing
• 7 items with sizes 0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8

Fig 10.20 Optimal packing

2020-11-25 Weiss, Data Structures & Alg's 17

 Bin Packing Algorithm
• Two versions
– On-line bin packing : each item must be placed
in a bin before the next item can be processed
and the decision can’t be changed

– Off-line bin packing: it is not necessary to do

anything until all the input has been read

2020-11-25 Weiss, Data Structures & Alg's 18

 On-line Algorithms
• An on-line algorithm cannot always give an
optimal solution.
• Theorem: There are inputs that force any
on-line bin packing algorithm to use at least
4/3 the optimal number of bins.
• Three simple algorithms that guarantee that
the number of bins used is no more than
twice optimal.

2020-11-25 Weiss, Data Structures & Alg's 19

 Next Fit
• Probably the simplest algorithm
• When processing any item, check whether it fits
in the same bin as the last item.
– If it does, it is placed there
– Otherwise, a new bin is created.

2020-11-25 Weiss, Data Structures & Alg's 20

 Next fit
• 7 items with sizes 0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8

Fig 10.21 Using Next fit

2020-11-25 Weiss, Data Structures & Alg's 21

 Next Fit
• (Theorem10.2) Let M be the optimal number of
bins required to pack a list I of items. Then next
fit never uses more than 2M bins. There exist
sequences such that next fit uses 2M – 2 bins.

2020-11-25 Weiss, Data Structures & Alg's 22

 Example for Theorem 10.2

Fig 10.22 Optimal packing for 0.5, 2/N, 0.5, 2/N,…

where N is divisible by 4
2020-11-25 Weiss, Data Structures & Alg's 23
 Example for Theorem 10.2

Fig 10.23 Next fit packing for 0.5, 2/N, 0.5, 2/N,…

2020-11-25 Weiss, Data Structures & Alg's 24

 First Fit
• To scan the bins in order and place the new
item in the first bin that is large enough to
hold it.
• A new bin is created only when the results
of previous placements have left no other
alternative.
• Processing each item by scanning down
the list of bins sequentially, which would
take O (N 2)

2020-11-25 Weiss, Data Structures & Alg's 25

 First Fit
• Items with sizes 0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8

Fig 10.24 Using First fit (4 bins)

2020-11-25 Weiss, Data Structures & Alg's 26

 First Fit
(Theorem 10.3)
Let M be the optimal number of bins required to
pack a list I of items. Then first fit never uses
more than [17/10* M] bins. There exist sequences
such that first fit uses 17/10(M-1) bins.

(Ex) The input consists of 6M items of size 1/7+e,

followed by 6M items of size 1/3+e, followed by
6M items of size ½+e. One simple packing places
one item of each size in a bin and requires 6M
bins.

2020-11-25 Weiss, Data Structures & Alg's 27

 First Fit: Worst Case

Fig 10.25 A case where FF uses 10M

bins instead of 6M
2020-11-25 Weiss, Data Structures & Alg's 28
 Best Fit
• Instead of placing a new item in the first spot
that is found, it is placed in the tightest spot
among all bins.
• Even though we make a more educated choice
of bins, the generic bad cases are the same
• Best fit is never more than roughly 1.7 times as
bad as optimal.

2020-11-25 Weiss, Data Structures & Alg's 29

 Best Fit
• Items with sizes 0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8

Fig 10.26 Best Fit

2020-11-25 Weiss, Data Structures & Alg's 30

 Off-line Algorithms
• Can view the entire item list before producing
an answer.
• All the on-line algorithms have difficulty in
packing the large items, especially when they
occur later in the input.
• This can be solved by sorting the items and
placing the largest items first.
• We can then apply first fit or best fit, yielding
first fit decreasing and best fit decreasing,
respectively.

2020-11-25 Weiss, Data Structures & Alg's 31

 First Fit Decreasing
• Items with sizes 0.8, 0.7, 0.5, 0.4, 0.3, 0.2, 0.1

• Optimal, but not true in general.

2020-11-25 Weiss, Data Structures & Alg's 32
 Dynamic Programming
• A problem that can be mathematically
expressed recursively can also be expressed as
a recursive algorithm.
• In case a recursive algorithm is not efficient,
the recursive algorithm can be rewritten as a
non-recursive algorithm that systematically
records the answers to the subproblems in a
table.
• Dynamic programming makes use of this
approach.

2020-11-25 Weiss, Data Structures & Alg's 33

 Inefficient Fibonacci Algorithm

2020-11-25 Weiss, Data Structures & Alg's 34

 Linear Fibonacci Algorithm

2020-11-25 Weiss, Data Structures & Alg's 35

 Recursive algorithm
• The recursive algorithm is slow due to repeated
function calls

FN-3 3 times / FN-4 5 times / FN-5 8 times

2020-11-25 Weiss, Data Structures & Alg's 36

 Binary Search Tree
• A binary search tree T is a binary tree; either
it is empty or each node in the tree contains
an identifier and:

1. all identifiers in the left subtree of T are less

than the identifier in the root node T;
2. all identifiers in the right subtree of T are greater
than the identifier in the root node T;
3. the left and right subtrees of T are also binary
search trees.

37
 Two Examples
if if

for while for read

read loop while

loop

Which one is more desirable in terms of search?

38
 Algorithm
procedure SEARCH(T, X, i) {
// search binary search tree T for X
i ← T;
while i ≠ 0 do {
case {
:X < IDENT(i): k ← LCHILD(i) //search left tree
:X = IDENT(i): return
:X > IDENT(i): i ← RCHILD(i) //search right tree
}
}
}

39
 Optimal Binary Search Tree
• Input: a list of words, w1, w2,…, wN, and fixed
probabilities p1, p2,…, pN of their occurrence.

• Output: A binary search tree that minimizes

the expected total access time or total no. of
comparisons required.
• Hence, the tree should minimize
n
T = ∑ pi * (1 + di )
1

where di is the depth of word wi in the tree

2020-11-25 Weiss, Data Structures & Alg's 40
 Sample Input

2020-11-25 Weiss, Data Structures & Alg's 41

 Possible BST #1
• Use a greedy approach where the word with the
highest probability was placed at the root.

if

a two

and the

am egg

2020-11-25 Weiss, Data Structures & Alg's 42

 Possible BST #1

2020-11-25 Weiss, Data Structures & Alg's 43

 Possible BST #2
• Perfectly balanced
search tree.

2020-11-25 Weiss, Data Structures & Alg's 44

 Possible BST #3

2020-11-25 Weiss, Data Structures & Alg's 45

 Comparison

2020-11-25 Weiss, Data Structures & Alg's 46

 Structure of Optimal BST
• Place sorted words wLeft, wLeft+1,…, wi,…,
wRight-1, wRight into a binary search tree.

2020-11-25 Weiss, Data Structures & Alg's 47

 Cost Formula
CLeft, Right = Left≤i≤Right
min { pi + CLeft, i-1 + Ci+1, Right
i-1 Right
+ ∑ pj + ∑ pj }
j=Left j=i+1

Right
= min { CLeft, i-1 + Ci+1, Right + ∑ pj }
Left≤i≤Right j=Left

• For each subrange of words starting from a single

word, the algorithm produces the cost and root of
the optimal BST as in the following table.

2020-11-25 Weiss, Data Structures & Alg's 48

 Computation for the sample input

on the next slide

2020-11-25 Weiss, Data Structures & Alg's 49

 Computation of table entry for am..if

2020-11-25 Weiss, Data Structures & Alg's 50

 Quiz
• Show the optimal binary search tree for the
following words, where the frequency of
occurrence is in parentheses: at (0.16), by
(0.30), for (0.18), it (0.24), or (0.12)

2020-11-25 Weiss, Data Structures & Alg's 51

2020-11-25 Weiss, Data Structures & Alg's 52