演算法
Computer Algorithms
| 節 | 週一 |
|---|---|
5 13:20–14:10 | 演算法 MB312 3 節連堂 |
6 14:20–15:10 | |
7 15:30–16:20 |
* 根據陽明交大上課時間表所列
The course is intended as a first undergraduate course in the design and analysis of algorithms. The main focus is on known and well-established results in the literature. The course will give an overview of common techniques and applications of these techniques in different settings.
Data structures (optional)
- Homework assignments (4 assignments, including written problem solving and/or coding): 40% - Midterm: 30% - Final project and presentation: 30%
| 週次 | 主題 |
|---|---|
| 第 1 週 | Preliminaries: mathematical proofs, in particular induction and contradiction big-O notation (Big-O, Omega, Theta), how to apply them |
| 第 2 週 | Preliminaries: mathematical proofs, in particular induction and contradiction big-O notation (Big-O, Omega, Theta), how to apply them |
| 第 3 週 | Preliminaries: basic discrete math such as evaluating sums and simple recurrences basic algorithms such as binary search, sorting basic graph algorithms such as connected components, BFS, DFS |
| 第 4 週 | Preliminaries: basic discrete math such as evaluating sums and simple recurrences basic algorithms such as binary search, sorting basic graph algorithms such as connected components, BFS, DFS |
| 第 5 週 | Intro to Theory of Computation: Autamata, Turing machines and algorithms, decidability and complexity Greedy algorithms |
| 第 6 週 | Greedy algorithms |
| 第 7 週 | Greedy algorithms |
| 第 8 週 | Midterm |
| 第 9 週 | Divide and Conquer |
| 第 10 週 | Dynamic programming |
| 第 11 週 | Dynamic programming |
| 第 12 週 | Max-Flow/Min-Cut |
| 第 13 週 | NP-hardness and reduction Approximation Linear programming |
| 第 14 週 | Randomization PAC Learnability and learning |
| 第 15 週 | Final presentation |
| 第 16 週 | Final presentation |
Algorithm Design by Jon Kleinberg and Éva Tardos. 2005 References: Introduction to Algorithms (any available edition) by Cormen, Leiserson, Rivest, and Stein Approximation Algorithms by Vazirani. 2001 Introduction to the Theory of Computation 3rd edition, Michael Sipser. 2012 Understanding Machine Learning: From Theory to Algorithms, Shai Shalev-Shwartz and Shai Ben-David. 2014
- 地點
- 313C, Management Building 2
- 時間
- Office hours: Mon 4:20-5:20pm
- 聯絡方式
- poanchen@nycu.edu.tw (instructor) tim901005.mg13@nycu.edu.tw; suy535628@gmail.com (TAs)