Return to course page  

Mathematics 2513-002 - Discrete Mathematical Structures - Fall 2005
Information about Final Exam

The Final Exam will be in the usual classroom on Wednesday, December 14, 2005, 8:00-10:15 a. m. It will emphasize the material since Exam III, plus selected earlier topics as described below. It will be worth 80 points.

I will start grading the exams immediately and might be able to finish them and post grades late Wednesday. More likely, it will be some time Thursday.

Calculators or other mechanical assistance are not needed and are not to be used. Blank paper will be provided, so all you will need is something to write with.

Unfortunately, the exam is scheduled to start at 8:00 a. m. However, you can work until 10:15, so you should have plenty of time for all the questions without needing to hurry.

The following topics will be covered, although the exam not necessarily limited to these topics. Also, any question that appeared on one of the in-class exams could appear.
  1. The three basic methods of proof: direct argument, proving the contrapositive, and proof by contradiction.
  2. Disproving universally quantified statements by giving a counterexample.
  3. Cantor's method for proving that a set is countable.
  4. Cantor's method for proving that a set is uncountable.
  5. Proof by induction.
  6. The Pigeonhole Principle and its use.
  7. Counting using permutations and combinations. The Product Rule and the Sum Rule.
  8. Pascal's triangle, binomial coefficients (n “choose” k) and the Binomial Theorem.
  9. Counting arguments that involve counting something in two different ways.
  10. Relations, equivalence relations, and equivalence classes.
  11. Congruence modulo m as an equivalence relation, and its equivalence classes.

You should know the definition and meaning of congruence modulo m, of a | b (a “divides” b), the formulas for permutations and combinations, and the statement of the Binomial Theorem.

The following do not appear on this exam: truth tables, tautologies, formal negation of quantified statements, interpretation of quantified statements using “truth sets,”, the “there exists uniquely” quantifier, the book's “rules of inference,” “vacuously” true statements, proving basic properies of set union and intersection, intersections or unions of infinitely many sets, the Archimedean Property of the real numbers, the Triangle Inequality, Rolle's Theorem, inverse functions, the Prime Number Theorem, relatively prime integers, greatest common divisor and least common multiple, the Euclidean algorithm, sequences, strong induction, differentiation or integration, the Well-ordering Principle and the proof of the Basic Induction Theorem.