Final Review

Posted on May 23, 2016 by Miguel Castillo
  1. a) Using quick sort, sort 3, 5, 7, 8, 1, 9, 2, 4, 6. Show each step.
    b) Count the number of comparisons in 1a
  2. a) Set up a binary tree for the following list, in the given order, using alphabetical ordering: SHE< SELLS< SEA SHELLS BY THE SEASHORE.
    b) How many comparisons with words in the tree are needed to determine if the word SHARK is in the tree? Explain your answer.
    c) How many comparisons with word in the tree are needed to determine if the word SHELLS is in the tree? Explain your answer.
  3. a) Determine the codes for the letters d, i, o, t, u, and y if the coding scheme is represented by the following tree:
    d: 00
    i: 010
    o: 011
    t: 11000
    u: 11001
    y: 111
    b) given the coding scheme represented by the tree above, find the words represented by: 11101111001 0001000 01011000
  4. a) Perform a depth first search to find a spanning tree for the graph, beginning at vertex A. Show each step
    b) Perform a breadth first search to find a spanning tree for the graph, beginning at vertex A. Show each step.
  5. The map of New York State below shows cities and major highways. Distances between cities are indicated in miles. A major blizzard blankets the whole state in 40 feet of snow. Governor Cuomo is responsible for making sure there that every city can be accessed by a highway. He must decide the most efficient way to plow the stretches of highway, but he never took discrete math.
    a) Determine the stretches of highway that Governor Cuomo should plow so that all the cities are connected in the most efficient way. Indicate on the graph above.
    b) Write a short note to Governor Cuomo describing how you came up with your answer.
  6. a) Let f(n) and g(n) be functions from the set of positive integers to the set of real numbers. State the definition of the fact that f(n) is O(g(n)).
    b) Use your definition from (a) to prove that 1^2 + 2^2 + ……. + n^2 is O(n^3).
  7. Give a big O estimate for an increasing function “f” which satisfies for n = 2k. f(n) = f(n/2) +1 with f(1) = 1.
  8. Solve the recurrence relation:
    an = an-1 + 6an-2 for n >= 2 with initial conditions a0 = 3 and a1 = 6.
This entry was posted in Final Exam Review. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *