Algorithms Final Exam Study Guide

53 Questions | Total Attempts: 140

SettingsSettingsSettings
Please wait...
Algorithms Final Exam Study Guide

Exam 1-3, True/False questions & multiple choice questions.


Questions and Answers
  • 1. 
    N^2 = o(n^2)
    • A. 

      True

    • B. 

      False

  • 2. 
    N = O(n^2)
    • A. 

      True

    • B. 

      False

  • 3. 
    The reflexive property hold for o (little-oh) and w.
    • A. 

      True

    • B. 

      False

  • 4. 
    For two functions f(n) and g(n), if f(n) = w(g(n)), we know that f(n) is asymptotically larger than g(n).
    • A. 

      True

    • B. 

      False

  • 5. 
    For two algorithms A and B, if O(A) = n^100 and O(B) = 10^n, then algorithm A is the better choice.
    • A. 

      True

    • B. 

      False

  • 6. 
    The recurrence could be written equivalently as T(n) = T(n/2) + θ(n)
    • A. 

      True

    • B. 

      False

  • 7. 
    There is a significant difference in the running time f(n) = n and the running time g(n) = lg n.
    • A. 

      True

    • B. 

      False

  • 8. 
    F(n) = o(g(n)) means that f(n) is asymptotically smaller than g(n).
    • A. 

      True

    • B. 

      False

  • 9. 
    All functions can be compared asymptotically.
    • A. 

      True

    • B. 

      False

  • 10. 
    F(n) = Ω(g(n)) is like saying f(n) ≥ g(n)
    • A. 

      True

    • B. 

      False

  • 11. 
    The min-heap property states that for every node i other than the root, A[PAERENT(i)] ≤ A[i].
    • A. 

      True

    • B. 

      False

  • 12. 
    An array constructed with the values [23, 17, 14, 6, 13, 10, 1, 5, 7, 12] is a max heap.
    • A. 

      True

    • B. 

      False

  • 13. 
    For a node A at index i in a heap, the right child of A can be computed as 2*i.
    • A. 

      True

    • B. 

      False

  • 14. 
    The master method can be used to solve all recurrence equations that have the form T(n) = aT(n/b) + f(n).
    • A. 

      True

    • B. 

      False

  • 15. 
    Quicksort has a worst-case running time of θ(n^2).
    • A. 

      True

    • B. 

      False

  • 16. 
    One good reason for using a hash table would be to reduce storage requirements.
    • A. 

      True

    • B. 

      False

  • 17. 
    If we are using the division method for our hashing function, a table size of 64 would be a good choice.
    • A. 

      True

    • B. 

      False

  • 18. 
    Printing every node in a binary tree takes θ(lg n) time.
    • A. 

      True

    • B. 

      False

  • 19. 
    We do not have to make any key comparisons to find the min or max nodes of a binary search tree.
    • A. 

      True

    • B. 

      False

  • 20. 
    Open addressing is usually preferred over chaining for solving hash function collisions.
    • A. 

      True

    • B. 

      False

  • 21. 
    Red-black trees are an attempt to minimize the time of dynamic set operations by creating a balanced tree.
    • A. 

      True

    • B. 

      False

  • 22. 
    In a red-black tree, a black node must have only red children.
    • A. 

      True

    • B. 

      False

  • 23. 
    A problem that generates completely new subproblems at each step is a good candidate for a dynamic programming solution.
    • A. 

      True

    • B. 

      False

  • 24. 
    Dynamic programming has the potential to transform exponential-time algorithms to polynomial time.
    • A. 

      True

    • B. 

      False

  • 25. 
    A topological sort for a directed acyclic graph (DAG) can be created by performing a breadth-first search on the DAG.
    • A. 

      True

    • B. 

      False

  • 26. 
    A minimum spanning tree for a graph with N vertices will have N-2 edges.
    • A. 

      True

    • B. 

      False

  • 27. 
    A matrix is a good choice for representing a dense graph.
    • A. 

      True

    • B. 

      False

  • 28. 
    Both matrix and lists can be used to represent weighted graphs.
    • A. 

      True

    • B. 

      False

  • 29. 
    In Kruskal's algrorithm for building a minimum spanning tree, we proceed node by node, adding the connecting edges to the tree.
    • A. 

      True

    • B. 

      False

  • 30. 
    Huffman encoding uses a dynamic programming strategy to compress data.
    • A. 

      True

    • B. 

      False

  • 31. 
    If the following functions were sorted in increasing order of complexity (big-Oh), which one would be in the 3rd place? f1(n) = n^(0.999999)logn f2(n) = 10000000n f3(n) = 1.000001^n f4(n) = n^2
    • A. 

      F1

    • B. 

      F2

    • C. 

      F3

    • D. 

      F4

  • 32. 
    Select the correct asymptotic notation for the function f(n) n^3 + 1000 - 100n^2 - 100n.
    • A. 

      θ(n^3)

    • B. 

      O(n^3)

    • C. 

      O(n lg n)

    • D. 

      Ω(2^n)

  • 33. 
    What is the smallest value of n such that an algorithm whose running time is n^2 runs slower than an algorithm whose running time is 3n + 1?
    • A. 

      2

    • B. 

      25

    • C. 

      4

    • D. 

      15

  • 34. 
    Given the algorithm for Bubblesort below, what is an accurate description of it's running time? BUBBLESORT(A)    for I = 1 to A.length -1       for j = A.length downto I + 1          If A[j] < A[j-1]             exchange A[j] with A[j-1]
    • A. 

      T(n-1) + θ(n)

    • B. 

      θ(n^2)

    • C. 

      2T(n/2) + θ(1)

    • D. 

      O(n)

  • 35. 
    The most precise form of asymptotic notation is
    • A. 

      O

    • B. 

      Ω

    • C. 

      O

    • D. 

      θ

  • 36. 
    In analyzing a divide-and-conquer algorithm, any subproblem that is not part of the original problem is incorporated into which part of the recurrence?
    • A. 

      Recursion

    • B. 

      Divide

    • C. 

      Combine

    • D. 

      Base case

  • 37. 
    An algorithm that takes constant time is represented by
    • A. 

      Ω(o)

    • B. 

      W(g(n))

    • C. 

      θ(n)

    • D. 

      θ(1)

  • 38. 
    Before running MAX-HEAPIFY on node i of a heap, what must be true?
    • A. 

      The heap must be totally sorted in decreasing order.

    • B. 

      The heap must be totally sorted in increasing order.

    • C. 

      The parent of node i must be the root of a max heap.

    • D. 

      Both children of node i must be the roots of max heaps.

  • 39. 
    In which approach do we randomly select a hash function to avoid bad hashing behavior caused by a selected set of keys?
    • A. 

      Double hashing

    • B. 

      Division method

    • C. 

      Multiplication method

    • D. 

      Universal hashing

  • 40. 
    The recurrence equation T(n) = T(n-1) + θ(n) represents the
    • A. 

      Best case running time for Quicksort

    • B. 

      Worst-case running time for Quicksort

    • C. 

      Best-case running time for Heapsort

    • D. 

      Worst-case running time for Heapsort

  • 41. 
    Primary clustering is a problem in what hashing technique?
    • A. 

      Universal hashing

    • B. 

      Double hashing

    • C. 

      Quadratic probing

    • D. 

      Linear probing

  • 42. 
    In hashing with chaining, the load factor α represents
    • A. 

      The worst case search time

    • B. 

      The space remaining in the hash table

    • C. 

      The number of expected elements at any slot

    • D. 

      The number of probes for insertion

  • 43. 
    The worst-case search time for hashing with chaining is
    • A. 

      θ(n)

    • B. 

      O(1)

    • C. 

      O(α)

    • D. 

      θ(n^2)

  • 44. 
    Which one of the following is a true for a red-black tree?
    • A. 

      The root is red.

    • B. 

      The root and leaves are black.

    • C. 

      All simple paths from a node to the leaves contain the same number of red and black nodes.

    • D. 

      A red node can have only one black child.

  • 45. 
    What distinguishing feature should cause us to choose dynamic programming rather than a divide-and-conquer approach to a problem?
    • A. 

      It is an optimization problem.

    • B. 

      The problem can be solved recursively.

    • C. 

      The problem does not have a brute force solution.

    • D. 

      The subproblems for the solution overlap.

  • 46. 
    Which of the following is true regarding Prim's algorithm for finding a minimum spanning tree?
    • A. 

      The starting node must be connected to the edge with the least weight.

    • B. 

      The algorithm grows only a single tree from start to finish.

    • C. 

      "Marked" nodes indicate nodes that will not be in the final tree.

    • D. 

      When selecting the next edge, we consider only edges that connect unmarked nodes to the other unmarked nodes.

  • 47. 
    Which of the following is NOT a property of a minimum spanning tree?
    • A. 

      It may have one or more cycles.

    • B. 

      It has |V| -1 edges.

    • C. 

      It is not necessarily unique.

    • D. 

      The sum of weights of the edges is minimal.

  • 48. 
    What is the name of the technique that stores computed values for future lookup, rather than recomputing them?
    • A. 

      Overlapping subproblems

    • B. 

      Topological sort

    • C. 

      Memoization

    • D. 

      Dynamic recursion

  • 49. 
    Bottom-up dynamic programming works by
    • A. 

      Doubling the recursive calls

    • B. 

      Transforming recursive calls to a loop

    • C. 

      Solving the same subproblem multiple times

    • D. 

      Solving larger subproblems first, followed by smaller subproblems

  • 50. 
    The basic restructuring operation for red-black trees is
    • A. 

      Dynamic programming

    • B. 

      Binary sort

    • C. 

      Depth-first search

    • D. 

      Rotation

  • 51. 
    Which of the following is true for optimal binary search trees?
    • A. 

      An optimal binary search tree will always be balanced.

    • B. 

      Putting the highest-probability node at the root will always give us an optimal tree.

    • C. 

      Optimal binary search trees are constructed through the principal of optimal substructure.

    • D. 

      An optimal binary search tree for a set of nodes will always be unique.

  • 52. 
    The general comparison used to determine if a graph is sparse or dense is between
    • A. 

      |V| and |E^2|

    • B. 

      In E and |V|

    • C. 

      |E| and |V^2|

    • D. 

      |V| and |E| + |V|

  • 53. 
    Greedy algorithms make _______________optimal choices leading to _______________ optimal solutions.
    • A. 

      Globally, locally

    • B. 

      Top-down, bottom-up

    • C. 

      Locally, globally

    • D. 

      Bottom-up, top-down