Time and Place

The final exam will take place on Thursday Dec 18, 2002, 11 - 1 pm in room G205 (the usual classroom).

General Information

Please do not arrive late since the class room may needed for the next exam. If you miss this exam, a makeup (if given) will be harder. Please remember that the college permits an INC grade only for those with passing averages who have missed an exam.

Office Hours

Office Hours as usual: Tuesday and Thursday 2-3:30 pm

The Exam

There may be additions and/or slight changes to this study outline up to December 14. So re-check the web site after the last class!

THERE WILL BE CHOICES ON THE EXAM

Although there are choices, you will definitely have to choose some graph and/or tree problems and combinatorics problems!

Be sure to go over the problems assigned with each chapter; see the Web pages for problem numbers.

Reminder of subject-matter to be covered:

  • Material covered on midterm 1;
  • Proving that relations are equivalence relations or partial orders (i.e., proving that they are reflexive, symmetric or anti-symmetric, and transitive);
  • Algorithm complexity: big O, theta, and omega notations, and counting how many times a loop is executed.
  • Combinatoric problems
  • Proof of the Euclidean algorithm (just learn it!)
  • Sections 6.1-6.2 and 7.1-7.2

    Here are the types of tree and graph problems that may be on the exam:

    1. Recognize a cycle(or circuit) in a graph or give an example of one.

    2. Know what Euler circuits are. Be able to determine if a graph has an Euler circuit; if not, say why not; if so, find an Euler circuit.

    3. Be able to define the components of a tree (root, terminating vertex, interior vertex) and identify the level of a vertex and the height of a tree.

    4. Know the diference between "free" trees (as special types of graphs) and "rooted" trees.

    Here are some possibilities for questions on old material (in addition to the assigned problems):

    A mathematical induction proof (yes again).

    Give examples of relations having some or all of the 3 properties we studied: Be sure you understand equivalence relations and partial orders.

    Counting, Permutations and Combinations: be able to solve problems about orderings of a sequence, both when there are no repetitions in the sequence (ABCDE) or when there are repetitions (MISSISSIPPI); selecting some number of elements out of a set; and picking some number of elements, some of which may be duplicates, out of a jar (alternatively, classifying elements into groups).