Lecture Notes -- Week 4
CS 115-01

October 18, 1999 (Monday)

Ex 1.41, 1.42, 1.43

Rational arithmetic

• hierarchy of abstractions
• cons, car, cdr

Ex 2.1

Alternative representations

• alternative to make-rat, numer, denom, based on delayed gcd's
• alternative implementation of cons,car,cdr.

Ex. 2.4

October 20, 1999 (Wednesday)

Box and Pointer representations -- hierarchical structures (cons (cons 1 2) (cons 3 4))

Representing sequences. nil, list. car and cdr as list operations. cons as a list operation. list-ref, length. append.

Ex. 2.17, 2.18, 2.19, 2.20.

October 22, 1999 (Friday)

Hierarchical lists. ((1 2) 3 4). Tree structure.

Sequences as interfaces. Higher order functions: map, filter, accumulate.

Consider two problems:

1. sum the squares of the odd leaves of a tree
2. build a list of even fibonacci numbers.

Ex 2.21, 2.28, 2.33, 2.34