Material: The exam will emphasize all concepts taught
in this course. There will be 15 questions that you can
answer in two hours. Approximately six questions will be from
material covered by Exam #1 (review
at this link) and Exam #2
(review at this link). The remainder of the material
is summarized below.
Note: It may be necessary to ask a question that
requires you to use concepts that we covered early in the
course. For example, you might be asked to prove a property
of a relation on one or two sets by mathematical induction.
This is part of the concept of a comprehensive exam, so plan
your study effort accordingly.
- Read and study Rosen Chapters 1 and 2, Sections
3.1-3.5, 4.1-4.4, 5.1-5.2, 6.1-6.5, 7.1-7.5, and 8.1-8.4. No
material from Chapters 9 or 10 will be included. It is
recommended that you work again through the assigned homework
problems, as well as all previous exam problems that you
missed. You might also want to work through the supplementary
exercises at the end of each chapter.
- Topical areas of Final Exam include:
- Topic 1 -- Relations:
- Know each relational property (reflexive,
transitive, etc.) and how they apply to closure
of relations and n-ary relations. Be able to
prove closure of given relations, and
relationships between closure properties.
- Know what an equivalence relation is, and how to
prove that a given relation is an equivalence
relation.
- Pay special attention to matrix representations of
relations, composition of relations, and the
derivation of relational properties or closure from
matrix representations of relations.
- Topic 2 -- Graphs
- Know the different types of graphs and be able to
draw or sketch instances of each type.
- Be able to determine the number of paths in a
given graph (and know how to find Euler
or Hamilton paths, as well as Euler circuits) from
a graph or its matrix representation.
- Know what graph connectivity is, how to express
it, and how to determine (a) the connected components
of a graph, as well as (b) cut edges, etc.
- Know what a shortest path is and what it means
in the context of a graph. However, you will not
be held responsible for the algorithms in the
book for computing a shortest path. These will be
taught in detail in Data Structures and Algorithms
class.
- Topic 3 -- Trees
- Know what distinguishes a tree from other types
of graphs, and how this property gives a tree
its distinctive shape. Be able to recognize
drawings of trees given drawings of objects
that are either trees or non-tree graphs.
- Know the different kinds of tree traversal,
and how they cause the vertices of a tree to
be visited in differing order. Given a sketch
of a tree and a traversal method, be able to
list the vertices of the tree in the order
which the method causes them to be visited.
- Know what a binary (or m-ary) search tree (BST) is,
how many operations are required to find an
object in a BST with n leaves, and why this
number of operations is required. Be able to
construct a BST for a finite sequence of integers.
- Know what a spanning tree is, and what is the
difference between a spanning tree and a minimum
spanning tree. You might also be asked to find
a minimum spanning tree given a simple graph
that has a few vertices. However, you will not
be required to know algorithms for finding the
minimum spanning tree, which will be covered in detail
in the Data Structures and Algorithms class.