CS 477/677 Assignment 1

Due date: September 6, 2005, 11:30 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 or to the graduate assistant on or before the due date.
  1. Give the asymptotic time complexity, in terms of n, using "Theta" notation, for each of the following code fragments:
    1. The code fragment given in problem 3(a) of your textbook on page 45.
    2. The code fragment given in problem 3(b) of your textbook on page 45.
    3. This code fragment.
    4. Sometimes problems that are very simple to state are very difficult, or even impossible, to solve. Here is an example. This code fragment looks simple, but is extremely hard to analyze. I do not expect you to find the asymtotic time complexity. But, perhaps some of the more adventurous of you could research the history of this problem using the world wide web.
  2. Work Exercise 8(b,g,l) on page 47 of your textbook.
  3. Work Exercise 9(a) on page 47 of your textbook.

Back to Course Page