Final Lab Quiz Solutions, Foundations of Computing, Fall 2000

1. The Scheme interpreter evaluates each of these expressions. Write down the value that Scheme returns.

   1. (+ 1 3)
      
      
   2. (* 3 (+ 1 3))
      
      




2. For all parts in this questions, assume the following definitions have been executed:

   (define s '(a b c d))
   

   (define t '((a b) c d))
   

   The Scheme interpreter evaluates each of these expressions. Write down the value that Scheme returns.

   1. s
      
      
   2. (car s)
      
      
   3. (cdr s)
      
      
   4. (cons 'a '(b c d))
      
      
   5. (cons (car s) (cdr s))
      
      
   6. (car (cdr s))
      
      
   7. t
      
      
   8. (car t)
      
      
   9. (cdr t)
      
      
   10. (cons '(a b) '(c d))
       
       
   11. (list '(a b) '(c d))
       
       
   12. (append '(a b) '(c d))
       
       




3. For all parts in this question, assume that a procedure named add-1 has been defined. It takes a number as an argument, and returns the number that is one greater than the argument. For example (add-1 3) evaluates to 4.

   The Scheme interpreter evaluates each of these expressions. Write down the value that Scheme returns.

   1. (map add-1 '(1 2 3))
      
      
   2. (map (lambda (x) (* 2 x)) '(1 2 3))
      
      







4. Define a Scheme variable named x that has the value 3.

   
   
   

5. This table shows the number of electoral votes allocated to several states:

   Washington	11
   Oregon	7
   Iowa	7
   California	54
   Florida	25

   Define a Scheme variable named electoral-votes to encode this table. Represent the table by an association list: a list of sublists, one for each state, where each sublist has two elements. The first element of each sublist is the name of the state and the second element is the number of electoral votes for that state.

   
   
   
   
   
   
   
   
   

6. Define a Scheme procedure named add-1 that takes a number as an argument, and returns the number that is one greater than the argument.

   
   
   
   
   
   
   

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

   
   
   
   
   
   
   
   
   






8. This definition is executed:

   ;; Like Scheme length
   (define (len lst)
     (if (null? lst)
         0
         (+ 1 (len (cdr lst)))))
   

   Then this expression is typed into the Scheme interpreter and evaluated. It returns the result shown:

   > (len '(x y z))
   3
   

   The following questions all concern what happens when the expression (len '(x y z)) is evaluated.

   1. What is the base case?
      
      
      
   2. What does len return when the base case is reached?
      
      
      
   3. How many times is len called?
      
      
      
   4. What is lst bound to when len is called the first time?
      
      
      
   5. What is the value of (cdr lst) when len is called the first time?
      
      
      
   6. What is the value of (len (cdr lst)) when len is called the first time?
      
      
      
   7. What is the value of (+ 1 (len (cdr lst))) when len is called the first time?