CSci 1901: 2nd Homework
Due: Monday, February 12th
in class at the beginning of the lecture

This homework is to be done on paper and individually. Working alone will help you assess how prepared you are for the upcoming In Class Quiz and Midterm. Homeworks done in collaboration with others will be considered in violation of the Scholastic Conduct Code stated in the syllabus: "Collaboration on homeworks, or exams is cheating and grounds for failing the course."
Material you need to read from the textbook for this homework:
Section 1.3.2 for questions 1-3
Section 1.3.1 for questions 4 and 5
Section 1.2.6 for questions 6 and 7
The material for questions 8 and 9 will be covered in class on Wednesday.
  1. (10 points)
    You are given the following code:
    (define a 1000)
    
    (define pi 3.1415926)  ; first pi
    
    (define radius 4)  ;  first radius
    
    (define (area radius)  ; second radius
        (* pi radius radius))  ; second pi, third radius
    
    (define (circumference radius)  ; fourth radius
    
        (define pi 3.14)  ; third pi
    
        (define (diameter radius)  ; fifth radius
            (* 2 radius))  ; sixth radius
    
        (* pi (diameter radius)) ) ; fourth pi, seventh radius
    
    (define (volume radius)  ; eighth radius
    
        (define pi 3.1)  ; fifth pi
    
        (* pi radius radius radius) )  ; sixth pi, ninth radius
    
    Given the above code, evaluate each of the following expressions by hand. Then, compare with the values that you obtain by hand with those obtained when you evaluate the expressions below using the Scheme interpreter. If there are any differences between the values you computed by hand and those from the Scheme interpreter, you will need to more closely study static name scoping.
    1. (area 100)
    2. (circumference 10)
    3. (volume 1)
    4. (area radius)
    5. (circumference a)
    6. (volume radius)
    7. How will the above code be affected if the third pi line is deleted?
    8. How will the above code be affected if "radius" is removed as a parameter of the diameter on the "fifth radius" line?
  2. (5 points)
    Evaluate:
    (define a 1)
    (define b 2)
    (let ((a (+ a 5))
          (old a))
         (+ a old b) )
    
  3. (5 points)
    Evaluate:
    (define x 10)
    (+ x 
       (let ((x 2)
             (y 3))
            (+ x y) ))
    
  4. (15 points) [This is exercise 1.34 from the book.]
    Suppose we define the procedure
    STk> (define (f g) (g 2))
    
    Then we have:
    STk> (f square)
    4
    STk> (f (lambda (z) (* z (+ z 1))))
    6
    
    What happens if we (perversely) ask the interpreter to evaluate the combination (f f)? Explain.
  5. (15 points) [This is exercise 1.42 from the textbook].
    Let f and g be two funtions of one argument. We say that the composition f after g is the function f(g(x)). Define a procedure (compose f g) that composes f after g. As an example:
    STk>(define (inc x) (+ 1 x))
    inc
    STk>((compose square inc) 3)   ; computes (square (inc 3))
    16
    
  6. (10 points) [This is exercise 1.25 from the textbook.]
    Alyssa P. Hacker complains that we went to a lot of extra work in writing expmod. After all, she says, since we already know how to compute exponentials, we could have simply written
    (define (expmod base exp m)
      (remainder (fast-expt base exp) m))
    
    Is she correct? Would this procedure serve as well for our fast prime tester? Explain.
  7. (10 points) [This is exercise 1.26 from the textbook.]
    Louis Reasoner is having great difficulty doing exercise 1.24. His fast-prime? test seems to run more slowly than his prime? test. Louis calls his friend Eva Lu Ator over to help. When they examine Louis's code, they find that he has rewritten the expmod procedure to use an explicit multiplication, rather than calling square:
    (define (expmod base exp m)
      (cond ((= exp 0) 1)
    	((even? exp)
    	 (remainder (* (expmod base (/ exp 2) m) 
    		       (expmod base (/ exp 2) m)) 
    		    m))
    	(else (remainder (* base (expmod base (- exp 1) m)) 
    			 m))))
    
    "I don't see what difference that could make," says Louis. "I do." says Eva. "By writing the procedure like that, you have transformed the (log n) process into a (n) process." Explain.
  8. (15 points)
    Write a procedure (double l) to double every element of a list. It should work like this:
    STk> (double (list 3 7 -4 1 72))
    (6 14 -8 2 144)
    
  9. (15 points)
    Write a procedure (add-lists l1 l2) that takes two lists of the same length and adds the elements of the two lists together (same positions are added), creating a new list of the same length. For example:
    STk> (add-lists '(1 2 3 4 5) '(6 7 8 9 10))
    (7 9 11 13 15)
    STk> (add-lists '(0 1 1) '(1 2 2))
    (1 3 3)
    
Copyright: © 2000-2006 by the Regents of the University of Minnesota
Department of Computer Science and Engineering. All rights reserved.
Comments to: Maria Gini
Changes and corrections are in red.