New exam dates:
Final: June 20, Friday, 1:30-3:30 pm, 2008.
(Another 霹靂博: 3HY, EC115)
General TAs: 呂禮君, 黃帥維, 洪培翔, EC 131, 程式語言與系統實驗室, phone: 56649.
Discrete mathematics is the foundation of computer science. You are advised to study this course carefully so that you will be able to handle other, more advanced courses in the future. In this course, we will study the following subjects:
For the textbook, we will discuss the following sections:
Chap1: Logic and Proofs
1. Proposition Logic
2. Proposition Equivalences
3. Predicates and Quantifiers
4. Nested Quantifiers
5. Rules of Inference
6. Introduction to Proofs
7. Proof Methods and Strategy
Chap 2: Sets, Functions, Sequences, and Sums
1. Sets
2. Set Operations
3. Functions
4. Sequences and Summations
Chap 3: Algorithms and the Integers
4. The Integers and Division
5. Primes and Greatest Common Divisors
6. Integers and Algorithms
7. Applications of Number Theory
Chap 4: Induction and Recursion
1. Mathematical Induction
2. Strong Induction and Well-Ordering
3. Recursive Definitions and Structural Induction
4. Recursive Algorithms
Chap 5: Counting
1. The Basics of Counting
2. The Pigeonhole Principle
3. Permutations and Combinations
4. Binomial Coefficients
5. Generalized Permutations and Combinations
6. Generating Permutations and Combinations
Chap 7: Advanced Counting Techniques
1. Recurrence Relations
2. Solving Linear Recurrence Relations
3. Divide-and-Conquer Algorithms and Recurrence Relations
4. Generating Functions
5. Inclusion-Exclusion
6. Applications of Inclusion-Exclusion
Chap 8: Relations
1. Relations and Their Properties
2. n-ary Relations and Their Applications
3. Representing Relations
4. Closures of Relations
5. Equivalence Relations
6. Partial Orderings
Chap 9 Graphs
1. Graphs and Graph Models
2. Graph Terminology and Special Types of Graphs
3. Representing Graphs and Graph Isomorphism
4. Connectivity
5. Euler and Hamilton Paths
6. Shortest-Path Problems
7. Planar Graphs (optional)
8. Graph Coloring (optional)
Chap 10: Trees
1. Introduction to Trees
2. Applications of Trees
3. Tree Traversal
4. Spanning Trees
5. Minimum Spanning Trees
Our objective in the source is to train you to look at problems precisely, to grasp the essence of problems at hand, and to learn techniques to solve them. Although the definitions, lemmas, theorems, corollaries, etc., are also of vital importance to your study of computer science, we really hope that you will gain the ability of solving new problems independently from this course. I do not want you just to memorize the solutions of problems because that's too simple a task for anybody. Rather, I want you to understand how the problems are solved because that is the most interesting part of the course.
Furthermore, we also wish to make the students comfortable with writing rigorous proofs. Though proof techniques are important, it is equally important for students to learn the skill of writing rigorous proofs at this stage. The students are asked to write answers in homework and in exams very carefully.
Kenneth H. Rosen, Discrete Mathematics and Its Applications, 6th ed., McGraw-Hill Inc. ( table of contents of the textbook).
(recommended only) C.L. Liu, Elements of Discrete Mathematics, 2nd ed., McGraw-Hall, 1985. ( table of contents of the textbook).
(recommended only) Donald M. Davis, The Nature and Power of Mathematics, Dover, 2004, Chapter 3 Number Theory.
(recommended only) G. Polya, How to Solve It, 2nd ed., Princeton U. Press, 1945 (reference only).
IT IS RECOMMENDED THAT YOU USE CHINESE AND ENGLISH TO ANSWER QUESTIONS IN THE EXAMS. DO NOT USE ANY OTHER LANGUAGES.
1st term: April18, Tuesday, 8-10, 2008.
2nd: May 16, Friday, 1:30-3:30 pm, 2008.
Final: June 20, Friday, 1:30-3:30 pm, 2008.