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
算法设计与分析(H Algorithm Design and Analysis (H)
2.
授课院系
Originating Department
计算机科学与工程系 Department of Computer Science and Engineering
3.
课程编号
Course Code
CS216
4.
课程学分 Credit Value
3
5.
课程类别
Course Type
专业基础课 Major Foundational Courses
6.
授课学期
Semester
春季 Spring
7.
授课语言
Teaching Language
中英双语 English & Chinese
8.
他授课教师)
Instructor(s), Affiliation&
Contact
For team teaching, please list
all instructors
于仕琪,副教授,计算机科学与工程系,yusq@sustech.edu.cn
Shiqi Yu, Associate Professor, Department of Computer Science and Engineering,
yusq@sustech.edu.cn
9.
实验员/所属学系
方式
Tutor/TA(s), Contact
赵耀,教学实验师,计算机科学与工程系 zhaoy6@sustech.edu.cn
Yao Zhao, Assistant Teaching Technician, Department of Computer Science and
Engineering, zhaoy6@sustech.edu.cn
10.
选课人数限额(可不填)
Maximum Enrolment
Optional
2
11.
讲授
Lectures
习题/辅导/讨论
Tutorials
实验/实习
Lab/Practical
其它(请具体注明)
OtherPlease specify
总学
Total
32
32
64
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 introduces basic concepts on algorithms by looking at the real-world problems that motivate them. It
teaches various design and analysis techniques for problems that arise in computing applications, and encourage the
students to understand the algorithm design process and the role of algorithms in the broader field of computer
sciences. 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, network flow algorithms and some randomized algorithms.
4) Apply design and analysis methods to the above-mentioned major algorithms.
5) Implement these major algorithms by using a programming language.
6) Understand the algorithm design process.
7) Understand the role of algorithms in the broader field of computer sciences.
学习了本门课程后,学生可以具有如下能力:
1) 证明算法的正确性;
2) 分析算法计算量增长的渐进级别;
3) 熟悉一系列主要的算法:图算法、贪婪算法、分治算法、动态规划、网络流算法和随机算法;
4) 对前述一系列算法能够进行设计和分析;
5) 使用某一种编程语言实现前述一系列算法;
6) 理解算法设计流程;
7) 理解算法在计算机科学领域中的作用。
3
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.)
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
4
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, using Huffman to solve some problems
Week 8 & 9: Divide and Conquer
Mergesort
Counting Inversions
Closest Pair of Points
Integer Multiplication
Convolution and FFT
[Lab 8] Implementing a simple application of Divide and Conquer
[Lab 9] Implementing a comprehensive application of Divide and Conquer
Week 10 & 11: Dynamic Programming
Weighted Interval Scheduling
Segmented Least Squares
Knapsack Problem
RNA Secondary Structure
Sequence Alignment
Shortest Paths
[Lab 10] Solving a simple dynamic programming problem; Solving the simple knapsack problem.
[Lab 11] Solving the comprehensive knapsack problem
Week 12 & 13: Network Flow
5
Minimum Cut Problem
Maximum Flow Problem
Ford-Fulkerson Algorithm
Good Augmenting Paths
[Lab 12] Explaining Network Flow algorithms and Application Examples
[Lab 13] Solving the comprehensive network problem
Week 14 & 15: Randomized Algorithms
Finding the Global Minimum Cut
Randomized Approximation Algorithm for MAX 3-SAT
Randomized Divide and Conquer
Hashing
Randomized Caching
[Lab 14] Contention Resolution
[Lab 15] Finding the closest pair of points by a randomized approach
Week 16: Review and Preparation for Final Exams
[Lab 16] Review, Q&A
1周:介绍算法设计和分析
稳定匹配问题
[Lab 1] 学习稳定匹配问题,测试案例构建
2周:算法中的五个代表性问题
区间调度
带权重的区间调度
二分图匹配
独立集问题
竞争设施选址问题
[Lab 2] 编程实现稳定匹配算法
6
3周:算法分析基础
计算复杂性理论
渐进分析
常见运行时间
[Lab 3] 编写一个运行时间分析程序,测试具有 nnlognn
2
和其他时间复杂度的算法,并观察随着输入量级增加,运行
时间如何变化。
4-5周:图算法
图遍历
测试双向图
有向图连通性
有向无环图及拓扑排序
[Lab 4] 使用深度优先或宽度优先解决图搜索问题。
[Lab 5] 使用拓扑排序解决一些常见问题,例如排课或者项目规划。
6-7周:贪婪算法
区间调度
区间分割
最小延迟调度问题
贪心算法
图中的最短路径
最小生成树
聚类
哈夫曼编码
[Lab 6] 解决区间调度问题。
[Lab 7] 使用 MST解决一些问题,使用哈夫曼编码解决问题。
8-9周:分治算法
7
归并排序
统计逆序数
最近点对算法
整数乘法
卷积和快速傅立叶变换
[Lab 8]实现一个简单的分治算法的应用。
[Lab 9]实现一个完整的分治算法应用。
10-11 周:动态规划
带权重的区间调度
分段最小二乘法
背包问题
RNA 二级结构
序列对齐
最短路径
[Lab 10]解决一个简单的动态规划问题;解决一个简单的背包问题。
[Lab 11]解决一个完整的背包问题。
12-13 周:网络流算法
最小割问题
最大流问题
最大流量算法
好的增广路径
[Lab 12] 分析网络流算法和应用案例。
[Lab 13] 解决一个完整的网络流问题。
14-15 周:随机算法
寻找最小割
用于 MAX 3-SAT的随机近似算法
8
随机分治算法
哈希
随机贪心算法
[Lab 14] 了解和分析竞争消除算法。
[Lab 15] 使用随机方法寻找最近点对。
16周:复习本学期内容
[Lab 16] 复习、答疑。
18.
教材及其它参考资 Textbook and Supplementary Readings
Jon Kleinberg and Eva Tardos, Algorithm Design, Pearson
课程评估 ASSESSMENT
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
9
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