FINAL REVIEW, CSCI S-51, Summer 1999 File: final-review.help Author: Bob Walton (walton@das.harvard.edu) Version: 1 The final examination will be Wed 8/18 9:15 AM in Science Center 102b The final is closed book, except (1) you may have open any COMMONLISP programming language textbook, such as Paul Graham's; (2) you may have open any C++ programming language textbook, such as Johnsonbaugh and Kalin; and (3) you may bring any four pages (8 page sides) of notes you make yourself. These notes be turned in with the exam blue book, and will be kept with the graded blue book (they will NOT be returned to you, so make a Xerox copy if you want them). The exam will include a reference sheet on the MIPS language, so you need not memorize that. The exam will include the axioms or rewrite rules of any algebra for which you need these rules. The final will be on all lectures and assignments. However, theory topics covered by midterm exam questions will not be on the final. Its generally a good idea to be able to run the main algorithms by hand on simple examples, showing results as a trace of some kind. 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. The following is the same as the midterm review. 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. ====================================================== The following is new since the midterm: * Can you compute (MOD 7 3), (MOD -7 3)? * Can you explain two's complement arithmetic in terms of arithmetic modulo some number? Could arithmetic modulo 7 be used to represent integers from -2 through 4? Can you write a simple MIPS program given C code, using standard prolog and epilog? Can you write pseudo-C comments for the MIPS code? Given RR rules can you write C code and then the MIPS code? Having done the above for a tail-recursive function, can you perform the tail-recursive optimization as a compiler would perform it? Given a function defined by RR, find the time complexity of the function assuming the execution time is bounded by a small constant times the size of a call tree of a function execution. Given an NDFA as a picture and a particular input, could you label each state with the numbers of the run steps for which that state was current. Could you write a trace of the execution of `run' for the NDFA and input. Given an RE can you draw the associated NDFA? Do you know the rules for building NDFAs from REs. Explain what a non-terminal in a grammar is? Explain what a terminal is? Given a grammar defining a set of expressions, tell whether some given expression is in the set? Given a grammar defining a set of expressions, describe the set of expressions in English? Given a set of expressions, give a grammar defining that set of expressions. Given a grammar, compute first-of-x for some non-terminal x of the grammar? Given a grammar and an expression, construct the parse tree for the expression and the grammar? * Given a parse tree you have constructed for an interpreted language, assign values to the tree nodes? Given a grammar, write pseudocode for a recursive descent parser that assigns interpreted values to the parse tree nodes? Given pseudocode for the parser, write the corresponding grammar. * Given a list of some components of lisp51 that you have worked on (see lisp51.pd, 2. Components) write a very brief description of these components? Write data grammars or code synopses for the LISP object types (object, fixnum, symbol, cons, function) in lisp51? See lisp51.pd, 3.1. Write class declarations for the data parts of the above classes. See lisp51.pd, 3.2? Given a data grammar for an additional type like vector, write the class declaration for the data part of the vector class, as per lisp51.pd, 3.2? Given a specification for simple lexemes, write a grammar for the lexemes? Given a lexical grammar, write a DFA in the form used in scanner.cc in assignment 8? Given a DFA write a corresponding data grammar. Given a DFA write corresponding C++ code, or vice versa. Given the class definition for a new vector type, write vector::print and make_vector? Explain the differences between may_be_xxx, must_be_xxx, and unchecked_must_be_xxx? Given RR for a non-standard simple LISP evaluator, write the code for the evaluator? Ditto for bind_args or eval_args? Explain the environment data structure in lisp51 and the functions that directly change and access it (bind_args and binding_pointer)? Trace the execution of successive calls involving closures produced by INTEGERS-FROM (meta-lisp page 9) or other simple closure related functions? Given a LISP memory model graph, with some nodes designated as garbage collection roots, give the gc call tree that includes the top level gc and the scavenge functions. Write simple macros that use &REST starting from RR? * Consider implementing the environment as a C++ stack like the preserve stack. What is the problem with doing this? How many ways can you think of to solve this problem? Explain the preserve stack and the root set for gc? Give the pseudocode for gc_mark and explain what it means to scavenge an object? Write pseudocode for gc() and explain what sweep means? Compare graph search algorithms with marking algorithms. What are the conceptual similarities, and what are the implementation differences? What is a spanning tree? ======================================================== Things that will NOT be on the exam. Polynomials or rational polynomials (we will ask about simple expressions instead). The memory allocator example. Cryptography, finite fields, etc. But Modulo arithmetic may be on the exam. Randomized data structures (other than hash tables), such as treaps and skip lists. Questions about how computer hardware is built. Questions about software engineering. Components of lisp51 you did NOT work on in assignments.