16. Developing Efficient Algorithms21 Questions
Created by Y. Daniel Liang
 http://www.cs.armstrong.edu/liang/index.html
Free

Estimating algorithm efficiency is ________
An input that results in the shortest execution time is called the _____________.
Why is the analysis often for the worst case?
Which of the following complexity is O(nlogn) ?
On an average, linear search searches
What is the number of iterations in the following loop:
int count = 5;
while (count < n) {
count = count + 3;
}
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.
O(1) is ________.
The time complexity for the Towers of Honoi algorithm in the text is ________.
The time complexity for the selection sort algorithm in the text is ________.
The time complexity for the insertion sort algorithm in the text is ________.
______________ 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.
The time complexity for the recursive Fibnacci algorithm in the text is ________.
The time complexity for the algorithm using the dynamic programming approach is ________.
The time complexity for the Euclid?s algorithm is ________.
The time complexity for the Sieve of Eratosthenes algorithm is ________.
The time complexity for the the closest pair of points problem using divideandconquer is ________.
______________ 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 divideandconquer approach don?t overlap. A subproblem is like the original problem with a smaller size, so you can apply recursion to solve the problem.
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.
The giftwrapping algorithm for finding a convex hull takes ______________ time.
The Graham's algorithm for finding a convex hull takes ______________ time.