A checklist of review questions to help you prepare for the mid-term.

  1. General

    • Make sure you understand and feel comfortable with rex and Java syntax. Although the test concentrates on high-level ideas, those ideas are often precisely and concisely expressed in those languages.
    • Make sure you are familiar with the ideas emphasized in the homework problems throughout the term.
    • You should be able to write basic rex functions like those in assignments 1-3 (nothing as involved as the scrabble or unicalc problem will be expected, however). Also, you should feel able to write Java code manipulating data structures similar to those in Assignments 4-8. Do not worry about the details of graphics programming or code that was provided (like the Tokenizer class, for example).


  2. Data Structures

    • What are the following data structures: Queues, Stacks, Trees, Linked Lists, Hashtables, Deques, etc.? What operations do they support?
    • How do breadth-first search and depth-first search work? How can queues and stacks be used in each of these algorithms?
    • Review data representations for trees, graphs, etc.
    • What are the differences between open and closed lists and the comparative advantages for using destructive vs. non-destructive list operations?


  3. Functional Programming in rex

    • What is a partial function? A total function?
    • Review rex's rule-based programming (rewrite rules) and recursion. Recursion is the secret to happiness in functional programming. How can you take a problem and formulate it using recursion?
    • What is a function and what is a predicate? How can a function return a function as a result? What are anonymous functions and where are they useful?
    • What is a higher-order function? A higher-order predicate? Know how to use some examples of these. (map, reduce, drop, some, ...) You may also want to remind yourself of the functions rex provides for manipulating open lists: append, cons, list, reverse, etc.
    • How can data strcutures such as trees and graphs be encoded as lists? Make sure that you feel comfortable writing rex functions to manipulate such objects.
    • What is tail recursion, why is it important, and what are ways to make a non-tail-recursive function tail recursive?
    • What is meant by the "state" of a program?
    • How is an list like a partial function?
    • What is McCarthy's transformation principle? How does it allow the translation of any imperative program into an equivalent set of mutually recursive functions.


  4. Object-oriented Programming in Java

    • What is inheritance, why is it useful, and how does it work?
    • What is an abstract class and why is it useful?
    • What are the differences between modeling relationships via embedding and inheritance? What are some advantages and disadvantages of each?
    • How can references be manipulated to implement linked lists in Java?
    • What is a constructor and when is it invoked?
    • What does "super" refer to in a java class?
    • What does "this" refer to in a java class?
    • What do private, public, and protected mean?
    • What are "static" methods (member functions) and why would they be used? What is the difference between "static" and "nonstatic" methods?


  5. Parsing and Grammars

    • What is the difference between tokenizing and parsing?
    • What is a grammar? Given a grammar and a legal expression that that grammar generates, how do you form the parse tree (or derivation tree) for that expression?
    • What is recursive descent parsing and how does it work?


  6. Propositional Logic

    • You should be familiar with the basic logical functions: and, or, xor, equals, implies, and not, as well as notations for these.
    • How are tautologies, unsatisfiable expressions, and satisfiable expressions different? What is an algorithm for distinguishing among these types of logical statements?