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

CSC 715 Assignment 1

Due date: Tuesday, January 19, 2010, 10:00 AM.

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 on or before the due date.
  1. Work Problem 4-1 b., d., f., and h. on page 85 of your textbook. These can all be solved by application of the master theorem, although the last one requires a substitution.
  2. Work Problem 4-4 b., d., f., h., and j. on page 86 of your textbook. These are hard.
  3. Work Problem 4-7 b. on page 88 of your textbook. (We will return to the other parts of that problem later. Part d. of this problem gives one of the two reductions needed to work the famous SMAWK algorithm, a linear time algorithm that revolutionized matrix searching in the 1980s. As a project, we will write a Wikipedia article on the SMAWK algorithm this semester, unless someone beats us to it.)
  4. Let the function f(x) be defined by the equation f(x)f(x) = x.
    For example, f(4) = 2, f(27) = 3, f(256) = 4, and f(1000000) is some number between 7 and 8.
    Find the asymptotic complexity class of f(x) as x gets large, and express the answer using Θ notation.
    Hint: You might think the answer is Θ(log x). That's close, but wrong.

Back to Course Page