Syllabus
Discrete Mathematics (Spring 2011)
http://www.cs.nctu.edu.tw/~yi/Courses/DiscreteMath/2011SpringDM.htm
Instructor: Dr. Chih-Wei Yi
(易志偉)
Class: Tu 15:40-16:30, F 10:10-12:00 @ EC016
Office Hours: Tu 12:30-13:20, F 12:30-13:20
Office: EC432
Phone: (03)5131346
E-mail: yi@cs.nctu.edu.tw
TA:
Yi-Ta Chuang (莊宜達) Office Hours: @ EC235 E-mail: izeki Phone: x56680 |
TA:
Joseph Cheng (鄭淵舟) Office Hours: @ EC235 E-mail: minibarque@hotmail.com Phone: x56680 |
TA:
Benny Lu (呂孝恆) E-mail: bennylu.cs98g@nctu.edu.tw Phone: x56680 |
TA:
Zong-Long Chen (陳宗隆) Office Hours: @ EC235 E-mail: chenzolon@gmail.com Phone: x56680 |
TA:
Frank Nian (粘家盛) E-mail: frank750526@hotmail.com Phone: x56680 |
*Important Note: All items on this syllabus are subject to change. Any in-class announcement, verbal or written, is considered official addendum to this syllabus.
Textbooks:
Kenneth H. Rosen, Discrete Mathematics and Its Applications, 6th ed., McGraw-Hill Inc.
Other references:
C. L. Liu, Elements of Discrete Mathematics, 2nd ed., McGraw-Hill Inc.
Ralph P. Grimaldi, Discrete and Combinatorial Mathematics, 5th ed..
Pre-requisite:
To demonstrate to students how mathematics can be applied to solve nontrivial real-life problems
To gain more experience with mathematical thinking, arguments and proof techniques, which are essential in reasoning about computation
To learn about a number of different discrete structures (e.g., sets, relations, graphs, trees, etc.) that provide the mathematical formalizations for many computational problems
To hope that students will not only learn some powerful mathematical tools but also develop their ability to perceive, to formulate, and to solve mathematical problems
To provide a gateway to more advanced courses in any computer science courses, including data structures, algorithm, database automata theory, computer security, etc.
Course Outline:
Chap1: Logic and Proofs
- Proposition Logic
- Proposition Equivalences
- Predicates and Quantifiers
- Nested Quantifiers
- Rules of Inference
- Introduction to Proofs
- Proof Methods and Strategy
Chap 2: Sets, Functions, Sequences, and Sums
- Sets
- Set Operations
- Functions
- Sequences and Summations
Chap 3: Algorithms and the Integers
- The Integers and Division
- Primes and Greatest Common Divisors
- Integers and Algorithms
- Applications of Number Theory
Chap 4: Induction and Recursion
- Mathematical Induction
- Strong Induction and Well-Ordering
- Recursive Definitions and Structural Induction
- Recursive Algorithms
Chap 5: Counting
- The Basics of Counting
- The Pigeonhole Principle
- Permutations and Combinations
- Binomial Coefficients
- Generalized Permutations and Combinations
- Generating Permutations and Combinations
Chap 7: Advanced Counting Techniques
- Recurrence Relations
- Solving Linear Recurrence Relations
- Divide-and-Conquer Algorithms and Recurrence Relations
- Generating Functions
- Inclusion-Exclusion
- Applications of Inclusion-Exclusion
Chap 8: Relations
- Relations and Their Properties
- n-ary Relations and Their Applications
- Representing Relations
- Closures of Relations
- Equivalence Relations
- Partial Orderings
Chap 9 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 (optional)
- Graph Coloring (optional)
Chap 10: Trees
- Introduction to Trees
- Applications of Trees
- Tree Traversal
- Spanning Trees
- Minimum Spanning Trees
Grading Policy:
There will be 8 1-hour exams in this semester. (8*12.5%)
Course Log: (Under Construction)
Week
Date
Topics
Slides
1 Feb 22 (Tu) Course Introduction Feb 25 (F) 1.1 Proposition Logic
1.2 Proposition Equivalences
1.3 Predicates and QuantifiersLogic (3 hours) 2 Mar 1 (Tu) 1.4 Nested Quantifiers
Mar 4 (F) 1.5 Rules of Inference
1.6 Introduction to Proofs3 Mar 8 (Tu) The 1st Exam
Proofs (2 hours) Mar 11 (F) 1.7 Proof Methods and Strategy
2.1 SetsSets (2 hours) 4 Mar 15 (Tu)
Mar 18 (F) 2.2 Set Operations
2.3 Functions
5 Mar 22 (Tu) The 2nd Exam Functions (1.5 hours) Mar 25 (F) 2.4 Sequences and Summations Sequences (1.5 hours)
Examples6 Mar 29 (Tu)
Apr 1 (F) 3.4 The Integers and Division 7 Apr 5 (Tu) The 3rd Exam (調課) Numbers (5 hours) Apr 8 (F) 3.5 Primes and Greatest Common Divisors
3.6 Integers and Algorithms8 Apr 12 (Tu) 3.7 Applications of Number Theory Apr 15 (F) 3.7 Applications of Number Theory
4.1 Mathematical Induction
4.2 Strong Induction and Well-OrderingInduction and Recursion (3 hours) 9 Apr 19 (Tu) The 4th Exam Apr 22 (F) 4.3 Recursive Definitions and Structural Induction
4.4 Recursive Algorithms
5.1 The Basics of CountingCombinatorics (4 hours) 10 Apr 26 (Tu) 5.2 The Pigeonhole Principle
5.3 Permutations and CombinationsApr 29 (F) 5.4 Binomial Coefficients
5.5 Generalized Permutations and Combinations11 May 3 (Tu) The 5th Exam May 6 (F) 5.6 Generating Permutations and Combinations
7.1 Recurrence Relations
7.2 Solving Linear Recurrence RelationsRecurrences (5 hours) Examples 12 May 10 (Tu) 7.2 Solving Linear Recurrence Relations (Cont.)
7.3 Divide-and-Conquer Algorithms and Recurrence Relations (Skip)
May 13 (F) 7.4 Generating Functions
7.5 Inclusion-Exclusion
7.6 Applications of Inclusion-Exclusion13 May 17 (Tu) The 6th Exam May 20 (F) 8.1 Relations and Their Properties Relations (5 hours) 14 May 24 (Tu) 8.3 Representing Relations May 27 (F) 8.4 Closures of Relations
8.5 Equivalence Relations
8.6 Partial Orderings15 May 30 (Tu) The 7th Exam Jun 3 (F) 9.1 Graphs and Graph Models
9.2 Graph Terminology and Special Types of Graphs16 Jun 7 (Tu) 9.3 Representing Graphs and Graph Isomorphism Graphs (5.5 hours) Jun 10 (F) 9.4 Connectivity
9.5 Euler and Hamilton Paths
9.6 Shortest-Path Problems
10.1 Introduction to Trees
10.3 Tree Traversal
10.5 Minimum Spanning Tree17 Jun 14 (Tu) The 8th Exam Trees (5 hours) Jun 17 (F) 調課到第三次考試 18 Jun 21 (Tu) No Class Jun 24 (F) No Class