CSE 143 Final Exam Topics, 5/31/06
The final exam is scheduled from 2:30-4:20 on Tuesday, June 6, in our regular
lecture room. As with the midterm, the exam is open book and
open notes. It will consist of a mix of questions: some short answer,
some longer; some involving reading code and analyzing what it does, some involving
writing code, maybe some asking for written answers to questions that don't
have any specific coding involved. You are responsible for topics covered in
lecture, sections, and on the homework assignments.
The list of topics below is a reminder of
what we have covered since the midterm, but might not exhaustively list everything. You
remain responsible for the course material covered during the first part of
the quarter and summarized on the midterm topic list.
When studying for the exam, spend time working problems. While it is important
to review notes and other materials, there is a difference between being
able to recognize something or follow an existing solution or sample problem,
and being able to solve new problems. You need practice working problems -
just "going
over" the
notes is likely not to be enough. Also, don't spend effort memorizing large
chunks of code.
It is unlikely that you would be asked
to reproduce code that you've seen, particularly on an open book test. Instead,
you will be asked to solve problems related to ones you've done before or seen
as examples. You should know how to analyze a problem, understand how to organize
a solution (using diagrams can help), and then work out the code from those
ideas. You should know algorithms at the level of being
able to diagram a solution - if you can do that, you should be able to work
out coding details as needed.
You also should not spend time memorizing reference material.
You should know the common operations and be able to use them, but brief reference
material will be provided on the exam where needed so you won't have to remember,
for example, the order of the parameters or exact names of all the methods
in a large class.
Topics
- Recursion: Be able to write and hand-simulate recursive algorithms, in
particular on recursive data structures, and for recursive backtracking problems
like 8-Queens and the anagram puzzles
- Preprocessing: understand the reasons for precomputing information
(like the reduced dictionaries in the anagram program) vs recomputing information
wherever needed, and the tradeoffs (implementation complexity vs speed)
- Iterators and the for-each loop: you should know what an iterator is and
how to use it. You do not need to know the syntax of the for-each loop, but
you are free to use it in your code whenever you find it helpful
- Binary trees and binary search trees
- Know the terminology: root, leaves, edges, subtrees, parent and child
nodes. etc.
- Know the standard tree traversals: preorder, inorder, postorder
- Be able to write and understand recursive algorithms that process trees
(e.g., process the node and recursively process the subtrees); what is
(are) the base case(s)? what are the recursive cases?
- Know what a binary search tree is and how it differs from an arbitrary
binary tree; be able to construct proper binary search trees given a
list of data and the
order
in which
it is
inserted;
be
able to
process
BSTs
efficiently
(e.g., search or insert by looking only at the necessary nodes in the
tree); as well as knowing recursive algorithms, be able to use iterative
algorithms (loops) on a BST if they make sense (e.g., search, find
the min/max)
- Understand the expected performance of BST algorithms (O(log n)) and
the worst case time (O(n)); know what a balanced tree is and
why
it is needed to get the expected performance (but you are not expected
to know how to ensure that a tree is kept balanced as nodes are inserted
and deleted)
- Hashing: know the basic idea behind a hash table (e.g., what is a hash
function?) and why it yields O(1) expected time for operations like insert
and
search; understand the basic tradeoffs between a hashmap and a treemap -
when would you use one instead of the other?
- Classes, objects, and inheritance
- Know the basic ideas behind inheritance (mostly review from the midterm)
- Be able to understand and write code that uses super in constructors
and in ordinary methods
- Understand how to define equals() and compareTo() in classes
- Sorting: know the material from the midterm: O(n2)
sorts like insertion sort; mergesort, which is O(n log n); know the basic
ideas behind quicksort
and
its expected and worst-case performance (O(n log n) vs O(n2))
and what needs to be true to get good performance
- Plus everything from the midterm topic list...