cdr'ed You should read through the end of Section 2.2 in order to be fully prepared for this lab.
Please complete the following exercises before your recitation on Friday. Should you have any difficulties working these basic exercises, bring your questions to recitation.
For the drawing component of these exercises, you may use any drawing program you like, as long as the final drawings are output in PostScript format (.ps file extensions). We recommend the xfig or the dia programs, both of which are installed on the CS cluster computers. Submit the drawings as separate files to CS1man.
[25] Draw box and pointer diagrams for the following Scheme
expressions. Assume that nil has been defined to be the
empty list, i.e. (define nil (list)).
(cons 1 2)
(list 1 2)
(cons 1 (cons 2 nil))
(list 1 (list 2 (list)))
You can use the word nil for the empty list (the thing
returned by (list)), or you can represent it by a single
box with a line drawn diagonally through it.
(cons 1 (list 2 3))
(list 1 (cons 2 3))
(list (list 1 2 3) (list 4 5 6) 7 (list 8 9 10) 11 12)
[25] Give a Scheme expression which will build each of the structures shown in the box and pointer diagrams:
[15] What's wrong with these expressions? Describe why each of them will result in an error.
(cdr (list))
(cdr (cdr (cdr (list 1 2))))
(car (car (list 1 2)))
(define (buggy-sum lst)
(+ (car lst) (buggy-sum (cdr lst))))
(buggy-sum (list 1 2 3))
(+ 1 2 3 (list 1 2 3))
After figuring out what's wrong with them, type them into the Scheme interpreter and see how the interpreter will respond to these "bugs".
[15] Explain the function of the following procedure which operates on lists:
(define (fh x)
(define (fh-aux l aux)
(cond ((null? l) (list))
((null? (cdr l)) (list))
(else (cons (car aux) (fh-aux (cdr (cdr l)) (cdr aux))))))
(fh-aux x x))
Write the following procedures which involve lists:
[15] A procedure that counts the negative elements in a list and returns the count.
[10] A procedure that takes in an integer, n, and creates a list containing the first n powers of 2 starting with 20=1.
[25] A procedure that takes in a list of numbers, and
returns a list containing the prefix sum of the original list.
e.g.(prefix-sum (list 1 3 5 2)) ==> (1 4 9
11). The prefix sum is the sum of all of the elements in
the list up to that point, so for the list (1 3 5 2)
the prefix sum is (1, 1+3, 1+3+5, 1+3+5+2) or (1
4 9 11).
Please do the following exercises from the textbook. We've added some clarifications which should make the problems easier to manage.
[30] Exercise 2.20 (dotted tail notation). The phrase "even-odd parity" just means evenness or oddness, so that if the first number in the list is even, you should return a list of all the even numbers in the list, and if the first number is odd, you should return a list of all the odd numbers in the list. Note that the function you define will always have to take at least one argument.
You can use the remainder procedure to determine if a
number is even or odd i.e. (remainder x 2) returns 0 if
x is even or 1 if x is odd.
[30]
Exercise 2.21 (using map). Read the section just
preceding the exercise to learn how the map higher-order
procedure works. map is actually one of the most
frequently-used higher-order procedures. Use (list) where
the book says to use nil (coding standards have changed since
the book was written).
[30]
Exercise 2.32 (generate all subsets of a set, fill in code and
explain). Again, use (list) where the book
uses nil.
Note that the append procedure concatenates two lists,
returning a new list containing all the elements of both old lists in
order. So, for instance, (append (list 1 2 3 4) (list 5 6 7
8)) gives the result (1 2 3 4 5 6 7 8) without altering
either of the first two lists.
Hint: The code you need to add is very short; it will easily fit
on the same line as the map.
[30] Exercise 2.34 (evaluate polynomials).
Note that the accumulate procedure is defined as:
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
and is discussed at length in section 2.2.3 of SICP.
To solve this problem, it may be helpful to take an example (e.g.
(horner-eval 2 (list 1 3 0 5 0 1)), figure out what
computation you want to be performed, and then write the code so that it
performs it. Note that the coefficients in the list are in reverse order,
so the first 1 is the x^0 coefficient and the last 1 is the x^5
coefficient. Again, the amount of code you have to add here is extremely
small. Hint: Think carefully about what the arguments of the
lambda expression refer to.
[45]
Exercise 2.37 (matrix calculations; dot product, transpose). Note that
you'll need to read exercise
Exercise 2.36 to familiarize yourself with accumulate-n.
A working definition of accumulate-n is:
(define (accumulate-n op init seqs)
(if (null? (car seqs)) ; sequences are empty
(list) ; we prefer this to nil, since nil isn't predefined in DrScheme
(cons (accumulate op init (map car seqs))
(accumulate-n op init (map cdr seqs)))))
None of the code fragments you need to fill in in any of the functions in this exercise are more than a line long. Feel free to use the earlier functions in the definitions of the later functions.
There is no part D in this week's lab (and there was much rejoicing).