Solutions Manual for
Python Programming for
Engineers and Scientists 1e By
Cengage
(All Chapters 1-13, 100% Original
Verified, A+ Grade)
All Chapters Arranged Reverse: 13-1
This is the Original Solutions Manual
for 1st Edition, All Other Files in the
Market are Wrong/Old Questions.
,Solution and Answer Guide
CENGAGE , PYTHON PROGRAMMING FOR SCIENTISTS AND ENGINEERS, 1E;CHAPTER 13,
SEARCHING, SORTING, AND COMPLEXITY ANALYSIS
TABLE OF CONTENTS
Exercise Solutions.........................................................................................................1
Exercise 13.1...........................................................................................................................................1
Exercise 13.2...........................................................................................................................................2
Exercise 13.3...........................................................................................................................................3
Exercise 13.4...........................................................................................................................................4
Exercise 13.5...........................................................................................................................................4
Review Questions Answers...........................................................................................5
Programming Exercises Solutions.............................................................................11
EXERCISE SOLUTIONS
EXERCISE 13.1
1. Write a tester program that counts and displays the number of iterations of the following loop:
Solution:
2. Run the program you created in Exercise 13.1 using problem sizes of 1000, 2000, 4000, 10,000, and
100,000. As the problem size doubles or increases by a factor of 10, what happens to the number of
iterations?
Solution:
When the problem size doubles, the number of iterations increases by 1. When the problem increases by a
factor of 10, the number of iterations increases by 3.
3. The difference between the results of two calls of the function is an elapsed time. Because the operating
system might use the CPU for part of this time, the elapsed time might not reflect the actual time that a
Python code segment uses the CPU. Browse the Python documentation for an alternative way of recording
the processing time and describe how this would be done.
Solution:
© 2025 Cengage Learning, Inc. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
1
, According to the Python documentation, the function can be used to measure the time that a process
actually uses the CPU, without including the time that the process sleeps.
EXERCISE 13.2
1. Assume that each of the following expressions indicates the number of operations performed by an
algorithm for a problem size of n. Point out the dominant term of each algorithm and use big-O notation to
classify it.
a. 2n – 4n2 + 5n
b. 3n2 + 6
c. n3 + n2 – n
Solution:
a. 2n, O(n)
b. 3n2, O(n2)
c. n3, O(n3)
2. For problem size n, algorithms A and B perform n2 and ½ n2 + ½ n instructions, respectively. Which
algorithm does more work? Are there particular problem sizes for which one algorithm performs
significantly better than the other? Are there particular problem sizes for which both algorithms perform
approximately the same amount of work?
Solution:
Algorithm A does more work, on all problem sizes.
3. At what point does an n4 algorithm begin to perform better than a 2n algorithm?
Solution:
When n is 16, then n4 and 2n are the same, 65536. When n is 17, n4 is 83521 and 2n is 131072.
EXERCISE 13.3
1. Suppose that a list contains the values
20 44 48 55 62 66 74 88 93 99
at index positions 0 through 9. Trace the values of the variables left, right, and midpoint in a binary search
of this list for the target value 90. Repeat for the target value 44.
Solution:
Trace of first run:
left right midpoint
0 9 4
© 2025 Cengage Learning, Inc. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
2
, 5 9 7
8 9 8
Trace of second run:
left right midpoint
0 9 4
0 3 1
2. The method we usually use to look up an entry in a phone book is not exactly the same as a binary search
because, when using a phone book, we don’t always go to the midpoint of the sublist being searched.
Instead, we estimate the position of the target based on the alphabetical position of the first letter of the
person’s last name. For example, when we are looking up a number for “Smith,” we first look toward the
middle of the second half of the phone book, instead of in the middle of the entire book. Suggest a
modification of the binary search algorithm that emulates this strategy for a list of names. Is its
computational complexity any better than that of the standard binary search?
Solution:
Let’s assume, somewhat unrealistically, that the names are distributed evenly through the list (as many
beginning with “A” as with “B,” and so forth) and that there are thousands of names in the list. Then, on the
first pass of the search, the midpoint will be a function of the size of the list and the ordinal value of the
target name’s first letter. The first pass will eliminate many more elements than before, and the other
passes, if they are necessary, will have smaller search spaces as well. However, the modified algorithm is
still closer to O(lg n) than to O(1) in the worst case.
EXERCISE 13.4
1. Which configuration of data in a list causes the smallest number of exchanges in a selection sort? Which
configuration of data causes the largest number of exchanges values?
Solution:
A sorted list causes the fewest exchanges in selection sort (0). A list with the largest item as the first one
and the rest of the items in ascending order causes the greatest number of exchanges (n – 1).
2. Explain the role that the number of data exchanges plays in the analysis of selection sort and bubble sort.
What role, if any, does the size of the data objects play?
Solution:
The worst-case number of exchanges in selection sort (n – 1) does not predominate, so there is little impact
on performance. The worst-case number of exchanges in bubble sort (approximately n2) is similar to the
worst-case complexity, so there is significant extra work. The size of the elements has no impact, because
references only are exchanged.
3. Explain why the modified bubble sort still exhibits O(n2) behavior on the average.
© 2025 Cengage Learning, Inc. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
3
Python Programming for
Engineers and Scientists 1e By
Cengage
(All Chapters 1-13, 100% Original
Verified, A+ Grade)
All Chapters Arranged Reverse: 13-1
This is the Original Solutions Manual
for 1st Edition, All Other Files in the
Market are Wrong/Old Questions.
,Solution and Answer Guide
CENGAGE , PYTHON PROGRAMMING FOR SCIENTISTS AND ENGINEERS, 1E;CHAPTER 13,
SEARCHING, SORTING, AND COMPLEXITY ANALYSIS
TABLE OF CONTENTS
Exercise Solutions.........................................................................................................1
Exercise 13.1...........................................................................................................................................1
Exercise 13.2...........................................................................................................................................2
Exercise 13.3...........................................................................................................................................3
Exercise 13.4...........................................................................................................................................4
Exercise 13.5...........................................................................................................................................4
Review Questions Answers...........................................................................................5
Programming Exercises Solutions.............................................................................11
EXERCISE SOLUTIONS
EXERCISE 13.1
1. Write a tester program that counts and displays the number of iterations of the following loop:
Solution:
2. Run the program you created in Exercise 13.1 using problem sizes of 1000, 2000, 4000, 10,000, and
100,000. As the problem size doubles or increases by a factor of 10, what happens to the number of
iterations?
Solution:
When the problem size doubles, the number of iterations increases by 1. When the problem increases by a
factor of 10, the number of iterations increases by 3.
3. The difference between the results of two calls of the function is an elapsed time. Because the operating
system might use the CPU for part of this time, the elapsed time might not reflect the actual time that a
Python code segment uses the CPU. Browse the Python documentation for an alternative way of recording
the processing time and describe how this would be done.
Solution:
© 2025 Cengage Learning, Inc. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
1
, According to the Python documentation, the function can be used to measure the time that a process
actually uses the CPU, without including the time that the process sleeps.
EXERCISE 13.2
1. Assume that each of the following expressions indicates the number of operations performed by an
algorithm for a problem size of n. Point out the dominant term of each algorithm and use big-O notation to
classify it.
a. 2n – 4n2 + 5n
b. 3n2 + 6
c. n3 + n2 – n
Solution:
a. 2n, O(n)
b. 3n2, O(n2)
c. n3, O(n3)
2. For problem size n, algorithms A and B perform n2 and ½ n2 + ½ n instructions, respectively. Which
algorithm does more work? Are there particular problem sizes for which one algorithm performs
significantly better than the other? Are there particular problem sizes for which both algorithms perform
approximately the same amount of work?
Solution:
Algorithm A does more work, on all problem sizes.
3. At what point does an n4 algorithm begin to perform better than a 2n algorithm?
Solution:
When n is 16, then n4 and 2n are the same, 65536. When n is 17, n4 is 83521 and 2n is 131072.
EXERCISE 13.3
1. Suppose that a list contains the values
20 44 48 55 62 66 74 88 93 99
at index positions 0 through 9. Trace the values of the variables left, right, and midpoint in a binary search
of this list for the target value 90. Repeat for the target value 44.
Solution:
Trace of first run:
left right midpoint
0 9 4
© 2025 Cengage Learning, Inc. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
2
, 5 9 7
8 9 8
Trace of second run:
left right midpoint
0 9 4
0 3 1
2. The method we usually use to look up an entry in a phone book is not exactly the same as a binary search
because, when using a phone book, we don’t always go to the midpoint of the sublist being searched.
Instead, we estimate the position of the target based on the alphabetical position of the first letter of the
person’s last name. For example, when we are looking up a number for “Smith,” we first look toward the
middle of the second half of the phone book, instead of in the middle of the entire book. Suggest a
modification of the binary search algorithm that emulates this strategy for a list of names. Is its
computational complexity any better than that of the standard binary search?
Solution:
Let’s assume, somewhat unrealistically, that the names are distributed evenly through the list (as many
beginning with “A” as with “B,” and so forth) and that there are thousands of names in the list. Then, on the
first pass of the search, the midpoint will be a function of the size of the list and the ordinal value of the
target name’s first letter. The first pass will eliminate many more elements than before, and the other
passes, if they are necessary, will have smaller search spaces as well. However, the modified algorithm is
still closer to O(lg n) than to O(1) in the worst case.
EXERCISE 13.4
1. Which configuration of data in a list causes the smallest number of exchanges in a selection sort? Which
configuration of data causes the largest number of exchanges values?
Solution:
A sorted list causes the fewest exchanges in selection sort (0). A list with the largest item as the first one
and the rest of the items in ascending order causes the greatest number of exchanges (n – 1).
2. Explain the role that the number of data exchanges plays in the analysis of selection sort and bubble sort.
What role, if any, does the size of the data objects play?
Solution:
The worst-case number of exchanges in selection sort (n – 1) does not predominate, so there is little impact
on performance. The worst-case number of exchanges in bubble sort (approximately n2) is similar to the
worst-case complexity, so there is significant extra work. The size of the elements has no impact, because
references only are exchanged.
3. Explain why the modified bubble sort still exhibits O(n2) behavior on the average.
© 2025 Cengage Learning, Inc. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
3
