資料結構與圖論演算法

Data Structures and Graph Algorithms

學期

115-1

學分

3 學分

當期課號

536708

永久課號

SCMA30018

開課單位

應用數學系

授課教師

官大智

校區

光復

類別

選修

上課時間表

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

概述

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

先修科目

C/C++ 或 Java 程式設計.

教學方式

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

評分方式

每 1-2 周以實際應用為主, 講解以及練習使用適合的資料結構.

週次計畫

週次	主題
第 1 週	review C/C++ programming: subprogram parameter passing, etc.
第 2 週	review: 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 arithmetic expressions.
第 7 週	stack and tree: evaluation of arithmetic 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 basic 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.

教科書

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

Office Hours