MIDTERM REVIEW, CSCI S-51, Summer 1999

File:		midterm-review.txt
Author:		Bob Walton (walton@das.harvard.edu)
Version:	4

The midterm will be on all lectures through and
including logic programming and on all of
assignments 1, 2, and 3, EXCEPT for the code of the
CHILDREN and GOAL functions for logic programming in
assignment 3 (we suggest you do all the rest of
assignment 3 before the midterm even if you plan to
submit the assignment after the midterm).

The midterm is closed book, except (1) you may have
open any COMMONLISP programming language textbook,
such as Paul Graham's; and (2) you may bring any
two pages (4 page sides) of notes you make yourself.
These must be turned in with the exam blue book, and
will be returned with the graded blue book.

Material you should have learned while doing the
assignments is strongly emphasized in the midterm.
Below, study topics that are NOT (necessarily) learned
while doing assignments are *'ed, and should be studied
AFTER the other study topics have been mastered.


Can You:

  Evaluate by hand simple expressions with operators
    like +, - , *, /, CONS, CAR, CDR, ATOM, CONSP,
    SYMBOLP, NUMBERP, ODDP, EVENP, MEMBER, EQL.
  Define simple functions like CIRCLE-AREA.
  Define short recursive functions using rewrite rules:
    see exercise 1.5.3.1.
  Write LISP code given a function defined by rewrite
    rules: see exercise 1.5.3.2.

  Draw a call tree given a function defined by rewrite
    rules or by code: see exercise 1.5.3.3.
  Tell which dotted/undotted lists represent the
    same internal list structure: e.g., (A . (B . NIL))
    == (A B . NIL)  == (A B)
  Describe the memory model of LISP.  What represents
    an atom, a variable, a cons-cell.
  Given a LISP memory model graph, give the correspond-
    ing s-expressions.
  Given s-expressions, draw the LISP memory model graph
    they represent.
  Tell how (QUOTE X) and (FUNCTION X) print?  What do
    they do as special functions?
  Explain LET and LET*.
  Given a LET with several variables can you draw the
    memory model diagram produced.
  Describe what EQL does in terms of the memory model.
  Describe what a rewrite rule (RR) is.
  Tell the difference between a normal function,
    a macro, and a special function.
  Explain &OPTIONAL.
  Write RR to define COND, CONS, CAR, CDR, NTH, APPEND,
    REVERSE, CONSP, EQL, ATOM, LISTP, OR, AND, MEMBER,
    EQUAL, MAPCAR
  Define functions that use closures by RR or code:
    see exercise 1.6.1.1 and 1.6.1.2.
  Given a SIMPLE backquote expression, e.g.
    `(x ,y), could you write an equivalent using only
    CONS and QUOTE (') instead of BACKQUOTE (`) and
    COMMA (,).
* Could you tell what a simple macro call does.
  Could you translate a simple function whose entire
    body was a simple DO to a recursive function.
  Given a function defined by RR, show how a call on
    the function evaluates by rewrites.
  Describe what a grammar is.
* Given a grammar defining a set of expressions, tell
    whether some given expression is in the set.

  Define normal form.  Why is it important?
  Can you do rewrites in an algebra of integer
     evaluation.  Ditto modulo N for N = 2 to 9.
  Tell what is and is not a wff.
  Demonstrate provable equality in the algebra of
     simple expressions or boolean algebra or
     propositional calculus with constants.
  Do rewrites in the algebra of simple expressions
     or using the dnf rewrite rules or using
     boolean algebra rewrite (evaluation) rules.
  Define terminating and confluent and tell why each
     is important.
* Define sound and complete and tell why each is
     important.
  Describe how one might instrument a function.
     What advantages does this have over trace?
  Can you define `theorem' and `unsatisfiable' and
    explain how these concepts are related.

  Given a simple graph could you construct the first
    few levels of the search tree.
  Given a small search tree construct the associated
    graph.
  Could you run each of the goal search algorithms on a
    simple example by hand, given either the search
    tree or the graph.  Can you number the nodes in the
    order they are visited.
  Could you run the game search algorithm on a simple
    example by hand.  See exercise 3.2.9.1.
  Can you explain alpha-beta pruning.
  Can you define all the terms associated with
    trees and graphs.
  Could you complete a RR like:
    (dnf-distribute '(and (or x y) z)) ===> ????
    or
    (literals '(and x y)) ===> ???
  Could you answer a query given a simple database.
  Could you draw a path to a goal in an SLD-resolution
    tree.

  Could you execute a substitution for an expression.
  Could you unify two expressions given an input
    substitution.
* Could you complete a RR like:
    (breadth-first-search '(state . more-states)
			  #'children #'goal)
	===> ???
    or
    other tree searches.
* Ditto for unify if most of the RR were given and
    you were asked to fill in the blanks.
    

Things that will NOT be on the exam.

  Complexity Theory (next exam).
  Closures with variables bound into them (next exam).
  Polynomials or Rational Expressions (we will ask
    about simple expressions or wff instead).
  Rewrites using constant elimination or cnf rules
    (we will use dnf rules instead).
  Tail Recursion (next exam).
  Grammars (next exam).
  Design and code for logic programming.
    (but theory will be on this midterm)