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)
((7))
(1 (2 (3 (4 (5 (6 7))))))

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