Complementi di analisi matematica per l'ingegneria informatica - esercitazioni svolte dal Cormen

REE NSERT

A node and value

Input: z k.

The binary tree with inserted.

Output: k

if nil then

=

z

key[z] k

← nil

left[z] ← nil

right[z] ←

else

if then

key[z]

k <

T -I (left[z], k)

REE NSERT

else

T -I (right[z], k)

REE NSERT

end if

end if 17

−

12.3 5

The deletion operation is not commutative. A counterexample is shown in figure 1.

5 5

5

2 4

2

Delete 1 Delete 2

1 4 3

4

3 3

5 5 5

2 3 3

Delete 2 Delete 1

1 4 1 4 4

3

Figure 1: Two deletions where the order of the operations matter.

18

−

13.1 5

By property the longest and shortest path must contain the same number of black nodes. By

5

property every other nodes in the longest path must be black and therefore the length is at most

4

twice that of the shortest path.

−

13.1 6

Consider a red-black tree with black-height If every node is black the total number of internal

k.

k 2k

nodes is If only every other nodes is black we can construct a tree with nodes.

− −

2 1. 2 1

−

13.3 1

If we choose to set the colour of a newly inserted node to black then property is not violated but

4

clearly property is violated.

5

−

13.3 2

Inserting the keys into an initially empty red-black tree yields the trees depicted

41, 38, 31, 12, 19, 8

in figure 2 on page 20. 19

41 b

41 b

38 r 41 b 38 b

3

38 41

r r

31 r

r

31 38 b 38 b

1

41 r

31 r 41

b b

31

12 r 12 r

38 b 38 b 38 b

41 41 41

31 b b 31 b b 19 b b

2 3

12 19 12 31 r

r r r

r 12 r

19 38 b

38 b 41

19 r b

41

19 b b 1 12 31 b

b

12 31 r

r r

8

r

8

Figure 2: Inserting into a red-black tree. The arrows indicate transformations.

41, 38, 31, 12, 19, 8

Notice that the root is always coloured black

−

13.3 3

Show that property is preserved in figure and assumming the height of and

5 13.5 13.6 α, β, γ, δ

is For the black height for nodes and is in both cases since all the subtrees

+

k. 13.5 A,B D k 1

have black height Node has black height on the left and on the right since the

+ +

k. C k 1 k 2

20

black height of its black children is For it is clearly seen that both and have black

+

k 1. 13.6 A, B C

height We see that the black height is well defined and the property is maintained through

+

k 1.

the transformations.

−

13.4 7

Inserting and immidiately deleting need not yield the same tree. Here is an example that alters

the structure and one that changes the colour.

b

3 b

2

b

2 Delete 1

Insert 1 r

2 r r

r 3

1 3

b

3

b

3 b

3

Delete 1

Insert 1 r

r b

r

r b

2 4

2 4 2 4

1

Figure 3: Inserting and deleting 1

21

−

15.1 5

Show that and is impossible for any in any instance of F -W . Assume

[j] = [j] =

l 2 l 1 j ASTEST AY

1 2

that this is the case and consider the values of We have by definition that:

f.

min(f

[j] = [j − + [j − + +

f 1] a , f 1] t a , j)

1 1 1,j 2 2,j−1 1

min(f

[j] = [j − + [j − + +

f 1] a , f 1] t a , j)

2 2 2,j 1 1,j−1 2

Since and we have that:

[j] = [j] =

l 2 l 1

1 2 [j − + [j − + +

f 1] a > f 1] t a , j

1 1,j 2 2,j−1 1

[j − + [j − + +

f 1] a > f 1] t a , j

2 2,j 1 1,j−1 2

By cancelling out the we obtain a contradiction and the statement follows.

a’s

−

15.2 1

Solve the matrix chain order for a specific problem. This can be done by computing M -

ATRIX

h5,

C -O where or simply using the equation:

(p) =

p 10, 3, 12, 5, 50, 6i

HAIN RDER if =

0 i j

=

m[i, j] if

+ + +

{m[i, }

min k] m[k 1, j] p p p i < j

i6k<j i−1 k j

The resulting table is the following:

i\j 1 2 3 4 5 6

1 0 150 330 405 1655 2010

2 0 360 330 2430 1950

3 0 180 930 1770

4 0 3000 1860

5 0 1500

6 0

The table is computed simply by the fact that for all This information is used to

=

m[i, i] 0 i.

compute for an so on.

+ = −

m[i, i 1] i 1, . . . n 1

−

15.3 2

Draw a nice recursion tree. The M algorithm performs at most a single call to any pair

ERGESORT

of indices of the array that is being sorted. In other words, the subproblems do not overlap and

therefore memoization will not improve the running time.

−

15.4 3

Give an efficient memoized implementation of LCS-L . This can done directly by using:

ENGTH

 if or

= =

0 i 0 j 0





=

c[i, j] if and

− − + =

c[i 1, j 1] 1 i, j > 0 x y

i j



 6

max(c[i, if and

− − =

j 1], c[i 1, j]) i, j > 0 x y

i j

22

LCS-L

Algorithm 8 (X, Y)

ENGTH

The two strings and

Input: X Y.

The longest common substring of and

