Trees Kun-Mao Chao (趙坤茂)

Presentation on theme: "Trees Kun-Mao Chao (趙坤茂)"— Presentation transcript:

1 Trees Kun-Mao Chao (趙坤茂)
Department of Computer Science and Information Engineering National Taiwan University, Taiwan WWW:

2 About this course Course: Special topics on graph algorithms
We will focus on those tree-related algorithmic problems. In particular, spanning trees … Spring semester, 2007 Tuesday 10:20 – 13:10, 107 CSIE Building. 3 credits Web site:

3 Coursework: Two midterm exams (35% each)
Oral presentation of selected topics or papers (20%) Homework and class participation (10%)

4 Outlines Counting spanning trees Minimum spanning trees
Shortest-paths tree Minimum routing cost spanning trees Communication spanning trees Light approximate spanning trees Steiner minimal trees Trees and diameters Swap edges Tree splitting Other advanced topics

5 Our book on spanning trees
Spanning Trees and Optimization Problems, by Bang Ye Wu and Kun-Mao Chao (2004), Chapman & Hall/CRC Press, USA. Link to Amazon Link to CRC Press

6 Spanning Trees and Optimization Problems
S T O P ! Trees Optimization Problems & B.Y. Wu and K.-M. Chao CRC press, 2004 It’s available in NTU library now! Bang Ye’s ppt

7 元宵燈謎 (字謎) 路上行人走，小月照其上 四個人搬木頭 日落半林中 太陽掛在樹頂上 李字少了木，不作子字猜 百年前是草，百年後是木
才字多一撇，禾字少一撇，大字多一豎，本字減一橫 四個人搬木頭 日落半林中　 太陽掛在樹頂上 李字少了木，不作子字猜 百年前是草，百年後是木 刮目相看 草木之中有個人 竹林深處有僧家

8 元宵燈謎 (字謎) 路上行人走，小月照其上 趙 四個人搬木頭 杰 日落半林中 東 太陽掛在樹頂上 果 李字少了木，不作子字猜 一
路上行人走，小月照其上　　　 趙 才字多一撇，禾字少一撇，大字多一豎，本字減一橫 木 四個人搬木頭 杰 日落半林中　　　　　　　　　 東 太陽掛在樹頂上 果 李字少了木，不作子字猜 一 百年前是草，百年後是木 葉 刮目相看 木 草木之中有個人 茶 竹林深處有僧家 等

9 更多樹謎 森 (猜台灣地名) 籬笆 (猜台灣地名) 一條狗行經獨木橋就不叫了(成語) 水中浮木 (猜人名，以閩南語構思) 守株待兔

10 更多樹謎 森 (猜台灣地名) 樹林 籬笆 (猜台灣地名) 木柵 一條狗行經獨木橋就不叫了(成語) 過目不忘
森 (猜台灣地名) 樹林 籬笆 (猜台灣地名) 木柵 一條狗行經獨木橋就不叫了(成語) 過目不忘 水中浮木 (猜人名，以閩南語構思) 劉邦 守株待兔 柳

11 回應與挑戰（一） 同學：停電，猜一字 趙老：．．． 同學：請用英文想 同學：停電是black out 趙老：原來是黑出，黜！

12 回應與挑戰（二） 趙老：我在水中，猜一字 同學：．．． 趙老：請用英文想 趙老：是一個英文字，I in the WATER
同學：原來是WAITER！