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, most of those ideas are most 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-6 (open lists, closed lists, etc.) Do not worry about the details of graphics programming or provided classes like Graph, Node, and Arc.


  2. Data Structures

    • What are the data structures: Queues, Stacks, Trees, Linked Lists, Hashtables, 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?
    • What is an S-expression?
    • Describe some ways in which S-expressions can be viewed as trees.


  3. Functional Programming in rex

    • What is a partial function? A function? A one-to-one function?
    • What is programming by induction (rewrite rules)? What is programming with recursion? Recursion is the secret to all 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 take a function as an argument? How can a function return a function as an argument? 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.
    • How can objects such as arrays, trees, and graphs be encoded as lists? Make sure that you feel comfortable writing rex functions to manipulate such objects.
    • What is the difference between normal order and applicative order? What are the merits of each?
    • 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?
    • What is a binary relation? How are binary relations used in modeling transitions between states?
    • How is an array like a 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. Open Lists. By an "open-list" abstraction, we mean the collection of functions cons, first, rest, isEmpty, and the empty list nil. In this abstraction, how would you do the following: 

    • create a list of 3 elements: a, b, c
    • create a list of 1 element: a
    • determine whether the list contains at least 3 elements
    • extract the third element from a list
    • square each element in a list
    • find out the index of an element in a list
    • create a new list from a list, dropping each element satisfying a certain predicate
    • append one list to another
    • reverse a list


  5. 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 Java interface and what is a situation in which it would be useful?
    • What is a constructor and when is it invoked?
    • 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 deep copy and shallow copy (or deep and shallow tests for equality) and what are the advantages and disadvantages of each?