CSci 433: Algorithm & Data Structure Analysis
Spring Semester 1999

Assignment #1
Due Thursday, 28 January, 11:00 a.m.

Prepare this assignment paper by the above deadline in accordance with the instructions given in the Professional Conduct and Assignments sections of the Syllabus .

In the problems below, the symbol ^ indicates the exponentiation operation. The symbol _ (i.e., underscore) indicates a subscript (e.g., to indicate bases for logarithms). A logarithm is indicated by log and, by default, has base 2. A natural logarithm is denoted by ln, the square root function is indicated with sqrt, and the factorial function by an exclamation point ( ! ).

Unless otherwise noted, the exercises mentioned are from the Goodrich and Tamassia textbook.

1. Do exercise R-2.2 on page 58.

2. List the following functions in lowest to highest order according to the big-Oh notation. If two or more are of the same order, indicate which. (Note: You do not have to show proofs for these.)

   6n log n	5n	n!
   5n^2 + 4n	5n + 10	sqrt n
   5n^3 + n^2 + 4	log (log n)	4^n
   (log n)^2	13 log n + 7 log log n	n^3

3. Do exercise R-2.13 on page 59.

4. Do exercise R-2.20, R-2.22, and R-2.24 on page 60.

5. Do exercise C-2.7 on page 62. Do an analysis of the algorithm to verify that it satisfies the 1.5n bound on comparisons.

UP to CSCI 433 assignments document?