Skip to main content

教学内容(Syllabus

2014年秋季学期开始在edx.org开设《数据结构与算法》课程,分两期共16周来开设,每一期各8周。第二期的内容如下:(第一期的链接)

The Couse Data Structures and Algorithms is opened on edx.org in fall 2014, divided into two sessions, with eight weeks for each session. Following are the 8 lectures for Part 2.(The link of Part 1)

第一周 内排序 上 (Week one Internal Sorting I)(SLIDES_CH)(SLIDES_EN)

1.1 排序问题的基本概念 (The Basic Concept of Sorting)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)
1.2 插入排序----- Shell 排序  (	Insertion Sort ----Shell Sort )(video)(Slide_CH)(Slide_CH_v2)(Slide_EN)(Slide_EN_v2)(Captions_CH)(Captions_EN)
1.3 选择排序----堆排序 (Selection Sort----Heap Sort)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)
1.4 交换排序-----冒泡排序、快速排序 (Exchange Sort ----- Bubble Sort, Quick Sort)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)

第二周 内排序 下 (Week two Internal Sorting II)(SLIDEs_CH)(SLIDES_EN)

2.1 归并排序 (Merge Sort)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)
2.2 桶排序 (Bucket Sort)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)
2.3 静态基数排序 (Static Radix Sort)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)
2.4 链式基数排序 (Linked Radix Sort)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)
2.5 索引排序 (Indexing Sort)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)
2.6 排序算法的时间代价 (The Time Expense of Sort)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)

第三周 文件与外排序 (Week three File and External Sort)(SLIDES_CH)(SLIDES_EN)

3.1 主存、外存、文件的组织 (Main Memory, External Memory and File’s Architecture)(video)(Slide_CH)(Slide_EN)(Captions_CH&Captions_EN)
3.2 外排序  (External Sort)(video)(Slide_CH)(Slide_EN)(Captions_CH&Captions_EN)

第四周 检索 (Week four Retrieval)(SLIDES_CH)(SLIDES_EN)

4.1 检索的概念 (The Concept of Retrieval)(video)(Slide_CH)(Slide_EN)(Captions_CH&Captions_EN)
4.2 基于线性表的检索(Linear Retrieval)(video)(Slide_CH)(Slide_EN)(Captions_CH&Captions_EN)
4.3 集合的检索 (Set-based Retrieval)(video)(Slide_CH)(Slide_EN)(Captions_CH&Captions_EN)

4.4 散列表的概念和散列函数(The Concept of Hash Table)
(video)(Slide_CH)(Slide_EN)(Captions_CH&Captions_EN)
4.5 散列冲突处理 (Solving Hash Collision)(video)(Slide_CH)(Slide_EN)(Captions_CH&Captions_EN)
4.6 散列的实现及性能分析 (The Implementation of Hash Table and Its Efficiency Analysis)(video)(Slide_CH)(Slide_EN)(Captions_CH&Captions_EN)

第五周 索引 (Week five indexing) (SLIDE_CH)(SLIDE_EN)

5.1 静态索引 (Static Indexing)(video)(Slide_CH)(Slide_EN)(Captions_CH&Captions_EN)
5.2 倒排索引 (Inverted Indexing)(video)(Slide_CH)(Slide_EN)(Captions_CH&Captions_EN)
5.3 B树 (B-Trees)(video)(Slide_CH)(Slide_EN)(Captions_CH&Captions_EN)
5.4 B+树 (B+-Trees)(video)(Slide_CH)(Slide_EN)(Captions_CH&Captions_EN)
5.5 位索引技术 (Bitmap Indexing)(video)(Slide_CH)(Slide_EN)(Captions_CH&Captions_EN)
5.6 红黑树(Red-Black Tree)(video)(Slide_CH)(Slide_EN)(Captions_CH&Captions_EN)

第六周 高级数据结构(上——线性结构) (Week 6 Advanced Data Structures I , List-Structure)(SLIDE_CH)(SLIDU_EN)

6.1 多维数组 (Multi-dimensional Array)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)
6.2 广义表 (Generalized Table)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)
6.3 存储管理 (Storage Management)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)

第七周 高级数据结构(下——树形结构) (Week 7 Advanced Data Structures II , Tree-Structure)(SLIDE_CH)(SLIDU_EN)

7.1 Trie 树 (Tries)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)
7.2 AVL树概念及插入算法 (The AVL Tree and Its Inserting Algorithm)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)
7.3 AVL树删除及性能分析 (	The Deletion of AVL Tree and Its Efficiency Analysis)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)
7.4 Splay树(The Splay Tree)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)

第八周 扩充:数据结构应用 (The application of Data Structures)

