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 1. (The link of Part 2  )

课程相关源码 Source Code for Course(Code

第一周  概论 Overview (Slides & Slides_EN)

问题求解  Solving Problems  (video) (Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)
 数据结构与抽象数据类型 Data Structures and Abstract Data Types  (video) (Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)
 算法特性及分类 The Properties and Categories of Algorithm (video) (Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)
 算法效率与度量  Evaluating Efficiency of Algorithm(video) (Slide_CH)(Slide_EN)(Captions_CH)(Captions_EN)

补充 面向对象的数据结构描述

补充  面向对象简介(video)(slide)
补充  类的特殊成员(video)(slide)
补充 模版函数与模版类(video)(slide)
补充 输入输出流 (video)(slide)

第二周 线性表 Linear List (Slides & Slides_EN)

线性结构 The Structure of Lists (video)(slide)(Slide_EN)(C_CH)(C_EN)
顺序表 Sequential Lists(video)(slide)(Slide_EN)(C_CH)(C_EN)
链表 Linked Lists (video)(slide)(Slide_EN)(C_CH)(C_EN)
顺序表和链表的比较 The Comparison of Sequential Lists and Linked Lists (video)(slide)(Slide_EN)(C_CH)(C_EN)

第三周 栈与队列 Stack and Queue(Slides & Slides_EN

栈 Stacks (video)(slide)(Slide_EN)(C_CH)(C_EN)
栈与递归 Stacks and Recursion (video)(slide)(Slide_EN)(C_CH&C_EN)
递归转非递归(选修)Implementation of Recursion using Stacks (Optional) video(slide)(Slide_EN)(C_CH&C_EN)
队列 Queues (video)(slide)(Slide_EN)(C_CH&C_EN)
队列的应用 The Application of Queues (video)(slide)(Slide_EN)(C_CH)(C_EN)

第四周 字符串 Strings(Slides & Slides_EN)

字符串基本概念   The Basic Concept of Strings(video)(slide)(slide_EN)(C_CH)(C_EN)
字符串的存储结构   The Storage Structure of Strings(video)(slide)(slide_EN)(C_CH)(C_EN)
字符串运算的算法实现 The Implementation of Strings’ Operations(video)(slide)(slide_EN)(C_CH)(C_EN)
字符串的快速模式匹配(选修) KMP Fast String Matching (Optional) (video)(slide)(slide_EN)(C_CH)(C_EN)

第五周 二叉树(上)Binary Trees I (Slides_CH & Slides_EN

二叉树的概念  The Basic Concept of Binary Trees (video)(slide_CH)(slide_EN)(C_CH)(C_EN)
二叉树的抽象数据类型   The Abstract Data Type for a Binary Tree(video)(slide_CH)(slide_EN)(C_CH)(C_EN)
二叉树的搜索     Binary Tree Traversals(video)(slide_CH)(slide_EN)(C_CH)(C_EN)
二叉树的存储结构  The Storage Structures for Binary Trees(video)(slide_CH)(slide_EN)(C_CH)(C_EN)

第六周 二叉树(下)Binary Trees II (Slides_CH & Slides_EN)

二叉搜索树   Binary Search Trees (video)(slide_CH)(slide_EN)(C_CH)(C_EN)
堆与优先队列 Heaps and Priority Queues (video)(slide_CH)(slide_EN)(C_CH)(C_EN)
Huffman树及其应用  Huffman Coding Trees and Its Application (video)(slide_CH)(slide_EN)(C_CH)(C_EN)

第七周 树 Trees (Slides_CH & Slides_EN

树的定义、树与二叉树的等价转换 The Definitions of Trees and Equal Translation between Trees and Binary Trees(video)(slide_CH)(slide_EN)(C_CH)(C_EN)
树的抽象数据类型及树的遍历   The Abstract Data Types of a Tree, Tree Traversals(video)(slide_CH)(slide_EN)(C_CH)(C_EN)
树的链式存储结构    The Linked Structure of Trees(video)(slide_CH)(slide_EN)(C_CH&C_EN)
树的父指针表示法   The Parent Point Implementation of Trees(video)(slide_CH)(slide_EN)(C_CH&C_EN)
树的顺序存储和K叉树   Serialization of Trees, and K-ary Trees(video)(slide_CH)(slide_EN)(C_CH)(C_EN)

第八周 图 Graphs(Slides_CH & Slides_EN)

图的概念和抽象数据类型 The Concept and Abstract Data Types of a Graph(video)(slide_CH)(slide_EN)(C_CH)(C_EN)
图的存储结构   The Storage Structure of a Graph(video)(slide_CH)(slide_EN)(C_CH)(C_EN)
图的遍历    Graph Traversal(video)(slide_CH)(slide_EN)(C_CH)(C_EN)
最短路径  Shortest Path(video)(slide_CH)(slide_EN)(C_CH)(C_EN)
最小生成树   Minimum-Cost Spanning Trees(video)(slide_CH)(slide_EN)(C_CH)(C_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