You may bring one two-sided 8.5-by-11 sheets of paper to the exam with whatever notes you'd like on both sides, typed or handwritten.

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

Study Guide

• Java 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?
  • 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?
  • 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 and under what conditions can it be used?
  • How many points per minute is one furlong per fortnight?
  
  
  
• Data Structures
  • A note on terminology: an information structure is a datatype adhering to a specific interface, such as a StackInterface or a QueueInterface; a data structure is a specific implementation of an information structure.
  • How do Java interfaces work - and how do they facilitate the connection between information structures and data structures?
  • What operations do the information structures named Open Lists, Queues, Stacks, and Deques support?
  • You should be comfortable with the data-structure implementation of the above structures using linked lists of cells, as we showed for Stack and you wrote for OpenList and Queue.
  • What are the differences between open lists and closed lists?
  • How do breadth-first search and depth-first search work? How are queues and stacks used in each of these algorithms? What are the potential advantages/disadvantages of each?
  • 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? What are free and bound variables within an expression?
  
  
  
• 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, etc.
  • 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?
  • Make sure that you can write basic Scheme functions like those developed in lecture and in the assignments. Nothing so large as the CLI or Unicalc, to be sure, 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 in Scheme?
  • What is tail recursion and how can it improve performance?
  • You should be familiar with the Scheme higher-order functions such as map, foldl, and foldr. You certainly don't need to memorize them, but you should feel like you could implement them and other higher-order functions from a definition using recursion. You should also feel comfortable using them in order to implement higher-level tasks.
  • How can objects such as trees (for example, parse trees) be encoded as lists? Make sure that you feel comfortable writing Scheme functions to manipulate such objects when represented as S-expressions.