Exam Notes

Version 4.0/2005-08-10

What Kurt thinks about exams

This isn't high school anymore. Exams are no longer about testing your ability to memorize things. Instead, we are concerned with your ability to use the concepts we have taught you to create and innovate.

Here's a useful analogy: A carpentry exam could come in two flavors: It could be a 100-question multiple-choice exam, where question are like follows:

 
67. A hammer is principally used for ________.
A. pounding in nails. C. eating sandwiches.
B. driving cars. D. none of the above.

Or, a carpentry exam could look like this:

 
2a. Build a doghouse. It should look clean, elegant, and
require a minimum of wood.
 
2b. Build another doghouse, but, this time, you are not
allowed to use a straightedge or screws.

Your exams in 61a will look much more like the second version.

How to study

Study in study groups! Your fellow classmates will be very helpful. Don’t just talk about problems, but try to talk about a deep understanding of the material. Try to come up with exam-level questions for each other.

All of Kurt's previous exams (which have covered largely the same material) are available on the website. These are an excellent resource. Watch out for material covered in previous exams that might differ somewhat from material we covered this semester. (E.g. we haven’t done concurrency this semester.)

You should understand every procedure done in the book, in lecture, labs and the homework.

I'm less concerned about things like proper syntax for scheme (this will come over time) and more concerned about your ability to use the "big ideas" we've covered in the class.

On the first exam, you'll have to prove your understanding by writing code. It is not enough to explain what you are doing. On later exams, we are much more willing to give partial credit for having the right idea about how to approach the problem.

What we expect from you on Exam 1

Here are some things we expect you to be able to do on the exam. This list is not meant to be exhaustive, but you should make sure that you understand everything on this list.

• Understand the consequences of functional programming, applicative and normal order evaluation.
• Write recursive procedures, in iterative and recursive style, without using unnecessary helpers.
• Be comfortable using procedures as arguments and return values, especially the creation of HOFs.
• Detect patterns that can benefit from the standard HOFs we have defined in this class (viz. keep, map, accumulate, et cetera). (And actually using HOFs!!)
• Define and implement reasonable abstract datatypes, including the proper usage of datatypes that are constructed from other datatypes.
• Give reasonably rigorous proofs of elementary running-time and space complexity problems.
• Be able to describe the order of evaluation for scheme expressions and be able to predict the return value of any given expression.

What we expect from you on Exam 2

Here are some things we expect you to be able to do on the exam. This list is not meant to be exhaustive, but you should make sure that you understand everything on this list.

• Be comfortable with trees as developed in lecture: Creating (new) tree abstractions designed to solve problems, writing recursive procedures that operate on trees.
• Deep recursions on nested lists.
• Recognize and take advantage of the tree-like recursive processes that exist in lots of computer science processes. (For example: scheme expressions as trees, frames as trees, etc.)
• Build systems that use DDP programming and/or tagged data. Understand the relative strengths and weakness of DDP/tagged data/etc.
• Be comfortable implementing objects and datatypes in our OOP language, as well as creating methods to have objects do interesting things.
• Be able to effectively utilize the three main features of our OOP language: Inter-object Message Passing, Local State, and Inheritance. We are less concerned with the oddities of the OOP language and more concerned with you writing clear, simple OOP code.
• Understand how OOP message passing and local state are implemented. Be comfortable enough with the OOP system below-the-line to be able to make changes to implement new behavior.
• Be able to apply the environment model to trace evaluations; understand why each rule in the environment model is why it is, and what linguistic consequences attach to each rule. (E.g. lexical scoping) Understand why we need the environment model in the first place. Draw environment models to our satisfaction.

What we expect from you on Exam 3

The focus of the third exam will be the topics from weeks 5 and 6 (including the bits of lazy covered on the Monday of week 7). Pay particular attention to streams, mce, and lazy. Topics from weeks 1 through 4 will not be tested directly, but may re-occur as elements (or necessary parts) of questions that test week 5 and 6 material.

Here are some things we expect you to be able to do on the exam. This list is not meant to be exhaustive, but you should make sure that you understand everything on this list.

