CS212 Exams
Spring 1999 - Final

True and False

TRUE or FALSE:

1. It is possible to write a program that determines whether an arbitrary Scheme program halts.
   
   
2. It is possible to write a program that determines whether the Scheme program ((lambda (x) (x x)) (lambda (x) (x x))) halts.
   
   
3. It is possible to encode recursive functions in Scheme without using macros, letrec, define, or side-effects.
   
   
4. It is possible to sort a list of length n, in time O(n²).
   
   
5. The heap-based implementation of priority queues given in class had the property that inserting and removing elements took at most constant time.
   
   
6. An algorithm that runs in time O(n log n) is always faster than an algorithm that runs in time O(n²).
   
   

Solution

Return to CS 212 Final - Spring 1999