﻿ Discrete Mathematics Course

# Discrete Mathematics

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

Unlike you [Bill Gates],
---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.

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.

## 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.

• The first examination will be held on March 30, 2023.
1. The examination will cover Section 1.1-Section 7.2 ("The Rules of Sum and Product"~"Zero-One Matrices and Directed Graphs") and the relevant lecture notes (pp. 1--362).
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.
4. To avoid congestion, you should take the test in the room based on your student ID as follows:
• R107: B06902***.
• R101: the rest.
• The second examination will be held on May 4, 2023.
1. The examination will cover Section 7.2-Section 10.5 ("Zero-One Matrices and Directed Graphs"~"A Special Kind of Nonlinear Recurrence Relations") and the relevant lecture notes (pp. 363--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.
4. To avoid congestion, you should take the test in the room based on your student ID as follows:
• R107: B06902***.
• R101: the rest.
• The third examination will be held on June 8, 2023.
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"), Sections 17.1-17.2 ("Polynomial Rings"~"Irreducible Polynomials: Finite Fields"), and the relevant lecture notes (pp. 641--1006).
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.