University of Chicago: CMSC 11500: Autumn 2002: Homework #2

CMSC 11500 - Introduction to Computer Programming
Homework #2

Problem 1

(Exercise 2.25 from SICP)

Give combinations of cars and cdrs to extract 7 from the following lists.

(1 3 (5 7) 9)
(car (cdr (car (cdr (cdr ...)))))
((7))
(car (car ..))
(1 (2 (3 (4 (5 (6 7))))))
(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr ...))))))))))))

Problem 2

Define a procedure sum-up that takes a list of numbers as input and returns the sum of all the numbers in the list.

For example,

(sum-up '(1 2 3 4 5))

(sum-up '())

(sum-up '(10 15))

Problem 2 Solution

(define (sum-up alon)
   (cond ((null? alon) 0)
         (else (+ (car alon) (sum-up (cdr alon))))))

Problem 3

The procedure you defined above was most likely a linear recursive process to compute the sum across the elements of the flat list. Now implement an iterative version of sum-up in which all information about the current state of the computation is captured in a set of variables such that, based on that information alone, the process could be restarted and produce the desired result.

Problem 3 Solution

(define (sum-up2 alon)
   (sum-up-iter alon 0))

(define (sum-up-iter alon acc)
   (cond ((null? alon) acc)
   (else (sum-up-iter (cdr alon) (+ acc (car alon))))))

Problem 4

You should recall that lists can be used not only as the input but also as the output of procedures. Create a new variant of sum-up, sum-up-incremental, that takes a list as input and produces a list in which each element is the incremental sum up to that point as below:

(sum-up-incremental '(1 2 3 4 5))

(1 3 6 10 15)

(sum-up-incremental '())

(0)

Problem 4 Solution

(define (sum-up-incremental alon)
    (cond ((null? alon) '(0))
    (else (sum-up-incr-iter alon 0))))
(define (sum-up-incr-iter alon acc)
    (cond ((null? alon) '())
          (else (cons (+ acc (car alon))
                      (sum-up-incr-iter (cdr alon) (+ acc (car alon)))))))

Problem 5

Thus far we have only computed sums across flat lists like '(1 2 3 4 5). Now we would like to extend the summation procedure to general, hierarchically structured lists - i.e. lists of lists. Implement a new version of sum-up, sum-up-tree, that computes the sum across tree structured lists as below.

(sum-up-tree '((1 2) 3 4))

Problem 5 Solution

(define (sum-up-tree alist)
      (cond ((null? alist) 0)
            ((not (pair? alist)) alist)
	    (else (+ (sum-up-tree (car alist)) (sum-up-tree (cdr alist))))))

CMSC 11500 - Introduction to Computer Programming Homework #2