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） Data Structures and Algorithm Analysis(H)
2.
授课院系
Originating Department
计算机科学与工程系 Department of Computer Science and Engineering
3.
课程编号
Course Code
CS217
4.
课程学分 Credit Value
3
5.
课程类别
Course Type
专业基础课 Major Foundational Courses
6.
授课学期
Semester
秋季 Fall
7.
授课语言
Teaching Language
英文 English
8.
授课教师、所属学系、联系方
式（如属团队授课，请列明其
他授课教师）
Instructor(s), Affiliation&
Contact
（For team teaching, please list
all instructors）
唐博，助理教授，计算机科学与工程系，tangb3@sustech.edu.cn
Bo Tang, Assistant Professor, Department of Computer Science and Engineering,
tangb3@sustech.edu.cn
9.
实验员/助教、所属学系、联系
方式
Tutor/TA(s), Contact
沈昀，教学实验员，计算机科学与工程系， sheny@mail.sustech.edu.cn
Yun Shen, Assistant Teaching Technician, Department of Computer Science and
Engineering, sheny@mail.sustech.edu.cn
10.
选课人数限额(可不填)
Maximum Enrolment
（Optional）
2
11.
授课方式
Delivery Method
讲授
Lectures
习题/辅导/讨论
Tutorials
实验/实习
Lab/Practical
其它(请具体注明)
Other（Please specify）
总学时
Total
学时数
Credit Hours
32
32
64
12.
先修课程、其它学习要求
Pre-requisites or Other
Academic Requirements
CS102A 计算机程序设计基础 A Introduction to Computer Programming A
13.
后续课程、其它学习规划
Courses for which this course
is a pre-requisite
CS208 算法设计与分析 Algorithm Design and Analysis
CS302 计算机操作系统 Operating Systems
CS305 计算机网络 Computer Networks
CS303 人工智能 Artificial Intelligence
CS419 高级算法 Advanced Algorithms
14.
其它要求修读本课程的学系
Cross-listing Dept.
教学大纲及教学日历 SYLLABUS
15.
教学目标 Course Objectives
中文：数据结构与算法(H)分析主要介绍计算机科学中常用数据结构（比如基础数据结构和高级数据结构）、算法分析方
法以及算法设计思想。从数据结构角度而言，本课程主要介绍数组，链表，栈，队列，字符串，树，和图。从算法分析角
度而言，本课程涵盖算法时间复杂度分析，空间复杂度分析，以及算法正确性证明等。从算法设计思想角度而言，该课程
将介绍典型的算法设计思想，如二分法，贪心发，分而治之法，随机算法等。本课程的目的是让每一位学生掌握数据结构
以及基本算法设计思想和分析方法，为学生将来进一步学习计算机其他专业核心课程（如高级算法，操作系统，人工智
能）等打下坚实基础。
English: In this course, we will study the data structures (fundamental and advanced data structures), algorithms
analysis and algorithm design methodology (generic and specific algorithm design techniques). Such knowledge is at
the core of computer science, and allows us to write faster programs, especially ones whose running time has attractive
worst-case bounds. Techniques for analyzing the performance of algorithms, designing beautiful/efficient algorithm will
also be discussed in detail. Tentative topics to be covered include array, linked list, queue, stack, searching in ordered
lists, sorting, priority queues, binary search trees, graph algorithms, and so on.
16.
预达学习成果 Learning Outcomes
(1) 掌握计算机算法设计及分析的基本知识，
(1) The students will know how to design data structures and algorithm design and analysis techniques
(2) 学会分析问题以及构造合适的数据结构或算法解决问题，
(2) The students can analysis the problem and use / design proper data structures and algorithms to solve it.
(3) 掌握评价算法性能及分析及改进算法性能的基本方法。
3
(3) The students could analysis the performance (both time and space complexity) for a given algorithm, then propose
optimization techniques to improve it.
(4) 了解先进的数据结构和算法思想，并能简单的加以引用
(4) The students will know some advanced data structures and algorithms, and they also can use them in simple cases
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.)
Lecture tentative schedule:
Lec 1 Course introduction, preliminary review (math, programming language)
Lec 2 Algorithm analysis (Searching on ordered array and binary search)
Lec 3 Linked List, Stack and Queue (basic operators, implementations and applications)
Lec 4 String, KMP, and FSA (string introduction, KMP algorithm)
Lec 5 Advanced strings (FSA introduction, the suffix tree)
Lec 6 Tree (tree definition, properties)
Lec 7 Priority Queue / Heap / Binary Search Tree (binary tree and complete binary tree)
Lec 8 Balanced Binary Search Tree: AVL-tree, Red-black tree, Splay tree (insertion/deletion operators)
Lec 9 Graph (graph definition, properties, traversal algorithms and applications: SSSP, Topological Sort, DAG)
Lec 10 Advanced Graph Theory I (Union-find structure, Euler-tour structure)
Lec 11 Advanced Graph Theory II (Dynamic connectivity, Binomial and Fibonacci heaps)
Lec 12 Points (kd-tree, bootstrapping, priority search tree, and range tree)
Lec 13 Intervals (Interval tree and segment tree)
Lec 14 Nearest neighbor search (Locality Sensitive Hashing)
Lec 15 Computational Complexity (P, NP, NP-hard, NP-Complete)
Lec 16 Course Review
Lab tentative schedule:
Lab 1 fundamental programming language skill training
Lab 2 fundamental math problems
Lab 3 searching problems
4
Lab 4 basic linked list/ stack application
Lab 5 string matching problems
Lab 6 finite state automata problems
Lab 7 basic tree properties
Lab 8 heap and its application
Lab 9 AVL-tree implementation
Lab 10 graph applications
Lab 11 BFS/DFS problems
Lab 12 BFS+DFS applications
Lab 13 SSSP and DAG applications
Lab 14 K-D tree applications
Lab 15 computational theory problems
Lab 16 course review
18.
教材及其它参考资料 Textbook and Supplementary Readings
No Textbook
参考资料:
Introduction to Algorithms, Third Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford
Stein, MIT Press
课程评估 ASSESSMENT
19.
评估形式
Type of
Assessment
评估时间
Time
占考试总成绩百分比
% of final
score
违纪处罚
Penalty
备注
Notes
出勤 Attendance
The whole semester
10
课堂表现
Class
Performance
0
小测验
Quiz
One hour per quiz
20
课程项目 Projects
0
平时作业
Assignments
5-6 problems per
assignment, 10
assignments in total
20
期中考试
Mid-Term Test
2 hours written exam
20
期末考试
2 hours written exam
30
5
Final Exam
期末报告
Final
Presentation
0
其它（可根据需要
改写以上评估方
式）
Others (The
above may be
modified as
necessary)
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
