Trees Kun-Mao Chao (趙坤茂) Department of Computer Science and Information Engineering National Taiwan University, Taiwan E-mail: kmchao@csie.ntu.edu.tw WWW: http://www.csie.ntu.edu.tw/~kmchao
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: http://www.csie.ntu.edu.tw/~kmchao/tree07spr
Coursework: Two midterm exams (35% each) Oral presentation of selected topics or papers (20%) Homework and class participation (10%)
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
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
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
元宵燈謎 (字謎) 路上行人走，小月照其上 四個人搬木頭 日落半林中 太陽掛在樹頂上 李字少了木，不作子字猜 百年前是草，百年後是木 才字多一撇，禾字少一撇，大字多一豎，本字減一橫 四個人搬木頭 日落半林中 太陽掛在樹頂上 李字少了木，不作子字猜 百年前是草，百年後是木 刮目相看 草木之中有個人 竹林深處有僧家
元宵燈謎 (字謎) 路上行人走，小月照其上 趙 四個人搬木頭 杰 日落半林中 東 太陽掛在樹頂上 果 李字少了木，不作子字猜 一 路上行人走，小月照其上 趙 才字多一撇，禾字少一撇，大字多一豎，本字減一橫 木 四個人搬木頭 杰 日落半林中 東 太陽掛在樹頂上 果 李字少了木，不作子字猜 一 百年前是草，百年後是木 葉 刮目相看 木 草木之中有個人 茶 竹林深處有僧家 等
更多樹謎 森 (猜台灣地名) 籬笆 (猜台灣地名) 一條狗行經獨木橋就不叫了(成語) 水中浮木 (猜人名，以閩南語構思) 守株待兔
更多樹謎 森 (猜台灣地名) 樹林 籬笆 (猜台灣地名) 木柵 一條狗行經獨木橋就不叫了(成語) 過目不忘 森 (猜台灣地名) 樹林 籬笆 (猜台灣地名) 木柵 一條狗行經獨木橋就不叫了(成語) 過目不忘 水中浮木 (猜人名，以閩南語構思) 劉邦 守株待兔 柳
回應與挑戰（一） 同學：停電，猜一字 趙老：．．． 同學：請用英文想 同學：停電是black out 趙老：原來是黑出，黜！
回應與挑戰（二） 趙老：我在水中，猜一字 同學：．．． 趙老：請用英文想 趙老：是一個英文字，I in the WATER 同學：原來是WAITER！