Chapter 1
Michelle Bodnar, Andrew Lohr
December 30, 2015
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 santuary 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 resizing,
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.
1
,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 > 21 4 = 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 dday month and 365 day year.
1 Second 1 Minute 1 Hour 1 Day 1 Month 1 Year 1 Century
6 7 9
8.64×1010 12
3.1536×1013 15
lg n 21×10 26×10 23.6×10 2 22.592×10 2 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 × 106 6 × 107 3.6 × 109 8.64 × 1010 2.59 × 1012 3.15 × 1013 3.16 × 1015
n lg n 189481 8.64 × 106 4.18 × 108 8.69 × 109 2.28 × 1011 2.54 × 1012 2.20 × 1014
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
2
, Chapter 2
Michelle Bodnar, Andrew Lohr
December 30, 2015
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 Nonincreasing 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: end for
10: A[i + 1] = key
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 procede 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 N IL in i
is correct.
1
, 1: i = N IL
2: for j = 1 to A.length do
3: if A[j] = v then
4: i=j
5: return i
6: end if
7: return i
8: end for
Exercise 2.1-4
Input: two n-element arrays A and B containing the binary digits of two
numbers a and b.
Output: an (n + 1)-element array C containing the binary digits of a + b.
Algorithm 2 Adding n-bit Binary Integers
1: carry = 0
2: for i=1 to n do
3: C[i] = (A[i] + B[i] + carry) (mod 2)
4: if A[i] + B[i] + carry ≥ 2 then
5: carry = 1
6: else
7: carry = 0
8: end if
9: end for
10: C[n+1] = carry
Exercise 2.2-1
n3 /1000 − 100n2 − 100n + 3 ∈ Θ(n3 )
Exercise 2.2-2
Input: An n-element array A.
Output: The array A with its elements rearranged into increasing order.
The loop invariant of selection sort is as follows: At each iteration of the for
loop of lines 1 through 10, the subarray A[1..i − 1] contains the i − 1 smallest
elements of A in increasing order. After n − 1 iterations of the loop, the n − 1
smallest elements of A are in the first n − 1 positions of A in increasing order,
so the nth element is necessarily the largest element. Therefore we do not need
to run the loop a final time. The best-case and worst-case running times of
selection sort are Θ(n2 ). This is because regardless of how the elements are
initially arranged, on the ith iteration of the main for loop the algorithm always
inspects each of the remaining n − i elements to find the smallest one remaining.
2
Michelle Bodnar, Andrew Lohr
December 30, 2015
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 santuary 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 resizing,
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.
1
,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 > 21 4 = 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 dday month and 365 day year.
1 Second 1 Minute 1 Hour 1 Day 1 Month 1 Year 1 Century
6 7 9
8.64×1010 12
3.1536×1013 15
lg n 21×10 26×10 23.6×10 2 22.592×10 2 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 × 106 6 × 107 3.6 × 109 8.64 × 1010 2.59 × 1012 3.15 × 1013 3.16 × 1015
n lg n 189481 8.64 × 106 4.18 × 108 8.69 × 109 2.28 × 1011 2.54 × 1012 2.20 × 1014
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
2
, Chapter 2
Michelle Bodnar, Andrew Lohr
December 30, 2015
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 Nonincreasing 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: end for
10: A[i + 1] = key
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 procede 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 N IL in i
is correct.
1
, 1: i = N IL
2: for j = 1 to A.length do
3: if A[j] = v then
4: i=j
5: return i
6: end if
7: return i
8: end for
Exercise 2.1-4
Input: two n-element arrays A and B containing the binary digits of two
numbers a and b.
Output: an (n + 1)-element array C containing the binary digits of a + b.
Algorithm 2 Adding n-bit Binary Integers
1: carry = 0
2: for i=1 to n do
3: C[i] = (A[i] + B[i] + carry) (mod 2)
4: if A[i] + B[i] + carry ≥ 2 then
5: carry = 1
6: else
7: carry = 0
8: end if
9: end for
10: C[n+1] = carry
Exercise 2.2-1
n3 /1000 − 100n2 − 100n + 3 ∈ Θ(n3 )
Exercise 2.2-2
Input: An n-element array A.
Output: The array A with its elements rearranged into increasing order.
The loop invariant of selection sort is as follows: At each iteration of the for
loop of lines 1 through 10, the subarray A[1..i − 1] contains the i − 1 smallest
elements of A in increasing order. After n − 1 iterations of the loop, the n − 1
smallest elements of A are in the first n − 1 positions of A in increasing order,
so the nth element is necessarily the largest element. Therefore we do not need
to run the loop a final time. The best-case and worst-case running times of
selection sort are Θ(n2 ). This is because regardless of how the elements are
initially arranged, on the ith iteration of the main for loop the algorithm always
inspects each of the remaining n − i elements to find the smallest one remaining.
2
