available and keep you up to date with everything that is going on in the course.

Here
is a link to a paper I wrote that discusses some of the potential
pitfalls
that arise in trying to

solve counting problems. It refers to some of
the same
examples we will discuss in class.

Our final exam
will
take place on Thursday, December 16 from 3 - 6 PM in West Hall
Auditorium.

No books,
notes or
calculators are
allowed. The final exam will contain all of the formulas
included on

the previous three exams.

There will
be a review class conducted by Dr. Schmidt on Wednesday, December 15
from 1:00 - 2:30 PM in Darrin 324.

Here are some
practice
problems. Note that the document has been submitted for scanning,
but the link may

take some time to become active.

Dr. Schmidt will
also have office hours on Thursday, December 16 from 10 - 11 AM.

FORMAT OF THE FINAL EXAM:

The final exam will consist of two parts:

The first part will consist of three problems, all of which you must
solve. These problems will be worth

15 points each, for a total of 45
points.

The second part will consist of four problems. You must choose three of the
four to solve.

You will need to indicate on the front of the exam which problem you do
not want graded.

These problems will be worth 20 points each, for a total of 60 points.

Thus, the final exam is worth 105 points just like all of our other exams.

TOPICS COVERED
ON THE FINAL EXAM:

Below is a list of topics to be
potentially covered on the exam, with
textbook citations. Since we didn't necessarily

discuss every section in its entirety, the class
notes
are the best guide to the exact material covered.

Propositional Logic (1.1)

Propositional Equivalence (1.2)

Quantifiers (1.3, 1.4)

Rules of Inference (1.5)

Methods of Proof (1.6, 1.7)

Basic Set Theory (2.1, 2.2)

Basic Number Theory: Divisibility and division algorithm (3.4)

Prime Numbers: GCD and LCM (3.5)

The Euclidean Algorithm (3.6)

Solving linear congruences (3.7, supplemental material from notes)

Mathematical Induction (4.1, 4.2)

The Basics
of Counting (5.1)

Permutations
and Combinations (5.3)

Binomial
Theorem and Pascal's Triangle (5.4)

Combinations
with Repetition (5.5)

Distinguishable
Permutations (5.5)

Discrete Probability (6.1)

Conditional Probability and Independent Events (6.2)

Fibonacci
Recurrence and Fibonacci Numbers (4.3)

Recurrence Relations (7.1)

Solving
Constant-Coefficient, Homogeneous Recurrences (7.2)

Generating
Functions and Counting Problems (7.4)

Principle of Inclusion/Exclusion (7.5,
7.6)

Graph Terminology: degree, degree sequence, complete graphs, bipartite graphs, subgraphs (9.2)

Graph Isomorphism (9.3)

Connectedness, Paths, Circuits (9.4)

Planarity, Euler's Formula, Kuratowski's Theorem (9.7)

Graph and Map Coloring, Chromatic Number (9.8)

Chromatic Polynomials (not in text)

Course Information:

Course
Policies

Quiz Dates: The following are the dates of all of
the short quizzes we will take during recitation:

Quiz 1: Friday, 9/10 or Tuesday, 9/14

Quiz 2: Friday, 9/17 or Tuesday, 9/21

Quiz 3: Friday, 9/24 or Tuesday, 9/28

Quiz 4: Friday, 10/15 or Tuesday, 10/19

Quiz 5: Friday, 10/22 or Tuesday, 10/26

Quiz 6: Friday, 10/29 or Tuesday, 11/2

Quiz 7: Tuesday, 11/16 or Friday, 11/19

Quiz 8: Tuesday, 11/30 or Friday, 12/3

Office Hours
Information :

Dave Schmidt's Office Hours (in Amos
Eaton 408): Wednesday 11 AM - 12:30 PM and Thursday 11 AM -
12 PM

Recitation
Instructor Office Hours:

Course Resources:

Author's
Website
Contains many resources
designed to help students learn

discrete mathematics from the Rosen text, including guides to writing
proofs

and common mistakes in discrete mathematics, links for tutoring help
and
a

useful bulletin board, as well as companion material identified by Web
icons

printed in the book. The companion material includes links to external
Web

sites, extra examples and additional steps, self-assessment on some key

topics, and interactive demonstrations of important algorithms.