• View
• Edit
• History
• Print

PS3

Home Assignments Lecture Blog Resources

91.301 Organization of Programming Languages
Prof. F. Martin

Problem Set 3: Data Abstractions & Data Structures

Scheme Settings

• Use the Standard (R5RS) language in DrScheme
• You should define nil as follows in your evaluation buffer:

What to turn in

Keep your Scheme answers in a file named ps3-ans.scm and your Python answers in ps3-ans.py. Put your name at the top of the file in a comment block. Put the code for each problem sequentially in the definitions buffer. Put the problem number in a comment before the code for that problem (use a semi-colon to make a line a comment). Underneath the code for each problem, cut and paste the appropriate sample runs. You can put semi-colons (Scheme) or hash-marks (Python) in front of the sample runs, which will comment them out and allow you to load the entire buffer in another session.

If you have any hand-written content, print the answers buffer and turn it in at the beginning of class on the due date. Staple any handwritten portions of the assignment to your code file that you turn in. Also submit your answer buffer using the submit command on Mercury:

Exercises

1. SICP exercise 2.2 (pp. 89-90). In this problem you create data structures in Scheme representing line segments in a plane.
2. SICP exercise 2.3 (pp. 90). Here you represent rectangles and construct procedures to compute perimeter and area.
3. For each of the following definitions,
   a. Draw the box and pointer diagram
   b. Give the sequence of cars and cdrs needed to return the number 4
   
   
   (define a (list 1 2 3 4))
(define b (cons (cons 3 4) (cons 5 6)))
(define c (list 1 (list 2 3) 4))
4. Draw a box and pointer diagram for each of the lists d, e and f defined as follows:
   
   
   (define d (list 1 2))
(define e (cons d d))
(define f (append d d))
   
   
   What would be printed by Scheme when asked for the values of d, e and f sequentially?
5. Consider the following recursive procedure:

       (define (list-prod lst) 
           (if (null? lst) 
              1 
              (* (car lst) 
                 (list-prod (cdr lst))))) 
    
   

   a) How many times is list-prod called when evaluating the expression (list-prod '(1 2 3 4)) ?
   b) What is the order of growth in space and time for the list-prod procedure above?
   c) Write an iterative version of the procedure list-prod.
   d) What is the order of growth in space and time for your iterative list-prod procedure from part c?
6. *Write a procedure called double-list in three different ways:
   a) Write a list manipulation procedure of your own to do this.
   b) Use the scale-list procedure on pp. 105 in your definition.
   c) Use the map procedure on p. 105 in your definition.
7. SICP exercise 2.20 (pp. 104), on the dotted-tail notation.
8. *SICP exercise 2.21 (pp. 106), on square-list.
9. *SICP exercise 2.33 (pp. 119), implementing map, append, and length.
10. *SICP exercise 2.35 (pp. 120), redefining count-leaves as an accumulation.
11. Learn about object-orientation in Python by reading this quick intro (http://linuxgazette.net/issue56/orr.html) and/or parts of Chapter 13 in CP.