Chapter 1

Introduction to Algorithms

Finding Counter Examples

1.1. Show that a + b can be less than min(a, b).

1.2. Show that a × b can be less than min(a, b).

1.3. Design/draw a road network with two points a and b such that the fastest route between a and b is not the shortest route.

1.4. Design/draw a road network with two points a and b such that the shortest route between a and b is not the route with the fewest turns.

1.5. The knapsack problem is as follows: given a set of integers S = {s1, s2. . . , sn}, and a target number T, find a subset of S that adds up exactly to T. For example, there exists a subset within S = {1, 2, 5, 9, 10} that adds up to T = 22 but not T = 23.

Find counterexamples to each of the following algorithms for the knapsack problem. That is, give an S and T where the algorithm does not find a solution that leaves the knapsack completely full, even though a full-knapsack solution exists.

(a) Put the elements of S in the knapsack in left to right order if they fit, that is, the first-fit algorithm.

(b) Put the elements of S in the knapsack from smallest to largest, that is, the best-fit algorithm.

(c) Put the elements of S in the knapsack from largest to smallest.

1.6. The set cover problem is as follows: given a set S of subsets S1, . . . , Sm of the universal set U = {1, ..., n}, find the smallest subset of subsets T ⊆ S such that ∪ti∈T ti = U. For example, consider the subsets S1 = {1, 3, 5}, S2 = {2, 4}, S3 = {1, 4}, and S4 = {2, 5}. The set cover of {1, . . . , 5} would then be S1 and S2.

Find a counterexample for the following algorithm: Select the largest subset for the cover, and then delete all its elements from the universal set. Repeat by adding the subset containing the largest number of uncovered elements until all are covered.

1.7. The maximum clique problem in a graph G = (V, E) asks for the largest subset C of vertices V such that there is an edge in E between every pair of vertices in C. Find a counterexample for the following algorithm: Sort the vertices of G from highest to lowest degree. Considering the vertices in order of degree, for each vertex add it to the clique if it is a neighbor of all vertices currently in the clique. Repeat until all vertices have been considered.

Proofs of Correctness

1.8. Prove the correctness of the following recursive algorithm to multiply two natural numbers, for all integer constants c ≥ 2.

Multiply(y, z)

if z = 0 then return(0) else

return(Multiply(cy, [z/c]) + y · (z mod c))

1.9. Prove the correctness of the following algorithm for evaluating a polynomial anxn + an−1xn−1 + · · · + a1x + a0.

Horner(a, x)

p = an

for i from n − 1 to 0

p = p · x + ai

return p

1.10. Prove the correctness of the following sorting algorithm.

Bubblesort (A)

for i from n to 1

for j from 1 to i − 1

if (A[j] > A[j + 1])

swap the values of A[j] and A[j + 1]

1.11. The greatest common divisor of positive integers x and y is the largest integer d such that d divides x and d divides y. Euclid’s algorithm to compute gcd(x, y) where x > y reduces the task to a smaller problem:

gcd(x, y) = gcd(y, x mod y)

Prove that Euclid’s algorithm is correct.

Induction

1.12.

1.13

1.14

1.15

1.16

1.17

1.18

1.19

1.20

Estimation

1.21. Do all the books you own total at least one million pages? How many total pages are stored in your school library?

1.22. How many words are there in this textbook?

1.23. How many hours are one million seconds? How many days? Answer these questions by doing all arithmetic in your head.

1.24. Estimate how many cities and towns there are in the United States.

1.25. Estimate how many cubic miles of water flow out of the mouth of the Mississippi River each day. Do not look up any supplemental facts. Describe all assumptions you made in arriving at your answer.

1.26. How many Starbucks or McDonald’s locations are there in your country?

1.27. How long would it take to empty a bathtub with a drinking straw?

1.28. Is disk drive access time normally measured in milliseconds (thousandths of a second) or microseconds (millionths of a second)? Does your RAM memory access a word in more or less than a microsecond? How many instructions can your CPU execute in one year if the machine is left running all the time?

1.29. A sorting algorithm takes 1 second to sort 1,000 items on your machine. How long will it take to sort 10,000 items. . .

(a) if you believe that the algorithm takes time proportional to n2, and

(b) if you believe that the algorithm takes time roughly proportional to n log n?

Implementation Projects

1.30

1.31

1.32

Interview Problems

1.33

1.34

1.35

1.36

1.37

1.38

Back to Chapter List