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
数据结构与算法分析 Data Structures and Algorithm Analysis
2.
授课院系
Originating Department
计算机科学与工程系 Department of Computer Science and Technology
3.
课程编号
Course Code
CS203
4.
课程学分 Credit Value
3
5.
课程类别
Course Type
专业基础课 Major Foundational Courses
6.
授课学期
Semester
秋季 Fall
春季 Spring
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
程然，助理教授，计算机科学与工程系，chengr@sustech.edu.cn
Ran Cheng, Assistant Professor, Department of Computer Science and Engineering,
chengr@sustech.edu.cn
9.
实验员/助教、所属学系、联系
方式
Tutor/TA(s), Contact
沈昀，教学实验员，计算机科学与工程系， sheny@mail.sustech.edu.cn
Yun Shen, Teaching laboratory technician, Department of Computer Science and
Engineering, sheny@mail.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
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
数据结构与算法分析主要介绍计算机中基础的数据结构和算法分析方法。从数据结构角度而言，本课程主要介绍数组，链
表，栈，队列，字符串，树，和图。从算法分析角度而言，一方面该课程将介绍典型的算法设计思想，如二分法，分而治
之法，随机算法等，此外本课程还将介绍算法分析的基本方法，如时间、空间复杂度分析。本课程的目的是让每一位学生
掌握基础数据结构以及基本算法设计思想和分析方法，为学生将来进一步学习计算机其他专业核心课程（如计算机操作系
统，人工智能）等打下坚实基础。
In this course, we will study the fundamental data structures and algorithms. 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 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,
fundamental graph algorithms, and so on.
16.
预达学习成果 Learning Outcomes
预期学习成果：
1）初步掌握算法设计及分析的基本知识。
2）掌握常用数据结构的实现方式及性能分析。
3）学会分析问题以及选用/构造合适的数据结构及算法解决问题。
4）掌握评价算法性能（时间、空间复杂度），分析及改进算法性能的基本方法。
Learning Outcomes：
1) Student will know the basic concept of algorithm design and analysis.
2) Student will know the implementation and performance analysis of common data structures.
3) Student can analysis the problem and use / design proper data structures and algorithms to solve it.
4) Student could analysis the performance (both time and space complexity) for a given algorithm, then propose
optimization techniques to improve it.
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
Lecture Topic
Lec 1 Course introduction, preliminary review (math, programming language)
Lec 2 Algorithm analysis (Searching on ordered array and binary search)
Lec 3 Linked List (Linked list operators and applications)
Lec 4 Stack (Stack implementation, operations, and applications)
Lec 5 Queue (Queue implementation, operations, and applications)
Lec 6 String and KMP (string introduction and KMP algorithm)
Lec 7 Tree (tree definition, properties)
Lec 8 Priority Queue / Heap (binary tree and complete binary tree)
Lec 9 Binary Search Tree / AVL-tree (insertion/deletion operators)
Lec 10 Graph (graph definition, properties)
Lec 11 Breadth First Search and Depth Frist Search (SSSP, Topological Sort, DAG)
Lec 12 Shortest Path (Dijkstra Algorithm)
Lec 13 Minimum Spanning Tree (Prim’s Algorithm)
Lec 14 Strongly Connected Components
Lec 15 Sorting Algorithm (Selection, Insertion, Bubble, Merge, Heap, Quick sort)
Lec 16 Course Review
Lab Topic
Lec 1 Introduce how to design algorithm and how to use online judge system.
Lec 2 Recursion and Deep first search Exercise.
Lec 3 Binary Search (Basic exercise and futher exercise)
Lec 4 Linked List exercise (How to design a Linked List, and when need to using Linked List)
Lec 5 Stack (How to design a stack, and what problem can be solved by using stack)
Lec 6 Queue (How to design a queue, and what problem can be solved by using queue)
Lec 7 String and KMP (Basic exercise of String, next array of KMP and how to use KMP)
Lec 8 Binary Tree (How to design a binary structure, and different kinds of traversal of binary tree )
Lec 9 Priority Queue / Heap (Floating and sinking and how to use heap)
Lec 10 Binary Search Tree / AVL-tree (insertion / deletion operators)
Lec 11 Tree and Graph (Defination of tree and graph)
Lec 12 Breadth First Search and Depth Frist Search (SSSP, Topological Sort, DAG)
Lec 13 Shortest Path (Dijkstra Algorithm, finding shortest path of two node)
Lec 14 Minimum Spanning Tree (Prim’s Algorithm, finding shortest path of all nodes)
Lec 15 Strongly Connected Components
Lec 16 Sorting Algorithm (Selection, Insertion, Bubble, Merge, Heap, Quick sort)
18.
教材及其它参考资料 Textbook and Supplementary Readings
4
No Textbook
参考资料:
Introduction to Algorithms, Third Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford
Stein, MIT Press
数据结构与算法分析：C++描述（英文版）（第 3 版）， [美] Mark Allen Weiss 著，人民邮电出版社
数据结构与算法分析：Java 语言描述（第 2 版），[美] Mark Allen Weiss 著 冯舜玺 译， 机械工业出版社
课程评估 ASSESSMENT
19.
评估形式
Type of
Assessment
评估时间
Time
占考试总成绩百分比
% of final
score
违纪处罚
Penalty
备注
Notes
出勤 Attendance
课堂表现
Class
Performance
10%
10 次随堂测验
Ten in-class quizes
小测验
Quiz
20%
2 次闭卷测验
Two closed book quizes
课程项目 Projects
平时作业
Assignments
20%
编程作业
Coding assignments
期中考试
Mid-Term Test
25%
闭卷考试
Closed book exam
期末考试
Final Exam
25%
闭卷考试
Closed book exam
期末报告
Final
Presentation
其它（可根据需要
改写以上评估方
式）
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