Comp210: Principles of Computing and Programming
Fall 2004 -- Exam 3 Need-To-Knows   

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?

1. Stuctures with data and behavior
   1. Know how to define structures that have fields that can be functions.
   2. Be able to instantiate and use such a structure.
   3. Defining and using abstract structures
   4. Explain how abstract structures with functions enable us to implement polymorphic behavior.
   5. How does using abstract structures raise the abstraction level of your code?
      
      
2. Factories
   1. Why do you use them instead of the stock structure constructor: make-[struct]?
   2. How do factories use closures to create a common environment for multiple functions?
   3. How can factories create concrete sub-classes of abstract structures?
   4. How can a factory be used to create a structure whose functions can refer to their containing structure (i.e. itself)?
      
      
3. Closures
   1. How can closures be used to hide and encapsulate implementation details?
   2. How can closures be used to correlate two or more functions--that is, make them work together, but independently from anything else?
      
      
4. Visitor Design Pattern
   1. Be able to define visitors to an abstract structure.
   2. Be able to write the execute function for those visitors.
   3. Be able to discuss the Visitor pattern in terms of the separation of variant and invariant.
      
      
5. State Design Pattern
   1. Be able to discuss the State pattern and its behavior in terms of dynamic reclassification.
   2. Be able to code a State pattern implementation
      1. the use of factories to create polymorphic behavior.
      2. the use of locals and closures to hide/encapsulate implementation details.
         
         
6. Strategy Design Pattern [omitted from this year's exam]
   1. Be able to create higher order functions that take in abstract functions or structures and use them to perform specific abstract tasks.
      
      
7. Higher-order functions
   1. Be very comfortable using map, foldr, foldl, filter, etc.
      
      
8. Restricted Access Containers
   1. Understand how they work.
   2. The difference between stack, queue, and other policy-driven RACs.
   3. Understand and be able to use visitors to a RAC.
   4. 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.
   5. Be able to write code using internal factories that enable objects to recursively generate themselves.
      
      
9. Traversals
   1. Graphs vs. Trees
   2. Multiple connectedness issues--be able to explain them and understand how one gets around them.
   3. Traversals without using a RAC -- be able to code this.
   4. Traversals using a RAC -- be able to understand this.
      
      
10. Mutation
    1. The difference between set! and set-[struct]-[field]!
    2. The pitfalls and perils of mutation -- when to/not to use them.
    3. How does set! on a locally enclosed placeholder alleviate some of the problems of set! on globally accessible placeholders?
    4. 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).
       
       
11. Generative Recursion
    1. For traversals -- know the basic algorithms for depth-first and breadth-first traversals.
    2. Have a complete understanding of how Missionaries and Cannibals works
       1. be sure to obtain properly working code (preferably from someone you trust, like a labbie).
       2. be able to code it completely on your own.
    3. Generating the objects vs generating the proccess -- be able to compare and contrast, as well as code.
    4. Divide-and-conquer algorithms, e.g. template-based sorting.
    5. Know how to solve Missionaries-and-Cannibals!  
       1. Saving a state as "seen".
       2. Generating the set of all possible next states
       3. Filtering (using the higher order function filter!) to retain only the viable next states.
       4. Filtering the seen states from the viable state.
       5. Accumulating a path to a state along the way.
       6. Detecting the ending condition.
       7. Know how to use other higher order functions such as map, apply append, foldr/l, ormap, andmap, etc.
          
          
12. Listeners/Observers [omitted from this year's exam]
    1. relationship to event-driven systems.
    2. using lambdas and mutation as a way of communicating between different parts of a system.
       
       
13. 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.

Last Revised Wednesday, 24-Nov-2004 09:58:15 CST

©2004 Stephen Wong and Dung Nguyen