Comp210 Exam 3 Need-To-Knows
Fall 2002
This document
is constantly being updated--recheck it often!
Exam 3 includes all previous Need-To-Knows!!
In no particular order and NOT all inclusive and some
topics may be mentioned in several places as they appear under different contexts:
ASK YOURSELF THIS QUESTION: IN ALL THE STUFF BELOW,
HOW MANY DIFFERENT CONCEPTS ARE REALLY THERE?
- Stuctures with data and behavior
- Know how to define structures that have fields that can be functions.
- Be able to instantiate and use such a structure.
- Defining and using abstract structures
- Explain how abstract structures with functions enable us to implement
polymorphic behavior.
- How does using abstract structures raise the abstraction level of your
code?
- Factories
- Why do you use them instead of the stock structure constructor: make-[struct]?
- How do factories use closures to create a common environment for multiple
functions?
- How can factories create concrete sub-classes of abstract structures?
- How can a factory be used to create a structure whose functions can
refer to their containing structure (i.e. itself)?
- Closures
- How can closures be used to hide and encapsulate implementation details?
- How can closures be used to correlate two or more functions--that is,
make them work together, but independently from anything else?
- Visitor Design Pattern
- Be able to define visitors to an abstract structure.
- Be able to write the execute function for those visitors.
- Be able to discuss the Visitor pattern in terms of the separation of
variant and invariant.
- State Design Pattern
- Be able to discuss the State pattern and its behavior in terms of dynamic
reclassification.
- Be able to code a State pattern implementation
- the use of factories to create polymorphic behavior.
- the use of locals and closures to hide/encapsulate implementation
details.
- Strategy Design Pattern
- Be able to create higher order functions that take in abstract functions
or structures and use them to perform specific abstract tasks.
- Higher-order functions
- Be very comfortable using map, foldr, foldl, filter, etc.
- Restricted Access Containers
- Understand how they work.
- The difference between stack, queue, and other policy-driven RACs.
- Understand and be able to use visitors to a RAC.
- Be able to discuss why you would want to write code using visitors to
a RAC rather than by directly dealing with a stack or queue or etc.
- Traversals
- Graphs vs. Trees
- Multiple connectedness issues--be able to explain them and understand
how one gets around them.
- Traversals without using a RAC -- be able to code this.
- Traversals using a RAC -- be able to understand this.
- Mutation
- The difference between set!
and set-[struct]-[field]!
- The pitfalls and perils of mutation -- when to/not to use them.
- How does set! on a locally
enclosed placeholder alleviate some of the problems of set!
on globally accessible placeholders?
- Be able to draw diagrams showing different instances of a structure
and what other structures to which they hold references (similar to UML
class diagrams, but for the actual instances of structures).
- Generative Recursion
- For traversals -- know the basic algorithms for depth-first and breadth-first
traversals.
- Have a complete understanding of how Missionaries and Cannibals works
- be sure to obtain properly working code (preferably from
someone you trust, like a labbie).
- be able to code it completely on your own.
- Generating the objects vs generating the proccess -- be able to compare
and contrast, as well as code.
- Divide-and-conquer algorithms, e.g. template-based sorting.
- Listeners/Observers
- relationship to event-driven systems.
- using lambdas and mutation as a way of communicationg between different
parts of a system.
- More coming....
Study advice:
-
Don't try to learn all the above topics as separate
entities. Instead, remember that except for set!
and set-[struct]-[field]! there's really nothing new that was presented
here, just different applications of what we already knew. So
look for the common, unifiying ideas that are running throughout
all the topics, e.g. variant/invariant, abstraction, closures, encapsulation,
base/inductive case, design template, etc.
- Practice coding! Try reproducing
the lecture, lab and homework code without looking at it. Try slight modifications
of the various code.