教學大綱與進度

課程基本資料：

學年期	課號	課程名稱	階段	學分	時數	修	教師	班級	人	撤	備註
110-2	300596	資料結構	1	3.0	3	★	黃柏鈞	電子二丙	39	2	◎

教學大綱與進度：

教師姓名	黃柏鈞　教師諮商時間(Office Hours)
Email	pchuang.19840320@gmail.com
最後更新時間	2022-01-21 16:54:05
課程大綱	本課程介紹常用的基礎資料結構。請注意本課程以中英語混和授課。 This course introduces fundamental data structures. Please note that this course is given in a mixture of Mandarin Chinese and English.
課程進度	第1週 概論：時／空間效率分析與漸進式符號 第2週 一維與多維陣列（矩陣）、堆疊、佇列、雙向佇列、環狀佇列 第3週 最小與最大堆積、費氏堆積 第4週 單向鏈結串列、雙向鏈結串列、環狀鏈結串列、XOR鏈結串列、省略串列 ※ 第5週 第一次小考 第6週 二元搜尋樹、AVL樹、伸張樹 第7週 2-3樹、2-3-4樹 第8週 紅黑樹 ※ 第9週 期中考 第10週 B-樹及B+-樹 第11週 替罪羔羊樹、堆積樹 (treap)、vEB樹 第12週 雜湊表、綻放過濾器 ※ 第13週 第二次小考 第14週 無向圖、有向圖、先深搜尋 (DFS)、先寬搜尋 (BFS) 第15週 最短路徑演算法 第16週 伸展樹 (spanning tree) 第17週 總複習 ※ 第18週 期末考 Week 1. Overview: analysis of time--space efficiency and asymptotic notations Week 2. One-dimensional and multi-dimensional arrays, stack, queue, double-ended queue (deque), and circular queue Week 3. Min and max heaps, and Fibonacci heap Week 4. Singly and doubly linked lists, circular linked list, XOR linked list, and skip list ※ Week 5. Quiz 1 Week 6. Binary search tree (BST), AVL tree, and splay tree Week 7. 2-3 tree and 2-3-4 tree Week 8. Red-black tree ※ Week 9. Midterm examination Week 10. B-tree and B+-tree Week 11. Scapegoat tree, treap, and van Emde Boas (vEB) tree Week 12. Hash table and bloom filter ※ Week 13. Quiz 2 Week 14. Undirected graphs, directed graphs, depth-first search (DFS), and breadth-first search (BFS) Week 15. Shortest path algorithms Week 16. Spanning trees Week 17. Review ※ Week 18. Final examination
評量方式與標準	※ 期中考30% ※ 期末考30% ※ 小考20% ※ 作業與課堂參與20% ※ Midterm examination: 30% ※ Final examination: 30% ※ Quizzes: 20%, 10% each ※ Homework assignments and in-class participation: 20%
使用教材、參考書目或其他	【遵守智慧財產權觀念，請使用正版教科書，不得使用非法影印教科書】 使用外文原文書：是 Textbook (mandatory) ※ Thomas Cormen et al., Introduction to Algorithm, 3rd edition, MIT Press, 2009. References (optional) ※ Erik Demaine, MIT Course 6.851 "Advanced Data Structures," 2012. Available at: https://courses.csail.mit.edu/6.851/spring12/scribe/2012scribes.pdf ※ Sukhamay Kundu, Advanced Data-structures & Algorithm Analysis, 2011. Available at: https://www.csc.lsu.edu/~kundu/dstr/notes.html ※ Gerth Stolting Brodal, Advanced Algorithms - Data Structures, 2011. Available at: http://tildeweb.au.dk/au121/aa11/
課程諮詢管道
備註	* 如疫情發生變化，為各位同學健康著想，採取全遠距教學，並將線上點名。 * 如需遠距教學，將採用Google Meet進行：https://meet.google.com/ckr-rsjc-nbv * 線上Office hours採用Facebook社團，以及Messenger即時問答進行。