CS 350 Algorithms and Complexity
Winter 2019
Lecture 10: Divide & Conquer —
Trees and Multiplication
Andrew P. Black
Department of Computer Science
Portland State University
What is Divide-and-Conquer?
Solves a problem instance of size n by:
1. dividing it into b smaller instances, of size ~ n/b
2. solving some or all of them (in general, solving a of
them), using the same algorithm recursively.
3. combining the solutions to the a smaller problems
to get the solution to the original problem.
!2
Binary Trees
✦ The perfect data structure for divide-into-two
and conquer.
!3
Binary Trees
! Ex. 1: Classic traversals
" (preorder, inorder, postorder)
! Algorithm Inorder(T)
if T ≠ ∅ then a
Inorder(TL)
print(root of T) b c
Inorder(TR)
d e
! Efficiency: Θ(n)
! Could it be better? Worse?
!4
Binary Trees
! Ex. 2: Height of a Binary Tree
h(T) = max{h(TL), h(TR)} + 1
if T ≠ ∅ and h(∅) = -1
Efficiency: Θ(n)
!5
Summing Numbers
! Compute the sum of this array
0 1 2 3 4 5 6 7 8 9 10 11 12
15 3 19 0 21 78 46 94 97 49 57 89 91
! How can treating this as a binary tree
help us?
!6
! Build a tree +
0 10 21 32 43 54 56 67 78 89 9
10 10
11 11
12 12
15 15
3 193 019 210 21
78 78
46 46
94 94
97 97
49 49
57 57
89 89
91 91
!7
! Build a tree +
+
+
00 1010 2121 3232 4343 5454 5656 6767 7878 8989 10
9 10
910 10 11
11 11
11 12
12 12
12
15 315
15 15 33 019
3 19
19 019 21
00 21
21 21
78 78
78 78
46 46
46 46
94 94
94 94 97
97 97
97 49
49 49
49 57
57 57
57 89
89 89
89 91
91 91
91
! When does this win?
!8
Product of Numbers
! Compute the product of this array
0 1 2 3 4 5 6 7 8 9 10 11 12
15 3 19 0 21 78 46 94 97 49 57 89 91
! How can treating this as a binary tree
help us?
! What’s different with product,
compared to sum?
!9
Problem — Levitin §5.2 Q2
Exercises 4.4
1. Design a divide-and-conquer algorithm for computing the number of levels
in a binary tree. What is the efficiency class of your algorithm?
2. The following algorithm seeks to compute the number of leaves in a binary
tree.
Algorithm LeafCounter( T )
//Computes recursively the number of leaves in a binary tree
//Input: A binary tree T
//Output: The number of leaves in T
if T = ∅ return0
else returnLeafCounter (TL )+ LeafCounter (TR )
Is this algorithm correct? If it is, prove it; if it is not, make an ap-
propriate correction.
3. Prove equality (4.5) by mathematical induction.
Hint: trythe
4. Traverse it on a tree with
following onetree
binary node
a.. in preorder. b. in inorder. c. in postorder.
a !10
if T = ∅ return0
else returnLeafCounter (TL )+ LeafCounter (TR )
Problem
Is this algorithm correct? If it is, prove it; if it is not,
! Traverse
propriate this
correction. tree in pre-order:
3. Prove equality (4.5) by mathematical induction.
4. Traverse the following binary tree
a.. in preorder. b. in inorder. c. in postorder.
a A. abdecf
B. debfca
b c . C. abcdef
d e f
D. dbeacf
E. defbca
5. Write a pseudocode for one of the classic traversal algorithm
inorder, and postorder) for binary trees. Assuming that yo
!11
is recursive, find the number of recursive calls made.
if T = ∅ return0
else returnLeafCounter (TL )+ LeafCounter (TR )
Problem
Is this algorithm correct? If it is, prove it; if it is not,
! Traverse
propriate this
correction. tree inorder:
3. Prove equality (4.5) by mathematical induction.
4. Traverse the following binary tree
a.. in preorder. b. in inorder. c. in postorder.
a A. abdecf
B. debfca
b c . C. abcdef
d e f
D. dbeacf
E. defbca
5. Write a pseudocode for one of the classic traversal algorithm
inorder, and postorder) for binary trees. Assuming that yo
!12
is recursive, find the number of recursive calls made.
if T = ∅ return0
else returnLeafCounter (TL )+ LeafCounter (TR )
Problem
Is this algorithm correct? If it is, prove it; if it is not,
! Traverse
propriate this
correction. tree in post-order:
3. Prove equality (4.5) by mathematical induction.
4. Traverse the following binary tree
a.. in preorder. b. in inorder. c. in postorder.
a A. abdecf
B. debfca
b c . C. abcdef
d e f
D. dbeacf
E. defbca
5. Write a pseudocode for one of the classic traversal algorithm
inorder, and postorder) for binary trees. Assuming that yo
!13
is recursive, find the number of recursive calls made.
Karatsuba Multiplication
! The “grade school algorithm” for multiplying
n-digit numbers uses O(n2) multiplications
! Karatsuba’s algorithm uses O(nlg 3) ≅
O(n1.585) multiplications (and exactly nlg 3
when n is a power of 2)
! What’s the approximate ratio of
multiplication counts when n = 29 = 512?
A. 10 B. 13 C. 17 D. 20 E. 50
!14
Basic idea
Let x and y be represented as n-digit strings in some base B. For any
positive integer m less than n, one can write the two given numbers as:
x = x 1 B m + x0 y = y1 Bm + y0,
where x0 and y0 are less than Bm. The product is then
xy = (x1 Bm + x0)(y1 Bm + y0) = z2 B2m + z1 Bm + z0
where
z2 = x1y1 z1 = x1y0+ x0y1 z0 = x0y0.
These formulae require four multiplications. Karatsuba observed that xy
can be computed in only three multiplications, at the cost of a few
extra additions.
z1 = (x1 + x0)(y1 + y0) – z2 – z0
which holds because
z1 = x1y0+ x0y1
z1 = (x1 + x0)(y1 + y0) – x1y1 – x0y0.
!15
Practice
! Multiply 41 × 20:
(40 + 1) × (20 + 0)= (4×2)×100 +
(1×2 + 4×0)×10 +
(1×0)
but (1×2 + 4×0) =
(4+1)×(2+0) − (4×2) − (1×0)
! Your Turn! Multiply 53 × 67:
53 × 67 = ( × )×100 +
( × + × )×10 +
( × ) !16
! Your Turn! Multiply 53 × 67:
53 × 67 = (5×6)×100 +
(5×7 + 3×6)×10 +
(3×7)
= 30×100 +
1. 5×6=30 (5×7 + 3×6)×10 +
2. 3×7=21 21
3. 8×13=104
What is (5×7 + 3×6)? Don't spend two
multiplications to find out!
A. 35 B. 63 C. 53 D. 74
!17
You put the pieces together:
4153 × 2067
= (41×20) ×10000
+ [(41+53)(20+67) − 41×20 − 53×67]×100
+ (53×67)2
Answer:
A. 858471 B. 8485251 C. 8584251
D. None of the above
!18
Strassen’s Algorithm
! Three big ideas:
1. You can split a matrix into blocks and
operate on the resulting matrix of blocks
like you would on a matrix of numbers.
2. The blocks necessary to express the result
of 2x2 block matrix multiplication have
enough common factors to allow computing
them in fewer multiplications than the
original formula implies.
3. Recursion.
!19
10 00 +Strassen’s
7. Apply 11 10 algorithm to compute
A B
1 + 3 2 + 6 =1 ( 000 +2 111 )( 00 + 011 )1+ 000 ( 101 11 ) ( 10 +
11 ) 00 + ( 10 00 )( 00
4 +1 01 )1 = 0 2 1 0 4
C=
00 00 + 11 00 + 00 11 + 0 111 113+ 000 01 002 110 1 001
10 11 00 + 10 00
00 00 + 10 01 00 015 0 2 1 1 3 5 0
= 10 01 + 11 11
exiting the recursion when = 2 i.e., computing the products of 2-by-2
matrices
7. For by the given,
the matrices brute-force algorithm.
Strassen’s algorithm yields the following:
¸ number of additions
8. Solve the recurrence for the ¸ required¸ by Strassen’s
00 01 00 01 00 01
algorithm. =(Assume that = is a power of 2.)
10 11 10 11 10 11
9. where
V. Pan [Pan78] has discovered a divide-and-conquer matrix multiplication
algorithm that¸is based on multiplying
¸ two 70-by-70
¸ matrices using 143,640
¸
1 0
multiplications. Find=the2 asymptotic
1 0 1 of Pan’s algorithm
e ciency 3 0 (you
00 = 01 10 = 11 =
4 additions)
can ignore 1 and 1compare
0 5 0of Strassen’s algorithm.
it with that 2 1
¸ ¸ ¸ ¸
10. Practical0 implementations
1 0 of 1Strassen’s algorithm
2 0 usually switch
1 1 to the
00 = 01 = 10 = 11 =
2 method
brute-force 1 0 4 sizes become1smaller
after matrix 3 than some5 “crossover
0
point”. Run an experiment to determine such crossover point on your
Therefore,
computer system. !20
¸ ¸ ¸
00 01 10 11
2 1 0 4 1 3 5 0
Therefore,
¸ ¸ ¸
4 0 1 2 4 8
1 = ( 00 + 11 )( 00 + 11 ) = =
6 2 7 1 20 14
¸ ¸ ¸
3 1 0 1 2 4
2 = ( 10 + 11 ) 00 = =
7 1 2 1 2 8
¸ ¸ ¸
1 0 1 0 1 0
3 = 00 ( 01 11 ) = =
4 1 5 4 9 4
¸ ¸ ¸
3 0 2 1 6 3
4 = 11 ( 10 00 ) = =
2 1 1 2 3 0
¸ ¸ ¸
3 1 1 1 8 3
5 = ( 00 + 01 ) 11 = =
5 1 5 0 10 5
¸ ¸ ¸
1 1 0 2 2 3
6 = ( 10 00 )( 00 + 01 ) = =
1 1 2 5 2 3
¸ ¸ ¸
1 1 3 1 3 2
7 = ( 01 11 )( 10 + 11 ) = =
1 1 6 3 9 4
!21
Accordingly,
00 = 1+ 4 + 7
¸ 5 ¸ ¸ ¸ ¸
4 8 6 3 8 3 3 2 5 4
= + + =
20 14 3 0 10 5 9 4 4 5
01 = 3+ 5
¸ ¸ ¸
1 0 8 3 7 3
= + =
9 4 10 5 1 9
10 = 2+
¸4 ¸ ¸
2 4 6 3 8 1
= + =
2 8 3 0 5 8
11 = 1+ 3 + 6
¸ 2 ¸ ¸ ¸ ¸
4 8 1 0 2 4 2 3 3 7
= + + =
20 14 9 4 2 8 2 3 7 7
That is,
5 4 7 3
4 5 1 9
=
8 1 3 7
5 8 7 7
8. For = 2 the recurrence ( ) = 7 ( 2)+18( 2)2 for 1 (1) = 0!22
becomes
Problem
! Which tree traversal yields a sorted list
if applied to a binary search tree?
A. preorder
B. inorder
C. postorder
! Prove it!
!23
inorder, and postorder) for binary trees. Assuming that your algorithm
is recursive, find the number of recursive calls made.
Problem — Levitin §5.3 Q8
6. Which of the three classic traversal algorithms yields a sorted list if applied
to a binary search tree? Prove this property.
7. a. Draw a binary tree with ten nodes labeled.0, 1, 2, ..., 9 in such a way
that the inorder and postorder traversals of the tree yield the following
lists: 9, 3, 1, 0, 4, 2, 7, 6, 8, 5 (inorder) and 9, 1, 4, 0, 3, 6, 7, 5, 8, 2
(postorder).
b. Give an example of two permutations of the same n labels 0, 1, 2, .., n−1
that cannot be inorder and postorder traversal lists of the same binary tree.
c. Design an algorithm that constructs a binary tree for which two given
lists of n labels 0, 1, 2, .., n − 1are generated by the inorder and postorder
traversals of the tree. Your algorithm should also identify inputs for which
the problem has no solution.
25
!24
inorder, and postorder) for binary trees. Assuming that your algorithm
is recursive, find the number of recursive calls made.
Problem — Levitin §5.3 Q8
6. Which of the three classic traversal algorithms yields a sorted list if applied
to a binary search tree? Prove this property.
7. a. Draw a binary tree with ten nodes labeled.0, 1, 2, ..., 9 in such a way
that the inorder and postorder traversals of the tree yield the following
lists: 9, 3, 1, 0, 4, 2, 7, 6, 8, 5 (inorder) and 9, 1, 4, 0, 3, 6, 7, 5, 8, 2
(postorder).
b. Give an example of two permutations of the same n labels 0, 1, 2, .., n−1
Hint:
that cannot be inorder and postorder traversal lists of the same binary tree.
First, find the label of the root.
c. Design an algorithm that constructs a binary tree for which two given
listsThen, identify
of n labels 0, 1, 2the
, .., nleft andgenerated
− 1are right subtrees.
by the inorder and postorder
traversals of the tree. Your algorithm should also identify inputs for which
the problem has no solution.
25
!25
that E = I + 2n where n is the number of internal nodes in the tree.
Problem — Levitin §5.3, Q11
9. Write a program for computing the internal path length of a binary search
tree. Use it to investigate empirically the average number of key compar-
isons for searching in a randomly generated binary search tree.
10. Chocolate bar puzzle Given an n-by-m chocolate bar, you need to break
it into nm 1-by-1 pieces. You can break a bar only in a straight line, and
only one bar can be broken at a time. Design an algorithm that solves the
problem with the minimum number of bar breaks. What is this minimum
number? Justify your answer by using properties of a binary tree.
Hint:
Breaking the chocolate bar can be represented as
a binary tree
!26
