開課單位系所

 

  資訊系

 

 

課   程

█一般課程

(含必、選修)

□  通識課程

 

□教育學程

 

□軍訓課程

 

□体育課程

□(1人文 2社會

3物質 4生命

課號：

班次：

學分：3

名稱：圖形演算法特論 (Special topics on graph algorithms)

授 課 教 師

趙坤茂 (Kun-Mao Chao)

 

課程大綱內容(含進度、教科書或參考書目、成績評量方式)

Web site: http://www.csie.ntu.edu.tw/~kmchao/tree04spr

 

In this course, we will focus on algorithms for spanning trees. Some related topics will also be covered.

 

Prerequisites: Some basic knowledge on algorithm development is required. Background in approximation algorithms is welcome but not required for taking this course.

 

Outlines:

1.          Counting spanning trees

2.          Minimum spanning trees

3.          Shortest-paths tree

4.          Minimum routing cost spanning trees

5.          Communication spanning trees

6.          Optimal product-requirement communication spanning trees

7.          Optimal sum-requirement communication spanning trees

8.          Light approximate shortest-paths trees

9.          Light approximate routing cost spanning trees

10.      Steiner minimal trees

11.      Trees and diameters

12.      Other advanced topics

 

References:

1.          Class notes

2.          Related journal and conference papers

3.          Spanning Trees and Optimization Problems, by Bang Ye Wu and Kun-Mao Chao (2004), Chapman & Hall/CRC Press, USA.

 

Coursework:

Midterm exam (45%)

Oral presentation of selected topics or papers (40%)

Homework and class participation (15%)