This is a checklist of review questions to help you prepare for the mid-term. While there is no guarantee that it covers everything that could possibly be asked, it should cover a reasonable portion of such things.

  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 such as those in assignments 1-2. Also, you should feel able to write Java code manipulating data structures similar to those in Assignments 3-5.


  2. Information and Data Structures

    • What are the differences between open and closed lists and the comparative advantages for using destructive vs. non-destructive list operations?

    • What are the following data structures: Queues, Stacks, Trees, Linked Lists, 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 and graphs -- acyclic vs. cyclic; directed vs. undirected.
      • How can you determine whether a graphic is cyclic, say by functional programming.

    • What is an equivalence relation? What are some ways to represent them? Why are they useful?


  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, any, keep, ...) 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?

    • How is a 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 (or one singly-recursive function).


  4. Object-oriented Programming in Java

    • What are "static" methods (member functions) and why would they be used? What is the difference between "static" and "nonstatic" methods?

    • What is a constructor and when is it invoked?

    • What is a pseudo-constructor (or "factory")?

    • What does "this" refer to in a java class?

    • What is an interface and why is the concept useful? How does Java support this concept?

    • What does it mean to implement an interface?

    • What are Enumeration and Iterator in Java? Give some examples.

    • How is the equivalent of higher-order functions implemented in Java? How does one deal with "imported" values?

    • What is the meaning of equality and copying (or cloning)? What is the distinction between deep and shallow in each of these contexts?

    • What is inheritance, why is it useful, and how does it work?

    • Contrast interfaces with inheritance.

    • What is an abstract class and why is the concept useful?

    • What are the differences between modeling relationships via composition and inheritance? What are the characteristics of each?

    • How can references be manipulated to implement linked lists (such as Queues, Stacks, OpenLists, and Deques) in Java?

    • How do you read assignment statements involving references or pointers?

    • What does "super" refer to in a java class?

    • What do private, public, and protected mean? What if they aren't specified?


  5. Grammars 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? (It is possible that we won't get to this topic.)