PS3

Home Assignments Lecture Blog Resources Project Discussion Group

Problem Set 3: Data Abstraction, Lists, and Higher-Order Functions

In this problem set, we do:

abstraction with data and matching procedures (ideas that preceded the development of OO programming)
ways of using procedures to implement data structures (you can do everything in the world with procedures and closures)
box-and-pointer diagrams of lists and lists-of-lists (also known as trees)
recursion with lists and trees
some cool higher order procedural thinking (extra credit/grad students)

What To Turn In

Please use the autograder to obtain starter code, and upload your completed work there. Here is a direct link to the assignment: https://grader.cs.uml.edu/assignments/357

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. SICP exercise 2.4 (pp. 90), on an alternative procedural representation of pairs.

4. 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))

5. 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?

6. 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?

7. 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 pp. 105 in your definition.

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

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

10. SICP exercise 2.33 (pp. 119), implementing map, append, and length.

11. SICP exercise 2.35 (pp. 120), redefining count-leaves as an accumulation.

Honors, Grad Students, and Extra Credit

12. SICP exercise 2.6 (pp. 91), on Church numerals.

13. 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 the process of how you got there (including false starts or other incomplete attempts). If you did work at this and you don't fully solve it, show how far you got.