Chapter 22 Developing Efficient Algorithms
Section 22.2 Measuring Algorithm Efficiency Using Big O Notation
1. Analyzing algorithm efficiency is .
a. to measure their actual execution time
b. to estimate their execution time
c. to estimate their growth function
#
2. An input that results in the shortest execution time is called the .
a. best-case input
b. worst–case input
c. average-case input
#
3. Why is the analysis often for the worst case?
a. Best–case is not representative.
b. Worst–case is not representative, but worst–case analysis is very useful. You can show that the algorithm will never
be slower than the worst–case.
c. Average–case analysis is ideal, but difficult to perform, because it is hard to determine the relative probabilities and
distributions of various input instances for many problems.
#
4. Which of the following complexity is O(nlogn)?
a. 300n + 400n*n
b. 23nlogn + 50
c. 45n + 45nlogn + 503
d. n*n*n + nlogn
#
5. On an average, if an element is in the list, linear search searches
a. the whole list
b. half of the list
c. just one element in the list
d. one fourth of the list
#
Section 22.3 Examples: Determining Big O
6. What is the number of iterations in the following loop:
int count = 5;
while (count < n) {
count = count + 3;
}
a. n – 5
b. n – 3
c. n / 3 – 1
a.
11
b.
100
c.
512
d.
6
d. (n – 5) / 3
e. the ceiling of (n – 5) / 3
#
Section 22.4 Analyzing Algorithm Time Complexity
7. For a sorted list of 1024 elements, a binary search takes at most comparisons.
#
8. O(1) is .
a. constant time
b. logarithmic time
c. linear time
d. log–linear time
#
9. The time complexity for the Towers of Hanoi algorithm in the text is .
a. O(n)
b. O(n^2)
c. O(n^3)
d. O(2^n)
#
11. The time complexity for the binary search algorithm in the text is .
a. O(nlogn)
b. O(logn)
c. O(n^2)
d. O(2^n)
#
10. The time complexity for the selection sort algorithm in the text is .
a. O(nlogn)
b. O(n^2)
c. O(logn)
d. O(2^n)
#
Section 22.5 Finding Fibonacci Numbers using Dynamic Programming
12. approach is the process of solving subproblems, then combining the solutions of the subproblems
to obtain an overall solution. This naturally leads to a recursive solution. However, it would be inefficient to use
recursion, because the subproblems overlap. The key idea behind dynamic programming is to solve each subproblem
only once and store the results for subproblems for later use to avoid redundant computing of the subproblems.
a. Divide–and–conquer
b. Dynamic programming
c. Brutal-force
d. Backtracking
#
13. The time complexity for the recursive Fibonacci algorithm in the text is .
a. O(nlogn)
b. O(n^2)
c. O(logn)
#
14. The time complexity for the algorithm using the dynamic programming approach is .
a. O(n)
b. O(n^2)
c. O(logn)
d. O(2^n)
#
Section 22.6 Finding Greatest Common Divisors Using Euclid’s Algorithm
15. The time complexity for the Euclid’s algorithm is .
a. O(n)
b. O(n^2)
c. O(logn)
d. O(2^n)
#
Section 22.7 Efficient Algorithms for Finding Prime Numbers
16. The time complexity for the Sieve of Eratosthenes algorithm is .
a. O(n)
b. O(n^(1.5)/logn)
c. O(logn)
d. O(2^n)
#
Section 22.8 Finding the Closest Pair of Points Using Divide–and–Conquer
17. The time complexity for the the closest pair of points problem using divide-and–conquer is .
a. O(n)
b. O(nlogn)
c. O(logn)
d. O(2^n)
#
18. approach divides the problem into subproblems, solves the subproblems, then combines the
solutions of the subproblems to obtain the solution for the entire problem. Unlike the approach, the
subproblems in the divide-and–conquer approach don’t overlap. A subproblem is like the original problem with a
smaller size, so you can apply recursion to solve the problem.
a. Divide–and–conquer/dynamic programming
b. Dynamic programming/divide–and–conquer
c. Brutal-force/divide–and–conquer
d. Backtracking/dynamic programming
#
Section 22.9 Solving the Eight Queens Problem Using Backtracking
19. The approach searches for a candidate solution incrementally, abandoning that option as soon as it
determines that the candidate cannot possibly be a valid solution, and then looks for a new candidate.
a. Divide–and–conquer
b. Dynamic programming
c. Brutal-force
d. Backtracking
#
Section 22.10 Computational Geometry: Finding a Convex Hull
Section 22.10.1 Gift-Wrapping Algorithm
20. The gift–wrapping algorithm for finding a convex hull takes time.
a. O(n)
b. O(nlogn)
c. O(logn)
#
Section 22.10.2 Graham’s Algorithm
21. The Graham’s algorithm for finding a convex hull takes time.
a. O(n)
b. O(nlogn)
c. O(logn)
d. O(n^2)
#
Section 22.11 String Matching
22. To find a match for a string of size m in a text of size n, the brute-force algorithm would take in the
worst case.
a. O(n) time
b. O(m) time
c. O(n + m) time
d. O(m*n) time
#
Section 22.11.1 The Boyer–Moore Algorithm
23. To find a match for a string of size m in a text of size n, the Boyer–Moore algorithm would take in
the worst case.
a. O(n) time
b. O(m) time
c. O(n + m) time
d. O(m*n) time
#
24. To find a match for a string of size m in a text of size n, the KMP algorithm would take in the
worst case.
a. O(n) time
b. O(m) time
c. O(n + m) time
d. O(m*n) time