Study Guide for Test on SICP Sections 2.2.2-3 and 2.3.1-2
		See also the Little Schemer, Chapter 5

This study guide contains two parts. The first is the actual
directions from the test.  These will appear on the first page.  The
second is a list of topics.


DIRECTIONS FROM THE FIRST PAGE OF THE TEST

For this test, you can use one (1) page (8.5 by 11 inches, one (1)
side, no less than 9pt font) of notes.  Don't use anything with
printing on the other side. No photo-reduction is permitted.  You may
not share your notes with anyone else during the test.  These
notes are to be handed in at the end of the test, so please have your
name in the upper right hand corner of your notes.  Use of other notes
or failure to follow these instructions will be considered cheating.

WARNING: you won't have time to learn the material on during the test.
Just write down what would be too tedious to remember otherwise.

If you need more space, use the back of a page.  Note when you do that
on the front.

This test is timed.  We will not grade your test if you try to take
more than the time allowed.  Therefore, before you begin, please take
a moment to look over the entire test so that you can budget your
time.

For programs, indentation is important to us for ``clarity'' points;
if your code is sloppy or hard to read, you will lose points.  Correct
syntax also matters.  Check your code over for syntax errors.  You
will lose points if your code has syntax errors.

Of course, you may write helping procedures or methods whenever you
wish.  It may be helpful to give a comment that describes what they
do, if it's not completely clear from the name.

You may use any of the built-in procedures in Scheme.


TOPICS FOR THE TEST

The problems on the test of the similar to homeworks 5 and 6.
Study Hint: probably the most helpful thing you can do is to create
your own test (perhaps from problems in the textbook that were not assigned),
take it on paper, and then type and debug your programs on-line.

Many of the problems will involve writing Scheme procedures.  There
will be little, if any, Java to be written in this test.

Topics and skills that are more important are indicated by a +,
those are less important by a -.

1. Hierarchical Structures (SICP 2.2.2, Little Schemer ch. 5)

- Explain the concept of "closure" used in SICP and how it relates to trees.
+ Draw box-and-pointer diagrams and tree diagrams for trees.
+ Use car and cdr to extract parts of trees.
+ You should understand the differences between
  the grammars for trees and atomic-expressions,
  and how they relate to patterns of recursion.
  (Recall that the book itself doesn't make this distinction,
  but we discussed it in class.)
+ Write recursions in Scheme over trees using either one of the
  two available grammars: i.e., using either map or not for trees,
  and using atomic-expression recursion over atomic-expressions and trees.
  (Homework problems included deep-reverse, fringe.)
- Know when you can use map in tree recursion and when you can't.
+ Write procedures that abstract recursion patterns over trees,
  as in the tree-map homework problem.
+ Write recursions in Scheme over other datatypes that have
  mutually recursive structure.  (Homework: the binary mobile problem.)
  Note: this is a good place to combine the idea of symbolic data
  with that of trees.  Scheme expressions are trees of atomic data composed
  of symbols and numbers (hint, hint).

2. Sequences as Conventional Interfaces (SICP 2.2.3)
   also known as Pipe and Filter Architectures 

+ Use map, filter, and accumulate to write Scheme programs
  by filling in the missing parts of Scheme programs
  (as in the homework where you defined "map", "append", "length",
  and "count-leaves" using accumulate, and various matrix operations using map
  and accumulate-n).
+ Implement new versions of such higher-order procedures
  (like accumulate-n in the homework).
- Explain the behavior of and use fold-right and fold-left.
  Which is the same as accumulate?  What are the differences?
+ Give the output of expressions that use flatmap, filter, map,
  and various enumerations to do nested mappings
  (as in the homework's eight queens problem)
- Use flatmap and various enumerations to do nested loops.

3. Symbolic Data (SICP 2.3.1-2, in the Revised^5 Report on Scheme,
   see also the section on "Literal Expressions" and the section on
   "Equivalence Predicates")

+ Explain what quotation does in Scheme and how it is used to make symbols.
- Explain the differences between Scheme's predicates
  equal?, eq?, eqv?, and =, and their counterparts in Java (.equals() and ==)
  and use them in writing Scheme procedures.
+ Given various helping procedures, write recursions
  to process symbolic data in more complex grammars (as in the homework's
  symbolic derivative program).