﻿ Discrete Mathematics Course

# Discrete Mathematics

Time: 14:20 ~ 15:10 Thursday (Spring Semester)
Location: Room 111 of the CSIE Building

Unlike you [Bill Gates],
I had actually tried to do the reading.
---Steve Ballmer (1999)

In after years I have deeply regretted that
I did not proceed far enough at least to understand
something of the great leading principles of mathematics.
---Charles Darwin (1809-1882)

At best he could never have been a mathematician;
at worst he would never have cared to be one;
but he needed to read mathematics,
like any other universal language,
and he never reached the alphabet.
---Henry Adams (1838-1918)

To the students,
 This course is on discrete mathematics. It covers combinatorics, boolean logic, computation theory, analysis of algorithms, probability, algebra, number theory, graph theory, set theory, and many other fields. Parts of the book should have been covered in high school and will be skipped or only briefly reviewed. I have in mind basic combinatorics, logic, and basic set theory. It is never an easy job to teach discrete mathematics, because it touches so many areas of learning. Furthermore, unlike algebra, discrete mathematics does not seem to have a structure that can be said to form its foundation. But, for precisely the same reason, the subject is fascinating. Please note that this course will be taught in English.

## Notes [ 2001, 2002, 2003, 2004, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2022, 2023, 2024 ]

1. 2024.02.22
2. 2024.02.29
3. 2024.03.07
4. 2024.03.14
5. 2024.03.21
6. 2024.03.28 mid-term exam
7. 2024.04.04 holiday
8. 2024.04.11
9. 2024.04.18
10. 2024.04.25
11. 2024.05.02 mid-term exam
12. 2024.05.09
13. 2024.05.16
14. 2024.05.23
15. 2024.05.30
16. 2024.06.06 final exam

## Book sections to be covered (based on the 5th ed.)

• Chapter 1 ("Fundamental Principles of Counting"): all sections.
• Chapter 2 ("Fundamentals of Logic"): 2.1-2.3.
• Chapter 3 ("Set Theory"): 3.1-3.3.
• Chapter 4 ("Properties of Integers: Mathematical Induction"): all sections.
• Chapter 5 ("Relations and Functions"): 5.1-5.6.
• Chapter 7 ("Relations: The Second Time Around"): 7.1-7.4.
• Chapter 8 ("The Principle of Inclusion and Exclusion"): 8.1-8.3.
• Interesting odd-numbered exercises (5th ed.): 8.1.17, 8.1.21, 8.1.23, 8.2.5, 8.3.1, 8.3.5, 8.3.7, 8.3.13, 8.3.15, 8.6.5, 8.6.11, 8.6.17.
• Chapter 9 ("Generating Functions"): all sections.
• Interesting odd-numbered exercises (5th ed.): 9.1.1, 9.1.3, 9.1.5, 9.2.1, 9.2.3, 9.2.17, 9.2.21, 9.2.33. 9.3.1, 9.3.3, 9.3.5, 9.5.1, 9.5.5, 9.6.1, 9.6.5, 9.6.9, 9.6.13.
• Chapter 10 ("Recurrence Relations"): 10.1-10.5.
• Interesting odd-numbered exercises (5th ed.): 10.1.3, 10.2.1, 10.2.3, 10.2.7, 10.2.9, 10.2.15, 10.2.23, 10.2.27, 10.2.31, 10.2.33.
• Chapter 11 ("An Introduction to Graph Theory"): all sections.
• Interesting odd-numbered exercises (5th ed.): 11.1.3, 11.1.9, 11.1.13, 11.1.15, 11.2.1, 11.2.5, 11.2.9, 11.2.13, 11.2.17, 11.3.1, 11.3.11, 11.3.21, 11.3.25, 11.3.27, 11.3.31, 11.4.3, 11.4.5, 11.4.7, 11.4.9, 11.4.17, 11.4.19, 11,4,21, 11.5.7, 11.5.9, 11.5.13, 11.5.19, 11.6.7, 11.6.11b, 11.7.1, 11.7.7, 11.7.15.
• Chapter 12 ("Trees"): 12.1-12.2.
• Interesting odd-numbered exercises (5th ed.): 12.1.3, 12.1.5, 12.1.7, 12.1.9.
• Chapter 13 ("Optimization and Matching"): 13.3-13.4.
• Chapter 14 ("Rings and Modular Arithmetic"): 14.1-14.3.
• Interesting odd-numbered exercises (5th ed.): 14.1.11, 14.2.1, 14.2.3, 14.2.5, 14.2.7, 14.2.13, 14.2.15, 14.2.17, 14.2.21, 14.3.13, 14.3.17, 14.3.19.
• Chapter 16 ("Groups, Coding Theory, and Polya's Method of Enumeration"): 16.1-16.4, 16.10.
• Interesting odd-numbered exercises (5th ed.): 16.1.3, 16.1.9, 16.1.15, 16.1.17, 16.2.1, 16.2.11, 16.3.5, 16.3.9, 16.3.13.
• Chapter 17 ("Finite Fields and Combinatorial Designs"): 17.1-17.2.
• Interesting odd-numbered exercises (5th ed.): 17.1.5, 17.1.9, 17.1.17, 17.2.1, 17.2.3, 17.2.17, 17.2.25.

## Examinations and grading

• The first examination will be held at R103 on March 28, 2024.
1. The examination will cover Section 1.1-Section 7.4 ("The Rules of Sum and Product"~"Equivalence Relations and Partitions") and the relevant lecture notes (pp. 1--404).
2. The use of electromagnetic devices to transmit or receive signals during the examination will guarantee eviction from the classroom.
3. Bring your student photo ID for possible spot checks.
• The second examination will be held at R103 on May 2, 2024.
1. The examination will cover Section 8.1-Section 10.5 ("The Principle of Inclusion and Exclusion"~"A Special Kind of Nonlinear Recurrence Relation") and the relevant lecture notes (pp. 405--640).
2. The use of electromagnetic devices to transmit or receive signals during the examination will guarantee eviction from the classroom.
3. Bring your student photo ID for possible spot checks.
• The third examination will be held at R103 on June 6, 2024.
1. The examination will cover Sections 11.1-11.6 ("Definitions and Examples"~"Graph Coloring and Chromatic Polynomials"), Sections 12.1-12.2 ("Definitions, Properties, and Examples"~"Rooted Trees"), Sections 14.1-14.4 ("The Ring Structure: Definitions and Examples"~"Ring Homomorphisms and Isomorphisms"), Sections 16.1-16.4 ("Definitions, Examples, and Elementary Properties"~"The RSA Cryptosystem"), Section 16.10 ("Counting and Equivalence: Burnside's Theorem"), and the relevant lecture notes (pp. 641--953).
2. The use of electromagnetic devices to transmit or receive signals during the examination will guarantee eviction from the classroom.
3. Bring your student photo ID for possible spot checks.
• There will be no makeup examinations.