Algorithms - Problems

Hiqmet Kamberaj
Solved Problems in Algorithms

Introduction course in algorithms
February 19, 2016
Contents
Part I Week 1 to 7
1
Standard notations and common functions . . . . . . . . . . . . . . . . . . . . . . . .
Growth Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Part II Week 8 to 14
4
Probabilistic Analysis and Randomised Algorithms . . . . . . . . . . . . . . . . 57

4.1
Probabilistic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2
Randomised algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
The Quicksort Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
The Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Red-Black Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Part I
Week 1 to 7
Chapter 1
Standard notations and common functions
Example 1.1. Show that a = blogb a , where a, b > 0.

Solution: From the definition of the logarithmic function:
x = logb a a = bx
Now, take x logb a, and replace it in the above expression, you get
a = blogb a
which is what we wanted to prove.
Example 1.2. Show that logc (ab) = logc a + logc b, for a, b, c > 0.
Solution: Using the definition: y = logc (ab) is equivalent to ab = cy . Moreover
x = logc a a = cx
and
z = logc b b = cz
Multiplying side by side the last two equations, you get
a b = cx+z = cy
The last equality indicates that
y = x+z
3
1 Standard notations and common functions
or
logc (ab) = logc a + logc b
Example 1.3. Show that logb (an ) = n logb a, for a, b, n > 0.
Solution: Knowing that x = logb (a) is equivalent to a = bx . Taking the power n of
both sides, you get
an = (bx )n = bnx
Using the definition of the logarithmic function:
nx = logb an
or, by replacing the expression for x, you get
n logb a = logb an
Example 1.4. Show that logb a =
logc a
, where a, b, c > 0.
logc b
Solution: Using the definition of the logarithmic function: x = logc a, you get
a = cx
and
y = logc b b = cy
z = logb a a = bz
From the second expression, taking the power to z, you get
(cy )z = cyz = bz
The, using the third and the first expressions, you get
cyz = bz = a = cx
From here,
yz = x
or
z=
x
y
Replacing the logarithmic expressions for x, y and z, you get

logb a =
logc a
logc b
Example 1.5. Show that logc (a/b) = logc a logc b, a, b, c > 0.

Solution: From the definition:
x = logc a a = cx
y = logc b b = cy
Dividing side by side (since b 6= 0), you get
a/b = cxy
taking the logc , you get
logc (a/b) = (x y) logc c = x y = logc a logc b
Example 1.6. Show that logb (1/a) = logb a, a, b > 0.
Solution: Using the equation
logc (a/b) = (x y) logc c = x y = logc a logc b
for c = b and b = a and a = 1, you get
logb (1/a) = logb 1 logb a = logb a
Example 1.7. Show that logb a = 1/ loga b, a, b > 0.
x = loga b b = ax
and
y = logb a a = by
From the last expression:
a = by = (ax )y = axy
or
xy = 1 y = 1/x
Hence
logb a = 1/ loga b
Example 1.8. Show that alogb c = clogb a , a, b, c > 0.
x = logb a a = bx b = a1/x
and
y = logb c c = by b = c1/y
From these two expressions
a1/x = c1/y
Taking the xy power of both sides:
ay = cx
Replacing x and y, you get
alogb c = clogb a
Example 1.9. Show that
n
n
b c+d e = n
2
2
Solution: From the definition of the floor and ceil functions:

n
n
1 < b c
2
2
n
n
d e<
2
2
Adding side-by-side, you get
n
2
n
+1
2
n
n
n1 < b c+d e < n+1
2
2
or
n
n
b c+d e = n
2
2

a
b c=
b
a
d e=
b
a 1
b 2
a 1
+
b 2

a
a
1 < b c
b
b
a
a
d e<
b
b
a
b
a
+1
b
Taking the difference and the sum of the all sides, you get
a
a
a
d e+b c = 2
b
b
b
a
a
d eb c = 1
b
b
By combining these two last equations, you get
a
b c=
b
a
d e=
b
a 1
b 2
a 1
+
b 2

bbn/ac/bc = bn/abc
ddn/ae/be = dn/abe
bn/ac/b 1 < bbn/ac/bc bn/ac/b
dn/ae/b ddn/ae/be < dn/ae/b + 1

Moreover,
n/a 1 < bn/ac n/a
n/a dn/ae < n/a + 1
Therefore, you can write
n/ab 1 < bbn/ac/bc n/ab
n/ab ddn/ae/be < n/ab + 1
which prove that
bbn/ac/bc = bn/abc
ddn/ae/be = dn/abe
da/be (a + (b 1))/b
ba/bc ((a (b 1))/b
Solution: From the definition of the ceil and floor functions:
a/b 1 < ba/bc a/b
a/b da/be < a/b + 1
Moreover,
(a + 1)/b 1 < b(a + 1)/bc a/b
(a 1)/b d(a 1)/be < (a 1)/b + 1
and
ba/bc < b(a + 1)/bc
d(a 1)/be < da/be

Since the floor and the ceil functions are monotonically increasing functions, then
da/be (a + (b 1))/b
ba/bc ((a (b 1))/b
Example 1.13. If
f (i) (n) =
i=0
f ( f (i1) ) i > 0
Show that
f (i) (n) = 2i n
Solution: Using the Mathematical Induction:
For i = 0
f (0) (n) = 20 n = n
which is the same as the definition.

You can assume that is true for i = k, that is
f (k) (n) = 2k n
We have to prove it for i = k + 1:
f (k+1) (n) = 2k+1 n
To prove, we start with definition
f (k+1) (n) = f ( f ((k+1)1) (n)) = f ( f (k) (n))
= f (2k n) = 2(2k n)
= 2k+1 n
Example 1.14. The iteration logarithmic function is defined as
lg n = min{i 0 : lg(i) n 1}
10
where
lg(i) (n) =
i=0
lg(lg(i1) (n)) i > 0
Determine lg 2, lg 4, lg 16.
Solution: From the definition
lg 2 = min{i 0 : lg(i) 2 1}
As you can see, lg(0) 2 = 2 > 1, therefore i > 0. Thus,
lg 2 = min{i 0 : lg(lg( lg(2))) 1}
since lg 2 = 1 and lg a > 1 for any a > 2, then i = 1, hence
lg 2 : lg 2 = log2 2 = 1
hence lg 2 = 1.
Similarly,
lg 4 : lg lg 4 = log2 log2 22 = log2 (2 log2 2) = 1
hence, lg 4 = 2.
Also,
lg 16 : lg lg lg 16 = log2 log2 log2 16 = log2 log2 4 = 1
hence lg 16 = 3.
Example 1.15. The Fibonacci numbers are defined by the following recurrence:
F0 = 0
F1 = 1
Fi = Fi1 + Fi2
for i 2. Determine F2 , F3 , F4 , F5 .
Solution: From the definition
11
F2 = F1 + F0 = 1 + 0 = 1
F3 = F2 + F1 = 1 + 1 = 2
F4 = F3 + F2 = 2 + 1 = 3
F5 = F4 + F3 = 3 + 2 = 5
Example 1.16. Show that Fibonacci number is given as
Fi =
for every i 0, where
i i
1+ 5 1 5
=
, =
2
2
Solution: Using the principle of the mathematical induction:

1. The basis step: Lets prove it for i = 0.
F0 =
0 0
=0
5
which is true based on the definition of the Fibonacci numbers.

2. Inductive step, you have to prove that k(Fk Fk+1 ). For that, we assume first
that
Fk =
k k
, k 0
5
and show that

Fk+1 =
k+1 k+1
We start with the definition of the Fibonacci number:

Fk+1 = Fk + Fk1
k k k1 k1
+
5
5
k
k
k1
+
k1
=
5
k1
( + 1) k1 ( + 1)
=
5
=
12
k1 2 k1 2
5
k+1
k+1
=
5
=
Example 1.17. Prove that for i 0, the (i + 2)nd Fibonacci number satisfies Fi+2
i.
Solution: From the previous exercise:

Fi =
where | |< 1, and so
| |
1
1
< <
5
5 2
Thus,
i
Fi = d e
5
as such, you can write that
or
i i
i
i
Fi < + 1
5
5
2
i+2
Fi+2 = i
5
5
or since 2 / 5 is a positive constant
Fi+2 i
Example 1.18. Using Stirlings approximation
n! =
2n (n/e)n (1 + (1/n))
show that
n! = o(nn )
n! = (2n )
13
Solution: First, take the expression

n n
2n
= 2nn
e
2
for n 1 for all c =
. Hence
e

n
2 n
<
n
en
e
n! = o(nn )
Similarly,
for n >= 4 for all c =
n n
2n
> 42n
e
4. Hence
n! = (2n )
Chapter 2
Growth Functions
Example 2.1. Show that f (n) = an2 + bn + c is O(n2 ), where a > 0.

Solution: For n 1 using the triangle inequality, we have:
0 | an2 + bn + c |
(using triangle inequality)
an2 + | b | n+ | c |
(n 1)
an2 | b | n2 + | c | n2
= (a+ | b | + | c |)n2
If n0 = 1 and c = (a+ | b | + | c |) > 0, then
0 f (n) cn2
for all n n0 , hence f (n) = O(n2 ) with witnesses n0 = 1, c = a+ | b | + | c |.
How can big-O notation be used to estimate the sum of the first n positive integers?
Solution: Let S(n) be the sum of the first n positive integers:
S(n) = 1 + 2 + + n
Because each of the terms in this sum does not exceed n, it follows that for all n 1:
S(n) n + n + + n = n n = n2
If c = 1, then for all n 1:
15
16
2 Growth Functions
S(n) = O(n2 )
with witnesses n0 = 1 and c = 1.
Example 2.2. Give big-O estimates for the factorial function, where the factorial
function f (n) = n! is defined by
n! = 1 2 3 n
Solution: Because each term in the product does not exceed n, you have
n! n n n n = nn
for all n 1. Thus, using the witnesses n0 = 1 and c = 1,
0 f (n) nn
hence
f (n) = O(nn )
Example 2.3. Give big-O estimates for the logarithmic of factorial function where
the factorial function f (n) = n! is defined by
n! = 1 2 3 n
Solution: Using the result of the previous exercise,
n! nn
for all n 1. Taking the logarithmic of both sides, inequality holds because the
logarithmic function is monotonic function:
log n! log nn = n log n

for all n 1. Using the witnesses n0 = 1 and c = 1, then
log n! = O(n log n)
2 Growth Functions
17
Example 2.4. Let f (n) and g(n) be asymptotically nonnegative functions. Using the
basic definition of -notation, prove that
max ( f (n), g(n)) = ( f (n) + g(n))
Solution: Let denote h(n) = max ( f (n), g(n)). Then,
h(n) f (n)
h(n) g(n)
Adding side-by-side you get
2h(n) f (n) + g(n)
or
h(n)
1
( f (n) + g(n))
2
Using C = 1/2, then for n n0 , we have

h(n) C ( f (n) + g(n))
which means that
max ( f (n), g(n)) = ( f (n) + g(n))
Thus, f (n) + g(n) is a lower bound for max ( f (n), g(n)).
Lets determine the upper bound now. Starting with f (n) + g(n):
f (n) + g(n) h(n)
because, h(x) can be equal to either f (n) or g(n) and each of the functions is positive
f (n) 0 and g(n) 0. Thus,
h(n) f (n) + g(n)
for n n0 . If c2 = 1, then
h(n) = O( f (n) + g(n))
18
2 Growth Functions
Combining both results, you can say that

h(n) = max ( f (n), g(n)) = ( f (n) + g(n))
Example 2.5. Show that for any real constants a and b, where b > 0,
(n + a)b = (nb )
Solution: To show that (n + a)b = (nb ), we want to find the constants c1 , c2 , n0 > 0
such that
0 c1 nb (n + a)b c2 nb
for all n n0 . You can start with
n + a n+ | a |
2n
when | a | n. Also,
n a n | a |
1
n
2
when | a | n/2.
Combining these two last expressions, for all n 2 | a |, you get

1
0 n n a n + a 2n
2
Since b > 0, inequality holds also for power b:

0
or

1 b
n (n a)b (n + a)b (2n)b
2
b
1
0
(n)b (n a)b (n + a)b (2)b (n)b
2
Denoting, c1 = (1/2)b , c2 = 2b , and n0 = 2 | a |, we have

0 c1 (n)b (n + a)b c2 (n)b
2 Growth Functions
19
for all n n0 .
Example 2.6. Explain why the statement, The running time of algorithm A is at
least O(n2 ), is meaningless.
Solution: Let the running time be T (n). T (n) O(n2 ) means that T (n) f (n) for
some function f (n) in the set O(n2 ). This statement holds for any running time
T (n), since the function g(n) = 0 for all n is in O(n2 ), and running times are always
nonnegative. Thus, the statement tells us nothing about the running time.
Example 2.7. Is 2n+1 = O(2n )? Is 22n = O(2n )?
Solution: You can start with
2n+1 = 2 2n > 2n
for all n 0. If c = 1, then
0 2n+1 > c 2n
hence
2n+1 = (2n )
For the second expression, you can start with
0 22n = (2n )2
Using the property of the power
0 22n = (2n )2 2n
for all n 0. If c = 1, then
0 22n = (2n )2 c 2n
hence
22n = (2n )
Example 2.8. Let f (n) = 2n2 + 4n + 10, and g(n) one of the following functions
20
2 Growth Functions
a) g(n) = n3
b) g(n) = n2
Determine whether f (n) is O(g(n)), (g(n)), or (g(n)) and explain when.
Solution:
a) You can write
0 2n2 + 4n + 10 2n3 + 4n3 + 10n3
16n3
for all n 1. Hence, if c = 16 and n0 = 1, then
0 f (n) c n3
for n n0 . Thus, f (n) = O(n3 ) with witnesses n0 = 1 and c = 16.
b) You can write
0 2n2 + 4n + 10 2n2 + 4n2 + 10n2

