CS211 About the Final:
Thursday, 20 December 2001, 9-11:30am, in Kimball B11.
Anyone who is planning on taking it but has
a conflict should contact Gries immediately
Please indicate on the submission
webpage
whether or not you will take the final
(Note: the webpage has not yet been modified
to allow you to do this)
Early in the week of 10 November, we will post some review sessions
for the final, each of which will be focused on a particular topic.
The final is cumulative; it covers what we have done in the whole course.
Below, we discuss what will be covered.
-
For the material that prelim 1 covered, look
here.
-
For the material that prelim 2 covered, look
here. Here are solutions to problems.
-
Mathematical induction. There will be a question on induction, as covered
in a recitation. You will
be given a theorem to prove, much along the lines of those in the handout
for that recitation. It may be some theorem about integers, binary trees,
linked lists, or a recursive function that we will give you.
-
Binary trees and binary search trees. See chapter 19 of Weiss.
From 19.1. You are responsible for the definition of binary search tree.
You should be able to write a method for finding a value in a binary search
tree, for finding the minimum or maxium value in a binary search tree,
and for adding a value to a binary search tree. We won't ask you to write
an algorithm to remove an element from a binary search tree.
From 19.2. The idea in this section is to create a subclass of a binary
search tree; an instance of the subclass has a field size, which contains
the number of nodes in the tree whose root is that instance. This is useful
in finding the kth smallest value. You are responsible for understanding
this concept. You should be able to write a method to add a value to such
a binary-search-tree-with-size.
-
Graphs. See Weiss, chapter 14. You should know the definition of a graph,
path, and path length. Also, the two major ways of representing a
graph (the adjacency matrix and the adjacency list). You should be able
to write a (recursive) method that traverses a graph, processing each node
(vertex) of it once. [This is what you did in the assignment that constructed
the links on a set of reachable web pages!]. You do not have to know the
shortest path algorithms that are described in Weiss.