組合數學
Combinatorial Mathematics
| 節 | 週一 |
|---|---|
A 18:30–19:20 | 組合數學 EC122（光復） 3 節連堂 |
B 19:30–20:20 | |
C 20:30–21:20 |
* 根據陽明交大上課時間表所列
To learn the concepts of combinatorics and its potential applications in computer science. As a second goal for the students from the CS department, we will introduce a few classic computation problems and their optimal algorithmic solutions. Course website: https://sites.google.com/nycu.edu.tw/113-2-combo-math
Linear Algebra, Probability, Discrete Mathematics
無備註
Students are expected to read the lecture notes & slides and do homework problems spontaneously in order to fully understand the concepts.
Approximately 5 Handwritten Homework: 20% Approximately 4 Program Assignments: 20% Two Midterm Exams and Final: 60%
The classics
Probabilistic counting, The pigeonhole principle, The Lovász sieve and the local lemma
- 講授：
- 12
Topics in graphs
Hall's matching theorem, Maximum bipartite matching, The Hungarian algorithm, The max-flow min-cut theorem
- 講授：
- 12
Advanced algorithmic topics
Algorithmic Lovász local lemma, Optimal RMQ, Suffix trees and BWT transforms, Eigenvalues and graph expansions, Expander decomposition of graphs, Random walks
- 講授：
- 9
| 週次 | 主題 |
|---|---|
| 第 1 週 | Probabilistic method 2025-02-17(一) |
| 第 2 週 | The Pigeonhole principle 2025-02-24(一) |
| 第 3 週 | Miscellaneous topics in counting 2025-03-03(一) |
| 第 4 週 | The Lovasz sieve and the local lemma 2025-03-10(一) |
| 第 5 週 | Supplement: The Algorithmic Lovasz local lemma 2025-03-17(一) |
| 第 6 週 | *** Midterm (I) *** 2025-03-24(一) |
| 第 7 週 | Hall's matching theorem and System of distinct representatives 2025-03-31(一) |
| 第 8 週 | Maximum bipartite matching 2025-04-07(一) |
| 第 9 週 | Weighted bipartite matching The Hungarian algorithm for min-cost perfect matching 2025-04-14(一) |
| 第 10 週 | The max-flow min-cut theorem 2025-04-21(一) |
| 第 11 週 | The RMQ problem and optimal algorithms 2025-04-28(一) |
| 第 12 週 | *** Midterm (II) *** 2025-05-05(一) |
| 第 13 週 | Suffix tree, BWT transforms for strings 2025-05-12(一) |
| 第 14 週 | Eigenvalues and graph expansions, Expander decomposition of graphs (if time permits) 2025-05-19(一) |
| 第 15 週 | Expander decomposition of graphs (if time permits) Random walks in graphs 2025-05-26(一) |
| 第 16 週 | *** Final exam *** 2025-06-02(一) |
| 第 17 週 | 2025-06-09(一) |
| 第 18 週 | 2025-06-16(一) |
1. Applied Combinatorics, 6th Ed, Alan Tucker 2. Extremal Combinatorics, 2nd Ed, Stasys Junka.
- 地點
- 教師未提供此項資料
- 時間
- In class or by appointment via email (if necessary)
- 聯絡方式
- 教師未提供此項資料