This review sheet is intended to help you study for the midterm exam. It is not intended to be an exhaustive list of everything we've covered, but it should help remind you of the big ideas... .

It's a good idea to review your lecture notes and the solutions to your homework problems.  The lectures' "quizzes" are especially useful in helping you study for the exam, since they're the style and spirit (roughly) of the questions...

Please remember that you may use at the exam a 8.5 by 11 sheet of self-made notes; two-sided notes are OK.

Study Topics

Logical programming with Prolog

• Prolog "programs" are a collection of facts and rules. Make sure that you understand all of the examples that we saw in class and on homework.
• Why does prolog sometimes produce multiple identical answers to a query?
• What is the fundamental procedure that prolog uses in seeking bindings that satisfy predicates?
• What is "unification"? [Answer: it's instantiating a variable (in whole or in part) by binding a value or structure to it.] What are the differences among prolog's =, ==, and is operators? Similarly, what are the differences between \+, \==, and \=?
• Why does the order in which prolog clauses are placed sometimes matter to its inference of variable/value bindings?
• What type of problems is Prolog well-suited for?
• You should feel comfortable composing a Prolog solution to a (moderately-sized) problem similar to the ones we did in class and on the HW.
• What does it mean for a logical statement (that may include variables) to be satisfiable or unsatisfiable or a tautology?
• You should understand an algorithm that can determine which of the three categories above a particular logical statement falls under.
• How can you use the fail clause in Prolog in order to have it generate multiple results without additional interaction? How can you use setof for the same purpose (though with a different kind of result!)? How do assert and retract work with dynamic predicates in Prolog?

Functional programming with Racket...

• Be sure that you feel comfortable using the basics of Racket. You don't need to memorize all Racket's built-in functions, but you should be familiar (or have notes) on the main ones we used in class and on assignments, e.g., reverse, cons, list, append, first, rest, etc.
  You should feel comfortable with what they do and how they work.
• Be sure that you feel comfortable with higher order functions (e.g. filter, map, foldr), both how to write them from scratch, and how to use them.
• You should be comfortable about the differences in the assumptions that append, list, and cons make about their inputs.
• What does assoc do and what is an association list?
• How is the "use it or lose it" approach used for solving problems recursively? Good examples including finding all of the subsets of a set or whether one vertex is reachable from another in a graph.
• What are anonymous functions and how to you use them?
• What is tail recursion and how can it improve performance?
• What is the "merge" technique for combining two sorted lists?
• What are trees, graphs, cyclic graphs, directed graphs, and DAGS? How can they be represented as Racket lists? How can objects such as trees and graphs be represented as lists? Make sure that you feel comfortable writing Racket functions to manipulate such objects, e.g., by reviewing those we looked at in class.
• What are binary search trees and how can you manipulate them? What are the big-O running times for finding, inserting, and other operations: in the best case? worst case? or in the case that 99% of nodes fall to the right at each step of the tree?

Parsing and Evaluating a Language

• How do tokenizing, parsing, and evaluation each contribute to the interpretation and execution of a computer program?
• What is a parse tree? You should be able to build a parse tree that gives rise to a particular sequence of tokens for a provided grammar, as we did in class.
• How does recursive descent parsing work? You should feel comfortable extending a parser for a small grammar and/or explaining how one works.

Object-oriented Programming in Java

• What is a constructor and when is it invoked?
• What does this refer to in a java class?
• What do private and public mean and where is it most common to use each of them?
• What are getters and setters and why are they important?
• What does static mean and where and why would it be used?
• When is it necessary to cast a variable -- and why?
• You should be comfortable with box-and-arrow diagrams to illustrate how Java organizes references and data in computer memory. What is the difference between the stack and the heap?
• How many points per minute is one furlong per fortnight?

Run-time analysis

• What is the big-O running time of an algorithm? Be sure you are comfortable estimating the best-case and (more commonly) worst-case running times of algorithms such as those you wrote for homework. Here are some examples:
• What is the big-O runtime of the merge routine for combining two already-sorted lists? What is mergesort's worst-case big-O run time?
• What is the worst-case big-O runtime for Racket's (append L M) function?
• What is the worst-case big-O runtime for the Racket (reachable a b G) predicate we wrote in class?
• What are the big-O runtimes in the best and worst case for insert, find, and delete from a binary search tree? from a balanced binary search tree? from a linked list (such as OpenList)? from an array?

Some Practice Problems

These don't hope to span all of the topics we've covered, but they are meant to give a sense of the size and scope of possible exam problems.

1. Writing foldr in Racket! Recall the the foldr function in Racket takes as input three arguments: A function f of two variables, a unit (such that (f X unit) => X), and a list L. The foldr function returns the result of repeatedly applying the function f to the elements in L until to reduce them to a single value. For example,

     Racket> (foldr (lambda (X, Y) (+ X Y)) 0 '(1 2 3 4))
     10
     

   You should assume that foldr "associates" (orders operations) like this: 1 + 2 + 3 + 4 = 1 + (2 + (3 + (4 + 0))). (Notice that the 0 at the end is the unit for addition.) Write the foldr function from scratch. That is, your implementation my use Racket's list notation and recursion, but no built-in functions. Notice that foldr should not be written exclusively to handle addition! It's first argument can be any function of two variables, its second argument is the unit for that function, and its third argument is a list of elements of the type operated on by the given function.
   
   
2. Use-it-or-lose-it in Racket

   Write a function (closest-sum target L) that takes in a numeric target and a list of numbers L. Then, closest-sum should return the subset of the elements of L whose sum is as close as possible to target.

   For example,

   (closest-sum 19 '(3 4 7 7 22))
   '(4 7 7) 
   

   Ties may be handled arbitrarily... any best answer is OK.
   
   

3. Prolog problems

   Part A   Consider this set of lists:

     { L | L consists of N 0's followed by N 1's, for some N >= 0 }
   
     in other words, the possible values of L are
   
     { [], [0,1], [0,0,1,1], ... }
   

   
   Write a prolog predicate zerones(L,N) that yields true when L is bound to one of these lists and N is bound to the number of zeros (or ones) in the list L. It should yield false if L is not one of those lists or if N is not the correct numeric value. In addition, zerones should be able to generate bindings to L and/or N if those inputs are provided as variables.

   Here are some examples of zerones in action:

   ?- zerones([],0).
   true
   
   ?- zerones([0,0,0,0,0,1,1,1,1,1],N).
   N = 5
   
   ?- zerones([0,0,0,1,1,1,0],N).
   false
   
   ?- zerones([0,1],2).
   false
   
   ?- zerones(L,N).
   L = [], N = 0 ;
   L = [0,1], N = 1 ; ...
   
   ?- zerones(L,3).
   L = [0,0,0,1,1,1]
   

   
   

   Part B    Write a prolog predicate

    subseq( L, M )
   

   that is true when the list L is a subsequence of the list M. The idea is that L is a subsequence of M when M contains all of the elements of L in the same order they appear in L, but perhaps M contains some intervening elements, too. You may assume that L and M are both lists. Following are a couple of examples of subseq to clarify its desired behavior:

   ?- subseq( [1, 2, 3], [0, 1, 5, 3, 2, 4] ).
   no.
   
   ?- subseq( [1, 2, 3], [0, 1, 5, 3, 2, 4, 3] ).
   yes.
   

   
   

4. Java problems

   Part A   Within the OpenList class we wrote for homework, how would you implement the static and nonstatic versions of member, a method that returns true if obj is present in the OpenList and false otherwise. Here are the two method signatures for member:

     public static boolean member(Object obj, OpenList L)
   
     public boolean member(Object obj)
   

   
   

   Part B   Write a Java class Vec3 that represents three-dimensional vectors of real values. It should have data members x, y, and z. Include two methods: a constructor and cross, the cross-product operation. Here are their signatures:

     public Vec3(double x_in, double y_in, double z_in)
   
     public Vec3 cross(Vec3 v)
   

   Although the exact workings of the cross product are not really the point here, Wikipedia points out that if a1,a2,a3 and b1,b2,b3 are two three-vectors, their cross product is a2b3 - a3b2, a3b1 - a1b3, a1b2 - a2b1.
   

   Part C   In the Java-based parsing assignment, you included the ability to raise a Quantity to a power using the caret operator ^. Explain what changes you would make to the language in order to also enable Python's ** operator to be used to represent taking powers. Consider all three phases of the language: tokenizing, parsing, and evaluation.