16. Developing Efficient Algorithms - 21 Questions


16. Developing Efficient Algorithms

16. Developing Efficient Algorithms

21 Questions
Created by Y. Daniel Liang - http://www.cs.armstrong.edu/liang/index.html
Free
Algorithms have been commonly defined in simple terms as "instructions for completing a task". They've also been called "recipes". In The Social Network, an algorithm is what Zuckerberg needed to make Facemash work. If you saw the movie, you probably remember seeing what looked like a scribbly equation on a window in Mark's dorm room. But what does that scribbly algebra have to do with Mark's simple "hot or not" site?
  1. Estimating algorithm efficiency is ________



    to measure their actual execution time.
    to estimate their execution time.
    to estimate their growth function.
    none of these

    View Answer | Discuss in forum
  2. An input that results in the shortest execution time is called the _____________.



    best-case input
    worst-case input
    average-case input
    none of these

    View Answer | Discuss in forum
  3. Why is the analysis often for the worst case?

    1. Best-case is not representative.
    2. 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.
    3. 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.


    1 & 2
    2 & 3
    3
    1, 2 & 3

    View Answer | Discuss in forum
  4.  Which of the following complexity is O(nlogn) ?

    1. 300n + 400n*n
    2. 23nlogn + 50
    3. 45n + 45nlogn + 503
    4. n*n*n + nlogn


    1 & 2
    2 & 3
    3 & 4
    1 & 4

    View Answer | Discuss in forum
  5. On an average, linear search searches 



    the whole list
    half of the list
    just one element in the list
    one fourth of the list

    View Answer | Discuss in forum
  6. What is the number of iterations in the following loop:

     int count = 5;
     while (count < n) {
       count = count + 3;
     }



    n - 3
    n / 3 - 1
    (n - 5) / 3
    the ceiling of (n - 5) / 3

    View Answer | Discuss in forum
  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.



    11
    100
    512
    6

    View Answer | Discuss in forum
  8. O(1) is ________.



    constant time
    logarithmic time
    linear time
    log-linear time

    View Answer | Discuss in forum
  9. The time complexity for the Towers of Honoi algorithm in the text is ________.



    O(n)
    O(n^2)
    O(n^3)
    O(2^n)

    View Answer | Discuss in forum
  10. The time complexity for the selection sort algorithm in the text is ________.



    O(nlogn)
    O(n^2)
    O(logn)
    O(2^n)

    View Answer | Discuss in forum
  11. The time complexity for the insertion sort algorithm in the text is ________.



    O(nlogn)
    O(n^2)
    O(logn)
    O(2^n)

    View Answer | Discuss in forum
  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.



    Divide-and-conqure
    Dynamic programming
    Brutal-force
    Backtracking

    View Answer | Discuss in forum
  13. The time complexity for the recursive Fibnacci algorithm in the text is ________.



    O(nlogn)
    O(n^2)
    O(logn)
    O(2^n)

    View Answer | Discuss in forum
  14. The time complexity for the algorithm using the dynamic programming approach is ________.



    O(n)
    O(n^2)
    O(logn)
    O(2^n)

    View Answer | Discuss in forum
  15.  The time complexity for the Euclid?s algorithm is ________.



    O(n)
    O(n^2)
    O(logn)
    O(2^n)

    View Answer | Discuss in forum
  16. The time complexity for the Sieve of Eratosthenes algorithm is ________.



    O(n)
    O(n^(1.5)/logn)
    O(logn)
    O(2^n)

    View Answer | Discuss in forum
  17. The time complexity for the the closest pair of points problem using divide-and-conquer is ________.



    O(n)
    O(nlogn)
    O(logn)
    O(2^n)

    View Answer | Discuss in forum
  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. 



    Divide-and-conqure/dynamic programming
    Dynamic programming/divide-and-conqure
    Brutal-force/divide-and-conqure
    Backtracking/dynamic programming

    View Answer | Discuss in forum
  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.



    Divide-and-conqure
    Dynamic programming
    Brutal-force
    Backtracking

    View Answer | Discuss in forum
  20. The gift-wrapping algorithm for finding a convex hull takes ______________ time.



    O(n)
    O(nlogn)
    O(logn)
    O(n^2)

    View Answer | Discuss in forum
  21. The Graham's algorithm for finding a convex hull takes ______________ time.



    O(n)
    O(nlogn)
    O(logn)
    O(n^2)

    View Answer | Discuss in forum