The final exam will be in-class on Wednesday, December 17, 2008.

Notes: You may bring two two-sided 8.5-by-11 sheets of paper to the exam with whatever notes you want on both sides of the sheet.

Below is a study guide of topics that we have considered in CS 60 thus far this term. In addition to using this guide, I'd recommend reviewing the class homework assignments.

Review Session

There will be an entirely optional CS 60 review session on Tuesday, December 16th at 8pm in the evening in our usual classroom. To guide the review session, any and all questions are welcome; in addition, we'll go over the solutions to the practice final exam.

Study Guide

• Logic Programming
  • 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" ? What are the differences among prolog's =, ==, and is operators?
  • How does negation work in Prolog, including the use of \+, \==, and fail?
  • Why does the order in which prolog clauses are placed sometimes matter to the inference of variable/value bindings?
  • 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.
  
  
  
• Functional Programming in Scheme
  • What is an S-expression?
  • Make sure that you understand and feel comfortable with Scheme's syntax and basic functions like first, rest, cons, append, list, etc.
  • You should be comfortable about the differences in the assumptions that append, list, and cons make about their inputs and how each one works.
  • Make sure that you can write basic Scheme functions like those developed in lecture and in the assignments. You don't need to worry about writing anything as large as minimum-length-path finding in Scheme, but a small function that might use one helper function would make a reasonable exam question. In particular, recursion is the secret to all happiness in functional programming -- you may want to review decomposing problems recursively.
  • What are anonymous functions and where are they useful? How is lambda used to create anonymous functions?
  • What is tail recursion and how can it improve run-time performance?
  • You should be familiar with the Scheme higher-order functions such as map, and foldr.
  • What are trees, graphs, acyclic graphs, directed graphs, and DAGS?
  • How can objects such as trees and graphs be encoded as lists? Make sure that you feel comfortable writing Scheme functions to manipulate such objects.
  
  
  
• Finite Automata
  • What is a deterministic finite automaton (DFA)? What does the name mean? What is the definition of a regular language?
  • 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? How can a DFA be converted to a Regular expression?
  
  
  
• Computability and Turing Machines
  • Know the proofs that the "halting problem" and "autograder problem" are undecidable.
  • What is a Turing Machine? How does it operate? You should feel comfortable building a turing machine that will accept simple languages. What is the Church-Turing Hypothesis?
  
  
  
• Algorithm Analysis
  • Two useful formulas (formulae?) for analyzing algorithm run-time are the formula for the arithmetic progression

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

    and the sum-of-powers-of-two:

          1 + 2 + 4 + 8 + ... + 2**(N-1) == 2**N - 1 = O(2**N)
          

    which has an alternative form:

          1 + 2 + 4 + 8 + ... + N == 2N - 1 = O(N)
          

  • Make sure that you understand the informal algorithm-analysis examples we saw in class and on homework. In particular, you should be able to determine the big-O running time of small algorithms or pieces of code.
  • How did we prove that every comparison-based sorting algorithm requires at least n log n running time (asymptotic worst-case running time)?
  • What is a recurrence relation? Be sure you can "unwind" recurrence relations to find big-Oh running times for recursive programs.
  • Also, be sure you can analyze the running time of nested loops to find asymptotic performance.
  
  
  
• Java, data modeling, and object-oriented programming...
  • What is a constructor and when is it invoked?
  • What does this refer to in a java class?
  • What do private, protected, and public mean and where is it appropriate to use each of them?
  • What are accessor methods 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 does inheritance model data relationships well? What are some class relationships that it does not model well?
  • What are a base class and a derived class?
  • Within an inheritance hierarchy, how does Java decide which out of several overridden methods to actually invoke for an Object?
  • What is polymorphism 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. What is the difference between the stack and the heap in a program's memory -- and which data are stoed in which location?
  • How do reference counting and mark-and-sweep garbage-collection algorithms work in Java. What are the advantages/disadvantages of each?
  • What is the merge technique for combining two sorted lists -- and under what conditions can it be used?
  • How many points per minute is one furlong per fortnight?
  
  
  
• Java and data structure ideas...
  • What is the difference between an information structure and a data structure? Which of these two does an interface represent? What does an interface do in Java?
  • What basic operations do the information structures named OpenLists, Queues, Stacks, and Deques support?
  • You should be comfortable with the (data-structure) implementation of the above structures using linked lists of cells.
  • What are the differences between open lists and closed lists? Which are used to represent lists by the Scheme programming language?
  • How do breadth-first search and depth-first search work? How are queues and stacks used in each of these algorithms? How can recursion be used to implement depth-first search without explicitly using a stack?
  
  
  
• On the structure of (computer) languages...
  • What do tokenizing, parsing, and evaluation each contribute to the execution of a computer program.
  • How do grammars and production rules work? How does a grammar of production rules specify the meaning of a legal expression?
  • You should be familiar with how to use recursive descent in order to parse a list of tokens and how to use recursion to evaluate the resulting parse tree.
  • How does an environment contribute to the evaluation of an expression?