Copies of the classnotes are on the internet in PDF format as given below. These notes have not been classroom tested and may contain typographical errors. The notes are based on a section of Discrete Structures (MATH 2710) which I taught spring 2001 (this class is not longer on the books through the ETSU Department of Mathematics and Statistics). This class no longer exists, but the notes are close to what would be used in our current Mathematical Reasoning (MATH 3000) class.

Syllabus for the 2001 class.

1. The Foundations: Logic, Sets, and Functions.

• Section 1.1. Logic. Section 1.1 notes
• Section 1.2. Propositional Equivalences. Section 1.2 notes
• Section 1.3. Predicates and Quantifiers. Section 1.3 notes
• Section 1.4. Sets. Section 1.4 notes
• Section 1.5. Set Operations. Section 1.5 notes
• Section 1.6. Functions. Section 1.6 notes
• Section 1.7. Sequences and Summations. Section 1.7 notes
• Section 1.8. The Growth of Functions. Section 1.8 notes
• Study Guide 1.

Test 1 (1.1-1.8)

2. The Fundamentals: Algorithms, the Integers, and Matrices.

• Section 2.1. Algorithms. Section 2.1 notes
• Section 2.2. Complexity of Algorithms. Section 2.2 notes
• Section 2.3. The Integers and Division. Section 2.3 notes
• Section 2.4. Integers and Algorithms.
• Section 2.5. Applications of Number Theory.
• Section 2.6. Matrices. Section 2.6 notes
• Study Guide 2.

3. Mathematical Reasoning.

• Section 3.1. Methods of Proof. Section 3.1 notes
• Section 3.2. Mathematical Induction. Section 3.2 notes
• Section 3.3. Recursive Definitions. Section 3.3 notes
• Section 3.4. Recursive Algorithms.
• Section 3.5. Program Correctness.
• Study Guide 3.

Test 2 (2.1-2.3, 2.6, 3.1-3.3)

4. Counting.

• Section 4.1. The Basics of Counting. Section 4.1 notes
• Section 4.2. The Pigeonhole Principle. Section 4.2 notes
• Section 4.3. Permutations and Combinations. Section 4.3 notes
• Section 4.4. Discrete Probability. Section 4.4 notes
• Section 4.5. Probability Theory.
• Section 4.6. Generalized Permutations and Combinations.
• Section 4.7. Generating Permutations and Combinations.
• Study Guide 4.

5. Advanced Counting Techniques.

• Section 5.1. Recurrence Relations. Section 5.1 notes
• Section 5.2. Solving Recurrence Relations.
• Section 5.3. Divide-and-Conquer Relations.
• Section 5.4. Generating Functions.
• Section 5.5. Inclusion-Exclusion. Section 5.5 notes
• Section 5.6. Applications of Inclusion-Exclusion.
• Study Guide 5.

Test 3 (4.1-4.4, 5.1, 5.5)

6. Relations.

• Section 6.1. Relations and Their Properties. Section 6.1 notes
• Section 6.2. n-ary Relations and Their Applications.
• Section 6.3. Representing Relations. Section 6.3 notes
• Section 6.4. Closures of Relations.
• Section 6.5. Equivalence Relations. Section 6.5 notes
• Section 6.6. Partial Orderings.
• Study Guide 6.

7. Graphs.

• Section 7.1. Introduction to Graphs. Section 7.1 notes
• Section 7.2. Graph Terminology. Section 7.2 notes
• Section 7.3. Representing Graphs and Graph Isomorphism. Section 7.3 notes
• Section 7.4. Connectivity. Section 7.4 notes
• Section 7.5. Euler and Hamilton Paths. Section 7.5 notes
• Section 7.6. Sortest Path Problems.
• Section 7.7. Planar Graphs.
• Section 7.8. Graph Coloring.
• Study Guide 7.

Test 4 (6.1, 6.3, 6.5, 7.1-7.5)

Additional Chapters:

• Chapter 8. Trees
• Chapter 9. Boolean Algebra
• Chapter 10. Modeling Computation

Return to Bob Gardner's home page