Your name __________________________

Harvey Mudd College CS 60 Final Exam

Fall semester, 1999

Six Problems, 250 points

Closed book

During the exam, the only item to which you may refer is your own reference sheet, one double-sided sheet of 8.5" x 11" paper.

All papers must be turned in within 3 hours.

Please provide answers to the problem groups directly on these pages. It is suggested that you look over the exam first to get an idea of how to apportion your time. Work so as to maximize total points; do not get stuck on one problem at the expense of others. Partial answers to questions will receive partial credit.

When code is requested, exhibiting the correct idea is more important than syntactic precision. However, keep your definitions clean and readable. Use the clearest program structure possible.

The answers to these problems should not be exceptionally long. Please think through your solution before you plunge into a long exposition that might not address the main point of the question.

1. (Complexity) [45 points total]

(A) 25 points    

Derive a tight "O" upper bound on the computational complexity of the following program, as a function of N:

for( int i = N; i >= 1; i = i/2 )
  for( int j = 1; j <= i; j = j*2 )
    for( int k = 1; k <= j; k++ )
    {
    … some computation using O(1) time …
    }