資料結構與圖論演算法

Data Structures and Graph Algorithms

學期

110-1

學分

3 學分

當期課號

5418

永久課號

IAM5689

開課單位

應用數學系

授課教師

官大智

校區

光復

類別

選修

上課時間表

* 根據陽明交大上課時間表所列

概述

能以適合之資料結構撰寫更有效率之程式, 並為將來學習演算法打好基礎.

先修科目

C/C++ 或 Java 程式設計

教學方式

每 1-2 周以實際應用為例, 練習一個或多個常用的資料結構. 上課時, 除講授資料結構之理論外, 學生必須立即在電腦教室撰寫程式, 完成主要部分, 並在課餘時間完成整個程式.

評分方式

每 1-2 周以實際應用為主, 練習一個常用的資料結構.

週次計畫

週次	主題
第 1 週	review C/C++ programming, program compilation, subprogram; parameter passing
第 2 週	C struct, C++ class; new data types or objects, e. g. dates
第 3 週	array; find shortest path in a maze
第 4 週	array; sparse matrix operations
第 5 週	array; sparse matrix operations
第 6 週	stack; evaluation of arithematic expressions
第 7 週	stack and tree; evaluation of arithematic expressions and assignment statements
第 8 週	tree; segment tree for range queries
第 9 週	tree; segment tree for range queries
第 10 週	tree; Huffman code, encode
第 11 週	tree; Huffman code, encode and decode
第 12 週	graph; representation and operations
第 13 週	graph; minimum spanning tree
第 14 週	dynamic set; minimum spanning tree
第 15 週	graph; shortest path and Dijkstra's algorithm
第 16 週	graph; matching of bipartite graphs
第 17 週	weighted graph; maximum weight matching of bipartite graphs
第 18 週	final test

教科書

書名: Fundamentals of Data Structures 作者: Horowitz, Sahni, and Metha 出版社: Silicon Press

Office Hours