CS 251: Exam 3 Info

You are permitted one 8.5 x 11 handwritten notes sheet (both sides) for use as a reference during the exam.

Lots of research has shown that reading over material isn't a very good way to prepare for exams. The best thing to do is to practice. Reading how to swing a baseball bat or how to cross-country ski might give you some good ideas on how to get better the next time you try it, but it's not even close to just getting out there and swinging a bat or skiing in the Arb.

How can you practice? Go back to look at the assignments. Can you code selected portions of them from scratch on paper? Can you write down for all of the topics listed below? Can you invent questions to try for the topics listed below? Practice these under test conditions and see how you do. Even though the solutions may not be available, just trying to do them can be incredibly useful. The ones that involve programming you can put into the computer to see if they work. Otherwise, you can work with other students to see if you think you've got the right answers. Even if you don't know for sure if you've got the right answer, just practicing with these exercises can be helpful.

Go back and pick out all of the content from class that you understand least well. Then, without simultaneously looking at your notes, write down all that you know about that content. Think about what I might ask you to do on an exam that would be scary. Try to do that yourself. If you can't, work with other people in the class or stop by office hours to get help on doing that.

Finally, make sure to do all of your practicing on paper, not at a keyboard, so as to simulate the exam conditions.

Listed below is the material that I have in mind that you should know for the exam. It's what's in my head when creating it. That said, this isn't a contract. I may have inadvertently left something off this list that ends up on an exam question. I make no guarantees that the exam will be 100% limited to items listed below. Moreover, I will not be able to test all of this material given the time limitations of the exam. I will have to pick and choose some subset of it.

Students should be able to…

Regarding the interpreter project: Be able to answer questions about what we did at each stage, and why we did it. Be able to write variations of aspects of the project by writing C code, modifying provided C code, or describing what your technique might be. Specifically, be able to do the above regarding questions about and/or variations on:

• parsing
• lambda expressions
• closures
• frames
• bindings
• primitives / function pointers

Distinguish recursive descent parsing from the kind of parsing that we did for our Scheme interpreter. Be able to produce FIRST, FOLLOW, and PREDICT sets for a particular grammar. Be able to demonstrate how this information would be used in coding a parser.

Be able to distinguish between static and dynamic scoping, and be able to evaluate trade-offs. Be able to distinguish between shallow and deep binding. Be aware of scoping behavior for languages regularly discussed in class.

Evaluate lambda calculus expressions, and define well-known logical or arithmetic operations on Church booleans or numerals. Students should be able to work through problems of the same style that were done for the lambda calculus homework assignment.

Define, explain, compare, and contrast dangling pointer strategies such as tombstones and locks-and-keys; and garbage collection techniques, such as reference counters, mark and sweep (including tri-color marking), stop and copy, and generational approaches.

Explain and answer questions regarding how to manage free memory; including free lists, segregated free lists, and buddy system techniques.

Evaluate the results of pseudocode using different parameter passing methods, including call by value, by reference, and by sharing. Be able to think through considerations regarding how they are implemented underneath. (I removed a few other parameter passing methods from this list that we ran out of time to talk about.)