16n2
or all n 1. Hence, if c1 = 16 and n0 = 1, then
0 f (n) c1 n2
for n n0 . Thus, f (n) = O(n2 ) with witnesses n0 = 1 and c = 16.
On the other hand, you can also write
0 2n2 + 4n + 10 2n2
16n2
or all n 0. Hence, if c2 = 2 and n0 = 0, then
0 f (n) c2 n2
2 Growth Functions
21
for n n0 . Thus, f (n) = (n2 ) with witnesses n0 = 0 and c2 = 2. Combining
these both, we can say that
c2 n2 f (n) c1 n2
for all n 1, so n0 = 1, and hence
f (n) = (n2 )
Example 2.9. For each of the following pairs of functions, either f (n) = O(g(n)),
or f (n) = (g(n)), or f (n) = (g(n)). Determine which relationship is correct and
briefly explain why.
a) f (n) = log n2 ; g(n) = log n + 5.
Solution: From the property of logarithm functions
0 log n2 = 2 log n
2 log n + 10
= 2 (log n + 5)
for all n 1. if n0 = 1 and c = 2, then
0 log n2 c (log n + 5)
hence f (n) = O(g(n)).
b) f (n) = n, g(n) = log n2 .

Solution: Again using the property of the logarithmic function:
0
n log n
=
1
log n
2
for all n 1. Moreover, you can write

0
1
n log n
2
22
2 Growth Functions
12
log n
22
1
= log n2
4
again for all n 1. if n0 = 1 and c = 1/4, then

0
n c log n2
for all n n0 . Hence, n = (log n2 ).
c) f (n) = n and g(n) = log n.

Solution: Using the properties of the logarithmic function:
0
n log n
=
1
log n
2
for all n 1. If c = 1/2, and n0 = 1, then

0
for all n n0 . Hence,
n c log n
n = (log n).
d) f (n) = log2 n, g(n) = log n.

Solution: For the properties of the logarithmic function:
0 log2 n = (log n)(log n)
log n
for all n 10 (but not for n < 10!) If n0 = 10 and c = 1, then
0 log2 n c log n
for all n n0 . Hence, log2 n = (log n).
e) f (n) = 2n , g(n) = 10n2 .
Solution: The logarithmic function is monotonically increasing function, that is,

if lg f lg g, then f g, and vice versa. Then,
2 Growth Functions
23
0 lg 2n = n lg 2 = n
lg n
=
for all n 1. If you change n
0
Dividing both sides by
1
lg n2
2
10n, then
1
10n lg 2 lg(10n2 )
2
10, you get
1
0 lg 2n lg(10n2 )
2 10
for all n 10. If c = 1/2 10 and n0 = 10, then

0 lg 2n c lg(10n2 )
for all n n0 . Hence, f (n) = (g(n)).
Example 2.10. Let f (n) = n2 + n + 5. Show that f (n) = (n2 ).
Solution: To show that, we have to show that
f (n) = O(n2 )
f (n) = (n2 )
for all n n0 . First, let show that f (n) = O(n2 ). For that, we have to prove that
0 f (n) c1 n2
for all n n0 , where c1 > 0 real number. For that,
0 n2 + n + 5 n2 + n2 + 5n2
= 7n2
for all n 1. If c1 = 7 and n0 = 1, then
0 n2 + n + 5 c1 n2
24
2 Growth Functions
for all n 1, hence f (n) = O(n2 ).
Now, let show that f (n) = (n2 ). For that, we have to prove that
0 f (n) c2 n2
for all n n0 , where c2 > 0 real number. For that,

0 n2 + n + 5 n2
for all n 0. If c2 = 1 and n0 = 0, then
0 n2 + n + 5 c2 n2
for all n 0, hence f (n) = (n2 ). Combining these two results, we can write that
c2 n2 n2 + n + 5 c1 n2
where c1 = 7 and c2 = 1, for all n 1. Hence, f (n) = (n2 ).
Example 2.11. Let f (n) = n2 + n + 5. Show that f (n) = O(n3 ).
Solution: To show that, we have to show that
0 f (n) cn3
for all n n0 and real c > 0. You can write
0 n2 + n + 5 n3 + n3 + 5n3
= 7n3
for all n 1. If c = 7 and n0 = 1, then
0 n2 + n + 5 cn3
for all n 1, so n2 + n + 5 = O(n3 ).
Example 2.12. Let f (n) = 3n . Show that f (n) = (2n ).
Solution: From the property of the power functions:
2 Growth Functions
25
an bn
for all n 0, if a b and a 1. In our case, a = 3 and b = 2, hence
0 3n 2n
0 3n c2n
for all n n0 . Hence, 3n = (2n ) with witnesses n0 = 0 and c = 1.
Example 2.13. Let f (n) = 3n . Show that f (n) = O(4n ).
Solution: Similarly, from the property of the power functions:
an bn
for all n 0, if a b and a 1. In our case, a = 3 and b = 4, hence
0 3n 4n
0 3n c4n
for all n n0 . Hence, 3n = O(4n ) with witnesses n0 = 0 and c = 1.
Example 2.14. Show that if f1 (n) = O(g1 (n)) and f2 (n) = O(g2 (n)), then
f1 (n) + f2 (n) = O(max(g1 (n), g2 (n))).
Solution: From the definition of Big-O notation, f1 (n) = O(g1 (n)), means that
0 f1 (n) c1 g1 (n)
for all n n01 and c1 > 0 real number. Also, f2 (n) = O(g2 (n)), means that
0 f2 (n) c2 g2 (n)
26
2 Growth Functions
for all n n02 and c2 > 0 real number. Adding side by side, the above two equations,
you get
0 f1 (n) + f2 (n) c1 g1 (n) + c2 g2 (n)

Denoting by g(n) = max(g1 (n), g2 (n)), we can further write:
0 f1 (n) + f2 (n) (c1 + c2 )g(n) = cg(n)
for all n n0 , where n0 = max(n01 , n02 ) and c = c1 + c2 > 0. Hence
f1 (n) + f2 (n) = O(max(g1 (n), g2 (n)))
with witnesses
n0 = max(n01 , n02 ), c = c1 + c2
Example 2.15. Show that if f1 (n) = O(g1 (n)) and f2 (n) = O(g2 (n)) and both f1 and
f2 are positive functions, then
f1 (n) f2 (n) = O(g1 (n)g2 (n)).
Solution: From the definition of Big-O notation, f1 (n) = O(g1 (n)), means that
0 f1 (n) c1 g1 (n)
for all n n01 and c1 > 0 real number. Also, f2 (n) = O(g2 (n)), means that
0 f2 (n) c2 g2 (n)
for all n n02 and c2 > 0 real number. Multiplying side by side the above two
equations and since they are positive functions, you get
0 f1 (n) f2 (n) (c1 c2 )g1 (n)g2 (n)

for all n n0 , where n0 = max(n01 , n02 ) and c = c1 c2 > 0. Hence
f1 (n) f2 (n) = O(g1 (n)g2 (n))
with witnesses
2 Growth Functions
27
n0 = max(n01 , n02 ), c = c1 c2
Example 2.16. Give a big-O estimate for f (n) = 3n log(n!) + (n2 + 3) log n, where n
is a positive integer.
Solution: The f (n) can be seen as sum of two functions:
f (n) = f1 (n) + f2 (n)
where
f1 (n) = 3n log(n!)
f2 (n) = (n2 + 3) log n
Therefore, from one of previous exercises:
f (n) = O(max( f1 , f2 ))
On the other hand, f1 (n) can be seen as f1 (n) = g1 (n)g2 (n), where
g1 (n) = 3n, g2 (n) = log(n!)
We have found (from previous exercises) that
g1 (n) = O(n), g2 (n) = n log n
Thus,
f1 (n) = O(g1 (n)g2 (n)) = O(n2 log n)
Similarly, f2 (n) = g1 (n)g2 (n), where
g1 (n) = n2 + 3 = O(n2 ), g2 (n) = log n = O(log n)
Thus,
f2 (n) = O(g1 (n)g2 (n)) = O(n2 log n)
Finally,
f (n) = O(max( f1 , f2 )) = O(n2 log n)
28
2 Growth Functions
Example 2.17. Show that the function f (x) = 8x3 + 5x2 + 7 is (g(x)), where g(x)
is the function g(x) = x3 .
Solution: For x 0, we have
0 f (x) = 8x3 + 5x2 + 7
8x3
Using the witnesses x0 = 0 and c = 8, we have
f (x) = (x3 )
Example 2.18. Show that f (x) = 2x2 + 8x log x is (x2 ).
Solution: For all x 1
0 2x2 + 8x log x 2x2 + 8x x
= 10x2
Using the witnesses x0 = 1 and c1 = 10, then
0 f (x) c1 x2
for all x x0 , hence f (x) = O(x2 ).
In addition, for x 1:
0 2x2 + 8x log x 2x2

