算法导论答案.pdf

Solutions for Introduction to algorithms

second edition

Philip Bille

The author of this document takes absolutely no responsibility for the contents. This is merely

a vague suggestion to a solution to some of the exercises posed in the book Introduction to algo-

rithms by Cormen, Leiserson and Rivest. It is very likely that there are many errors and that the

solutions are wrong. If you have found an error, have a better solution or wish to contribute in

some constructive way please send a message to beetle@it.dk.

It is important that you try hard to solve the exercises on your own. Use this document only as

1.2 − 2

Insertion sort beats merge sort when 8n

2

< 64n lg n, ⇒n < 8 lg n, ⇒2

n/8

< n. This is true for

2 6 n 6 43 (found by using a calculator).

Rewrite merge sort to use insertion sort for input of size 43 or less in order to improve the

running time.

1 − 1

We assume that all months are 30 days and all years are 365.

2

2.1 − 2

In line 5 of INSERTION-SORT alter A[i] > key to A[i] < key in order to sort the elements in

nonincreasing order.

2.1 − 3

As a loop invariant we say that none of the elements at index A[1, . . . , i − 1] are equal to v.

Clearly, all properties are fullfilled by this loop invariant.

2.2 − 1

− 100n + 3 = Θ(n

3

).

2.2 − 2

j ←FIND -MIN(A, i, n)

A[j] ↔A[i]

As a loop invariant we choose that A[1, . . . , i − 1] are sorted and all other elements are greater

than these. We only need to iterate to n − 1 since according to the invariant the nth element will

then the largest.

The n calls of FIND -MIN gives the following bound on the time complexity:

This holds for both the best- and worst-case running time.

2.2 − 3

Given that each element is equally likely to be the one searched for and the element searched for is

present in the array, a linear search will on the average have to search through half the elements.

This is because half the time the wanted element will be in the first half and half the time it will

be in the second half. Both the worst-case and average-case of LINEAR-SEARCH is Θ(n).

3

2.2 − 4

One can modify an algorithm to have a best-case running time by specializing it to handle a best-

case input efficiently.

2.3 − 5

A recursive version of binary search on an array. Clearly, the worst-case running time is Θ(lg n).

Algorithm 3 BINARY-SEARCH(A, v, p, r)

return BINARY-SEARCH(A, v, p, j)

return BINARY-SEARCH(A, v, j, r)

2.3 − 7

if A[i] > 0 and BINARY-SEARCH(A, A[i] − x, 1, n) then

Clearly, this algorithm does the job. (It is assumed that nil cannot be true in the if-statement.)

4

3.1 − 1

Let f(n), g(n) be asymptotically nonnegative. Show that max(f(n), g(n)) = Θ(f(n) + g(n)). This

means that there exists positive constants c

1

, c

and n

0

such that,

1

average of f(n) and g(n). Note the significance of the “asymptotically nonnegative” assumption.

The first inequality could not be satisfied otherwise.

3.1 − 4

n+1

= O(2

n

) since 2

n+1

n

n

! However 2

2n

is not O(2

): by definition we have

2n

= (2

3 − 4

Let f(n) and g(n) be asymptotically positive functions.

a. No, f(n) = O(g(n)) does not imply g(n) = O(f(n)). Clearly, n = O(n

To show that this is smaller than b lg g(n) for some constant b we set lg c + lg g(n) = b lg g(n).

Dividing by lg g(n) yields:

b =

lg(c) + lg g(n)

lg g(n)

lg c

lg g(n)

+ 1 6 lg c + 1

The last inequality holds since lg g(n) > 1.

d. No, f(n) = O(g(n)) does not imply 2

f(n)

g(n)

). If f(n) = 2n and g(n) = n we have that

5