Discrete Mathematics  離散數學
Spring 2009

 

Instructor:

顏嗣鈞

 

Class:

Monday 3:30-5:20 PM (EE2-106)

 

Office:

BL-525

 

Phone:

3366-3581

 

E-mail:

yen@cc.ee.ntu.edu.tw

 

Office Hours:

By appointment

 

TA:

廖強棋(d96921026@ntu.edu.tw )  博理603

林與絜 (yuccalin@arbor.ee.ntu.edu.tw)  博理603

　

Syllabus

　

INTRODUCTION:
Much of what students need to learn in this course is not really "discrete" mathematics. It includes a fair amount of continuous abstract mathematics, e.g. functions, and basic ability to read and write proofs. Our goal is to prepare students for upper division computer science and mathematics courses, including: automata theory, combinatorics and graph theory, algorithm analysis, operating systems, data base, compilers, artificial intelligence, graphics, etc. This course also provides a rigorous introduction to formal approaches to software development (specifications, verification, testing, etc.) useful in the software engineering sequence. I will try to relate the topics to computer science problems wherever possible.

ANNOUNCEMENTS:

 

n          期中考、期末考 、以及作業成績  (Midterm Exam, Final Exam and Homework Grades)

1.   如要看期末考考卷或是對於分數登記有問題，請於以下時間來博理館525室找我

2.   作業三有位同學沒寫姓名，請該同學於以下時間來博理館525室找我

                   星期六 (6/27)  2 - 4 PM    or   星期一 (6/29) 11 - 12 AM

n          Final exam   will be held on Monday, June 15.  (Sample final exams: 1, 2, 3, 4)

期末考試範圍:

課本 (pp. 449-479; 519-530; 538-550; 555-575; 589-681) + 講義

n          Homework #3 (due June 15,  Monday)

n          Homework #2 (due May 4,  Monday)

n         Midterm Solutions

n         Midterm will be held on April 13 (3:30 – 5:20 PM).  (Sample midterm exams: 2008 , 2006 (sol), 1997, 1996)

n          Homework #1 (due March 23, Monday)

CLASS NOTES:

Introduction

Table of Contents of Textbook:

  1. The Foundations: Logic (Notes; Slides), Sets  and Functions  (Notes; Slides)
  2. The Fundamentals: Algorithms, the Integers, and Matrices  
  3. Mathematical Reasoning, Induction (Notes; Slides) , and Recurrence relations 
  4. Counting
  5. Discrete Probability  
  6. Advanced Counting Techniques     (Notes; Slides)
  7. Relations   (Notes; Slides)
  8. Graphs (Notes; Slides-1) (Slides-2) (Slides-3) (Slides-4)
  9. Trees
  10. Boolean Algebra  
  11. Modeling Computation  

Supplementary materials:

n          Natural Deduction for Propositional Logic

n          Natural Deduction for Predicate Logic   

n          Axiomatic  Set Theory

n          Hoare Logic (pdf); Loop Invariants

TEXT:
　

Discrete Mathematics and Its Applications, 6th Edition, Kenneth H. Rosen, McGraw-Hill

COURSE REQUIREMENTS:
There will be homework assignments, one midterm exam, and a final exam. The weightings within the semester grade will be:

Homework

20%

Midterm

40%

Final exam

40%

HOMEWORK:
Only homework turned in by the due date is guaranteed to be graded. Any special circumstances that cause difficulty in meeting the deadlines should be brought to the attention of the instructor in advance.

CHEATING:
With the exception of group assignments, the work (including homework and tests) must be the result of your individual effort. This implies that one student should never have in his/her possession a copy of all or part of another student's homework. It is your responsibility to protect your work from unauthorized access. Academic dishonesty has no place in a university, in particular, in NTUEE. It wastes our time and yours, and it is unfair to the majority of students. Any form of cheating will automatically result in a failing grade in the course and will be reported to the Dean's office.