ECEP VIRTUAL CAMPUS

数据结构与算法 Data Structures and Algorithms

“数据结构与算法”是计算机学科中的核心基础课程。课程的主要目标培养学生较全面地理解基本数据结构的概念和经典算法的思想及各种实现方法,掌握数据结构和算法的设计分析技术。根据所求解问题的性质选择合理的数据结构并对时间空间复杂性进行必要的控制,提高程序设计的质量。使得学生在将来的学习、研究和工作中,具备设计和实现高效的数据结构和算法的能力。

About the Course

介绍视频若无法正常播放,请看这里。 

计算机是现代社会中用于解决问题的重要工具。利用计算机解决实际问题需要将问题抽象,并对数据进行操作,最后通过计算机程序求解问题。而本门课程主要内容就是对以上内容进行研究。

图灵奖获得者N.Wirth写了一本经典著作“程序=算法+数据结构”。数据结构,是抽象的表示数据的方式;算法,则是计算的一系列有效、通用的步骤。算法与数据结构是程序设计中相辅相成的两个方面。

我们会围绕着“算法+数据结构=程序”的思路,以问题求解为导向进行学习。希望能够帮助大家提高理论、抽象、设计的能力。在扎实的经典理论基础上,运用问题抽象、数据抽象、算法抽象来分析问题,应用适当的数据结构和算法来设计和实现相应的程序。通过课程学习,大家的抽象思维能力、问题求解能力将得到较大提升,编程能力和代码质量会有质的飞跃!

在求解实际问题方面,我们会学习到通过权衡时空和其他资源开销,利用数据结构来组织数据、设计高效的算法、完成高质量的程序以满足错综复杂的实际应用需要。

此外,课程所学到的内容会被利用到计算机科学后续的各个课程中,如操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等。希望可以为大家将来从事计算机相关的学习、研究和开发工作打下扎实的基础。

本课程采用张铭主编的国家“十一五”规划教材《数据结构与算法》(高等教育出版社)。适合计算机以及相关理工专业的大二本科生学习,需要先修过计算概论等课程,具有结构化和面向对象的程序设计基础。

课程主要包括的内容有:线性表,栈与队列,字符串,二叉树,树,图,排序(内排序,外排序),检索,索引、以及高级数据结构。课程持续14周,学习者每周在本课程上需要投入4-8小时。作为完成课程学习的要求,学生需要熟悉教材有关章节的内容,独立正确地完成作业和考试,达到60%的成绩就能获得北大的课程结业证书(获得80%以上的成绩,能得到优秀证书)。

该课程是“北大-德稻网络公开课程”中的一门,由北京大学与德稻教育联合提供。

Computer, as an important tool for problem solving, has been deeply involved in every aspect of people’s daily lives. Data are the quantities on which operations are performed on computers. What is the logical relationship among data? How are the data stored in computers? What algorithms should be operated to solve the problems on the data? These are the questions that will be answered in “Data Structures and Algorithms”, one of the most important core courses in Computer Science. The course also covers fundamental data structures and classical algorithms which are widely used in the succeeding specialized courses, such as Operating Systems, Software Engineering, Database Systems, Compiler Principles, Computer Graphics and Human Computer Interaction.

What is the combination of data structures and algorithms? Niklaus Wirth wrote a book titled "Algorithms + Data Structures = Programs", which points out their important roles in computing discipline: algorithm and data structure are two closely linked and indivisible parts of programming.

The course will follow the idea of  “Algorithms + Data Structures = Programs”, aimed at improving  students’ knowledge and skills of theory, abstraction and design in problem solving. On a solid basis of the fundamental theory, the students will analyze the problems using problem, data and algorithm abstraction. Making a tradeoff between space and time complexity, the students will learn how to organize data reasonably, design efficient and effective algorithms, and implement high quality programs, so that they can solve real-world complex problems. After studying this course, students should be well prepared for further study, engineering and research in computer related areas.

The course uses the textbook “Data Structures and Algorithms” written by Prof. Ming Zhang and two other  coauthors. The course is appropriate for sophomore students majoring in computer science or other science/engineering disciplines. Students should have learned "introduction to computing", with the knowledge of structured and object-oriented programming.

The course will last for 14 weeks and requires the students to study for 4-8 hours per week. After studying the course, the students’ ability of abstract thinking and problem solving should have improved considerably. Their programming skills and the quality of their codes would have increased as well.

