Lab Quiz Solutions, Foundations of Computing, Week 3 -- Oct 10, 2000

1. Write a procedure named f that, when applied to the sample arguments, returns the sample result. Your procedure may not include any quoted data.

   > (f '(a b c) '(d e f))
   (a d)
   

   (define (f x y)
     (sentence (first x) (first y)))
   

2. Write a procedure named phase that takes a number as an argument. If the number is less than zero, it returns ice. If the number is greater than one hundred, it returns steam. Otherwise it returns water.

   (define (phase x)
     (cond ((< x 0) 'ice)
           ((> x 100) 'steam)
           (else 'water)))
   

3. Program A has a running time proportional to the number of items it must process --- it's complexity is O(n). Program B's running time is proportional to the square of the number of items -- it is O(n²). Both programs process a test set of 100 items in one minute.

   Can program A process 100,000 items a day?

   Yes. 100,000 items = 1000 x 100 items so running time = 1000 x 1 minute = 1000 minutes
   There are 24 x 60 = 1440 minutes in a day, which is more than 1000.

   Can program B process 100,000 items a year?

   No. Running time here is 1000² = 1000 x 1000 = 1,000,000 minutes (a million minutes).
   There are 1440 x 365 minutes in a year, which is less than a million.