CS212 Exams
Final Information

Date: Friday, May 14, 1999
Time: 9:00 - 11:30 am
Place: Hollister B14

Review: Thursday, May 13, 1999, 6:30-8:30pm, Upson 205
Office Hours: Professor Morrisett will be available by appointment all week

You're coming towards the end....  As before, you will not be allowed to bring any materials to the exam. The only thing you will need is a pencil and a functioning brain (i.e., get some sleep before the exam). We will again provide you with the Scheme and Swindle Quick References - it would be a good idea to know these by heart.

Material Coverage

This semester has covered a lot of material.  Here is a fairly comprehensive list of what you have learned. If you feel comfortable with everything in this list, you're in good shape. (Of course, I might have missed something in the list, so keep checking to see if something else shows up).

Topics From Lecture & Section

• Programming Paradigms
  • Functional Programming
  • Imperative Programming
• Good programming style
• Recursion vs. Tail Recursion
• Substitution Model
• Higher-order Functions
  • Curried functions
• Proof Techniques
  • Proof by Mathematical Induction
  • Proof by Strong Induction
  • Proof by Structural Induction
• Computational Complexity
  • Run-time Analysis
  • Recurrence Equations
  • Big-O notation
• Abstraction
  • Contract
  • Implementation
    • Encoding special forms as lambda expressions
• Environment Model
  • Frames, bindings, etc.
  • Look up rule
  • Side effects
    • Errors
    • I/O
    • Changing Values
  • set! vs. define
  • Garbage Collection
• Global vs. Local State
• Box and Pointer Diagrams
  • What is a value in the Environment Model?
• Data Structures
  • Lists
  • Vectors
  • Streams
• Abstract Data Types
  • Stacks
  • Queues
  • Priority Queues
  • Heaps
• Object-oriented Programming
  • Generic Functions vs. Message Passing
  • Class Hierarchies
• Computability
  • The Halting Problem
• Continuations (not on exam)

Topics From Problem Sets

• Problem Set 1
  • Recursion
  • Style
• Problem Set 2
  • RSA Encryption (not emphasized on exam)
  • Higher Order Function
  • Manipulating Lists
  • Style
• Problem Set 3
  • Boolean Logic (only basic concepts on exam)
  • Abstraction
  • Style
• Problem Set 4
  • Graph Theory
  • Style
• Problem Set 5
  • Applying Graph Theory to a Game
  • Generic Functions
  • Parsing User Input
  • Style
• Problem Set 6
  • Parsing User Input
  • Optimization
  • Compilation
  • Interpretation
  • Style

What should I study?

• Review your notes from lecture and section
• All the handouts are required reading, so whatever's there is fair game
• Look at your graded problem sets, and see what you could have improved. If you didn't get full credit for a problem, try redoing it.
• Make sure both you and your partner understand what went on in the problem sets.

Things to Think About

Here are a few things to get your brain warmed up.

• Remember in the last class, I asked you how you would tell if a given list has a cycle in it, using only constant space and linear time.  Well, keep thinking about that. If you get it, don't give it away.
• What is the big advantage of using local state over global state?  What's the difference with respect to the environment model?
• What is the importance of thinking before hacking?
• Many uninformed programmers who didn't take CS212 will try to discredit functional programming. They often say that functional programming languages lack object-oriented capabilities. Respond to this argument using what you know of Scheme and Swindle. Make sure to explain what make a programming language functional.
• Why don't we need for and while loops in Scheme?
• Is it possible to write a tail-recursive solution to all recursive problems?

What Will Happen at the Review Session

This web page already has a fairly extensive summary of the course, so it will be rather pointless to repeat this material. The review session will provide an opportunity for you to get last minute questions answered before the exam. Make sure to bring questions to the review. Additional examples and pointers on preparing for the exam will also be covered.

Sample Exams

Use these practice exams as a study tool. There's plenty of problem's here, and you should be able to do all of them.

Prelim I

• Fall 1996 Prelim 1

• Spring 1997 Prelim 1

• Spring 1998 Prelim 1

• Spring 1999 Prelim 1

Prelim II

• Spring 1997 Prelim 2

• Spring 1998 Prelim 2

• Spring 1999 Prelim 2

Final

• Spring 1998 Final