To be qualified for graduation in Peking University, the students need to be familiar about the materials in the textbook, do homework and exam independently, and obtain the score of 60% or more (80% for A score).

The course is one of the PKU-DeTao MOOCs, which is a joint effort by Peking University and DeTao Masters Academy.

Course Syllabus

时间安排

• 第一周:数据结构和算法简介以及线性表
• 第二周:栈和队列
• 第三周:字符串
• 第四周:二叉树(1)
• 第五周:二叉树(2)
• 第六周:树与森林
• 第七周:图
• 第八周:内排序(1)
• 第九周:内排序(2)
• 第十周:文件管理和外排序
• 第十一周:检索
• 第十二周:索引技术
• 第十三周:高级数据结构(1)
• 第十四周:高级数据结构(2)


任务安排(作业及考试)

考试分为期中考试(11.25-12.8)和期末考试(1.13-1.26课程关闭时间)

评分方案

评分按照日常作业的完成情况和期中期末考试的答题情况进行。平时(课程参与)10 %,作业30 % ,POJ 20 %,期中 15 %,期末 25 %。

POJ作业在程序自动评测网站发布:http://dsalgo.openjudge.cn/

课程参与度较高的同学(Meetup讨论会、论坛问答),可以得到加分。

高级数据结构的内容不作考核要求,如果学生主动完成高级数据结构的作业,也可以得到一定加分。

 

证书

设置“合格”(达到60%成绩)、"优秀"(达到80%成绩)两档课程标准,由任课教师签发北大统一的课程结业证书。

Recommended Background

先修技能:计算概论(含程序设计语言)

Suggested Readings

[1] 张铭,赵海燕,王腾蛟,《数据结构与算法实验教程》,高等教育出版社,2011年 1月。普通高等教育“十一五”国家级规划教材。

[2] 张铭、赵海燕、王腾蛟,《数据结构与算法--学习指导与习题解析》,高等教育出版社,2005年 10月。 “十五”国家级规划教材配套参考书。

Course Format

本课程由视频课程、在线测试、编程练习、期中/期末考试等部分组成。

FAQ

 1. 教材和参考网站

   主教材:张铭,王腾蛟,赵海燕,《数据结构与算法》 。高等教育出版社,2008年 6月。——普通高等教育“十一五”国家级规划教材(入选“十二五”)

   国家精品课网站:http://www.jpk.pku.edu.cn/pkujpk/course/sjjg

   程序自动评测网站:http://dsalgo.openjudge.cn/

 

2. 教材与参考文献

[1] 张铭,赵海燕,王腾蛟,《数据结构与算法实验教程》,高等教育出版社,2011年 1月。普通高等教育“十一五”国家级规划教材。

[2] 张铭、赵海燕、王腾蛟,《数据结构与算法--学习指导与习题解析》,高等教育出版社,2005年 10月。 “十五”国家级规划教材配套参考书。

[3] Sartaj Sahni ,《数据结构算法与应用—C++语言描述》 ,汪诗林等译,机械工业出版社,2000.

[4] M. H. Alsuwaiyel, Algorithms Design Techniques and Analysis, 电子工业出版社影印,2003年1月。

[3] Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, 高等教育出版社影印,2002年5月。

[4] Donald E.Knuth 著,苏运霖 译,《计算机程序设计艺术,第1卷基本算法》,国防工业出版社,2002年。

[5] J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005.

[6] 王晓东,《算法设计与分析》 ,清华大学出版社,2003年1月。

 

3. 参考网站

(1) 《数据结构与算法》精品课程

   http://www.jpk.pku.edu.cn/pkujpk/course/sjjg

(2) Berkeley《数据结构》  

   http://www.cs.berkeley.edu/~jrs/61b/

(3) MIT 的《算法导论》(有OCW链接)
    http://stellar.mit.edu/S/course/6/sp13/6.006/

(4) Stanford 算法

https://www.coursera.org/course/algo

(5) Princeton 算法课
   https://www.coursera.org/course/algs4partI

(6) Web 上的术语资源 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

 

4. 课程采用什么算法语言?

    本课程采用基于C++的伪代码授课和出习题。编程作业是POJ自动评判的,该平台目前接受 C、C++、Java等都可以。

Starts August 18, 2015

Course at a Glance

10 weeks of study 2-4 hours/week English English & Vietnamese subtitles