= c2 x2
where c2 = 2. Using the witnesses x0 = 1 and c2 = 2, we have
0 f (x) c2 x2
hence
f (x) = (x2 )
Therefore,
2 Growth Functions
29
f (x) = (x2 )
with witnesses x0 = 1 and c1 = 10, c2 = 2.
Example 2.19. For each of the following pairs of functions f (n) and g(n), give an
appropriate positive constant c such that f (n) c g(n) for all n 1.
a) f (n) = n2 + n + 1, g(n) = 2n3 ;
b) f (n) = n n + n2 , g(n) = n2 ;
c) f (n) = n2 n + 1; g(n) = n2 /2.
Solution:
a) You can start with the function f (n):
f (n) = n2 + n + 1 n3 + n3 + n3 (n 1)
3
= 3n3 = (2n3 )
2
= c(2n3 )
where c = 3/2.
b) You can start with the function f (n):
f (n) = n n + n2 n2 + n2 (n 1, because n n)
= 2n2
= c(n2 )
where c = 2.
c) You can start with the function f (n):
f (n) = n2 n + 1 = n2 (n 1)
n2 (n 1, because n 1 0)
= 2(n2 /2)
= c(n2 /2)
where c = 2.
30
2 Growth Functions
Example 2.20. For each of the following statements, decide whether it is always
true, never true, or sometimes true for asymptotically nonnegative functions and . If
it is always true or never true, explain why. If it is sometimes true, give one example
for which it is true, and one for which it is false.
a) f (n) = O([ f (n)]2 )
b) f (n) + g(n) = (max( f (n), g(n)))
c) f (n) + O( f (n)) = ( f (n))
d) f (n) = (g(n)) and f (n) = o(g(n))
e) f (n) 6= O(g(n)) and g(n) 6= O( f (n))
Solution:
a) f (n) = O([ f (n)]2 ): It is not always true. For example, if f (n) = 1/n, where n 1,
then the relation is not true, because
1
1
n2
n
for n 1.
b) f (n) + g(n) = (max( f (n), g(n))): This is always true, as shown in one of the
exercises above.
c) f (n) + O( f (n)) = ( f (n)): Let g(n) = O( f (n)), then
0 g(n) c f (n)
where c > 0 is a real number. Hence,
f (n) f (n) + g(n) f (n) + c f (n) = (c + 1) f (n) = c0 f (n)
where c0 = 1 + c > 0. This tells that
f (n) + g(n) = ( f (n))
d) f (n) = (g(n)) and f (n) = o(g(n)): This can never be true. Because, f (n) =
(g(n)) means that
0 c g(n) f (n)
2 Growth Functions
31
where c > 0 and for all n n0 . The relation f (n) = o(g(n)) requires that
0 f (n) < c g(n)
for all c > 0 and for all n n0 , which can not be satisfied since f (n) c g(n)
from first relation.
e) f (n) 6= O(g(n)) and g(n) 6= O( f (n)): Take for example, f (n) = 1 and g(n) =||
n sin(n) ||. In that case it is true, while for any f (n(= g(n) = 1, it is not true. So,
for some cases it is true and some others not.
Example 2.21. Determine whether f (x) = bxcdxe is O(x2 ), (x2 ) or (x2 ).

Solution: From the definition of the floor and ceil functions, you can write:
x 1 bxc < x
x dxe < x + 1
Multiplying side by side these two equations, for x > 1, you get:
x2 x bxcdxe < x2 + x
Then, from the left inequality, you may write that
bxcdxe x2 x
x2 x
x
2
= x /2
for x/2 1 or x 2. Thus, with witness parameters x01 = 2 and c1 = 1/2, you have
bxcdxe = (x2 )
From the left inequality, you may write that
bxcdxe x2 + x
x2 + x2
= 2x2
32
2 Growth Functions
for x 1 or x 2. Thus, with witness parameters x02 = 1 and c2 = 2, you have

bxcdxe = O(x2 )
Therefore,
bxcdxe = (x2 )
for all x 2.
Example 2.22. Determine whether f (x) = 2x is O(x2 ), (x2 ) or (x2 ).
Solution: Since the logarithm function is monotonically increasing function, then
lg f lg g
implies that f (x) g(x), and vice versa. Thus,
lg f (x) = x, lg g(x) = 2 lg x
Since, we know that
x lg x2
for all x 4, then
lg f (x) lg g(x)
Thus,
f (x) g(x)
Hence,
f (x) = (g(x))
with witness parameters x0 = 1 and c = 1.
x2 + 1
Show that
is O(x).
x+1
Solution: Starting with
f (x) =
x2 + 1
x+1
you can write

f (x) =
x2 + 1 + 2x 2x (x + 1)2
2x
=
x+1
x+1
x+1
2 Growth Functions
33
= (x + 1)
= x
x
for all x 1. Thus,
f (x) = O(x)
with witness parameters x0 = 1 and c = 1.
x1
x+1
2x
x+1
Chapter 3
Recurrences
Example 3.1. Using the substitution method show that the asymptotic behaviour of
the recurrence
T (n) = T (n/3) + T (2n/3) + n
is (n lg n).
Solution: To prove that we have to show that the upper bound is
T (n) = O(n lg n)
and the lower bound is
T (n) = (n lg n)
First, the upper bound, you have to prove that T (n) dn lg n, for d > 0. We can
write the recurrence as
T (n) = T (n/3) + T (2n/3) + cn

where c > 0. Since we are interested in asymptotic behaviour, we do not need to
prove the base case. So, we first assume that for k < n
T (k) dk lg k
and prove it for k n:
35
36
3 Recurrences

n
2n 2n
+d
lg
+ cn
3 3
3
3
dn
dn
2dn
2dn
2dn
=
lg n
lg 3 +
lg 2 +
lg n
lg 3 + cn
3
3
3
3

3
2dn
+ cn
= dn lg n + dn lg 3 +
3
T (n) d
n
lg
dn lg n
if

2dn
dn lg 3 +
+ cn 0
3
or
d
Hence
c
lg 3 2/3
T (n) = O(n lg n)
Lower bound: for that you have to show that T (n) dn lg n, for d > 0. You can
re-write the recurrence as
T (n) = T (n/3) + T (2n/3) + cn

First you can assume that for k < n, T (k) dk lg k. And, prove it for k n:

n n
2n 2n
T (n) d
+d
lg
lg
+ cn
3 3
3
3
dn
2dn
2dn
2dn
dn
lg n
lg 3 +
lg 2 +
lg n
lg 3 + cn
=
3
3
3
3
3

2dn
= dn lg n + dn lg 3 +
+ cn
3
dn lg n
if

2dn
dn lg 3 +
+ cn 0
3
or
d
Hence
c
lg 3 2/3
3 Recurrences
37
T (n) = (n lg n)
Thus, since T (n) has both the upper and lower bound equal to n lg n, we can say that
T (n) = (n lg n)
Example 3.2. Use the substitution method to determine asymptotic upper bound on
the recurrence
T (n) = T (n/8) + 3 n
as T (n) = O( 3 n).
Solution: We can simply write it as
T (n) = T (n/8) + c 3 n
where c > 0, which has to be determined. To find the upper bound T (n) = O( 3 n),
we have to prove that
T (n) d 3 n
where d > 0. Assume first that T (k) d 3 k for all k < n. Then, prove that T (k)
d 3 k for all k n:
r
n
T (n) d 3 + c 3 n
8
= (d/2 + c) 3 n
d 3n
for c + d/2 d, or c d/2.
Example 3.3. Show that the solution of the following recurrence formula is T (n) =
n lg n + n:
T (n) =
Solution:
if n = 1
2T (n/2) + n if n > 1
38
3 Recurrences
1. Guess: T (n) = n lg n + n. Here, we have a recurrence with an exact function,

rather than asymptotic notation, and the solution is also exact rather than asymptotic. We will have to check boundary conditions and the base case.
2. Induction:
Basis: n = 1 n lg n + n = 1 = T (n).
Inductive step: Inductive hypothesis is that T (k) = k lg k + k for all k < n. We

will use this inductive hypothesis for T (n/2).
T (n) = 2T (n/2) + n = 2
n
n n
+ n (by inductive hypothesis)
lg +
2 2 2
n
= n lg + n + n = n(lg n lg 2) + n + n
2
= n lg n n + n + n = n lg n + n.
Determine an upper bound of the recurrence
T (n) = 2T (bn/2c) + n.
Solution:
1. Guess: T (n) = O(n lg n). Our method is to prove that T (n) cn lg n for an appropriate choice of the constant c > 0.
2. Induction:
Basis: n = 1 = T (1) = 1 0. So, it fails. Chose n = 2 = T (2) = 2T (1) +
2 = 4 2c lg 2 only for c 2. Thus, b = 2 and c 2.
Inductive step: We start by assuming that this bound holds for bkc (k < n),
that is, that T (bkc) cbkc lg(bkc).
Substituting into the recurrence yields

T (n) 2(cbn/2c lg(bn/2c)) + n
cn lg(n/2) + n = cn lg n cn lg 2 + n
= cn lg n cn + n cn lg n,
where the last step holds as long as c 2.
3 Recurrences
39
Example 3.4. Consider the recurrence T (n) = 2T (n/2) + (n). What is the upper
bound solution of this recurrence?
Solution: If we want to show an upper bound of T (n) = 2T (n/2) + O(n), we write
T (n) 2T (n/2) + cn for some positive constant c.
Guess: T (n) dn lg n for some positive constant d. We are given c in the recurrence, and we get to choose d as any positive constant. Its OK for d to depend
on c.
Substitution:
T (n) 2T (n/2) + cn
n n
+ cn
= 2 d lg
2 2
= dn lg n/2 + cn
= dn lg n dn + cn
dn lg n, (d c)
Therefore, T (n) = O(n lg n).
Example 3.5. Consider the recurrence T (n) = 2T (n/2) + (n). What is the lower
bound solution of this recurrence?
Solution: If we want to show a lower bound of T (n) = 2T (n/2) + (n), we write
T (n) 2T (n/2) + cn for some positive constant c.
Guess: T (n) dn lg n for some positive constant d.
Substitution:
T (n) 2T (n/2) + cn
n n
n
= 2 d lg
+ cn = dn lg + cn
2 2
2
= dn lg n dn + cn = dn lg n, (d c)
Therefore, T (n) = (n lg n).
Example 3.6. Solve using the Master theorem the following recurrence:
40
3 Recurrences
T (n) = 4T (n/2) + n
Solution: For this recurrence, there are a = 4 subproblems, each dividing the input
by b = 2, and the work done on each call is f (n) = n. Thus nlogb a = n2 , and f (n) is
O(n2 ) for = 1, and Case 1 applies. Thus T (n) = (n2 ).
T (n) = 4T (n/2) + n2
Solution: For this recurrence, there are again a=4 subproblems, each dividing the
input by b = 2, but now the work done on each call is f (n) = n2 . Again nlogb a = n2 ,
and f (n) is thus (n2 ), so Case 2 applies. Thus T (n) = (n2 log2 n). Note that
increasing the work on each recursive call from linear to quadratic has increased the
overall asymptotic running time only by a logarithmic factor.
T (n) = 4T (n/2) + n3
Solution: For this recurrence, there are again a = 4 subproblems, each dividing the
input by b = 2, but now the work done on each call is f (n) = n3 . Again nlogb a = n2 ,
and f (n) is thus O(n2+ ) for = 1. Moreover, 4(n/2)3 = kn3 for k = 1/2, so Case
3 applies. Thus T (n) = (n3 ).
Example 3.9. Calculate the amount of work done at each call and the total cost of
the following recurrences.
T (n) = 2T (n/2) + n2
Solution: The recursion tree for this recurrence is of the following form (see
Fig. 3.1): The sub-problem size for a node at depth k is
n/2k
Thus, the sub-problem size hits n = 1 when
3 Recurrences
PRACTICE QUESTIONS March 13, 2012
41
a) What
is the problem size?
Fig. 3.1 Recursion tree of T (n) = 2T (n/2) + n2 .
The sub problem size for a node at depth k is /2 . nThus, the sub-problem size hits = 1 when
=1
2k tree has lg + 1 levels (0, 1, 2, . . . , lg ).

/2 = 1 or, equivalently, when = lg . Thus, the
solving this equation for k, you get the kmax :
b) What are the number nodes at depth ?
kmax = lg n
+ 1 = lg n + 1 levels: 0, 1, 2, , lg n + 1.
Hence,atthe
tree khas
The number of nodes
depth
is k2max
.
The number of nodes at level k = 0 is 1 (see also Fig. 3.1). At level k = 1 it is 2, at

kmax
lg n
levelis
k=
nodes
is 4,at
and
so on,,atand
the the
leveltotal
k = cost
lg n has
2
=?
2
c) What
the2 the
timenumber
cost atofeach
node
depth
at depth
nodes, or n2 nodes (since 2lg n = n2 ).
Time cost in each level k = 0, 1, 2, , lg n + 1 is as following:
Each node at depth , for = 0, 1, 2, . . . , 1, has a cost of (2 )2 = 22 . The total cost

2
: n
over all nodes at depth k, for = 0, 1, 2,i. =
. . ,0
1, is 2 (/2 )2 = 2 /2 .
n2
2
2
n 2 n2
i=2: 4
= 2
2 and the total cost of the last level?
d) What are the cost at each node of the4last level
:
2 n2
k n
= k
= k : 2each
The last level, at depth k = lg , has 2lg inodes,
cost (1), for a total cost of
2kcontributing
2
i=1: 2
2 (1) = (2 ).
n 2
:
k = lg n + 1 : n2 (1) = (n2 )
e) What is the total time cost of the recurrence tree?

The length of the tree is lg , then the total time cost is:
Lecturer: Hiqmet Kamberaj (International Balkan University)
Page 8
42
3 Recurrences
Thus, the total time is:

T (n) =
lg n1 2
n
k=0
2k
+ (n2 )
The upper bound of T (n) is calculated as:

T (n) =
<
lg n1 2
n
2k
+ (n2 )
k=0
n2
2k + (n2 )
k=0
k
1
= n
+ (n2 )
2
k=0
n2
+ (n2 ) = 2n2 + (n2 )
1 (1/2)
= 2n2
where terms (n2 ) are ignored and sum of geometric series formula is used:
ark = 1 r
k=
Hence,
T (n) = O(n2 )
Example 3.10. Calculate the amount of work done at each call and the total cost of
the following recurrences.
T (n) = 2T (b nc) + lg n
Solution: In this kind of problems, it is worth making the following change of variables:
m = lg n
Then,
T (2m ) = 2T (2m/2 ) + m
Denoting T (2m ) S(m), you get
S(m) = 2S(m/2) + m

Hint: For Geometric Series:
=0 =
b. () = 2
+ lg
3 Recurrences
Solution: In this kind of problems, it is worth making the following change of variables:
43
which is new recurrence formula tobe solved. For

the reduced problem, the recur-
= lg . Then, (2 ) = () = 2 2 2 + = 2
+ . Thus, the problem reduces to
rence tree is given below:

It can be seen that the sub-problem size for node 0 is
recurrence tree: () = 2
+ .
Fig. 3.2 Recursion tree of S(m) = 2S(m/2) + m.
1. What is the problem size of ()?
0 , for size
The
problem
forka=
node
/2node
. Thus,
the2,sub-problem
size
hits2 ,nand
= 1 when
m =sub
m/2
node
1, itat isdepth
m/2k1is, for
k=
it is m/4 =
m/2
so on,
/2 = 1 or, equivalently,k when = lg Thus, the tree has length of lg + 1 levels
for the k-th node is m/2 . Thus, the sub-problem size hits 1, when
(0, 1, 2, . . . , lg ).
m
=1
k
2
2. What are the number nodes at depth ?
Solving it for k, you get
k
= lg m
max
Lecturer: Hiqmet Kamberaj (International Balkan
University)
Thus, the length of the recursion tree is lg m + 1, and the levels are:
0, 1, 2, , lg m
To determine the number of nodes at each level, you can see from Fig. 3.2:
i = 0 : 1 = 20
i = 1 : 2 = 21
i = 2 : 4 = 22
i = k : 2k
i = lg m : 2lg m = m
Page 9
44
3 Recurrences
Now, we can also calculate the cost at each level:

i=0: m
i = 1 : 2(m/2) = m
i = 2 : 4(m/4) = m
i = k : 2k (m/2k ) = m
i = lg m : 2lg m (1) = (m)

The total time code can be calculated as:
lg m1
S(m) =
m + (m2 ) = m lg m + (m)
k=0
which has the upper bound:

S(m) = O(m lg m)
Then, the total cost of T (n) is
T (n) = O(lg n lg lg n)
Example 3.11. Use the recurrence tree and substitution method to solve the following recurrence:
T (n) = 8T (n/2) + n
Fig. 3.3). The sub-problem size for a node at depth k is
n
2k
Thus, the sub-problem size hits n = 1 when
n
=1
2k
solving this equation for k, you get the kmax :
lg 1
lg 1
lg 1 lg 1
2 2 22 2 22
2 lg
22 22 lg22 2 lg2 2
2 2 lg
2
lg 2
=
+ =+2 ++ ++ + lg 1
+
+ lg
2 +
==
22+
=
=
+
++ +
+2 +
+
+
2
+ + 2
+lg
2=lg = + 2+lg
2
2
4 28 4 2 8
22 42 284
8 2lg 12lg 1
2
2
2 1
=0
<
=0
=0
=0
=0
=0
=0
2
2
1
1
2 2 2lg lg 2 1 2 1 lg lg 2
2 ).
<
+ 2lg +=
22lg =
2 2lg1+ =
<(
2lg <
=+(
2+). 2= = 1 + 12+ 2= (= ).(2 ).
1+
2
2
2 2
1
1
1 1
=0
Hint: For Hint:

Geometric
For Geometric
Series:
Series:
=
= For
Hint:
Geometric
For Geometric
Series:Series:
=0
=0 Hint:
=0
=0= =
3 Recurrences
b. () =
b. 2
()
+ lg
= 2
45
b. ()
b. k=
()
2 ==
2lg+
nlg + lg
+ lg
max
Solution:Solution:
In this kind
In of
thisproblems,
kind of problems,
it is worthSolution:
itmaking
is worth
Solution:
the
In
making
following
thisInkind
the
thisfollowing
of
change
kind
problems,
of of
problems,
change
variables:
it is worth
ofitvariables:
is worth
making
making
the following
the following
changechange
of variables:
of variables:
)
)
n Thus,
2
2
2 reduces
)(2
)=
= lg .
Then,
= lg(2
. Then,
= (2
()
==2
()
2 2= +
2
=2=lg
2
.=
+Then,
lg
.
=+Then,
(2
2
.
=
+
()
the
.
Thus,
problem
()
= 2
the=
reduces
2
problem
2
+2
to
=+2
n=2to2+ .
Thus,
+ . Thus,
the problem
the problem
reduces
reduces
to
to
2
2
2
recurrence
tree: ()tree:
= 2
()
=+2
.
xxviii recurrence
xxviii
2
+ .
recurrence
tree: ()
= 2 =2 2+ .
+ .
xxviiirecurrence
xxviiitree: ()
2
n/2 n/2 n/2 n/2
n/2 n/2 n/2 n/2
8(n/2)=4n
Fig. 0.2 Recursion

Fig. 0.2 Recursion
tree of S(m)
tree=of2S(m/2)
S(m) =+
2S(m/2)
Fig.
m. 0.2
Fig.
+Recursion
m.
0.2 Recursion
tree oftree
S(m)
of =
S(m)
2S(m/2)
= 2S(m/2)
+ m. + m.
Fig. 3.3 Recursion tree of T (n) = 8T (n/2) + n.
1. What 1.
is the
What
problem
is thesize
problem
of ()?
size of ()?
1. What
1. What
is the problem
is the problem
size ofsize
()?
of ()?
0, 1, 2, 0,
,1,
lg2,
m , lg m
0, 1, 2,0,1,
2,
, lg m , lg m
The sub problem

The subsize
problem
for a size
nodefor
at depth
a nodekatisdepth
The
/2sub
.kThe
Thus,
isproblem
/2
subthe
problem
. Thus,
sub-problem
size for
the
size
asub-problem
node
forsize
a at
node
hits
depth
natsize
=depth
k1ishits
when
/2
knis=./2
1Thus,
when
. Thus,
the sub-problem
the sub-problem
size hits
sizen hits
= 1 when
n = 1 when
/2To =
/2
1 or,
=
1 or,number
equivalently,
when
nodes
=when
lg of
Thus,
/2
=
lgthe
/2
=
Thus,
tree
1each
or,
=
has
the
equivalently,
1level,
length
or,
tree
equivalently,
has
of
lg
length
when
+of
of
1when
Fig.
levels
lg
=from
lg0.2:
+
=1
Thus,
lg
levels
at
Thus,
theeach
tree
thelevel,
has
tree
length
has
of
lgfrom
of
+lg1from
levels
+1
levels
determine
Toequivalently,
determine
the
the of
number
at
nodes
each
To
determine
level,
at
To
determine
you
the
can
number
you
see
the
from
can
number
see
nodes
of
nodes
at
Fig.
each
0.2:
level,
you
can
youlength
see
can
see
Fig.
0.2:
Fig.
0.2:
Hence, the tree has kmax + 1 = lg n + 1 levels: 0, 1, 2, , lg n + 1.
(0, 1, 2, . . .(0,
, lg1,).
2, . . . , lg ).
(0, 1, 2,
(0,. .1,
. , 2,
lg .).
. . , lg ).
i = 0 : 1i =
= 020: 1 = 20
i = 0 i: =10=: 210 = 20
The number of nodes at level

k = 10 is 1 (see also Fig. 3.3).1 At1 level k = 1 it is 8, at
1
i = ?
1at: depth
2i =
=What
122.: 2What
2are
i=
1 i: =2?
1=: 22 = 2
2. What 2.
are What
the number
are thenodes
number
at depth
nodes
2.
?
are=the
number
the number
nodes nodes
at depth
at depth
?
k
lg n
level k = 2 the number
i = 2of
: nodes
4i =
= 222: is
4 =64,
22 and so on, at
i =the
2 i: =level
42=: 242k==
22lg n has 8 max = 8
nodes, or n3 nodes (since 2lg n = n3 ).
Lecturer: Hiqmet
Lecturer:
Kamberaj
Hiqmet Kamberaj
(International
(International
Balkan
Lecturer:
University)
Balkan
Hiqmet
University)
Kamberaj
Kamberaj
(International
(International
Balkan
PageBalkan
University)
9
Page
University)
kLecturer:
kHiqmet
k
k 9
i = k : 2i = k : 2
i = k i: =2k : 2
level
k
= 0, 1, 2, , lg n + 1 is
as
following:
Time cost in each

lg m
i = lg m i: =2lg
m=: m2lg m = m
i = lgi m
=:lg2mlg:m =
2lgmm = m
i=0: n=4 n
ncalculate
calculate
Now, weNow,
can also
we can
calculate
also calculate
the cost the
at each
Now,
costlevel:
Now,
atweeach
can
welevel:
also
can
also
the cost
the at
cost
each
at each
level:level:
i=1: 8
= 4n = 41 n
i=0: m
i=0: m
i = 0 i: =m0 : m
2
i = 1 : 2(m/2)
i=1: =
2(m/2)
m
=m
i=
2 : =64
4(m/4)
i=2: =
4(m/4)
m
m
i=2:
n
4
i = 1 i: =2(m/2)
1 : 2(m/2)
=m =m
= i16n
=24:2 n4(m/4)
= 2 i: =4(m/4)
=m =m

k:k:2)k=(m/2
m k ) = m
k
k
i = k : 2i =
(m/2
i = k i: =2kk (m/2
: 2k (m/2
)=m
)=m
n

k
k
=4 n
i = k :m 8
lg m
lg m
i = lg m i: =2lg
mq :(1)2lg
= qq(m)
(1) = 2
qk(m) i = lgi m
=:lg2mlg:m q2(1)
q=(1)
q (m)
= q (m)
k
The
:total
time
code
The totalThe
timetotal
code
time
cancode
be calculated
can be calculated
as:
The
as:
total
time code
can be
can
calculated
be calculated
as: as:
lg m 1
lg m 1
3 lg m 1lg m 1 3 2
2 = lg n
2
+=+1mq :(m)
(1)
S(m) = S(m)
q (mkm
)+=qm
(mlg2 )m
lgS(m)
mn+
S(m)
q=(m)
qm(m
+)q) (m
=m
)lg
=mm+lgqm(m)
+ q (m)
m=+
==m+(n
k=0
which has
which
the upper
has the
bound:
upper bound:
k=0
k=0
k=0
whichwhich
has the
hasupper
the upper
bound:
bound:
lg n1
T (n) =
k=0
Using sum of geometric series formula:
4k n + (n3 )
Page 9Page 9
46
3 Recurrences
n
ark =
k=0
arn+1 a
r1
Hence, for a = n and r = 4, you have

n4lg n+1 n
+ (n3 )
41
4n22 lg n n
=
+ (n3 )
3
2
4n2lg n n
=
+ (n3 )
3
4n3 n
+ (n3 )
=
3
T (n) =
Ignoring the term (n3 ), we can write

T (n) =
An upper bound of T (n) is:
4n3 n
3
4
T (n) n3
3
for n 0. If n0 = 0 and c = 4/3 are the witnesses, then

T (n) = O(n3 )
lower bound of T (n) is:
T (n)
4n3 n3
= n3
3
for n 0. If n0 = 0 and c2 = 1 are the witnesses, then

T (n) = (n3 )
Thus, the asymptotic solution is
T (n) = (n3 )
Example 3.12. Use the recurrence tree and substitution method to solve the following recurrence:
3 Recurrences
47
T (n) = 16T (n/4) + n

Fig. 3.4). The sub-problem size for a node at depth k is
n
PRACTICEPRACTICE
QUESTIONS
QUESTIONS
PRACTICE
PRACTICE
QUESTIONS
QUESTIONS
March
2012 13, 2012
MarchMarch
13, 2012
13, 2012
4k 13, March
2
22
28
22
lg 1
lg 1
22
22
22
lg 1 lg 1
2
lg

lg
2 sub-problem
2 lg
2
Thus,
=
when
=the
+ =+2 ++ ++ +size
+
+hits
lg
2n +
==
1
2+
=
=
+
++ +
+2lg +
+
+
2
+
+ 2
+lg
2=lg
lg 1
1
lg 1 lg 1
<
=0
4 28
=0
22
42
284
=0
82
=0
2 lg
+ 2+lg
2
2 2
=0
2
2
1
1
2 2 2lg lg 2 1 2 1 lg lg 2
n<(
lg 2 ).
<
+ 2lg +=
22lg =
2 2lg1+ =
2=
<1
=+(
2+). 2= = 1 + 12+ 2= (= ).(2 ).
1+
2
2
2 2
1
1
1 1
k
=0
=0
=0
you
solving
this
equation
for
the
kmaxSeries:
: Series:
Hint:
For Hint:
Geometric
For Geometric
Series:
Series:
=k,
Hint:
=get
For
Hint:
Geometric
For Geometric
= 1
=0
=0
=0
=0=
1
1
1
b. () =
b. 2
()
+ lg
= 2
b. ()
b.k =
()
2 =
=
2
log+lgn+ lg
+ lg
max
Solution:Solution:
In this kind
In of
thisproblems,
kind of problems,
it is worthSolution:
itmaking
is worth
Solution:
the
In
making
following
thisInkind
the
thisfollowing
of
change
kind
problems,
of of
problems,
change
variables:
it is worth
ofitvariables:
is worth
making
making
the following
the following
changechange
of variables:
of variables:
)
)
n Thus,
2
2
2 reduces
)(2
)=
= lg .
Then,
= lg(2
. Then,
= (2
()
==2
()
2 2= +
2
=2=lg
2
.=
+Then,
lg
.
=+Then,
(2
2
.
=
+
()
the
.
Thus,
problem
()
= 2
the=
reduces
2
problem
2
+2
to
=+2
n=2to2+ .
Thus,
+ . Thus,
the problem
the problem
reduces
reduces
to
to
2
2
2
recurrence
tree: ()tree:
= 2
() =+2
.
xxviii recurrence
xxviii
2
+ .
recurrence
tree: ()
= 2 = 2+ . + .
xxviiirecurrence
xxviiitree: ()
n/4 n/4 n/4
16(n/4)=4n
n/4 n/4 n/4
Fig. 0.2 Recursion

Fig. 0.2 Recursion
tree of S(m)
tree=of2S(m/2)
S(m) =+
2S(m/2)
Fig.
m. 0.2
Fig.
+Recursion
m.
0.2 Recursion
tree oftree
S(m)
of =
S(m)
2S(m/2)
= 2S(m/2)
+ m. + m.
Fig. 3.4 Recursion tree of T (n) = 16T (n/4) + n.
1. What 1.
is the
What
problem
is thesize
problem
of ()?
size of ()?
1. What
1. What
is the problem
is the problem
size ofsize
()?
of ()?
0, 1, 2, 0,
,1,
lg2,
m , lg m
0, 1, 2,0,1,
2,
, lg m , lg m
The sub problem

The subsize
problem
for a size
nodefor
at depth
a nodekatisdepth
The
/2sub
.kThe
Thus,
isproblem
/2
subthe
problem
. Thus,
sub-problem
size for
the
size
asub-problem
node
forsize
a at
node
hits
depth
natsize
=depth
k1ishits
when
/2
knis=./2
1Thus,
when
. Thus,
the sub-problem
the sub-problem
size hits
sizen hits
= 1 when
n = 1 when
/2To =
/2
1 or,
=
1 or,number
equivalently,
when
nodes
=when
lg of
Thus,
/2
=
lgthe
/2
=
Thus,
tree
1each
or,
=
has
the
equivalently,
1level,
length
or,
tree
equivalently,
has
of
lg
length
when
+of
of
1when
Fig.
levels
lg
=from
lg0.2:
+
=1
Thus,
lg
levels
at
Thus,
theeach
tree
thelevel,
has
tree
length
has
of
lgfrom
of
+lg1from
levels
+1
levels
determine
Toequivalently,
determine
the
the of
number
at
nodes
each
To
determine
level,
at
To
determine
you
the
can
number
you
see
the
from
can
number
see
nodes
of
nodes
at
Fig.
each
0.2:
level,
you
can
youlength
see
can
see
Fig.
0.2:
Fig.
0.2:
Hence, the tree has kmax + 1 = log4 n + 1 levels: 0, 1, 2, , log4 n + 1.
(0, 1, 2, . . .(0,
, lg1,).
2, . . . , lg ).
(0, 1, 2,
(0,. .1,
. , 2,
lg .).
. . , lg ).
i = 0 : 1i =
= 020: 1 = 20
i = 0 i: =10=: 210 = 20
The number of nodes at level

k =1 0 is 1 (see also Fig. 3.4).
At
level k = 1 it is 16,
1
1
1
i = ?
1at: depth
2i =
=What
122.: 2What
2are
i=
1 i: =2?
1=: 22 = 2
2. What 2.
are What
the number
are thenodes
number
at depth
nodes
2.
?
are=the
number
the number
nodes nodes
at depth
at depth
?
2
2 the level k = log n
at level k = 2 the number
i = 2 : of
4i =
=nodes
222: 4 =is2216 16 = 256,
i = 2and
i: =42so
=: 24on,
= 2at
4
log
n2 2
kmax
log4 n
2
4
Lecturer: Hiqmet
Lecturer:
Kamberaj
Hiqmet Kamberaj
(International
(International
Balkan
Lecturer:
University)
Balkan
Hiqmet
University)
Kamberaj
Kamberaj
(International
(International
Balkan
PageBalkan
University)
9
Page
University)
kLecturer:
kHiqmet
k
k 9
has 16
= 16
nodes, or n nodes (since 4
i = k : 2i = k : 2
= n ).
i = k i: =2k : 2
level
k = 0, 1, 2, , log4 n +
1
is
as
following:
Time cost in each
lg m
i = lg m i: =2lg
m=: m2lg m = m
i = lgi m
=:lg2mlg:m =
2lgmm = m
i = 0 : n = 40 n
Now, weNow,
can also
we can
calculate
also calculate
the cost the
at each
Now,
costlevel:
Now,
atweeach
can
welevel:
also
can
also calculate
the cost
the at
cost
each
at each
level:level:
calculate
n
1
i
=
1
:
16
=
4n
=
4
n
i=0: m
i=0: m
i = 0 i: =m0 : m
4
i = 1 : 2(m/2)
i=1: =
2(m/2)
m
=m
i=2:
2 : =256
4(m/4)
i = 2 i: =
=
4(m/4)
m
m
n i = 1 i: =2(m/2)
1 : 2(m/2)
=m =m
2
=
n= m = m
i = 16n
2 i: =4(m/4)
2=: 44(m/4)
16
i = k : 2i k=
(m/2
k : k2) k=
(m/2
m k) = m
k
k
i = k i: =2kk (m/2
: 2k (m/2
)=m
)=m
lg m
lg m
i = lg m i: =2lg
mq :(1)2lg
=mqq(m)
(1) = q (m) i = lgi m
=:lg2mlg:m q2(1)
q=(1)
q (m)
= q (m)
The totalThe
timetotal
code
time
cancode
be calculated
can be calculated
as:
The total
The
as:time
total code
time code
can be
can
calculated
be calculated
as: as:
lg m 1
lg m 1
k=0
k=0
lg m 1lg m 1
2
2
S(m) = S(m)
q (mm
)+=qm
(mlg2 )m=
+m
q (m)
lgS(m)
m +S(m)
q=(m)
=m
)lg
=mm+lgqm(m)
+ q (m)
m=+
= m+ qm(m+2q) (m
which has
which
the upper
has the
bound:
upper bound:
k=0
whichwhich
has the
hasupper
the upper
bound:
bound:
k=0
Page 9Page 9
48
3 Recurrences
:
i = k : 16k
n
= 4k n
4k
:
k = lg n + 1 : n2 (1) = (n2 )
T (n) =
log4 n1
4k n + (n2 )
k=0
Using sum of geometric series formula:

n
ark =
k=0
arn+1 a
r1
Hence, for a = n and r = 4, you have

n4log4 n+1 n
+ (n2 )
41
4n2 n
=
+ (n2 )
3
T (n) =
If we ignore the term (n2 ), then you can write the solution as:
T (n) =
An upper bound of T (n) is:
4n2 n
3
4
T (n) n2
3
for n 0. If n0 = 0 and c = 4/3 are the witnesses, then

T (n) = O(n2 )
The lower bound is:
T (n)
4n2 n2
= n2
3
for n 0. If n0 = 0 and c2 = 1 are the witnesses, then

T (n) = (n2 )
3 Recurrences
49
Thus, the asymptotic solution is

T (n) = (n2 )
Example 3.13. Give asymptotic upper and lower bounds for T (n) n each of the following recurrences. Assume that T (n) is a constant for n 10. Make your bounds
as tight as possible, and justify your answers.
a) T (n) = 2T (n/3) + n lg n
b) T (n) = 3T (n/5) + lg2 n
c) T (n) = T (n/2) + 2n
d) T (n) = 2T ( n) + (lg lg n)
e) T (n) = 10T (n/3) + 17n1.2
f) T (n) = 7T (n/2) + n3
g) T (n) = T (n 2) + lg n
Solution:
a)
T (n) = 2T (n/3) + n lg n
You can see that
a = 2; b = 3
and f (n) = n lg n. Lets take
g(n) = nlogb a = nlog3 2
because log3 2 < 1,
f (n) = (nlog3 2+ )
where > 0. Moreover,
a f (n/b) = 2(n/3) lg(n/3) = (2/3)n (lg n lg 3) (2/3)n lg n k f (n)
where k = 2/3 < 1. Based on the Case 3,
T (n) = (n lg n)
50
3 Recurrences
b)
T (n) = 3T (n/5) + lg2 n
You can see that
a = 3; b = 5
and f (n) = lg2 n. Lets take
g(n) = nlogb a = nlog5 3
Now, you can write for n 1:
lg(n)1/4 n1/4
or
1
lg n n1/4
4
Multiplying both sides with 4, you get

