课程详述

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.

课程名称 Course Title

算法设计与分析（H） Algorithm Design and Analysis (H)

授课院系

Originating Department

计算机科学与工程系 Department of Computer Science and Engineering

课程编号

Course Code

CS216

课程学分 Credit Value

课程类别

Course Type

专业基础课 Major Foundational Courses

授课学期

Semester

春季 Spring

授课语言

Teaching Language

中英双语 English & Chinese

授课教师、所属学系、联系方

式（如属团队授课，请列明其

他授课教师）

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

实验员/助教、所属学系、联系

方式

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）

11.

授课方式

Delivery Method

讲授

Lectures

习题/辅导/讨论

Tutorials

实验/实习

Lab/Practical

其它(请具体注明)

Other（Please specify）

总学时

Total

学时数

Credit Hours

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) 理解算法在计算机科学领域中的作用。

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

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

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

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] 编程实现稳定匹配算法

第 3周：算法分析基础

计算复杂性理论

渐进分析

常见运行时间

[Lab 3] 编写一个运行时间分析程序，测试具有 n、nlogn、n

和其他时间复杂度的算法，并观察随着输入量级增加，运行

时间如何变化。

第 4-5周：图算法

图遍历

测试双向图

有向图连通性

有向无环图及拓扑排序

[Lab 4] 使用深度优先或宽度优先解决图搜索问题。

[Lab 5] 使用拓扑排序解决一些常见问题，例如排课或者项目规划。

第 6-7周：贪婪算法

区间调度

区间分割

最小延迟调度问题

贪心算法

图中的最短路径

最小生成树

聚类

哈夫曼编码

[Lab 6] 解决区间调度问题。

[Lab 7] 使用 MST解决一些问题，使用哈夫曼编码解决问题。

第 8-9周：分治算法

归并排序

统计逆序数