These lists should be considered
a partial lists at best! Check back often to see if new items
are added. You are responsible for all topics covered in class, labs
and assignments, even if they do not appear here.
Midterm Exam: Need to Know
Linear structures
Know how to use both the immutable
IList and the mutable
LRStruct frameworks.
Be able to write both forward and reverse
accumulation algorithms.
Be able to write higher order functions (algortithms/visitors)
such as FoldL and
FordR.
Be able to write the lambda functions that
work with FoldL and/or
FordR to do things like add the
elements, print the elements, reverse the list, append the list,
etc.
Lazy evaluation
Understand and be able to program the decorator
design pattern.
Be able to write an
ALazyEval to create simple infinite lists, e.g. arithmetic
sequences, Fibonnacci sequence, etc.
Trees
Be able to use and write algorithms for
BiTrees.
Be able to write lambda functions for both
pre/in/post-order traversals and breadth traversals.
General design
MVC design pattern
Decoupling of parts of a system by breaking into
autonomous pieces
Utilizing abstract behaviors
Commands
Strategies
Factories
Lambdas
General hints
When a data structure is immutable (e.g. IList), share parts that are the same. Assume you have a visitor that returns a list with the Integer in the first incremented by one. You should let the lists (3 (2 (1 empty))) and (4 (2 (1 empty))) share the rest (2 (1 empty)).
When a data structure is mutable (e.g. LRStruct or BiTree), clone the rest! When you implement the visitor above, the LRStructs two (3 (2 (1 empty))) and (4 (2 (1 empty))) should not share the rest (2 (1 empty))!
The final exam will be available for download on OWL-Space on December 10. It will appear in the Assignments list as "Exam 2", with an attachment called exam2f08.zip. That zip file contains both the exam (in Microsoft Word doc format and pdf format) and the supporting code.
If you have any problems accessing the exam, please let us know!
Instructions for the exam:
This is an open-notes, open-book, open-computer, open-Internet, take-home exam.
You have 5 hours to work on this exam.
You may also take one contiguous 15-minute break during the exam, and that time will not count towards the 5 hours.
Except for the 15-minute break, this exam has to be taken in one sitting.
Please make sure you have all 9 pages of this exam.
This exam is comprehensive.
You will not be penalized on trivial syntax errors, such as a missing parenthesis. Multiple errors or errors that lead to ambiguous code will have points deducted, however.
In all of the questions, feel free to write additional helper methods to get the job done.
The emphasis is on correctness of the code, not efficiency or on simply generating the right result.
You are free to use any code that was given to you in the lectures and labs.
Code should be generic whenever possible.
When you are done, create a zip file of all your source code and this edited exam, and submit it on OWL-Space by the end of the exam period (Wednesday, December 17, 2008, 11:59 PM).
Do not discuss this exam with anyone other than the instructors or the teaching assistant until after the exam period is over.