Syllabus

Discrete Mathematics (Spring 2010)

http://www.cs.nctu.edu.tw/~yi/Courses/DiscreteMath/2010SpringDiscreteMath.htm

Instructor: Dr. Chih-Wei Yi (©ö§Ó°¶)
Class: Tu 9:00-9:50, F 13:30-15:20 @ 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

ÅRÆE³ÕTA: Yi-Ta Chuang (²ø©y¹F)

Recitation Website:
http://www.nol.cs.nctu.edu.tw/izeki/course/2010SpringDM.html 

Recitation Hours: TAB @ TBA
Office Hours: M,Tu,Th 12:00-13:00 @ EC235
E-mail: izeki.cs96g@nctu.edu.tw
Phone: x56680

 TA: Benny Lu (§f§µ«í)
Office Hours: W,Th 12:30~13:20 @ EC235
E-mail: bennylu.cs98g@nctu.edu.tw
Phone: x56680
TA: Alex Chiu (ªô¬f¶v)
Office Hours: M,Tu 12:30~13:20 @ EC235
E-mail: angeldie.cs98g@nctu.edu.tw
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:

  1. C. L. Liu, Elements of Discrete Mathematics, 2nd ed., McGraw-Hill Inc. 

  2. Ralph P. Grimaldi, Discrete and Combinatorial Mathematics, 5th ed..

Pre-requisite:

Goals of the Course:

  1. To demonstrate to students how mathematics can be applied to solve nontrivial real-life problems

  2. To gain more experience with mathematical thinking, arguments and proof techniques, which are essential in reasoning about computation

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

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

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

  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

  1. The Integers and Division
  2. Primes and Greatest Common Divisors
  3. Integers and Algorithms
  4. 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

Grading Policy:  

2 Preliminary Test (20%), 2 Midterm (40%), 1 Final (30%), Homework and Quizzes (10%)

Course Log:       

Week

Date

Topics

Slides
1 Feb 23 (Tu) 0.0 Introduction

1.1 Proposition Logic

 Introduction

Logic (3 hours)
Feb 26 (F) 1.2 Proposition Equivalences
1.3 Predicates and Quantifiers		 ¡@
2 Mar 2 (Tu)

1.4 Nested Quantifiers

  
Mar 5 (F) °±½Ò (±ö¦ËÁÉ)  
3 Mar 9 (Tu)

1.5 Rules of Inference
 1.6 Introduction to Proofs

 Proofs (2 hours)
Mar 12 (F) 1.7 Proof Methods and Strategy
2.1 Sets		 Sets (2 hours)
4 Mar 16 (Tu)

Preliminary Test #1

 Preliminary Test #1
Mar 19 (F) 2.2 Set Operations
  
5 Mar 23 (Tu) 2.3 Functions Functions (1.5 hours)
Mar 26 (F) 2.4 Sequences and Summations Sequences (1.5 hours)
Examples
6 Mar 30 (Tu)

Preliminary Test #2

 Preliminary Test #2
Apr 2 (F) Break ¡@
7 Apr 6 (Tu) 3.4 The Integers and Division Numbers (5 hours)
Apr 9 (F) 3.5 Primes and Greatest Common Divisors
3.6 Integers and Algorithms
8 Apr 13 (Tu) 3.7 Applications of Number Theory  
Apr 16 (F) 3.7 Applications of Number Theory Induction and Recursion (3 hours)
9 Apr 20 (Tu) 4.1 Mathematical Induction
4.2 Strong Induction and Well-Ordering 		 
Apr 23 (F) 4.3 Recursive Definitions and Structural Induction
4.4 Recursive Algorithms
5.1 The Basics of Counting		 Combinatorics (4 hours)
10 Apr 27 (Tu) 5.2 The Pigeonhole Principle
5.3 Permutations and Combinations		  
Apr 30 (F) Midterm #1 Ch 3.3~3.7 & Ch.4.1~4.4 Midterm #1
11 May 4 (Tu) 5.4 Binomial Coefficients
5.5 Generalized Permutations and Combinations		  
May 7 (F) 5.6 Generating Permutations and Combinations
7.1 Recurrence Relations
7.2 Solving Linear Recurrence Relations		 Recurrences (5 hours) Examples
12 May 11 (Tu) 7.2 Solving Linear Recurrence Relations (Cont.)
7.3 Divide-and-Conquer Algorithms and Recurrence Relations (Skip)
  
May 14 (F) 7.4 Generating Functions
7.5 Inclusion-Exclusion
7.6 Applications of Inclusion-Exclusion		 ¡@
13 May 18 (Tu) 8.1 Relations and Their Properties Midterm #2
May 21 (F) Midterm #2: Chapter 5,7 (not including 7.3) Relations (5 hours)
14 May 25 (Tu) 8.3 Representing Relations ¡@
May 28 (F) 8.4 Closures of Relations
8.5 Equivalence Relations		 ¡@
15 May 31 (Tu) 8.6 Partial Orderings ¡@
Jun 4 (F) 9.1 Graphs and Graph Models
9.2 Graph Terminology and Special Types of Graphs 		¡@
16 Jun 8 (Tu) 9.3 Representing Graphs and Graph Isomorphism Graphs (5.5 hours)
Jun 11 (F) 9.4 Connectivity
9.5 Euler and Hamilton Paths
9.6 Shortest-Path Problems		 ¡@
17 Jun 15 (Tu) 10.1 Introduction to Trees Trees (5 hours)
Jun 18 (F) 10.3 Tree Traversal
10.5 Minimum Spanning Tree		 ¡@
18 Jun 22 (Tu) Break Final Exam and Answers
Jun 25 (F) Final Exam Chapter 8,9,10 ¡@