# Dave Schmidt's Intro to Discrete Structures Page

Welcome to Intro to Discrete Structures. The purpose of this page is to make certain resources
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.

FINAL EXAM INFORMATION:

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)

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)

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:

Homework Assignments

Tentative Exam Dates

Exam Solutions

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.