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. Also, you should feel able to write Java code manipulating data structures similar to those in Assignments 4-6. Do not worry about details that were not focused on in class, e.g., graphics programming or threaded code .


  2. Data Structures

    • What are the following data structures: Queues, Stacks, Trees, Hashtables, Deques, OpenLists (linked lists) 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?
    • 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 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 might they be used? What is the difference between "static" and "nonstatic" methods?