演算法概論
Introduction to Algorithms
學期
111-1
學分
3
學分
當期課號
515512
永久課號
CSCS10009
開課單位
資訊學院共同課程
授課教師
施仁忠
校區
光復
類別
必修
上課時間表
| 節 | 週二 |
|---|---|
3 10:10–11:00 | 演算法概論 EC114 2 節連堂 |
4 11:10–12:00 |
* 根據陽明交大上課時間表所列
概述
Introduce different design strategies of computer algorithm and the analysis of algorithms.
先修科目
If "Data Structures" or "Object-Oriented Programming" failed, it is not allowed to study this course "Introduction to Algorithm"。 The required courses are C/C++ and Data Structures。
評分方式
Mid-term Exam 30% Final Exam 30% Programming Assignments & Exercises 40%
課程大綱
- Introduction to Algorithms
- Asymptotics and Mathematical Basics
- Divide and Conquer
- Recurrences and Summations
- Randomized Quicksort
- Median and Order Statistics
- Sorting in Linear Time
- Search and Hash Tables
- Red-Black Trees
- Dynamic Programming
- Greedy Algorithms
- Minimum Spanning Tree
- Graph Algorithms: Depth-First Search, Topological Sorting, Breadth-First Search
- Graph Algorithms: Single-Soruce Shortest Paths, Dijkstra's Algorithm
- All-Pairs Shortest Paths Algorithms
- NP-Complete Problems
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | Introduction to Algorithms |
| 第 2 週 | Asymptotics and Mathematical Basics |
| 第 3 週 | Divide and Conquer |
| 第 4 週 | Recurrences and Summations |
| 第 5 週 | Randomized Quicksort |
| 第 6 週 | Median and Order Statistics |
| 第 7 週 | Sorting in Linear Time |
| 第 8 週 | Search and Hash Tables |
| 第 9 週 | Red-Black Trees |
| 第 10 週 | Dynamic Programming |
| 第 11 週 | Greedy Algorithms |
| 第 12 週 | Minimum Spanning Tree |
| 第 13 週 | Graph Algorithms: Depth-First Search, Topological Sorting, Breadth-First Search |
| 第 14 週 | Graph Algorithms: Single-Soruce Shortest Paths, Dijkstra's Algorithm |
| 第 15 週 | All-Pairs Shortest Paths Algorithms |
| 第 16 週 | NP-Complete Problems |
教科書
Introduction to Algorithms, 3rd Ed., MIT Press, byCormen, Leiserson, Rivest, and Stein.
Office Hours
- 地點
- EC440
- 時間
- Every Tuesday 01:00pm~02:00pm
- 聯絡方式
- zcshih@cs.nctu.edu.tw