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.
FINAL EXAM INFORMATION:
Our final exam
will
take place on Thursday, May 8 from 11:30 AM - 2:30 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, May 7 from 3 - 5 PM in Sage 3510.
Here are some
practice
problems.
Dr. Schmidt will
also have office hours on Monday, May 5 from 3 - 4 PM and on Wednesday,
May 7 from 11AM - 12 PM.
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)
Introduction to Graphs (9.1)
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)
Quiz Dates: The following are the dates of all of
the short quizzes we will take during recitation:
Quiz #1: Friday, January 25 or Tuesday, January 29
Quiz #2: Friday, February 1 or Tuesday, February
5
Quiz #3: Friday, February 8 or Tuesday, February 12
Quiz #4: Friday, February 29 or Tuesday, March 4
Quiz #5: Friday, March 7 or Tuesday, March 18
Quiz #6: Friday, March 21 or Tuesday, March 25
Quiz #7: Friday, April 11 or Tuesday, April 15
Quiz #8: Friday, April 18 or Tuesday, April 22
Office Hours
Information :
Dave Schmidt's Office Hours (in Amos
Eaton 408): Wednesday and Thursday, 10 - 11:30 AM
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.