資料結構
Data Structures
學期
113-2
學分
3
學分
當期課號
517502
永久課號
MGIF10008
開課單位
資訊管理與財務金融系
授課教師
徐熊健
校區
光復
類別
必修
上課時間表
| 節 | 週一 |
|---|---|
9 17:30–18:20 | 資料結構 M101 3 節連堂 |
A 18:30–19:20 | |
B 19:30–20:20 |
* 根據陽明交大上課時間表所列
概述
This course is aimed at preparing the students with basic computing theory, representation schemes and solution methods through programming practice and implementation.
先修科目
Basic computer programming skills
教學方式
https://sites.google.com/view/sjshyudsimf FB: ds113_imf_nycu
評分方式
35% Programming assignments 25% Midterm 25% Final 15% In-class participation
課程大綱
- Introduction
- Arrays
- Programming tool introduction
- Stack
- Queue
- Linked Lists
- Tree
- Midterm Exam.
- Graphs
- Sorting
- Final Exam.
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | Introduction/Prerequisite Definitions of Data Structures and Algorithms, Flow chart of programming, Selection sort. Please join the FB club: ds113_imf_nycu to receive the timely news. |
| 第 2 週 | Performance evaluation Simplifying functions Performance analysis: Big-O Recursion |
| 第 3 週 | Performance analysis: Omega and Theta Optimal algorithms: defition and examples Passed by value, address Simple array operations: transpose, addition, multiplication |
| 第 4 週 | Magic squares Knight tours Addressing in 1/2/3-d arrays |
| 第 5 週 | Addressing in k-d arrays Stack: Concept, stack frame, array implementation, push/pop Balanced parentheses Rat in a maze: data structures |
| 第 6 週 | Rat in a maze: algorithm (try and error) Program demonstration Genarate Maze randomly Arithmetic expressions: infix/postfix/prefix Transformation from infix to postfix: Examples |
| 第 7 週 | Transformation from infix to postfix/prefix Transformation from postfix to prefix Transformation from prefix to postfix struct node |
| 第 8 週 | Linked lists Insertion, deletion, search in singly linked list Linked stack, linked queue Conctenating two linked lists Inverting linked list Circular lists Circular linked lists with header nodes Polynomial addition using linked lists |
| 第 9 週 | Doubly linked list Doubly/circular linked list with header node Sparse matrix Trees: definition and terminologies Generalized list for trees Left-child-right-sibling Binary trees |
| 第 10 週 | Midterm Exam |
| 第 11 週 | Binary trees: full, complete, formal, skew Inorder/postorder/preorder traversal Binary search tree: insertion BST+inorder-traversal ==> sorted sequence |
| 第 12 週 | Binary search tree: Deletion Non-recursive search in BST Non-recursive traversal: inorder/preorder/postorder Level-order traversal Copy/Equality/Counting nodes of binary trees Determine a binary tree by (infix, prefix) |
| 第 13 週 | Determine a binary tree by (infix, postfix) AVL tree: insertion/deletion Height of AVL tree: O(logn) Properties of trees/binary trees Heap_motivation |
| 第 14 週 | Heap_insertion/deletion/sort Graph: terminologies Shortest path: Single source all destination/Dijkstra algorithm |
| 第 15 週 | Transitive Closure Minimum cost spanning trees AOV networks |
| 第 16 週 | Sorting I: Insertion/Quick sort, How fast can we sort; Sorting II: Merge/Heap sort, List/Table sort |
| 第 17 週 | Final Exam |
教科書
E. Horowitz, S. Sahni, and S. Anderson-Freed, Fundamentals of Data Structures in C (2nd Edition), Silicon Press, 2008, NJ. 徐熊健,資料結構與演算法,第五版,高立圖書512326,ISBN: 978-986-378-425-8
Office Hours
- 地點
- AB101
- 時間
- GH, Monday
- 聯絡方式
- sjshyu@gmail.com sjshyu@nycu.edu.tw