lg n 4n1/4
Taking the square of both sides
lg2 n = f (n) 16n1/2 = 16nlog5 3
where > 0. Thus,
f (n) = O(nlog5 3 )
Using the Case 1,
T (n) = (nlog5 3 )
c)
T (n) = T (n/2) + 2n
So, a = 1, b = 2, and f (n) = 2n . We know that
f (n) = 2n n = nlogb a+
where > 0, thus
3 Recurrences
51
f (n) = (nlogb a+ )
From Case 3,
T (n) = (2n )
d)
T (n) = 2T ( n) + (lg lg n)
Substitute lg n m, or n = 2m , then
T (2m ) = 2T (2m/2 ) + (lg m)
Denoting S(m) T (2m ), you get
S(m) = 2S(m/2) + (lg m)
where a = 2, b = 2, and f (m) = lg m. Then, you can write that
f (m) = lg m 2 m = 2mlogb a
where = 0.5 > 0. Thus,
f (m) = O(mlogb a )
From Case 1,
S(m) = (mlogb a ) = (m)
or
T (n) = (lg n)
e)
T (n) = 10T (n/3) + 17n1.2
where a = 10, b = 3 and f (n) = 17n1.2 . You can write that
f (n) = 17n1.2 17n2 = 17nlogb a
where logb a = 2.096 and = 0.096 > 0. Thus
52
3 Recurrences
f (n) = O(nlogb a )
Use Case 1 of Master theorem, you can write
T (n) = (nlog10 3 )
f)
T (n) = 7T (n/2) + n3
where a = 7, b = 2 and f (n) = n3 . Since, log2 7 2.807, you can write
f (n) = n3 n3 = nlog2 7+0.193 = nlogb a+
where > 0. Thus,
f (n) = (nlogb a+ )
You can also prove that
7
a f (n/b) = 7(n/2)3 = n3 k f (n)
8
where
7
k < 1. Thus, using the Case 3 of the Master theorem,
8
T (n) = (n3 )
g)
T (n) = T (n 2) + lg n
You can solve this recurrence function using the recurrence tree method. The tree
for this function is shown in Fig. 3.5. As you can see, the total time cost is
T (n) = lg n + 2 (lg 2 + lg 4 + + lg(n 2))
The height of the tree is found by solving the following equation for k:
lg(n 2k) = lg 2
which gives
k=
n
1
2
3 Recurrences
53
Then, the nodes include the levels:

n
0, 1, 2, , 1
2
Thus,
T (n) = lg n + 2 (lg 2 + lg 4 + + lg(n 2))
lg n + 2 (lg n + lg n + + lg n)

n
1 lg n
= lg n + 2
2
= n lg n lg n
n lg n
for every n 1. Then, for witness parameters n0 = 1 and c = 1 > 0, we have
T (n) = O(n lg n)
lg n
lg(n-2)
lg(n-4)
lg(n-6)
lg 2
lg 6
lg(n-2)
Fig. 3.5 Recurrence tree of T (n) = T (n 2) + lg n.
lg 4
lg 2
Part II
Week 8 to 14
Chapter 4
Probabilistic Analysis and Randomised

Algorithms
4.1 Probabilistic Analysis

Example 4.1. In HIRE ASSISTANT , assuming that the candidates are presented
in a random order, what is the probability that you will hire exactly one time? What
is the probability that you will hire exactly n-times?
Solution: Because HIRE ASSISTANT always hires candidate 1, it hires exactly
once if and only if no candidates other than candidate 1 are hired. This event occurs
when candidate 1 is the best candidate of the n, which occurs with probability
P = 1/n
HIRE ASSISTANT hires n times if each candidate is better than all those who
were interviewed (and hired) before. This event occurs precisely when the list of
ranks given to the algorithm is 1, 2, , n, which occurs with probability:
P=
1
n!
Example 4.2. Use indicator random variables to compute the expected value of the
sum of n dice.
Solution: Let Xi be an indicator random variable associated with the event that the i
die is Xi , thus
57
58
4 Probabilistic Analysis and Randomised Algorithms
3
Xi =
if the ith is 1
if the ith is 2
if the ith is 3
if the ith is 4
if the ith is 5
if the ith is 6
The sum of the n dice is:
X = Xi
i=1
The expected value of X is

"
E[X] = E
Xi
i=1
and for E[Xi ], you can get

E[Xi ] =
P(Xi = j) j = 1 6 + 2 6 + 3 6 + 4 6 + 5 6 + 6 6 =
j=1
21
6
You can simplify this expression as following:

n
E[X] = E[Xi ]
i=1
n
21
i=1 6
=
=
7n
= 3.5n
2
where P(Xi ) is the probability of taking one of the numbers from 1 to 6: P(Xi ) = 1/6.
Example 4.3. Use indicator random variables to solve the following problem. Each
of n customers gives a hat-check person at a restaurant. The hat-check person gives
the hats back to the customers in a random order. What is the expected number of
customers that get back their own hat?
Solution: Use indicator random variables, you can define a random variable X that
equals the number of customers that get back their own hat, so that you want to
compute E[X].
For i = 1, 2, , n, define the indicator random variable
4.1 Probabilistic Analysis
59
Xi = I {customer i gets back his own hat}

Then,
X = X1 + X2 + + Xn = Xi
i=1
Since the the ordering of hats is random, each customer has a probability of 1/n of
getting back his or her own hat. Hence,
P(Xi = 1) =
1
n
and so
E[Xi ]P(Xi = 1) =
1
n
Therefore, you can write

"
E[X] = E
i=1
n
= E[Xi ]
i=1
n
= P(Xi = 1)
i=1
n
1
n
i=1
=
=1
Example 4.4. Let A[1..n] be an array of n distinct numbers. If i < j and A[i] > A[ j],
then the pair (i, j) is called an inversion of A. Suppose that each element of A is
chosen randomly, independently, and uniformly from the range 1 through n. Use
indicator random variables to compute the expected number of inversions.
Solution: Denote with Xi j an indicator random variable for the event where the pair
A[i], A[ j] for i < j is inverted, i.e.,
A[i] > A[ j]
More precisely, you can define
60
Xi j = I {A[i] > A[ j]}

for 1 i j n.
You can say that

P(Xi j = 1) = 1/2
since for any two distinct random numbers, the probability that the first is bigger
than the second is always 1/2. Thus,
E[Xi j ] = P(Xi j = 1) = 1/2
If you denote with X the random variable which is the total number of inverted
pairs in the array, then
X=
n1
i=1 j=i+1
Xi j
The expected number of X, which will give you the expected number of inverted
pairs, is given as
n1
"
E[X] = E
i=1 j=i+1
#
Xi j
You can simplify it using the linearity of expectation as:

"
#
E[X] = E
n1
i=1 j=i+1
n1
i=1 j=i+1
n1
Xi j
E[Xi j ]
(1/2)
i=1 j=i+1
n(n 1) 1
2
2
n(n 1)
=
4
=
Example 4.5. Determine the expected number of heads that we obtain when flipping
a fair coin.
Solution: Sample space is S = {H, T }, and we define a random variable Y which
takes on the values H and T , each with probability p = 1/2. We can then define an
4.2 Randomised algorithms
61
indicator random variable XH , associated with the coin coming up heads, which we
can express as the event Y = H. We write
1 if Y = H
XH = I{Y = H} =
0 if Y = T .
The expected number of heads obtained in one flip of the coin is simply the expected
value of our indicator variable XH :
E[XH ] = E[I{Y = H}] = 1 P(Y = H) + 0 P(Y = T )
= 1 (1/2) + 0 (1/2) = 1/2.
Example 4.6. Consider again the experiment of flipping a fair coin, which has two
possible outcomes, either tails (T ) or heads (H). Determine the expected number of
heads in n coin flips.
Solution: You can use indicator random variables. For i = 1, 2, ..., n, define
Xi = I {the i-th flip results in event H} .
Then, expected number of heads is calculated as
n
X = Xi .
i=1
Lemma says that E[Xi ] = P{H} = 1/2 for i = 1, 2, ..., n. Expected number of heads
is
i=1
i=1
i=1
E[X] = E[ Xi ] = E[Xi ] = 1/2 = n/2.

Example 4.7. Suppose you meet two arbitrarily chosen people. What is probability
their birthdays are different?
Solution: Let B2 denote the event that this happens.
62
Whatever the birthday of the first person is, there is only one day the second
person cannot pick as birthday, so:
P(B2 ) = 1 1/n.
When the same question is asked with three people, conditional probability become
helpful. The event B3 can be seen as the intersection of the event B2 the first two
have different birthdays, with the event A3 the third person has a birthday different
from that of the first two persons. Using multiplication rule,
P(B3 ) = P(A3 B2 ) = P(A3 |B2 )P(B2 )
P(A3 |B2 ) is the probability that when the first two days are marked in calendar than
the birthday of the third one should not coincide with any of these two days, that is:
P(A3 |B2 ) = 1 2/n).
P(B3 ) = P(A3 |B2 )P(B2 ) = (1 2/n)(1 1/n)
The event Bk of no coincident birthdays among k chosen persons, is the same as
the birthday of the first k 1 persons are different (event Bk1 ), and the birthday
of the kth person does not coincide with a birthday of any of the first k 1 persons
(the event Ak ), that is Bk = Ak Bk1 .
Applying multiplication rule:
P(Bk ) = P(Ak Bk1 ) = P(Ak |Bk1 )P(Bk1 )

= (1 (k 1)/k) P(Bk1 ),
since the person k should avoid k 1 days.
Apply the same step for
P(Bk1 ), P(Bk1 ), ,

k1
P(Bk ) = 1
P(Ak1 |Bk2 )P(Bk2 )
n
63

k2
k1
1
P(Bk2 )
= 1
n
n

k1
k2
= 1
1
P(Ak2 |Bk3 )P(Bk3 )
n
n
=

2
k1
1
P(B2 )
= 1
n
n

k1
2
1
= 1
1
1
n
n
n
Using the 1 + x ex , we get:
P(Bk ) e(k1)/n e(k2)/n e2/n e1/n
!
k1
= exp i/n
i=1

k(k 1)
= exp
1/2
2n
k(k 1)
ln(1/2) or k (1 + 1 + 8n ln 2)/2. For n = 365, k 23. Thus,
2n
if at least 23 people are in a room, the probability is at least 1/2 that at least two
when
people have the same birthday.
Chapter 5
The Quicksort Algorithm
Example 5.1. Illustrate the operation of PARTITION on the array:

A = [13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21]
Solution: The partition of the array is illustrated in figure below:
Example 5.2. What value of does PARTITION return when all elements in the array
have the same value?
Solution: The pseudo code is given in the figure below: If all elements of the array
A[p..r] are equal, then condition 4 is always satisfied, therefore, lines 5 and 6 will
be executed: n = (r 1) p + 1 = r p times. That is, the last will be:
i = (p 1) + r p = r 1
Since the value of q returned by this function is: i + 1, then
q = r1+1 = r
Example 5.3. Give a brief argument that the running time of PARTITION on a subarray of size n is (n).
Solution: Again, the pseudocode is given in Figure 5.2. The loop of line 3 is running
n = r 1 + p + 1 = r p times. The condition asked on the line 4 it takes a constant
time, let say c, then the total time of the algorithm is:
65
Chapter 7
Exercise 7.1-1: Illustrate the operation of PARTITION on the array:
= [13,19,9,5,12,8,7,4,11,2,6,21]
66
5 The Quicksort Algorithm
Solution to Exercise 7.1-1:

a)
i
13 19
12
11
21
r
b)
i
13 19
x
9
12
11
21
r
c)
i
13 19
12
11
21
r
d)
13 19
x
12
11
21
r
e)
13 19
12
x
8
11
21
r
f)
13 19
12
x
7
11
21
r
g)
13 19
12
x
4
11
21
r
h)
13 19
12
x
11
21
r
i)
13 19
12
11
x
2
21
r
j)
13 19
12
11
x
6
21
r
k)
13 19
12
11
21
l)
13 19
12
11
21
m)
i, x
13 19
12
11
21
r
Fig. 5.1 Partition

theWhat
array
[13,PARTITION
19, 9, 5, return
12, 8,
7, all
4,elements
11, 2, in6,the21].
Exerciseof
7.1-2:
valueAof=
does
when
array [. . ] have the
same value?
The pseudocode for the partition is:
PARTITION(A, p, r)
Exercise 7.1-2: What value of does PARTITION return when all elements in the array [. . ] have the
same value?
5 The Quicksort Algorithm The pseudocode for the partition is:
67
PARTITION(A, p, r)
1
[]
for to r-1
do if [] then
Fig. 5.2 Pseudocode.
+1
swap [] []
swap [ + 1] []
return + 1
If all elements of the array A[p..r] are equal, then condition 4 is always satisfied, therefore, lines 5 and 6
will be executed: = ( 1) + 1 = times. That is, the last will be:
T (n) = c(r p) = cn = (n) = ( 1) + = 1

Since the value
of q returned
this the
function
is: + 1, then = 1 + 1 = .
Example 5.4. Use the substitution
method
to provebythat
recurrence
T (n) = T (n 1) + (n)
Exercise 7.1-3: Give a brief argument that the running time of PARTITION on a subarray of size n is
the solution
().
T (n) = (n2 )
Solution: To show that T (n) = (n2 ), you have to show that T (n) = O(n2 ) and
T (n) = (n2 ).
1. T (n) = O(n2 ), which is the same as showing that
T (n) dn2 b
where d > 0 and b > 0. First you can write the recurrence as
T (n) = T (n) = T (n 1) + cn
and suppose that
T (k) dk2 b
for all k < n. Then, you have to show that T (k) dk2 b is also true for k n.
For that
68
T (n) = T (n 1) + cn d(n 1)2 b + cn

= dn2 2dn (b d) + cn
dn2 (b d)
which is true for
2dn + cn 0
and
bd > 0
Or
c
d<b
2
2. T (n) = (n2 ), which is equivalent to showing that

T (n) dn2 (d > 0)
Assumption is that
T (k) dk2 (k < n)
Then,
T (n) = T (n 1) + cn d(n 1)2 + cn
= dn2 2dn + d + cn
dn2 2dn + cn
dn2
For
2dn + cn 0
or
d c/2
Example 5.5. Suppose we use RANDOMIZEDSELECT to select the minimum
element of the array
69
A = {3, 2, 9, 0, 7, 5, 4, 8, 6, 1}
Describe
a sequence
partitions
that-SELECT
results
in the
a minimum
worst-case
performance
of
Exercise
7.2-2: Suppose of
we use
RANDOMIZED
to select
element of
the array
= {3; 2; 9; 0; 7; 5; 4; 8; 6; 1}. Describe a sequence of partitions that results in a worst-case
RANDOMIZEDSELECT.
performance of RANDOMIZED -SELECT.
Solution: Solution is describe by the figure below (Fig. 5.3):

Fig. 5.3 Partition of A.
Chapter 6
The Binary Search Trees
Example 6.1. For the set of keys

{1, 4, 5, 10, 16, 17, 21}
draw binary search trees of height 2, 3, 4, 5, and 6.
Solution:
Week 12
The height 2:
Exercise 12.1-1: For the set of keys {1,4,5,10,16,17,21}, draw binary search trees of height 2, 3, 4, 5, and 6.
10
a) The height 2
17
Fig. 6.1 The height 2.

b) Height 3
21
16
10
16
The height 3:
17
The height 4:
The height 5:
21
The height 6:
16
71
17
1
c) height 4
21
4
10
Exercise 12.1-1: For the set of keys {1,4,5,10,16,17,21},10

draw binary search trees of height 2, 3, 4, 5, and 6.
a) The height 2

4
72
1
b) Height 3
17
10
a) The height 2
17
16
510
16
21
6 The Binary Search Trees
21
16
10
17
b) Height 3
16
21
17
5
21
16
5
17
1
c) height 4
16
21
17
c) height 4
21
4
10
10
Example 6.2. Suppose that we have numbers between 1 and 1000 in a binary search
tree and want to search for the number 363. Which of the following sequences could
not be the sequence of nodes examined?
1. 2, 252, 401, 398, 330, 344, 397, 363
2. 924, 220, 911, 244, 898, 258, 362, 363
3. 925, 202, 911, 240, 912, 245, 363
4. 2, 399, 387, 219, 266, 382, 381, 278, 363
73
d) Height 5
4
5
1
d) Height 5
10
16
5
1
17
10
21
16
e) Height 6
17
1
4
e) Height 6
21
10
16
5
10
17
16
21
17
Exercise 12.2-1: Suppose that we have numbers between 1 and 1000 in a binary search tree and want to search
for the number 363. Which of the following sequences could not be the sequence of nodes
21 examined?
a. 2, 252, 401, 398, 330, 344, 397, 363
b. 924,
220, Suppose
911, 244,that
898,
363 between 1 and 1000 in a binary search tree and want to search
Exercise
12.2-1:
we258,
have362,
numbers
Fig. 6.5
6.240, of
c. The
925,height
202,
911,
912,
363 sequences could not be the sequence of nodes examined?
for the
number
363.
Which
the245,
following
d.
399, 401,
387, 398,
219, 330,
266,344,
382,397,
381,363
278, 363
a. 2,
2, 252,
e.
278, 911,
347, 244,
621,898,
299,258,
392,362,
358,363
363
b. 935,
924, 220,
c. 925, 202, 911, 240, 912, 245, 363
5. 935,
347,
621,
299,
392,
358,
Solution
Exercise
12.2-1:
The 381,
sequences
(a) can 363
be expected; (b) can be the sequence of nodes examined;
d. 278,
2, to
399,
387, 219,
266, 382,
278, 363
(c) can
a sequence
nodes
e. not
935,be
278,
347, 621,of299,
392,examined,
358, 363 because 912 > 911; sequence (d) can be a sequence of the nodes
Solution: The sequences (a) can be expected; (b) can be the sequence of nodes exSolution to Exercise 12.2-1: The sequences (a) can be expected; (b) can be the sequence of nodes examined;
amined;
(c) can not be a sequence of nodes examined, because 912 > 911; sequence
(c) can not be a sequence of nodes examined, because 912 > 911; sequence (d) can be a sequence of the nodes
(d) can be a sequence of the nodes examined; sequence (e) can not be, because after
621 we expect all the keys to be greater than 347, but 299 < 347.
Example 6.3. Print out the keys using the inorder tree walk algorithm of the following binary search tree: Solution: The pseudo code for inorder tree walk algorithm is
given in Fig. 6.7. The keys are printed out in the following order: 2, 3, 4, 5, 6, 7, 8.
examined; sequence (e) can not be, because after 621 we expect all the keys to be greater than 347, but 299 <
examined; sequence
347.(e) can not be, because after 621 we expect all the keys to be greater than 347, but 299 <
347.
74
6 The
Binary
Search
Trees
Exercise 3: Print out the keys using the inorder tree walk
algorithm
of the
following
binary search tree:
Exercise 3: Print out the keys using the inorder tree walk algorithm of the following binary search tree:
3
4
7
8
examined; sequence (e) can not be, because after 621 we expect all the keys to be greater than 347, but 299 <
347.
Solution to Exercise 3: The pseudo code for inorder tree walk algorithm is given below:
3: Printsearch
out the keys
Fig. 6.6 Exercise
The binary
tree.using the inorder tree walk algorithm of the following binary search tree:
Solution to Exercise 3: The pseudo code for inorder tree walk algorithm is given below:
5
The keys are printed out in the following order: 2, 3, 4, 5, 6, 7, 8.

