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