Course Objectives:

Discrete mathematics is the theoretical foundation of computer science and technology. The teaching objectives focus on two aspects: 1) It lays the necessary mathematical foundations for the subsequent courses, such as data structure, compiler principle, operating system, database theory, and artificial intelligence; 2) This course helps students to develop and improve skills of abstract thinking and logical reasoning, and improve the ability to analyze and solve problems independently.

Course Requirements:

After successfully completing this course, students will be able to:

1. Understand fundamental concepts, basic terminology, and basic theorems of discrete probability, counting techniques, relations, graph theory and Boolean algebra and modeling computation. 2. Develop and gain practical skills of abstract thinking and logical reasoning, and use the knowledge to analyze and solve practical problems.

Course Contents:

Chapter 8 Advanced Counting Techniques

Applications of Recurrence Relations; Solving Linear Recurrence Relations

Divide-and-Conquer Algorithms and Recurrence Relations; Generating Functions

Inclusion–Exclusion; Applications of Inclusion–Exclusion

Chapter 9 Relations

Relations and Their Properties; n-ary Relations and Their Applications

Representing Relations; Closures of Relations

Equivalence Relations; Partial Orderings

Chapter 10 Graphs

Graphs and Graph Models

Graph Terminology and Special Types of Graphs

Representing Graphs and Graph Isomorphism

Connectivity; Euler and Hamilton Paths

Shortest-Path Problems; Planar Graphs; Graph Coloring

Chapter 11 Trees

Introduction to Trees; Applications of Trees

Tree Traversal;Spanning Trees

Minimum Spanning Trees

Chapter 12 Boolean Algebra

Boolean Functions; Representing Boolean Functions

Logic Gates; Minimization of Circuits

Chapter 13 Modeling Computation

Languages and Grammars

Finite-State Machines with Output

Finite-State Machines with No Output

Language Recognition

Turing Machines

Credits: 2