每周課程進度與作業要求 Course Schedule & Requirements
| 教學週次Course Week |
彈性補充教學週次Flexible Supplemental Instruction Week |
彈性補充教學類別Flexible Supplemental Instruction Type |
|
|
|
|
|
第1週 Introduction (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
第2週 Data Structures and Algorithms (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
第3週 Design of Algorithm by Induction (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
第4週 Algorithms Involving Sequence and Sets (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
-
Binary Search
-
Finding Minimum in Cyclic Sorted Sequence
-
Binary Search of Unknown Size
-
Stuttering-Subsequence
-
Solving Equation: Bisection Algorithm
-
Interpolation Search
第5週 Algorithms Involving Sequence and Sets (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
- Bucket sort
- Radix sort
- Insertion sort
- Selection sort
- Bubble sort
- Merge sort
- Quick sort
- Heap sort
- Heap Construction: Top Down vs. Bottom Up Approaches
- Low bound of Comparison-based Sorting
- External Sorting
- Sorting of Large Structures
- Finding both Maximum and Minimum Elements
- Finding the K-th Smallest Element
- String Editing Distance: Levenshtein Distance, Damerau–Levenshtein distance
第6週 Algorithms Involving Sequence and Sets (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
- Longest Common Subsequence
- Sequence Alignment
- Dynamic Time Warping
- String Matching: KMP Algorithm
- Huffman Tree
第7週 Graph Algorithms (I) (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
第8週 Midterm Exam.
第9週 Graph Algorithms (II) (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
-
Review of Midterm Exam.
-
Topological Ordering
-
Unweighted Shortest Paths
-
Weighted Shortest Paths of Directed Acyclic Graph
-
Weightes Shortest Paths of Directed Cyclic Graph without Negative Weight: Dijkstra's Algorithm
第10週 Graph Algorithms (III) (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
-
All Pair Shortest Paths: Floyd-Warshall Algorithm
-
Minimum Spanning Tree: Prim's Algorithm
-
Minimum Spanning Tree: Kruskal's Algorithm
-
Bipartite Graph Matching
第11週 Graph Algorithms (IV) (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
-
Graph Coloring
-
Maximum Flow Problem: Ford–Fulkerson Algorithm
-
Maximum Flow Problem: Edmonds-Karp Algorithm
-
Graph Decomposition: Bocinnected Componnents
第12週 Geometric Algorithms (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
-
Computational Geometry
-
Determining Inside a Polygon
-
Constructing Simple Polygons
-
Convex Hull: Straight Forward Approach
-
Convex Hull: Gift Wrapping
-
Convex Hull: Graham's Scan
-
Closest Pair
第13週 Reduction (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
-
Reduction of Cyclic String Matching
-
Reduction of System Distinct Representatives
-
Reudction of Sequence Comparison
第14週 校慶停課(自主總整學習)
第15週 NP-Completeness (I) (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
-
Finite-State Machine
-
Push-Down Automata
-
Turing Machine
-
Non-Deterministic Turing Machine
-
Decision Problem vs. Optimization Problem
-
Non-Decidable Problem
-
Non-Deterministic Algorithm
第16週 NP-Completeness (II) (指定閱讀課本, 講課與討論, 課前預習1 hr., 課後複習3 hr.)
第17週 Final Exam.
第18週 Advaned Algorithms (線上課程)