6.001                                                Fall 1997

                  Material for Quiz 1 (October 8, 1997)

QUIZ 1 is CLOSED BOOK: no text, handouts, or notes may be used -- EXCEPT
for a single sided page of personal notes (in at least 10 pt font) which
students may bring to the quiz.

It is designed so most students can complete it in about ONE hour.  The
quiz sessions are TWO hours to lessen time pressure.

There are two quiz sessions, from 5pm--7pm, and 7pm--9pm.  Students may
not leave the 5pm session early (before 7pm), and may not arrive late for
the 7pm session.

Quiz 1 will be held in 4-270 and 4-370.  Both rooms will be used for both
quiz sessions.


                                 READING

  *  SICP, Chapter 1; Chapter 2, sections 2.1--2.2.3, 2.3.1--2.

  *  Problem Sets 0--3.

  *  Slides and notes (on the 6.001 Homepage) for
     @  Lectures 1--8, and
     @  Lecture 9 (Thurs, Oct 2) covering Abstract Syntax through
        slide 15 (omitting the remaining slides on storing "extra" data
        within an expression to speed up operations on the expression).


                                 TOPICS
  
  *  Simple general recursive and tail-recursive Procedures
  *  Iterative and General recursive Processes: Growth rates
     (Theta notation) of Time and Space.
  *  Substitution Model for evaluation of Scheme expressions.
  *  Abstracting program patterns as procedures.
  *  Higher Order procedures as first-class values.
  *  Abstract Data specified by Contracts; implementation independence.
      @ Abstract Pairs
      @ Rational Numbers
      @ Abstract Syntax
      @ Abstract Trees
  *  Scheme pairs; CONS, CAR CDR; box and pointer diagrams
  *  Lists and Trees
     @  Output notation: using parentheses to describe list structure.
     @  CDRing down lists with recursive procedures.
     @  Basic Operations: LIST, NULL?, PAIR?, LENGTH, LIST?, LIST-REF,
        APPEND, REVERSE, COUNT-LEAVES, FLATTEN
     @  Higher-order Operations: MAP, FILTER, ACCUMULATE, TREE-MAP
  *  Symbolic computation: symbols, EQ?, QUOTED expressions