University of Nevada Las Vegas
Howard R. Hughes College of Engineering
Department of Computer Science
My Home Page
Course Page

CSC 477/677 Assignment 9

Due date: Wednesday, November 26, 2013, 2:30 PM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on or before the due date.
  1. Draw a treap with six nodes, which hold the following data. The name is the datum, and the number is the "random" key.
    1. Ann, 3
    2. Bob, 8
    3. Cal, 9
    4. Sue, 4
    5. Ted, 7
    6. Tom, 2


  2. In class, we discussed a "tournament" algorithm which finds the maximum of an array of size n in O(log n) time, using n parallel processors. However, that algorithm is "wasteful," in the sense that most of the processors are idle most of the time.
    Describe a parallel algorithm which finds the maximum of an array of size n in O(log n) using only n/(log n) processors.

  3. Let f(n) be defined for all non-negative integers n, as follows:
    f(0) = 0,
    f(n) = 1 + f(⌊⅗ n⌋) + f(⌊⅘ n⌋) if n > 0.
    1. Give a recursive algorithm to compute f(n). Show that it has time complexity Θ(n2).
    2. Give a dynamic programming algorithm to compute f(n). Show that it has time complexity Θ(n).
    3. Give a memoization algorithm to compute f(n). Show that it has time complexity Θ(log2n).

Back to Course Page