Exercise 4: Print out2the keys using the preorder
tree walk algorithm
search tree:
4
8
6 of the following binary
5
The
keys
are printed
in the
following
order:
2, 3,below:
4, 5, 6, 7, 8.
to Exercise
3: for
The
pseudo
code
for out
inorder
tree
walk algorithm
is given
Fig. 6.7 Solution
The pseudo
code
inorder
tree
walk
algorithm.
Exercise 4: Print out the keys using the preorder tree walk algorithm of the following binary search tree:
3
5 algorithm of the folExample 6.4. Print out the keys using the preorder tree walk
4
lowing binary search tree (see Fig. 6.8.
Solution to Exercise 4: The pseudo code for preorder tree walk algorithm is given below:
TheThe
keys are
printed out
in the following
order: 2, 3,tree
4, 5, 6,
7,3 8. algorithm is given in Fig.76.9. The
Solution:
pseudo
code
for preorder
walk
Exercise 4: Print out the keys using the preorder tree walk algorithm of the following binary search tree:
3
Fig. 6.8 The binary search tree.
keys are printed out in the following order: 5, 3, 2, 4, 7, 6, 8.

Example 6.5. Print out the keys using the postorder tree walk algorithm of the following binary search tree in Fig. 6.10.
75
Fig. 6.9 The pseudo code

preorder
tree out
walk
Thefor
keys
are printed
in algorithm.
the following order: 5, 3, 2, 4, 7, 6, 8.
Exercise 5: Print out the keys using the postorder tree walk algorithm of the following binary search tree:
The keys
are printedcode
out in the
order: 5, 3,
2, 4, walk
7, 6, 8. algorithm is given in Fig. 6.11.
Solution: The
pseudo
forfollowing
postorder
tree
5
3
3
2
2
Solution
to Exercise
The pseudo
forispostorder
tree
Solution to Exercise
5: The pseudo
code for 5:
postorder
tree walkcode
algorithm
given below:
6
8
walk algorithm is given below:
Solution to Exercise 5: The pseudo code for postorder tree walk algorithm is given below:

Exercise 6: Which of the following is/are binary search trees?

Fig. 6.11 The pseudo code

The for
keyspostorder
are printedtree
outwalk
in thealgorithm.
following order: 2, 4, 3, 6, 8, 7, 5.
Example 6.6. Which of the following is/are binary search trees?

Solution: The first one is a binary search tree. The second one is a BST. The third
one is not, because, for example, the node with key 7 is on the right of the node with
key 8, which is wrong since 7 < 8 and it should be on the left of 8. Similarly, key 3
can not be on the right of 4, and the keys 8, 7, 6 can not be on the right of 9.
Solution to Exercise 5: The pseudo code for postorder tree walk algorithm is given below:
76
Fig. 6.12 The binary search trees.

Solution to Exercise 6: The first one is a binary search tree. The second one is a BST. The third one is not, because, for
example, the node with key 7 is on the right of the node with key 8, which is wrong since 7 < 8 and it should be on the left
Solution: The first one

is akey binary
search
of 8. Similarly,
3 can not be on the
right of 4, and tree.
the keys 8, 7,The
6 can not second
be on the right of 9.is not a BST, because 7
Solution to Exercise 6: The first one is a binary search tree. The second one is a BST. The third one is not, because, for
example, the node with key 7 is on the right of the node with key 8, which is wrong since 7 < 8 and it should be on the left
of 8. Similarly, key 3 can not be on the right of 4, and the keys 8, 7, 6 can not be on the right of 9.
Solution to Exercise 7: The first one is a binary search tree. The second is not a BST, because 7 can not be on the left of
Fig. 6.13 The binary search trees.
6. The third one is a BST.
can not be on the left of 6. The third one is a BST.

Solution to Exercise 7: The first one is a binary search tree. The second is not a BST, because 7 can not be on the left of
Solution to Exercise 8: The first one is a binary search tree. The second is a BST. The third is not a BST, because 3 can
6. Theis
thirda
onebinary
is a BST.
Solution: The first one
search tree. The second is a BST. The third is not
not be on the right of 4.
6
Exercise 9: Find the key 3 in the following binary search tree:
8
4
Solution to Exercise 8: The first one is a binary search tree. The second is a BST. The third is not a BST, because 3 can
not be on the right of 4.
Fig. 6.14 The binary search
trees.
Exercise 9: Find the key 3 in the following binary search tree:

2
a BST, because 3 can not be on the right of 4.
8
4
Example 6.9. Find the key 3 in the following binary search tree (see Fig. 6.15.)
Solution: Node 6, Key < 6 go to the left. Node 2, Key > 2 go to the right. Node
to Exercise 8: The first one is a binary

The
second is a BST. The third is not a BST, because 3 can
6 Thesearch
Binarytree.
Search
Trees
77
the right of 4.
6
9: Find the key 3 in the following binary search tree:

2
8
4
3
4, Key < 4, go to the left. Node 3, Key = 3. Time spent on each level is constant c,
so O(1). Time complexity is O(4), equal to the depth.
Example
6.10. Insert
the6,key
following
of to
Fig.
Solution
to Exercise
9: Node
Key5<in6 the
-> go
to the left.binary
Node 2,search
Key > tree
2 -> go
the6.16.
right. Node 4, Key < 4, go to the
left. Node 3, Key == 3. Time spent on each level is constant c, so O(1). Time complexity is O(4), equal to the depth.
Node 6, Key < 6, so go to the left. Node 2, Key > 2, so go to the right. Node 4,
Exercise 10: Insert the key 5 in the following binary search tree:
8
4
3
Solution
to Exercise
10:search
Nodetree.
6, Key < 6, so go to the left. Node 2, Key > 2, so go to the right. Node 4, Key > 4, so go to
Fig. 6.16
The binary
the right. Node NULL, insert Key=5. Time complexity is constant eat each level, O(1). Total time complexity is O(3).
6 Key = 5 as shown in Fig. 6.17. Time

Key > 4, so go to the right. Node NULL, insert
complexity is constant eat each level, O(1). Total time complexity is O(3).
Example 6.11. Delete the key 1 from the following binary search tree (Fig. 6.18).
1
3
7
5
3
Solution to Exercise 10: Node 6, Key < 6, so go to the left. Node 2, Key > 2, so go to the right. Node 4, Key > 4, so go to
the 78
right. Node NULL, insert Key=5. Time complexity is constant eat each
O(1). Total
complexity is O(3).
6 level,
The Binary
Searchtime
Trees
6
2
8
4
7
5
3
Fig. 6.17 The new binary search tree.
Week 13
Solution: Node 6, Key < 6, so go to the left. Node 2, Key < 1, so go to the left. Node
Exercise 1: Delete the key 1 from the following binary search tree:
6
8
4
Solution
to Exercise
1: search
Node tree.
6, Key < 6, so go to the left. Node 2, Key < 1, so go to the left. Node 1, Key ==1. No child
Fig. 6.18
The binary
of the key 1, so we are in the case 1. So, delete 1, and the new BST is given below.
6 in the case 1. So, delete 1, and the new
1, Key = 1. No child of the key 1, so we are
BST is given below in Fig. 6.19.

2
Example 6.12. Delete the key 8 from the following binary search tree, Fig. 6.20.
4
Solution: Node 6, Key > 6, so go to the right. Node7 8, Key = 8. One child of the key
8, so we are in the case 2. Point the parent of key 8 to its child, and the new BST is
5
given in Fig. 6.21.
6
Solution to Exercise 2: Node 6, Key > 6, so go to the right. Node 8, Key == 8. One child of the key 8, so we are in the
3 to the left. Node 2, Key < 1, so go to the left. Node 1, Key ==1. No
Solution to Exercise 1: Node 6, Key < 6, so go
of the key Solution

1, so
weBinary
are
inSearch
the1:case
theleft.
new
BST
is given
Exercise
Node1.6,So,
Keydelete
< 6, so1,goand
to the
Node
2, Key
< 1, sobelow.
go to the79
left. Node 1, Key ==1. No child
6 Theto
Trees
of the key 1, so we are in the case 1. So, delete 1, and the new BST is given below.
6
6
77
6
6
2
Fig. 6.20
The binary2:search
Solution
to Exercise
Nodetree.
6, Key > 6, so go to the right. Node 8, Key == 8. One child of the key 8, so we are in the
case 2. Point the parent of key 8 to its child, and the new BST is given below.
Example 6.13. Delete the key 2 from the following binary search tree as shown
Solution to Exercise
2: Node 6, Key > 6, so go to the right. Node 8, Key == 8. One child of the key 8, so we are1in
in Fig. 6.22.
case 2. Point the parent of key 8 to its child, and the new BST is given below.
Solution: Node 6, Key < 6, so go to the left. Node 2, Key = 2. Two children of the
key 2, so we are in the case 3. Find the minimum of the right subtree of the key 2,
which is the key 3, then delete the key 3 (using case 1). Finally, replace key 2 with
key 3 as shown in Fig. 6.23 in two steps. We can also think in a different way: Find
the maximum of the left subtree of the key 2, which is the key 1, then delete the key
1 (using case 1) and replace key 2 with key 1 as shown in Fig. 6.24 in two steps.
Week 136 The Binary Search Trees
80
Week 13
6
Week 13
11
24
7
4
3 3
3
Exercise 3: Delete
the key
2 from
the2following
binarybinary
search
tree:
Exercise
3: Delete
the key
from the following
search
tree:
6
6
2
1 4
7
3
Solution to Exercise 3: Node 6, Key < 6, so go to the left. Node 2, Key == 2. Two children of the key 2, so we are in the
Solution to Exercise 3: Node 6, Key < 6, so go to the

3 left. Node 2, Key == 2. Two children of the key 2, so we are in the
Fig.
Thethe
binary
search tree.
case6.22
3. Find
minimum
of the right subtree of the key 2, which is the key 3, then delete the key 3 (using case 1).
case 3. Find the minimum of the right subtree of the key 2, which is the key 3, then delete the key 3 (using case 1).
Finally, replace key 2 with key 3 as shown below in two steps:
Solution
Exercise
Node
Key
< 6,below
so gointotwo
thesteps:
left. Node 2, Key == 2. Two children of the key 2, so we are
Finally,toreplace
key 23:with
key6,
3 as
shown
6
case 3. Find the minimum of the right subtree of the key 2, which is the key6 3, then delete the key 3 (using case 1).
6
Finally, replace key 2 with

key 3 as shown below
in two steps:
2
8
2
1
8
7
3
4
7
3
3
1
We
can also
in a different
way: Find the maximum of the left subtree of the key 2, which is the key 1, then delete the
3 6.23
Fig.
The think
new binary
search tree.
key 1 (using case71) and replace key 2 with key 1 as shown below in two steps:
1 left subtree4of the key 2, which

7 is the key 1, then delete the
We can also think in a different way: Find the maximum of the
key 1 (using case 1) and replace key 2 with key 1 as shown below in two steps:
3
2
We can also think in a different way: Find the maximum of the left subtree of the key 2, which is the key 1, then de
key 1 (using case 1) and replace key 2 with key 1 as shown below in two steps:
WeekWeek
13 13
81
6
2
8
7
8
4
7
3
Exercise 4: Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an 3

initially empty binary search tree. Show the result of
deleting the root.
Example
6.14.4:Show
the result
inserting
1, 4,
Solution
to Exercise
The result
of theof
binary
search3,tree
is:6, 9, 2, 5, 7 into an initially empty
Exercise 4: Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an initially empty binary search tree. Show the result of
binary search tree. Show the result of deleting
the root.
3
deleting the root.
Solution: The result of the binary search tree is drawn in Fig. 6.25. The result of
1
Solution to Exercise 4: The result of the binary search
tree is:
The result of deleting the root, which the key 3 is as in the case 3, since it has two children. First, we find the minimum of
the right subtree, which is 4 and delete it. Since key 4 has one child, it is case 2, thus, we just point the parent of 4, key 3
to the child of 4, key 6. Then, replace key 3 with key 4.

3
7
4
6.25which
The binary
The result of deleting theFig.
root,
the search
key 3tree.
is as in the case 3, since it has two children. First, we find the minimum of
2
6 4 has one child, it is case 2, thus, we just point the 6parent of 4, key 3
the right subtree, which is 4 and delete it. Since key
deleting the root, which the key 3 is as in the case 3, since it has two children. First,
9
3
7
82
6 9The Binary Search Trees
we find the minimum of the right subtree, which is 4 and delete it. Since key 4 has
7
one child, it is case 2, thus, we just point the parent of 4, key 3 to the child of 4,
The result of deleting the root, which the key 3 is as in the case 3, since it has two children. First, we find the minimum of
key 6. Then, replace key 3 with key 4. The result is shown Fig. 6.26. Second way of
the right subtree, which is 4 and delete it. Since key 4 has one child, it is case 2, thus, we just point the parent of 4, key 3
3
3
7
deleting the root, is to find the maximum of the left subtree, which is 2, and delete
Week
it. In our example, this will be case 1, since
key 213has no children. Then, replace key
3 withway
key
2. Thethe
result
istoshown
6.27.of the left subtree, which is 2, and delete it. In our example, this
Second
of deleting
root, is
find the Fig.
maximum
will be case 1, since key 2 has no children. Then, replace key 3 with key 2.
2
Exercise 5: Show the result of deleting K, H and B. Indicate the corresponding CASE.
Solution to Exercise 5: Deleting K is the CASE 1:

F
Deleting H is the case 2:

B
Deleting B is the case 3:
83
9
Example
6.15. Show the result of deleting K, 5H and B from
binary search tree
9
in Fig. 6.28. Indicate the corresponding CASE.

7
7 Solution: Deleting K is the CASE 1 as shown in Fig. 6.29a. Deleting H is the CASE
se 5: Show the result of deleting K, H and B. Indicate the corresponding CASE.

F
n to Exercise 5: Deleting K is the CASE 1:

F
B
2 as shown
in Fig. 6.29b, and deleting B is the CASE 3 as shown in Fig. 6.29c.
D
Example 6.16. For Fthe following Binary Search Tree (Fig. 6.30), draw the resulting
g H is the case 2:
tree from inserting Integers 28, 7, 16, 35 in that order. Then draw the tree from
B
calling delete on Integers 13, 5, 25, 15, 20 in that order.

Solution:
A
g B is the case 3:
4
A
Exercise 5: Show the result of deleting K, H and B. Indicate the corresponding CASE.
F
B
84
H
6D The Binary Search Trees
Solution to Exercise 5: Deleting K is the CASE 1:
Deleting H is the case 2:

B
Deleting B is the case 3:
3.1
Example
For the following Binary Search Tree,

draw the resulting tree from inserting Integers 28, 7, 16,
K
35 in that order. Then draw the tree from calling delete on Integers 13, 5, 25, 15, 20 in that
order.
Fig. 6.29 The binary search
tree when
after deleting
a) K a
b)node
H andthat
c)B. has two children, choose to swap the node with its in-order
(Note:
you delete
predecessor.)
20
10
5
30
15
12
Fig. 6.30 The red-black tree.
25
17
Figure 2: Binary Search Tree
Chapter 7
Red-Black Trees
Example 7.1. Insert the key 4 in the following red-black tree, Fig. 7.1. Key 4 is
Week 13
black.
Exercise
6: Insert
key 4property
in the following
red-black
tree. Key
4 is black.
Solution: Inserting key
4 in black
maythe
violate
4: the number
of black
height
Fig. 7.1 The red-black Solution

tree.
to Exercise 6: Inserting key 4 in black may violate property 4: the number of black height m
each simple path from every node. First insert key 4 in the tree. Then, change the color of 3 to red.
must be the same on each simple path from every node. First insert key 4 in the tree.
Then, change the color of 3 to red. Next, rotate to the left around key 3 as shown in
Fig. 7.3.
Example 7.2. Insert the key 6 into the following read-black tree (Fig. 7.4). The key
6 is red.
Solution: First insert key 6 into the tree as shown in Fig. 7.5. It can be seen that there
Exercise 7: Insert the key 6 into the following read-black tree. The key 6 is red.
is no violation of the criteria for a red- black tree.
Example 7.3. Insert the key 5 with color red in the following red-black tree (Fig. 7.6).
10
4
85
8
18
Solution to Exercise 7: First insert key 6 into the tree. It can be seen that there is no violation of the c
black tree.
7
10
4
3
5
6
18
Solution: Inserting key

