spContent=本课程目标是帮助学生学得下列观念和能力:
1. 各种基本数据结构的认识。2. 透过实作数据结构让同学对所学有更深刻的了解,并加强同学写程式的训练。3. 用数据结构配合基本的演算法来解决问题。4. 本课程将透过OJ (Online Judge) 程式判读功能进行测验。
本课程目标是帮助学生学得下列观念和能力:
1. 各种基本数据结构的认识。2. 透过实作数据结构让同学对所学有更深刻的了解,并加强同学写程式的训练。3. 用数据结构配合基本的演算法来解决问题。4. 本课程将透过OJ (Online Judge) 程式判读功能进行测验。
—— 课程团队
课程概述
“数据结构”是学习以聪明的方法去储存数据,使得我们在有需要的时候能够快速有效地把数据撷取。例如我们希望把学生某一科的考试成绩整理,使得我们能随时查询任何学生的排名。为了节省查询的时间,我们或许会把学生们的成绩从高至低排好,而不会以随意的顺序排列。(对此问题,其实还有一个更好的方法呢!)在此课程,我们将针对各种基本的数据结构,进行理论探讨及分析,并辅以适量的程序训练,加强学生对数据结构实际应用的掌握。
本课程由台湾新竹清华大学提供,因课程视频由主讲教师录制并上传,凡课程视频中“国立清华大学”均指“台湾新竹清华大学”。
课程大纲
Week 0 | Overview |
Week 1 | Getting Started; Heap Sorting的方法&分析 Sorting的分析 Growth of Function Insertion Sort上机 Exercises Heap-1 Heap-2 Exercises
|
Week 2 | Sorting Lower Bound Basic Data Structures I (List, Queue, Stack) Pointers in C Basic Data StructureⅠ- 1 Basic Data StructureⅠ- 2 Josephus上机 Balanced括号上机 List上机_insert List上机_delete Exercises
|
Week 3 | Basic Data Structures II (Tree, Graph) Graph and Tree Traversals I (BFS, DFS) Breadth First Search Depth First Search Depth First Search分析 Exercises
|
Week 4 | Graph and Tree Traversals II (Tree Traversals, Expression Tree ) Graph and Tree Traversals III (Topological Sort) Topological Sort Topological 证明 Two IQ questions Exercises
|
Week 5 | Searching Set Data I (Binary Search Tree) Binary Search Tree Binary Search Tree 实作 (Min/Max) Binary Search Tree 实作 (Search Predecessor) Binary Search Tree 实作 (Insert/Delete) Binary Search Tree 实作 (Delete)- Case 1&2 Binary Search Tree 实作 (Delete)- Case 3 BST上机_insert BST上机_delete_1 BST上机_delete_2 BST上机_3 Exercises
|
Week 6 | Searching Set Data II (AVL Tree) AVL Tree AVL Tree- Rotation AVL Tree- Insertion的情形 AVL Tree- Insertion实作Case2.2 AVL Tree- Insertion实作Case2.3 AVL Tree Insert 补充& Delete Augmenting Data Structure Exercises
|
Week 7 | Searching Set Data III (B-Tree) B-tree EM Model B-tree insert B-tree delete Exercises
|
Week 8 | Hashing (Chaining, Open Addressing) Hashing Common Hash Function Exercises
Suffix Tree and Suffix Array |
展开全部
预备知识
证书要求
修习完毕课程内容并完成所有课程要求,可获得「修课证明」。
参考资料
指定用書
1.Introuction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
2.Fundamentals of Data Structures in C++
Ellis Horowitz, Sartaj Sahni, Dinesh Mehta
參考資料
Algorithms in C++; Robert Sedgewick