• Know all of the problems discussed in lab, homework, projects, and lectures, up to and including Lazy Evaluation.
• Be able to perform and trace mutations on explicit data structures (set-car, set-cdr) and mutations of variables (set!). Understand (and be able to apply) the idea that only pointers to things may be mutated. Understand how mutation functionality is implemented in the evaluators.
• Build complex data structures that do mutation (trees, tables, etc.)
• Undestand the different senses of equality (eq?, eqv?, equal?). We don’t expect you to memorize their exact behavior, but you should understand identity versus equality (eq? versus equal?). Don’t forget the the behavior of the equivalence predicates is defined in the back of the reader. Understand the connection between behavior/specification of the equivalence predicates and the underlying representation of objects. You don’t have to know the particularities/implementation dependencies of STk, but you should be able to reason logically about 1. why some things are implementation dependent and others are specified.
• Understand memorization generally as well as the two examples of memorization we have seen (table-based proc memorization, structure-based promise memorization). Be able to build memorizing objects.
• Understand vector interface and functionality. Be able to use the benefits of vectors, while avoiding the weaknesses. You do not need to know how vectors obtain their functionality. Have opinions on which of our datatypes would benefit from the use of vectors, and which would not. Have a rudimentary understanding of the consequences of choosing between lists and vectors on complex time/space bounds.
• Know the interface for streams, how to construct streams, and ways to build interesting, complex streams (like the sieve and pairs). You do not need to be able to trace the order of evaluation precisely, but you need a good idea of how it works (and could figure out the order of evaluation if given enough time). Be able to use a scheme that allows you to build complex streams (implicit and explicit) like fibs without a generator.
• Understand the implementation of streams in terms of delay and force. Be able to write other “lazy-ish” data structures by way of delay and force. Understand the implementation of delay and force.
• Be able to explain all of the features of scheme (as explained in lecture) and how to build an interpreter to implement them. Know which features come from the underlying stk and which are handled in our interpreters. We don’t care that you have the particular evaluators memorized, as long as (given a decent amount of time) could understand what each piece of any interpreter is doing.
• Be able to add linguistic features to the interpreters. (New special forms, different rules of evaluation, etc.) In such a question, we would give you a choice as to which interpreter you would like to modify. Be able to make intelligent design decisions and recognize the available options (e.g. the options in implementing datatypes). Understand the usefulness and concepts like syntactic transforms.
• Be able to reason through the consequences of modifications to any interpreter. (Again, we would not expect that you have each interpreter memorized.)
• Understand the benefits of normal order evaluation, including in which cases it is useful. Understand the limitations of streams, the benefits of lazy data structures. Understand the limitations of normal order evaluation, including a clear understanding of when and how things become thunks (and when and how they do not). Remember and apply what Kurt said about thunks only being created out of arguments to compound procedures.
• Understand the normal-order modifications to our meta circular evaluators. Understand when promises are created, and when they are forced. Understand the intricacies of lazy datatypes.
• Understand the problems with mutation and normal order evaluation. Know the behavior and implementation of memorized thunks.

What we expect from you on Exam 4

The final exam will be cumulative, but with a strong emphasis on weeks 7 and 8. Approximately 40 points will be drawn from amb and logic and the remaining will be from previous topics.

This exam has significantly less reading than previous exams.

Here are some things we expect you to be able to do on the exam. This list is not meant to be exhaustive, but you should make sure that you understand everything on this list.

• Know all of the problems discussed in lab, homework, projects, and lectures for the last two weeks. It is very important that you understand Kurt’s presentation of logic (as it departs from that in the book).
• Know how to write programs that take advantage of the amb evaluator.
• Understand continuations such that you could add cool and important new features to the amb evaluator.
• Know the basics of axiomatic (formal) systems, derivations, etc. Be able to give derivations. Concentrate on the ideal logical behavior as presented in lecture – I don’t care so much about the oddities of our evaluator, nor how the evaluator actually goes about things. Understand the consequences of dealing with a formal (syntactic) system.
• Be able to write complex logic descriptions – especially be able to model procedures we have previously written. Writing interesting logic programs will be a significan component of the exam.