Type of Credit: Required
Credit(s)
Number of Students
This is a fundamental mathematical course for computer science students. It is intended to introduce to the students basic discrete mathematical tools and skills that are needed in the study of computer science. These skills/tools include
1. mathematical reasoning: for the student be able to read comprehend and construct mathematical arguments
2. combinatorial analysis and discrete structures: knowledge of which is essential in problem solving/modeling and
3. algorithmic thinking: that would be helpful in the specification verification and analysis of computer algorithms/programs. Topics introduced in the course include logic induction counting recurrence relations relations graphs and trees.
* 欲加簽者請於第一堂課出席以方便教師統計加簽人數
能力項目說明
This is a fundamental mathematical course for computer science students. It is intended to introduce to the students basic discrete mathematical tools and skills that are needed in the study of computer science. These skills/tools include
1. mathematical reasoning: for the student be able to read comprehend and construct mathematical arguments
2. combinatorial analysis and discrete structures: knowledge of which is essential in problem solving/modeling and
3. algorithmic thinking: that would be helpful in the specification verification and analysis of computer algorithms/programs. Topics introduced in the course include logic induction counting recurrence relations relations graphs and trees.
| 教學週次Course Week | 彈性補充教學週次Flexible Supplemental Instruction Week | 彈性補充教學類別Flexible Supplemental Instruction Type |
|---|---|---|
|
Week |
Course Theme |
Content and Reading Assignment |
Activity and Homework |
Estimated time devoted to coursework per week |
|
|
Lecture Hours |
Preparation Time |
||||
|
1 |
The foundations: Logic, sets, functions, algorithm and complexity |
The foundations: Logic, sets, functions, algorithm and complexity |
Homework 1 |
3.0 |
4.5 |
|
2 |
中秋節 |
||||
|
3 |
Mathematical reasoning: Methods of proofs, Mathematical induction, recursive definitions, recursive algorithms and program correctness. |
Mathematical reasoning: Methods of proofs, Mathematical induction, recursive definitions, recursive algorithms and program correctness. |
Homework 2 |
3.0 |
4.5 |
|
4 |
Number Theory and its applications |
Number Theory and its applications |
|
3.0 |
4.5 |
|
5 |
Number Theory and its applications |
Number Theory and its applications |
|
3.0 |
4.5 |
|
6 |
Number Theory and its applications |
Number Theory and its applications |
Homework 3 |
3.0 |
4.5 |
|
7 |
Counting: Basic counting methods, pigeon hole principle, permutation and combinations. |
Counting: Basic counting methods, pigeon hole principle, permutation and combinations. |
|
3.0 |
4.5 |
|
8 |
Counting: Basic counting methods, pigeon hole principle, permutation and combinations. |
Counting: Basic counting methods, pigeon hole principle, permutation and combinations. |
Homework 4 |
3.0 |
4.5 |
|
9 |
Midterm Exam |
|
|
|
|
|
10 |
Advanced counting techniques: Recurrence relations, inclusion-exclusion principle and applications, generating functions. |
Advanced counting techniques: Recurrence relations, inclusion-exclusion principle and applications, generating functions. |
Homework 5 |
3.0 |
4.5 |
|
11 |
Advanced counting techniques: Recurrence relations, inclusion-exclusion principle and applications, generating functions. |
Advanced counting techniques: Recurrence relations, inclusion-exclusion principle and applications, generating functions. |
Homework 6 |
3.0 |
4.5 |
|
12 |
Relations: Relations and their properties, n-ary relatins and their applications, Relation representations, Closure of relations, Equivalence Relations, Partial Orderings. |
Relations: Relations and their properties, n-ary relatins and their applications, Relation representations, Closure of relations, Equivalence Relations, Partial Orderings. |
|
3.0 |
4.5 |
|
13 |
Relations: Relations and their properties, n-ary relatins and their applications, Relation representations, Closure of relations, Equivalence Relations, Partial Orderings. |
Relations: Relations and their properties, n-ary relatins and their applications, Relation representations, Closure of relations, Equivalence Relations, Partial Orderings. |
Homework 7 |
3.0 |
4.5 |
|
14 |
Graphs:terminology, representation, connectivity, Euler and Hamilton paths, shortest path problems, planar graphs, graph coloring. |
Graphs:terminology, representation, connectivity, Euler and Hamilton paths, shortest path problems, planar graphs, graph coloring. |
|
3.0 |
4.5 |
|
15 |
Graphs:terminology, representation, connectivity, Euler and Hamilton paths, shortest path problems, planar graphs, graph coloring. |
Graphs:terminology, representation, connectivity, Euler and Hamilton paths, shortest path problems, planar graphs, graph coloring. |
Homework 8 |
3.0 |
4.5 |
|
16 |
Trees:terminology, applications, tree traversal, trees and sorting, spanning trees, minimum spanning trees. |
Trees:terminology, applications, tree traversal, trees and sorting, spanning trees, minimum spanning trees. |
Homework 9 |
3.0 |
4.5 |
|
17 |
Final Exam | ||||
|
18 |
彈性補充教學 |
自主總整學習 |
|
|
|
Two examinations (60%)
Homeworks (30%)
class participation (10%)
Textbook: Discrete Mathematics and its applications, 8th edition, By Kenneth H. Rosen