• View
• Edit
• History
• Print

PS3

Home Assignments Lecture Blog Resources Project Discussion Group

91.301 Organization of Programming Languages
Prof. F. Martin

Out: Feb 9, 2009
Due: Feb 17, 2009

Problem Set 3: Data Abstractions & Data Structures

Scheme Settings

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

What to turn in

• Keep your answers in a file named ps3-ans.scm.
• 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 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, turn it in at the beginning of class on the due date. Submit code electronically.
• Submit your answer buffer using the submit command on Mercury: submit fredm 301-ps3 ps3-ans.scm

Reading

SICP reading: Sections 2.1 through 2.2.2.

The 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))))) 

6. Write a procedure called double-list in three different ways:

7. SICP exercise 2.20 (pp. 104), on the dotted-tail notation.

8. SICP exercise 2.21 (pp. 106), on square-list.

Honors, Grad Students, and Extra Credit

9. Solve SICP exercise 2.27 on deep-reverse. Note: it will be easy enough to Google for the answer on this. Obviously this will short-circuit your learning. So don't do that, and instead please show steps along the way to your solution—e.g., partly working code, what inputs you tested it on, what results it produced, what you did next.

Please don't just turn in the answer—that won't be credible. Show how you got there; or if you don't fully solve it, how far you got.