週次 |
授課內容 |
第1週 |
Introduction to the goal of algorithm design, Why we study algorithm? Who need Algorithm?
|
第2週 |
Time Complexity, Space Complexity, 3Sum Problem, Binary Search, Union Find Problem |
第3週 |
The unknown array size problem |
第4週 |
Element Sorting (Insertion Sort, Selection Sort, Shell Sort, Knuth shuffling) |
第5週 |
Merge Sort (Natural Sort, Sleep Sort, Top-down, Botton-up)
Quick Sort (three way sort, naive quick sort)
|
第6週 |
Counting Sort
Heap Sort
The Upper Bound and Lower Bound of Sorting |
第7週 |
Divide and Conquer, Master Theorem |
第8週 |
Midterm Exam |
第9週 |
DFS, BFS, Cycle Detection, Connected Component, Topological Sort
|
第10週 |
Minimum Spanning Tree (Prim and Kruskal algorithm)
|
第11週 |
Shortest Path Problem
|
第12週 |
Introduction to Dynamic Programming |
第13週 |
Introduction to Dynamic Programming |
第14週 |
P. vs. NP
NP-Completeness, NP-Hard
Salesman Problem |
第15週 |
Context Problem |
第16週 |
自主學習:利用網路資源,自主學習Knuth-Morris-Pratt Algorithm |
第17週 |
自主學習:利用網路資源,自主學習Kosaraju’s Algorithm for computing strong components
|
第18週 |
Final Exam |