数据结构与算法 Data Structures and Algorithms

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

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

图灵奖获得者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.

时间安排

• 第一周：数据结构和算法简介以及线性表
• 第二周：栈和队列
• 第三周：字符串
• 第四周：二叉树（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%成绩）两档课程标准，由任课教师签发北大统一的课程结业证书。