课程内容及教学日历 (如授课语言以英文为主,则课程内容介绍可以用英文;如团队教学或模块教学,教学日历须注明
主讲人)
Course Contents (in Parts/Chapters/Sections/Weeks. Please notify name of instructor for course section(s), if
this is a team teaching or module course.)
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: Greedy Algorithms