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 [omitted from this year's exam]
- 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.
- Be able to write code using internal factories that enable objects
to recursively generate themselves.
- 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 [omitted from this year's exam]
- 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 codes.
©2003 Stephen Wong