Comp210 Exam 2Need-To-Knows
Fall 2002
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:
- Family and Binary Trees (same thing)
- Data definition
- Template
- UML diagram
- Be versed in writing simple programs on such trees:
- Count all elements
- Sum/multiply all elements
- Find largest/smallest/particular element
- etc. etc.
- Composite pattern/Whole-part hierarchies
- be able to describe what they are and what they are used for.
- Be able to draw their UML diagrams
- Be able to specify a data definition for such a system.
- Generalized lists
- UML diagrams: Know the basic symbols for
- a structure (class)
- a composition ("has a") line
- an inheritance ("is a") line
- labels for composition lines to indicate the field they to which they
refer.
- labels for composition lines to indicate the number of elements being
referenced (e.g. 1, 1..*, 0..*)
- Functions of two non-trivial arguments
- Be able to do a Process Flow Analysis based solely on the function contract
- to create a general (worst-case) template for the function
- to be able to write the actual function based on that general template.
- Be able to create the multiway cond implementation as well.
- Descendent trees (trees with arbitrary numbers of children)
- Data definition
- UML diagram
- Be able to write simple functions on them, the same as with family/binary
trees above.
- Mutual Recursion
- Template from process flow
- Processing generalized whole-part hierarchies
- Locals
- Syntax
- Using locals to provide encapsulation
- Using locals to reduce redundant calculations
- Scoping rules
- Closures
- Using closures to reduce the number of parameters passed.
- Using closures to retain information -- curried functions.
- Lambdas
- Syntax
- Curried functions
- Returning a lambda from a function
- Higher order functions
- functions that take functions as inputs
- functions that return functions
- map, foldr, foldl -- what processes do they represent?
- Visitor Design Pattern
- Data definition for the Visitor structure
- Be able to write the code for execute.
- 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?
- Be able to write simple functions using visitors.
- Be able to write higher order functions using visitors.
- The built-in function apply
will 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.
- 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.