1
课程详述
COURSE SPECIFICATION
以下课程信息可能根据实际授课需要或在课程检讨之后产生变动。如对课程有任何疑问，请联
系授课教师。
The course information as follows may be subject to change, either during the session because of unforeseen
circumstances, or following review of the course at the end of the session. Queries about the course should be
directed to the course instructor.
1.
课程名称 Course Title
算法设计与分析 Algorithm Design and Analysis
2.
授课院系
Originating Department
计算机科学与工程系 Department of Computer Science and Technology
3.
课程编号
Course Code
CS208
4.
课程学分 Credit Value
3
5.
课程类别
Course Type
专业基础课 Major Foundational Courses
6.
授课学期
Semester
春季 Spring
7.
授课语言
Teaching Language
英文 English
8.
授课教师、所属学系、联系方
式（如属团队授课，请列明其
他授课教师）
Instructor(s), Affiliation&
Contact
（For team teaching, please list
all instructors）
史玉回，讲席教授，计算机科学与工程系 ，shiyh@sustech.edu.cn
Yuhui Shi, Chair Professor, Department of Computer Science and Engineering,
shiyh@sustech.edu.cn
9.
实验员/助教、所属学系、联系
方式
Tutor/TA(s), Contact
赵耀，教学实验员，计算机科学与工程系 ，zhaoy6@sustech.edu.cn
Yao Zhao, Teaching laboratory technician, Department of Computer Science and
Engineering, zhaoy6@sustech.edu.cn
10.
选课人数限额(可不填)
Maximum Enrolment
（Optional）
授课方式
Delivery Method
习题/辅导/讨论
Tutorials
实验/实习
Lab/Practical
其它(请具体注明)
Other（Please specify）
总学时
Total
11.
学时数
Credit Hours
32
64
2
12.
先修课程、其它学习要求
Pre-requisites or Other
Academic Requirements
CS102A 计算机程序设计基础 A Introduction to Computer Programming A
CS203 数据结构与算法分析 Data Structures and Algorithm Analysis
13.
后续课程、其它学习规划
Courses for which this course
is a pre-requisite
None
14.
其它要求修读本课程的学系
Cross-listing Dept.
Not applicable for other departments beside CS
教学大纲及教学日历 SYLLABUS
15.
教学目标 Course Objectives
The course aims to teach students the basic concepts on algorithms, and introduce the fundamentals of algorithm design
and analysis techniques. In this course, the students will be familiar with major algorithms, such as fundamental graph-
based algorithms, greedy algorithms, divide-and-conquer algorithms, dynamic programming algorithms, and network flow
algorithms. In addition, upon completion of this course, the students should be able to program these algorithms for
solving corresponding problems.
16.
预达学习成果 Learning Outcomes
Upon completion of this course, students shall have the capabilities of doing:
1) Prove the correctness of algorithms;
2) Analyze the asymptotic order of growth of algorithms;
3) Be familiar with major algorithms like fundamental graph-based algorithms, greedy algorithms, divide-and-conquer
algorithms, dynamic programming algorithms, and network flow algorithms;
4) Apply design and analysis methods to the above-mentioned major algorithms;
5) Implement these major algorithms by using a programming language.
17.
课程内容及教学日历 （如授课语言以英文为主，则课程内容介绍可以用英文；如团队教学或模块教学，教学日历须注明
主讲人）
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.)
3
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
4
Mergesort
Counting Inversions
Closest Pair of Points
Integer Multiplication
Convolution and FFT
[Lab 9] Implementing a simple application of Divide and Conquer
[Lab 10] Implementing a comprehensive application of Divide and Conquer
Week 11, 12 & 13: Dynamic Programming
Weighted Interval Scheduling
Segmented Least Squares
Knapsack Problem
RNA Secondary Structure
Sequence Alignment
Shortest Paths
[Lab 11] Solving a simple dynamic programming problem
[Lab 12] Solving the simple knapsack problem
[Lab 13] Ssolving the comprehensive knapsack problem
Week 14, 15 : Network Flow
Minimum Cut Problem
Maximum Flow Problem
Ford-Fulkerson Algorithm
Good Augmenting Paths
[Lab 14] Explaning Network Flow algorithms and Application Examples
[Lab 15] Solving the comprehensive network problem
Week 16: Review and Preparation for Final Exams
[Lab 16] Review, Q&A
18.
教材及其它参考资料 Textbook and Supplementary Readings
Jon Kleinberg and Eva Tardos, Algorithm Design, Pearson
课程评估 ASSESSMENT
5
19.
评估形式
Type of
Assessment
评估时间
Time
占考试总成绩百分比
% of final
score
违纪处罚
Penalty
备注
Notes
出勤 Attendance
5 min/per time
10%
课堂表现
Class
Performance
小测验
Quiz
课程项目 Projects
平时作业
Assignments
2 hours/per time
20%
期中考试
Mid-Term Test
期末考试
Final Exam
2 hours
40%
期末报告
Final
Presentation
其它（可根据需要
改写以上评估方
式）
Others (The
above may be
modified as
necessary)
2 hours per week
30%
Lab
20.
记分方式 GRADING SYSTEM
A. 十三级等级制 Letter Grading
B. 二级记分制（通过/不通过） Pass/Fail Grading
课程审批 REVIEW AND APPROVAL
21.
本课程设置已经过以下责任人/委员会审议通过
This Course has been approved by the following person or committee of authority