Output: X Y.

length[X]

m ← length[Y]

n ←

for to do

i 1 m

←

for to do

j 1 n

← −1

c[i, j] ←

end for

end for

L -L

return (X, Y, m, n)

OOKUP ENGTH

L -L

Algorithm 9 (X, Y, i, j)

OOKUP ENGTH

if then

−1

c[i, j] >

return c[i, j]

end if

if or then

= =

i 0 j 0

c[i, j] 0

←

else

if then

=

x y

i i L -L (X, − − +

c[i, j] Y, i 1, j 1) 1

← OOKUP ENGTH

else max{L -L L -L

(X, − (X, −

c[i, j] Y, i, j 1), Y, i 1, j)}

← OOKUP ENGTH OOKUP ENGTH

end if

end if

return c[i, j]

−

15.4 5 hx i

Given a sequence we wish to find the longest monotonically increasing subse-

=

X , x , . . . , x

1 2 n 0

quence. First sort the elements of and create another sequence . Finding the longest common

X X

0

subsequence of and yields the longest monotonically increasing subsequence of The run-

X X X.

2 2

ning time is since sorting can be done in lg and the call to L -L is

) ).

O(n O(n n) O(n

CS ENGTH

−

15 1

Compute the bitonic tour of points in the plane. Sort the points and enumerate from left to right:

n

For any and for any let denote the minimun length of

1, . . . n. i,1 i n, k,1 k n, B[i, k]

6 6 6 6

two disjoint bitonic paths, one from to the other from to When we have a minumin

=

1 i, 1 k. i k

cost bitonic tour through the first points. When we have a minimum cost bitonic tour

= =

i i k n

through all points. Note that we need only consider disjoint paths since any non-disjoint paths

n

cannot be optimal due to the triangle inequality. We can now describe how to compute using

B

dynamic programming.

First define We will determine the value of for some fixed and for all

= +

B[0, 0] 0. B[i 1, k] i k,

by using from the first rows and columns of

+

1 k i 1 B-values i i B.

6 6 The minimun cost disjoint paths from to and from to must contain the

Case +

1: k < i. 1 i 1 1 k

edge Therefore

(i, +

i 1). + = + +

B[i 1, k] B[i, k] w(i, i 1)

23

In other words, we a looking for The edge ending in comes from

Case = + +

2: k i. B[i 1, i]. i 1

Hence

u, 1 u < i.

6 min

+ = + +

{B[i,

B[i 1, i] u] w(u, i 1)}

16u<1

The two edges entering must come from and from some

Case = + +

3: k i 1. i 1 i u,1 u < i.

6

Therefore min

+ + = + + + +

{B[i,

B[i 1, i 1] u] w(i, i 1) w(u, i 1)}

16u<1

−

15 4

The problem can be transformed into a tree colouring problem where we consider the supervisor

tree and colour each node red if the employee is attending and white otherwise. The parent of a

red node must be white. We wish to colour the tree so that the sum of the conviality of the nodes

is maximised. Let be the conviviality of the three rooted at the node that is coloured

= (x,

v T c) x

with colour We can construct the following recursion:

c.

If is a leaf with convivialty and colour then:

x v c

if R

=

v x ED

(x, =

T c) if W

=

0 x HITE

If is not a leaf then similarly:

x P W if R

+ (x.child ) =

v T , x

HITE ED

i

i

(x, =

T c) P max(T W R if W

(x.child ), (x.child )) =

, T , x

HITE ED HITE

i i

i

The maximal conviviality is then given by max(T W R Im-

= (root, ), (root, ).

v v T

HITE ED

max max

plementing this recursion yields a straight forward algorithm using memoization. Since there is

exactly one subproblem for each node the running time will be for an node tree.

O(n) n

Notes for the exercises

• Thanks to Jarl Friis for the tedious calculation of the table in exercise −

15.2 1.

• Thanks to Pawel Winter for providing a solution to −

15 1.

24

−

16.1 3

Find the smallest number of lecture halls to schedule a set of activities in. To do this efficiently

S

move through the activities according to starting and finishing times. Maintain two lists of lecture

halls: Halls that are busy at time and halls that are free at time When is the starting time

t t. t

for some activity schedule this activity to a free lecture hall and move the hall to the busy list.

Similarly, move the hall to the free list when the activity stops. Initially start with zero halls. If

there are no halls in the free list create a new hall.

The above algorithm uses the fewest number of halls possible: Assume the algorithm used m

halls. Consider some activity that was the first scheduled activity in lecture hall was put in

a m. i

the hall because all of the halls were busy, that is, at the time is scheduled there are

−

mth m 1 a

activities occuring simultaneously. Any algorithm must therefore use at least halls, and the

m m

algorithm is thus optimal.

The algorithm can be implemented by sorting the activities. At each start or finish time we can

schedule the activities and move the halls between the lists in constant time. The total time is thus

dominated by sorting and is therefore lg

Θ(n n).

−

16.1 4

Show that selecting the activity with the least duration or with minimun overlap or earliest starting

time does not yield an optimal solution for the activity-selection problem. Consider figure 4:

(a) (b)

(c)

Figure 4: Three examples with other greedy strategies that go wrong

S