SOLUTION MANUAL
All Chapters Included
SOLUTIONS MANUAL TO INTRODUCTION TO ALGORITHMS
1
, Chapter 1
Michelle Bodnar, Andrew Lohr
August 28, 2017
Exercise 1.1-1
An example of a real world situation that would require sorting
would be if you wanted to keep track of a bunch of people’s file
folders and be able to look up a given name quickly. A convex hull
might be needed if you needed to secure a wildlife sanctuary with
fencing and had to contain a bunch of specific nesting locations.
Exercise 1.1-2
One might measure memory usage of an algorithm, or number of
people required to carry out a single task.
Exercise 1.1-3
An array. It has the limitation of requiring a lot of copying when
re-sizing, inserting, and removing elements.
Exercise 1.1-4
They are similar since both problems can be modeled by a graph
with weighted edges and involve minimizing distance, or weight, of a
walk on the graph. They are different because the shortest path
problem considers only two vertices, whereas the traveling
salesman problem considers minimizing the weight of a path that
must include many vertices and end where it began.
Exercise 1.1-5
If you were for example keeping track of terror watch suspects, it
would be unacceptable to have it occasionally bringing up a wrong
decision as to whether a person is on the list or not. It would be fine
to only have an approximate solution to the shortest route on which
to drive, an extra little bit of driving is not that bad.
2
,Exercise 1.2-1
A program that would pick out which music a user would like to
listen to next. They would need to use a bunch of information from
historical and pop- ular preferences in order to maximize.
Exercise 1.2-2
We wish to determine for which values of n the inequality 8n2 <
64n log2(n) holds. This happens when n < 8 ≤log2(n), or when n
43. In other words, insertion sort runs faster when we’re sorting at
most 43 items. Otherwise merge sort is faster.
Exercise 1.2-3
We want that 100n2 < 2n. note that if n = 14, this becomes
100(14)2 = 19600 > 214 = 16384. For n = 15 it is 100(15)2 =
22500 < 215 = 32768. So,
the answer is n = 15.
Problem 1-1
We assume a 30 day month and 365 day year.
1 Second 1 Minute 1 Hour 1 Day 1 Month 1 Year 1 Century
6 7 9 10 12 13 15
√ n
lg 21×10 26×10 23.6×10 28.64×10 22.592×10 23.1536×10 23.15576×10
n 1 × 1012 3.6 × 1015 1.29 × 1019 7.46 × 1021 6.72 × 1024 9.95 × 1026 9.96 × 1030
n 1 × 10 6
6 × 10 7
3.6 × 10 9
8.64 × 10 10
2.59 × 10 12
3.15 × 1013 3.16 × 1015
n lg n 62746 2801417 133378058 2755147513 71870856404 797633893349 6.86 × 1013
n2 1000 7745 60000 293938 1609968 5615692 56176151
n3 100 391 1532 4420 13736 31593 146679
2n 19 25 31 36 41 44 51
n! 9 11 12 13 15 16 17
1
, Chapter 2
Michelle Bodnar, Andrew Lohr
January 3, 2018
Exercise 2.1-1
31 41 59 26 41 58
31 41 59 26 41 58
31 41 59 26 41 58
26 31 41 59 41 58
26 31 41 41 59 58
26 31 41 41 58 59
Exercise 2.1-2
Algorithm 1 Non-increasing Insertion-Sort(A)
1: for j = 2 to A.length do
2: key = A[j]
3: // Insert A[j] into the sorted sequence A[1..j
— 1].
4: i = j— 1
5: while i > 0 and A[i] < key do
6: A[i + 1] = A[i]
7: i = i— 1
8: end while
9: A[i + 1] = key
10: end for
Exercise 2.1-3
On each iteration of the loop body, the invariant upon entering is
that there is no index k < j so that A[k] = v. In order to proceed to
the next iteration of the loop, we need that for the current value
of j, we do not have A[j] = v. If the loop is exited by line 5, then
we have just placed an acceptable value in i on the previous line.
If the loop is exited by exhausting all possible values of j, then we
know that there is no index that has value j, and so leaving NIL
in i is correct.
Exercise 2.1-4
2
All Chapters Included
SOLUTIONS MANUAL TO INTRODUCTION TO ALGORITHMS
1
, Chapter 1
Michelle Bodnar, Andrew Lohr
August 28, 2017
Exercise 1.1-1
An example of a real world situation that would require sorting
would be if you wanted to keep track of a bunch of people’s file
folders and be able to look up a given name quickly. A convex hull
might be needed if you needed to secure a wildlife sanctuary with
fencing and had to contain a bunch of specific nesting locations.
Exercise 1.1-2
One might measure memory usage of an algorithm, or number of
people required to carry out a single task.
Exercise 1.1-3
An array. It has the limitation of requiring a lot of copying when
re-sizing, inserting, and removing elements.
Exercise 1.1-4
They are similar since both problems can be modeled by a graph
with weighted edges and involve minimizing distance, or weight, of a
walk on the graph. They are different because the shortest path
problem considers only two vertices, whereas the traveling
salesman problem considers minimizing the weight of a path that
must include many vertices and end where it began.
Exercise 1.1-5
If you were for example keeping track of terror watch suspects, it
would be unacceptable to have it occasionally bringing up a wrong
decision as to whether a person is on the list or not. It would be fine
to only have an approximate solution to the shortest route on which
to drive, an extra little bit of driving is not that bad.
2
,Exercise 1.2-1
A program that would pick out which music a user would like to
listen to next. They would need to use a bunch of information from
historical and pop- ular preferences in order to maximize.
Exercise 1.2-2
We wish to determine for which values of n the inequality 8n2 <
64n log2(n) holds. This happens when n < 8 ≤log2(n), or when n
43. In other words, insertion sort runs faster when we’re sorting at
most 43 items. Otherwise merge sort is faster.
Exercise 1.2-3
We want that 100n2 < 2n. note that if n = 14, this becomes
100(14)2 = 19600 > 214 = 16384. For n = 15 it is 100(15)2 =
22500 < 215 = 32768. So,
the answer is n = 15.
Problem 1-1
We assume a 30 day month and 365 day year.
1 Second 1 Minute 1 Hour 1 Day 1 Month 1 Year 1 Century
6 7 9 10 12 13 15
√ n
lg 21×10 26×10 23.6×10 28.64×10 22.592×10 23.1536×10 23.15576×10
n 1 × 1012 3.6 × 1015 1.29 × 1019 7.46 × 1021 6.72 × 1024 9.95 × 1026 9.96 × 1030
n 1 × 10 6
6 × 10 7
3.6 × 10 9
8.64 × 10 10
2.59 × 10 12
3.15 × 1013 3.16 × 1015
n lg n 62746 2801417 133378058 2755147513 71870856404 797633893349 6.86 × 1013
n2 1000 7745 60000 293938 1609968 5615692 56176151
n3 100 391 1532 4420 13736 31593 146679
2n 19 25 31 36 41 44 51
n! 9 11 12 13 15 16 17
1
, Chapter 2
Michelle Bodnar, Andrew Lohr
January 3, 2018
Exercise 2.1-1
31 41 59 26 41 58
31 41 59 26 41 58
31 41 59 26 41 58
26 31 41 59 41 58
26 31 41 41 59 58
26 31 41 41 58 59
Exercise 2.1-2
Algorithm 1 Non-increasing Insertion-Sort(A)
1: for j = 2 to A.length do
2: key = A[j]
3: // Insert A[j] into the sorted sequence A[1..j
— 1].
4: i = j— 1
5: while i > 0 and A[i] < key do
6: A[i + 1] = A[i]
7: i = i— 1
8: end while
9: A[i + 1] = key
10: end for
Exercise 2.1-3
On each iteration of the loop body, the invariant upon entering is
that there is no index k < j so that A[k] = v. In order to proceed to
the next iteration of the loop, we need that for the current value
of j, we do not have A[j] = v. If the loop is exited by line 5, then
we have just placed an acceptable value in i on the previous line.
If the loop is exited by exhausting all possible values of j, then we
know that there is no index that has value j, and so leaving NIL
in i is correct.
Exercise 2.1-4
2
