CS3401 Practice Quiz 2 Part 3
Introduction to Java Programming, Ninth Edition, Y. Daniel Liang
Chapter 24 Developing Efficient Algorithms
Please send suggestions and errata to Dr. Liang at y.daniel.liang@gmail.com. Indicate which book and edition you are using. Thanks!
Section 24.2 Measuring Algorithm Efficiency Using Big O Notation
24.1 Estimating algorithm efficiency is ________
A. to measure their actual execution time.
B. to estimate their execution time.
C. to estimate their growth function.
Your answer is correct
24.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
Your answer is correct
24.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.
Your answer is correct
24.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
Your answer is correct
24.5 On an average, 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
Your answer is correct
24.6 What is the number of iterations in the following loop:
int count = 5;
while (count < n) {
count = count + 3;
}
int count = 5;
while (count < n) {
count = count + 3;
}
A. n - 5
B. n - 3
C. n / 3 - 1
D. (n - 5) / 3
E. the ceiling of (n - 5) / 3
Your answer is correct
24.7 For a sorted list of 1024 elements, a binary search takes at most _______ comparisons. Note that to check whether an element is greater than, equal to, or less than the other element is considered as one comparison here.
A. 11
B. 100
C. 512
D. 6
Your answer is correct
24.8 O(1) is ________.
A. constant time
B. logarithmic time
C. linear time
D. log-linear time
Your answer is correct
24.9 The time complexity for the Towers of Honoi algorithm in the text is ________.
A. O(n)
B. O(n^2)
C. O(n^3)
D. O(2^n)
Your answer is correct
24.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)
Your answer is correct
24.11 The time complexity for the insertion sort algorithm in the text is ________.
A. O(nlogn)
B. O(n^2)
C. O(logn)
D. O(2^n)
Your answer is correct
24.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-conqure
B. Dynamic programming
C. Brutal-force
D. Backtracking
Your answer is correct
24.13 The time complexity for the recursive Fibnacci algorithm in the text is ________.
A. O(nlogn)
B. O(n^2)
C. O(logn)
D. O(2^n)
Your answer is correct
24.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)
Your answer is correct
24.15 The time complexity for the Euclid?s algorithm is ________.
A. O(n)
B. O(n^2)
C. O(logn)
D. O(2^n)
Your answer is correct
24.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)
Your answer is correct
24.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)
Your answer is correct
24.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-conqure/dynamic programming
B. Dynamic programming/divide-and-conqure
C. Brutal-force/divide-and-conqure
D. Backtracking/dynamic programming
Your answer is correct
24.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-conqure
B. Dynamic programming
C. Brutal-force
D. Backtracking
Your answer is correct
24.20 The gift-wrapping algorithm for finding a convex hull takes ______________ time.
A. O(n)
B. O(nlogn)
C. O(logn)
D. O(n^2)
Your answer is correct
24.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)
Your answer is correct
Comments
Post a Comment