CSE 222 Final Review

The following is a list of the topics you should know and the tasks you should be able to perform for the final exam.

1. All material listed on the Midterm Review sheets.
2. In addition to the components listed for the midterm, be able to use the following software components:
• Array / Static_Array
• Binary_Tree
• List
3. You should be able to write a layered implementation of a kernel component. (For example, you might be asked to layer an implementation of Sequence_Kernel on an implementation of List_Kernel.)
4. You should understand the purpose of, desirable properties of, and be able to implement, a hash function. You should understand how hashing can be used to speed up program execution in implementing components that involve searching (Partial_Map and Set).
5. You should understand the purpose of, properties of, and rationale for using binary search trees, and should be able to manipulate BSTs as in the homework and lab assignments. You should understand how BSTs can be used to speed up program execution in implementing components that involve searching (Partial_Map and Set).
6. You should understand and be able to use the Pointer_C component.
• Declaring and using pointers
• Pointer problems: aliasing, dangling references, and memory (storage) leaks
• Using records and pointers to implement a component "at the lowest level"
7. You should be able to develop a rigorous specification-based test plan.
8. In quarters where loop invariants are covered in class, you should know how to perform the following tasks related to loop invariants.
• Determine the final effect of a loop (i.e., trace the loop) using only the loop invariant (i.e., not looking at the loop body).
• Given a loop body and a loop invariant, determine whether the loop body satisfies the loop invariant.