Week 1: Introduction to Algorithm Design and Analysis
Stable Matching Problem
[Lab 1] Reviewing the Stable Matching algorithm and construction skills of test cases
Week 2: Five Representative Problems
Interval Scheduling
Weighted Interval Scheduling
Bipartite Matching
Independent Set
Competitive Facility Location
[Lab 2] Programming stable matching algorithms
Week 3: Basics of Algorithm Analysis
Computational Tractability
Asymptotic Order of Growth
Common Running Time
[Lab 3] Writing a runtime survey program, and testing the algorithms with n, nlogn, n
2
and other time complexity.
Observing that how the runtime changes with the increase of the input scale of the problem.
Week 4 &5: Graphs
Graph Traversal
Testing Bipartiteness
Connectivity in Directed Graphs
DAG and Topological Ordering
[Lab 4] Using BFS or DFS to solve some Graph Search Problems
[Lab 5] Using Topological Ordering to solve some common problems, such as courses scheduling or projects planning
Week 6, 7 & 8: Greedy Algorithms
Interval Scheduling
Interval Partitioning
Scheduling to Minimize Lateness
Optimal Caching
Shortest Paths in a Graph
Minimum Spanning Tree
Clustering
Huffman Codes
[Lab 6] Solving some Interval Scheduling problems
[Lab 7] Using MST to solve some problems
[Lab 8] Using Huffman to solve some problems
Week 9 & 10: Divide and Conquer