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

This document is constantly being updated--recheck it often!

In no particular order and NOT all inclusive and some topics may be mentioned in several places as they appear under different contexts:

1. MAKE SURE YOU CAN DO ALL THE PROBLEMS FROM EXAM 1 AND LAST YEAR'S EXAM 2!!
2. Family and Binary Trees (same thing)
   1. Data definition
   2. Template
   3. UML diagram
   4. Be versed in writing simple programs on such trees:
      1. Count all elements
      2. Sum/multiply all elements
      3. Find largest/smallest/particular element
      4. etc. etc.
3. Composite pattern/Whole-part hierarchies
   1. be able to describe what they are and what they are used for.
   2. Be able to draw their UML diagrams
   3. Be able to specify a data definition for such a system.
   4. Generalized lists
4. UML diagrams: Know the basic symbols for
   1. a structure (class)
   2. a composition ("has a") line
   3. an inheritance ("is a") line
   4. labels for composition lines to indicate the field they to which they refer.
   5. labels for composition lines to indicate the number of elements being referenced (e.g. 1, 1..*, 0..*)
5. Functions of two non-trivial arguments
   1. Be able to do a Process Flow Analysis based solely on the function contract
      1. to create a general (worst-case) template for the function
      2. to be able to write the actual function based on that general template.
   2. Be able to create the multiway cond implementation as well.
6. Descendent trees (trees with arbitrary numbers of children)
   1. Data definition
   2. UML diagram
   3. Be able to write simple functions on them, the same as with family/binary trees above.
7. Mutual Recursion
   1. Template from process flow
   2. Processing generalized whole-part hierarchies
8. Locals
   1. Syntax
   2. Using locals to provide encapsulation
   3. Using locals to reduce redundant calculations
   4. Scoping rules
9. Closures
   1. Using closures to reduce the number of parameters passed.
   2. Using closures to retain information -- curried functions.
10. Lambdas
    1. Syntax
    2. Curried functions
    3. Returning a lambda from a function
11. Higher order functions
    1. functions that take functions as inputs
    2. functions that return functions
    3. map, foldr, foldl -- what processes do they represent?
12. Visitor Design Pattern
    1. Data definition for the Visitor structure
    2. Be able to write the code for execute.
    3. Be able to understand visitors in more than just the context of lists -- that is what would visitors to other abstract class + concrete subclass data structures look like?
    4. Be able to write simple functions using visitors.
    5. Be able to write higher order functions using visitors.
13. The built-in function apply may used in the exam. apply is a generalized version of the op function from Lecture 19. .apply takes a function and a list of arguments and "applies" the function onto those arguments. That is, it executes the function with those arguments. For example:
    
    (apply + (list 1 2 3 4 5)) is the same as ( + 1 2 3 4 5)
    (apply sqr (list 5)) is the same as (sqr 5)
    (apply string-append (list "How now " "brown cow!")) is the same as (string-append "How now " "brown cow!")
    
    apply is thus a function that abstracts the application of a function.
    
    Optionally, apply can take individual arguments before the list of arguments:
    (apply + 1 2 (list3 4 5)) is the same as ( + 1 2 3 4 5)
    (apply string-append "These are fruit: " (list "apple " "orange " "pear ")) is the same as (string-append "These are fruit:" "apple " "orange " "pear "))
    This syntax is useful if not every argument is available in a list.
    
    
14. More coming....

Study advice: Don't try to learn all the above topics as separate entities. Instead, remember that except for local and lambda, 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. encapsulation, base/inductive case, design template, etc.

Last Revised Tuesday, 24-Aug-2004 13:49:13 CDT

©2004 Stephen Wong and Dung Nguyen