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 you identify the "big ideas". You should also review your lecture notes and the solutions to your homework problems.  The lecture "quizzes" are especially useful in helping you study for the exam.

Like the midterm, the final examination will be a closed-book take-home exam. However, you may prepare two 8.5 by 11 sheets handwritten on one or both sides, and refer to these sheets during the exam. (If you like, one of these can be your sheet from the midterm.)

Study Topics

Foundations of functional programming with Scheme!

• Be sure that you recall the basics of Scheme. You don't need to memorize all Scheme's built-in functions, but if we give you a list of built-in functions that were used in class or on a homework assignment, you should feel comfortable using them to define new functions.
• 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?
• What is let* (or let) used for?
• 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.
• How is "use it or lose it" 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, how are they written in Schmeme, and how to you use them?
• What is tail recursion?
• What are trees, graphs, cyclic graphs, directed graphs, and DAGS?
• How can objects such as trees and graphs be represented as lists? Make sure that you feel comfortable writing Scheme functions to manipulate such objects, e.g., by reviewing those we looked at in class.
• How does functional programming differ from the more widely-used imperative programming?
• 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?

Run-time analysis

• What exactly does big-O running time tell us?
• You should be able to explain why the fact that an algorithm is O(n) does not imply that it's running time is directly proportional to n. (There are actually multiple reasons)
• 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 and saw in class (e.g., append, or the tail-recursive and non-tail-recursive definitions of reverse.)
• What is a recurrence and how is it used? (Hint: "T(0) = 1 and T(n) = T(n-1) + 1" is a specific recurrence.)
• You should be able to solve a simple recurrence.
• Two useful formulae for analyzing algorithms are the formula for the arithmetic progression.  You might want to write these on your sheet...

   1 + 2 + 3 + ... + n = n(n+1)/2 = O(N^2)

  and for the exponential/geometric progression, the last term dominates:

   x^0 + x^1 + ... + x^k = x^(k+1) - 1 / x-1 = O(x^k)
  

Algorithms

• What problem does memoizing and dynamic programming solve?
• You should be able to explain verbally how insertion sort, merge sort, and quick sort work. What are their asymptotic running times?

Logic Programming in 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 algorithm 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 is the "Generate-and-test" strategy?
• What types of problems is Prolog well-suited for?
• You should feel comfortable composing a Prolog solution to a smallish problem similar to the ones we did in class and on the HW.

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, public, and protected mean and where is it appropriate to use each of them?
• What are getters and setters and why are they important?
• What is static and where and why would it be used?
• What is inheritance, why is it useful, and how does it work?
• When is it necessary to cast a variable and why?
• What is a generic class (also known as a "parameterized type") and why is it useful?
• How are the terms extends, super, and implements used in Java?
• You should be comfortable with box-and-arrow diagrams to illustrate how Java organizes references and data in computer memory.
• You should be able to write code that creates and manipulates objects that reference each other (e.g., the linked list code used to implement stacks and queues).
• What are the differences between a Stack, a Queue, and a Double-Ended Queue?
• What is double-buffering and why is it used?

Lexing, Parsing and Grammars

• What is a context-free grammar?
• What is a lexer (a.k.a. tokenizer)?
• What is a parser?
• What is a parse tree, and how does it differ from an Abstract Syntax Tree?
• How can the organization of the grammar affect the meaning of inputs?
• How does recursive-descent parsing work?

Finite State Machines (Finite Automata)

• What is a decision problem?
• What is a language (also called a formal language)?
• What is a deterministic finite automaton (DFA)? What does the name mean?
• Feel comfortable building a DFA for a given regular language. Remember that the states can encode meaningful information about what the machine has seen so far.
• What does "distinguishable" mean? What does "pairwise distinguishable" mean?
• What does the Distinguishability Theorem state? How can it be used to prove that a specific DFA has the minimum possible number of states for the language that it accepts?
• What does the Nonregular Language Theorem state? How can it be used to prove that a given language is not regular? How did we prove this theorem?
• What is an NFA? What does it mean for an NFA to accept a string?
• What is a regular expression? Why are regular expressions useful? How can a regular expression be converted into an NFA and an NFA into a DFA?
• What are some practical applications of DFAs?
• Be able to describe a set of strings that is not regular.

Computability and Turing Machines

• Be comfortable with the proofs that the "halting problem" and "EQ" are undecidable.  
• What is a Turing Machine? How does it operate?
• What is the Church-Turing Hypothesis?
• Know how to prove a problem is undeciable via reduction from the Halting Problem, i.e., by building a Haltchecker from it.

Conclusion

• When or why would you choose Java as an implementation language?
• When or why would you choose Scheme/Racket as an implementation languages?
• When or why would you choose Prolog as an implementation languages?
• When or why would you choose Python as an implementation languages?