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 for 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?

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.