高级数据结构与算法

这门课程将帮助学生学习如何运用高级的数据结构和相关算法解决复杂的应用问题。本课隶属于程序设计与算法 Fundamentals of Programming and Algorithms Specialization »

北京大学

分享

高级数据结构与算法
  • 分类: 计算机
  • 平台: Coursera
  • 语言: 中文

课程概述

这门课程将帮助学生学习如何运用高级数据结构和相关算法解决复杂的实际问题。 我们将深入学习排序、检索、索引、高级数据结构以及数据结构应用等内容。涉及快速排序、外排序等各种经典排序算法,集合、散列、位图等检索方法,B/B+树、Trie树等索引结构,广义表、多维数组等高级线性结构,AVL、红黑树、伸展树等平衡二叉树。 通过课程学习,大家的抽象思维能力、问题求解能力将得到较大提升,编程能力和代码质量会有质的飞跃!

授课大纲

第一周 内排序(上)Lecture 1 Internal Sorting I
• 排序问题的基本概念 The Basic Concept of Sorting
• 插入排序 ( Shell 排序) Insertion Sort (Shell Sort)
• 选择排序 (堆排序) Selection Sort (Heap Sort)
• 交换排序(冒泡排序、快速排序)Exchange Sort (Bubble Sort, Quick Sort)

第二周 内排序(下)Lecture 2 Internal Sorting II
• 归并排序 Merge Sort
• 桶排序 Bin Sort
• 静态基数排序 Static Radix Sort
• 链式基数排序 Linked Radix Sort
• 索引排序 Indexing Sort
• 排序算法的时间代价 The Complexity of Sorting

第三周 文件与外排序 Lecture 3 File and External Sort
• 主存、外存、文件的组织 Main Memory, External Memory and File’s Architecture
• 外排序 External Sort

第四周 检索 Lecture 4 Searching
• 检索的概念 The Concept of Searching
• 基于线性表的检索 Linear Searching
• 集合的检索 Set-based Searching
• 散列表的概念和散列函数 The Concept of Hash Table, Hash Function
• 散列冲突处理 Solving Hash Collision
• 散列的实现及性能分析 The Implementation of Hash Table and Its Complexity Analysis

第五周 索引 Lecture 5 Indexing
• 静态索引 Static Indexing
• 倒排索引 Inverted Indexing
• B树 B-Trees
• B+树 B+-Trees
• 位索引技术 Bitmap Indexing
• 红黑树 Red-Black Tree

第六周 高级数据结构(上——线性结构)Lecture 6 Advanced Data Structures I , List-Structure
• 多维数组 Multilists
• 广义表 Generalized Tables
• 存储管理 Memory Management

第七周 高级数据结构(下——树形结构)Lecture 7 Advanced Data Structures II , Tree-Structure
• Trie 树 Trie Trees
• AVL树概念及插入算法 The AVL Tree and Its Inserting Algorithm
• AVL树删除及性能分析 The Deletion of AVL Trees, Complexity Analysis
• Splay树 Splay Tree

第八周 数据结构应用(不考核)Lecture 8 The application of Data Structures (Optional)

先修知识

熟悉C/C++描述的基础数据结构与算法
Basic Data Structures and Algorithms in C/C++

参考资料

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

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

授课形式

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

Quizzes and class participation 50% ,POJ cloze tests 20%,POJ Labs 10%,final exam 20%.
Hints: The programming Labs are also released on the website of POJ (Peking University Online Judge) http://dsalgo.openjudge.cn/ besides this MOOC site. You may practice on your own.

常见问题

1. 课程采用中英文教学吗? Will this course be delivered in both Chinese and English?
本课程的大部分资源,包括所有字幕、课件、小测作业、编程题、考试都同时提供中英文版本。课程组正在筹划制作英文讲课视频,期望在2015年开课时能提供完整的中英文双语版本。
Most of the learning materials are available in both Chinese and English, including subtitles, slides, quizzes, labs, and final test. We are preparing for the English course videos now, and hopefully we will have course videos in bilingual.

2. 课程采用的算法语言? Which programming languages does the course use?
本课程采用基于C++的伪代码授课和出习题。编程作业是POJ(http://dsalgo.openjudge.cn/)自动评判的,该平台目前接受 C、C++、Java等都可以。

The course’s content and exercises are both based upon C++ pseudo code. Programming assignments are automatically assessed by POJ (http://dsalgo.openjudge.cn/ ) which accepts code written in C/C++ and JAVA.

3.教材与参考文献 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, 电子工业出版社影印,2003年1月。
[6] T. H.Cormen, C. E.Leiserson, R. L. Rivest, C. Stein, Inroduction to Algorithms, 高等教育出版社影印,2002年5月。
[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] 王晓东,《算法设计与分析》 ,清华大学出版社,2003年1月。

4. 参考网站 Recommended Web Sites
(1) 《数据结构与算法》精品课程(该网站是教育网IP,不支持国外IP访问)
“Data Structures and Algorithms” Course Website at Peking University (Only available in Mainland China) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg
(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

声明:MOOC中国收录之课程均源自下列机构,版权均归他们所有。本站仅作报道并尊重其著作权益,感谢他们对MOOC事业做出的贡献!(排名不分先后)
  • Coursera
  • edX
  • OpenLearning
  • FutureLearn
  • iversity
  • Udacity
  • NovoEd
  • Canvas
  • Open2Study
  • Google
  • ewant
  • FUN
  • IOC-Athlete-MOOC
  • World-Science-U
  • Codecademy
  • CourseSites
  • opencourseworld
  • ShareCourse
  • gacco
  • MiriadaX
  • JANUX
  • openhpi
  • Stanford-Open-Edx
  • 网易云课堂
  • 中国大学MOOC
  • 学堂在线
  • 顶你学堂
  • 华文慕课
  • 好大学在线CnMooc

Copyright © 2008-2015 MOOC.CN 慕课改变你,你改变世界