4 in black
maythe
violate
4: the number
of black
height
13
Exercise
6: Insert
key 4property
in theWeek
following
red-black
tree. Key
4 is black.
Exercise 6: Insert the key 4 in the following red-black tree. Key 4 is black.
Solution to Exercise 6: Inserting key 4 in black may violate property 4: the number of black height must be the same on
86
7 Red-Black Trees
Week 13
Week 13
Exercise 6: Insert the key 4 in the following red-black tree. Key 4 is black.
Exercise 6: Insert the key 4 in the following red-black tree.3Key 4 is black.
Solution to Exercise 6: Inserting key 4 in black may violate property 4: the number of black height must be the same
Solution
to Exercise
Inserting
4 in
black
maynode.
violate
property
the4 number
of black height must be the same on
must be the
same on 6:
each
simplekey
path
from
every
First
insert 4:
key
in the tree.
Then,
change
thefrom
color
of
to red.
each
simple
path
every
key
4 in the tree. Then, change the color of 3 to red.
Fig.3node.
7.2
TheFirst
new insert
red-black
tree.
Exercise 7: Insert the key 6 into the following read-black tree. The key 6 is red.
37
4 simple path from every node. First insert key 4 in the tree.4Then, change the color
each
10 of 3 to red.
4
each simple path from every node.
3 First insert key 4 in the tree. Then, change the color of 3 to red.
3 3
3
3
18
5
4
Exercise4 7: Insert the key 6 into the following

4 read-black tree. The key 6 is red.
7 It can be seen that there is no violation of the criteria for a redto Exercise 7: First insert key 6 into the tree.
Fig. 4.2 The new red-blackSolution
tree.7.3 The
Fig.
new red-black tree.
Exercise 7: Insert the keyblack

6 into
the following read-black tree. The key 6 is red.
tree.
7 The key 6 is red.

Exercise 7: Insert the key 6 into the4following read-black tree.
7 following read-black tree. The key 6 is red.
Exercise 7: Insert the key 6 into the
10
10
4
5
10
4
4
3
3
7
7
5
5
10
10
8
8
8
lxxi
18
18
18
18
18
Solution to Exercise 7: First insert key 6 into the tree. It can be seen that there is no violation of the criteria for a redFig. 7.4 The red-black tree.
Solution
seen that there is no violation of the criteria for a redblack
tree. to Exercise 7: First insert key 6 into the tree. It can beseen
Solution to Exercise 7: First insert key 6 into the tree. It can be
that there is no violation of the criteria for a red7
black tree.
Solution to Exercise 7: First
insert key 6 into the tree. It can be seen
that there is no violation of the criteria for a red7
black tree.
black tree.
47
4
3
3
4
5
5
6 tree.
Fig. 7.5 The new red-black
10
5
6
6
10
10
10
6
8
18
8
18
8
8
18
18
5
5
7 Red-Black Trees
87
Week 13
Solution: First insert key 5 into the tree and the result is drawn in Fig. 7.7. We
Exercise 8: Insert the key 5 with color red in the following red-black tree.
Week 13
Exercise 8: Insert the key 5 with color red in the following red-black tree.
Week 10
13
Exercise 8:
Insert the key 5 with color red in the following red-black tree.
10
Solution to Exercise 8:4First insert key 5 into the tree. We are in the CASE 2, then left-rotate(4).
are in the CASE

left-rotate(4). Then using CASE
10 3, right-rotate(7) to ob4 2, then
10
4
Solution to Exercise 8: First insert key 5 into the tree. We are in the CASE 2, then left-rotate(4).
5
Solution to Exercise 8: First insert key 5 into the tree. We are in the
10 CASE 2, then left-rotate(4).
4
Then using CASE 3, right-rotate(7).
10
10
Fig. 7.7 The new red-black tree.

4
5

7
tain Fig. 7.8. Then, recoiler key 4 to obtain Fig. 7.9.

Then, recolor key 4.
10
4 4
7
10
10
Then, recolor key44.
5 tree.
Exercise 9: Delete key 5 from the following red-black
7
10
10
18
76
4
Example 7.4. Delete key 5 from the following red-black tree (Fig. 7.10).
Exercise 9: Delete key 5 from the following red-black tree.
10
7
10
10
4
3
5
6
18
18
10
4
88
7 Red-Black Trees
Then, recolor
5 key 4.
10
10
5
4 Fig. 7.9 The new red-black tree.
10
Solution: First delete the key 5 from the tree to obtain red-black tree in Fig. 7.11.
4
10
6
18
6
Week 13
Property 3 is violated, change the color of key 6 and obtain red-black tree of Fig. 7.12.
Solution to Exercise 9: First delete the key 5 from the tree:
7
10
18
7.11 Thechange
new red-black
Property Fig.
3 is violated,
the colortree.
of key 6.
7
4
18
10
Exercise 10: Delete the root of the following red-black tree.

6
10
Solution to exercise 10: First delete the root of the tree using the case 3 of the BST:
9
5
10
10
18
Week 13
3 4
Solution to Exercise 9: First delete
the key 56 from the tree:
10
1018
18
3 Trees
7 Red-Black
Property 3 is violated, change the color of key 6.
10
7
4
Exercise 10: Delete the root of the following red-black tree.7
18
18
10
Property 3 is violated, Fig.

change
the color of key 6.
7.12 The new red-black tree.
3
10
3 the color of6key 6.

Property 3 is violated, change
89
18
Example 7.5. Delete4the root of the following

Fig. 7.13).
7 red-black tree (see 10
9
Solution: First delete the root of the tree using the case 3 of10the BST to obtain red-
6
3 following red-black
Exercise 10: Delete the root of the
tree.
18
Solution to exercise 10: First delete the root of the tree using
the case 3 of the BST:
6
9
5
5
5
Exercise 10: Delete the root of the following
red-black tree.
10
9
10
It can
be seen 10:
that the
new
tree satisfies
all the
of the red-black
Solution to
exercise
First
delete
the root
of properties
the tree using
the casetree.
3 of the
9 BST:
5 tree.
Fig. 7.13 The red-black
10
black tree in Fig. 7.14.

5 It can be seen that the new tree satisfies10all the properties of
Solution to exercise 10: First delete the root of the tree using the case 3 of the BST:
9
It can be seen that the new tree satisfies all the properties of the red-black tree.
5
10
It can be seen that the new tree satisfies all the properties of the red-black tree.
the red-black tree.
90
7 Red-Black Trees
Example 7.6. Insert the key 9 in red in following red-black tree (Fig. 7.15A).
Solution: First insert key 9 (in red) as shown in Fig. 7.15B. Property (3) is violated.
Question 1
Question:
Insertof
thenodes
key 9 in red
in following
Then, change the
colors
with
keyred-black
8 andtree.
11 in black, as shown in Fig. 7.15C.
Solution: First insert key 9 (in red) as shown in the middle figure. Property (3) is violated.
Then, change the colors of nodes with key 8 and 11 in black, as shown in the right figure.
10
10
10
Insert 9
recolor
11
11
11
Example 7.7. Insert the key 9 in red in following red-black tree shown in Fig. 7.16A.
Question 2
Solution: First insert key 9 (in red) as shown in Fig. 7.16B. There is no need for
Question: Insert the key 9 in red in following red-black tree.
Solution: First insert key 9 (in red) as shown in the right figure. There is no need for recoloring
recoloring or rotations.
or rotations.
10
10
Insert 9
11
12
12
13
11
13
Example 7.8. Insert the key 9 in black in following red-black tree shown in Fig. 7.17A.
Solution: First insert key 9 (in black) as shown in Fig. 7.17B. Property (4) is vio-
Question 3
7 Question:
Red-BlackInsert
Treesthe key 9 in black in following red-black tree.
91
lated.
Thus,First
Left-Rotate(8),
as shown
in Fig.
7.17C,
where
property
is violated.
Solution:
insert key 9 (in black)
as shown
in the
right figure.
Property
(4) is(4)
violated.
Thus,
Left-Rotate(8), as shown in the third figure, where property (4) is violated. Then, recolor 8.
Then, recolor 8 (see Fig. 7.17D)).
10
10
10
Insert 9
11
13
recolor 8
11
12
12
12
10
Left-Rotate(8)
13
13
11
12
11
13
Example 7.9. Insert the key 7 in red in following red-black tree Fig. 7.18A.
Question 4
Solution: First insert key 7 (in red) as shown in Fig. 7.18B. There is no need for
Question: Insert the key 7 in red in following red-black tree.
Solution: First insert key 7 (in red) as shown in the right figure. There is no need for
10
10
Insert 7
11
11
Example 7.10. Insert the key 7 in black in following red-black tree Fig. 7.19A.
Solution: First insert key 7 (in black) as shown in Fig. 7.19B. Property (4) is violated. Thus, you Right-Rotate(10) to get the red-black tree in Fig. 7.19C, where
property (4) is violated. Then, recolor 11 to get the red-black tree in Fig. 7.19D.
Example 7.11. Delete the key 10 from following red-black tree Fig. 7.20A.
Question 5
Question: Insert the key 7 in black in following red-black tree.
Solution: First insert key 7 (in black) as shown in the right figure. Property (4) is
violated. Thus, you Right-Rotate(10) to get the third figure, where property (4) is
violated. Then, recolor 11.
92
7 Red-Black Trees
10
10
Right-Rotate(10)
11
Recolor 11
11
Insert 7
10
10
11
11
Question 6
Question: Delete the key 10 from following red-black tree.
Solution: First delete 10 as shown in Fig. 7.20B. Property (3) is violated. Thus,
Solution: First delete 10 as shown in the middle figure. Property (3) is violated. Thus,
recolor 11,
and 11.
get the red-black tree in Fig. 7.20C.
recolor
8
8
Delete 10
10
11
8
11
Recolor 11
11
Solution: First delete 8 as shown in Fig. 7.21B. The new tree satisfied all the ??properties of red-black trees.
Solution: First delete 7 as shown in Fig. 7.22B. Property (4) is violated. Then, LeftRotate(8) to get to Fig. 7.22C, where property (4) is violated. Then, recolor 11 to
get to Fig. 7.22D, which satisfies all the properties of a red-black tree.

Solution: First delete 8 as shown in the right figure. The new tree satisfied all the
properties of red-black trees.
7 Red-Black Trees
93
8
Delete 8
10
Question9 8
10
11
11

Solution: First delete 7 as shown in the 2nd figure. Property (4) is violated. Then,
Left-Rotate(8)
to get
the third figure, where property (4) is violated. Then, recolor 11
Fig. 7.21
The red-black
tree.
to get the fourth figure, which satisfies all the properties of a red-black tree.
8
8
Delete 7
10
10
11
10
Left-Rotate (8)
11
10
11
Recolor 11
11

Algorithms - Problems

Uploaded by

Copyright:

Available Formats

Algorithms - Problems

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Algorithms - Problems

Uploaded by

Copyright:

Available Formats

What are the main topics covered in the document?

What are the main topics covered in the document?

What is the process to insert a new key into a red-black tree?

What is the process to insert a new key into a red-black tree?

Hiqmet Kamberaj

Solved Problems in Algorithms

Standard notations and common functions . . . . . . . . . . . . . . . . . . . . . . . .

Probabilistic Analysis and Randomised Algorithms . . . . . . . . . . . . . . . . 57

The Quicksort Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

The Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

Standard notations and common functions

Example 1.1. Show that a = blogb a , where a, b > 0.

1 Standard notations and common functions

1 Standard notations and common functions

Replacing the logarithmic expressions for x, y and z, you get

Example 1.5. Show that logc (a/b) = logc a logc b, a, b, c > 0.

1 Standard notations and common functions

Solution: From the definition of the floor and ceil functions:

1 Standard notations and common functions

Example 1.10. Show that

Solution: From the definition of the floor and ceil functions:

Example 1.11. Show that

1 Standard notations and common functions

dn/ae/b ddn/ae/be < dn/ae/b + 1

1 Standard notations and common functions

d(a 1)/be < da/be

which is the same as the definition.

1 Standard notations and common functions

lg(lg(i1) (n)) i > 0

1 Standard notations and common functions

Solution: Using the principle of the mathematical induction:

which is true based on the definition of the Fibonacci numbers.

and show that

We start with the definition of the Fibonacci number:

1 Standard notations and common functions

Solution: From the previous exercise:

as such, you can write that

or since 2 / 5 is a positive constant

1 Standard notations and common functions

Solution: First, take the expression

for n >= 4 for all c =

Example 2.1. Show that f (n) = an2 + bn + c is O(n2 ), where a > 0.

(using triangle inequality)

log n! log nn = n log n

Using C = 1/2, then for n n0 , we have

Combining both results, you can say that

Combining these two last expressions, for all n 2 | a |, you get

Since b > 0, inequality holds also for power b:

Denoting, c1 = (1/2)b , c2 = 2b , and n0 = 2 | a |, we have

b) You can write

0 2n2 + 4n + 10 2n2 + 4n2 + 10n2

On the other hand, you can also write

for n n0 . Thus, f (n) = (n2 ) with witnesses n0 = 0 and c2 = 2. Combining

these both, we can say that

b) f (n) = n, g(n) = log n2 .

for all n 1. Moreover, you can write

again for all n 1. if n0 = 1 and c = 1/4, then

for all n n0 . Hence, n = (log n2 ).

c) f (n) = n and g(n) = log n.