The materials of this week are specified for peking university students  which are more challenging and difficult.  Note that, the materials are also acted as additional part in our session 1

8.1 快速字符串的模式匹配KMP算法(KMP for Quick Matching String )(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)
8.2 递归到非递归的转换 (The Transition between Recursion and Non-recursion)(video)(Slide_CH)(Slide_EN)(Captions_CH&Captions_EN)
8.3 树的顺序存储结构 (The Sequential Storage Structure of Trees)(video)(Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)

)

参考评分方案 
quiz
小测和课程参与50% POJ 算法填空20%POJ算法题10%,期末考试20%
注释:编程作业除了在EdX平台外,也同时发布于POJ程序自动评测网站http://dsalgo.openjudge.cn/ ,同学们可以自行练习。

Grading Policy 
Quizzes and class participation 50% 
POJ cloze tests 20%POJ Labs 10%final exam 20%.

Hints: The programming tasks are also released on the website of POJ (Peking University Online Judge) http://dsalgo.openjudge.cn/ besides Edx. You may practice on your own.

证书 
设置“合格”(达到60% ~ 79% 成绩)、"优秀"(达到80% 成绩,可能需要完成高难度的选做内容)两档课程标准,由任课教师签发北大统一的课程结业电子版证书。

Certificates

There are two kinds of curriculum standards. One is qualified (60% ~ 79% of the total score), the other is excellent (80% or more the total score, may need to finish the optional materials). Students who achieve these standards will receive the electronic version of the course completion certificate issued by Peking University.

Prerequisites

基本的C/C++编程能力

Basic programming skills in C/C++.

 

教材与参考文献(Textbooks and References)
[1] 
张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008 6月。普通高等教育十一五国家级规划教材。
Textbook: Ming Zhang, Tengjiao Wang, Haiyan Zhao, "Data Structures and Algorithms", Higher Education Press, 2008.
[2] 
张铭,赵海燕,王腾蛟,《数据结构与算法实验教程》,高等教育出版社,2011 1月。普通高等教育十一五国家级规划教材。
[3] 
张铭、赵海燕、王腾蛟,《数据结构与算法--学习指导与习题解析》,高等教育出版社,2005 10月。 “十五国家级规划教材配套参考书。
[4] S. Sahni 
,《数据结构算法与应用—C++语言描述》 ,汪诗林等译,机械工业出版社,2000. 
[5] M. H. Alsuwaiyel, Algorithms Design Techniques and Analysis, 
电子工业出版社影印,20031月。 
[6] T. H.Cormen, C. E.Leiserson, R. L. Rivest, C. Stein, Inroduction to Algorithms, 
高等教育出版社影印,20025月。 
[7] D. E.Knuth 
著,苏运霖 译,《计算机程序设计艺术,第1卷基本算法》,国防工业出版社,2002年。 
[8] J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005.
[9] C. A. Shaffer, Data Structures and Algorithm Analysis in C++, Third Edition, Dover Publications., 2011.
[10] 
王晓东,《算法设计与分析》 ,清华大学出版社,20031月。

 参考网站(Reference Site)
(1) 
《数据结构与算法》精品课程(该网站是教育网IP,不支持国外IP访问)   
   
http://www.jpk.pku.edu.cn/pkujpk/course/sjjg
"Data Structures and Algorithms" Course Website at Peking University (Only available in Mainland China) 
(2) Berkeley course:Data Structures
   
http://www.cs.berkeley.edu/~jrs/61b/
(3) MIT course: Intro to Algorithms. 
    
http://stellar.mit.edu/S/course/6/sp13/6.006/ 
(4) Stanford course 
https://www.coursera.org/course/algo 
(5) Princeton course
   
https://www.coursera.org/course/algs4partI 
(6) 
网上的术语资源(terminology resources online http://www.nist.gov/dads/   
(7) Algorithms in the Real World 
http://www.cs.cmu.edu/~guyb/realworld.html 
(8) Advanced Data Structures and Algorithms 
http://theory.stanford.edu/~rajeev/cs361.html
(9) Advanced Data Structures 
http://www.cs.biu.ac.il/~moshe/ds1.html

第一期内容如下 (The content of Part 1):

概论 Overview (Slides_CH)(Slides_EN)

线性表 Linear Lists (Slides_CH)(Slides_EN)

栈与队列 Stacks and Queues(Slides_CH)(Slides_EN)

字符串 Strings (Slides_CH)(Slides_EN)

二叉树 Binary Trees  (Slides_CH_I & Slides_CH_II ) (Slides_EN_I & Slides_EN_II )

树 Trees (Slides_CH)(Slides_EN)

图 Graphs (Slides_CH)(Slides_EN)