Algorithmics (演算法)

Lecturer: 江振瑞
Teacher Assistant
s (TAs): 黃郁誠 廖基豪 黃信文 陳思源 郭正屏 陳昱明 姚克翰 陳彥仲 潘邦睿
LMS System: (演算法B)
Time: (中大資工: 週二 15:00~16:50 週四 10:00-12:00) (福師大資工:  週四 14:00-15:50 週五下午14:00-15:50)
Place: (中大資工: 週二 E6-A2O7 週四 E6-A208) (福師大資工: 資策會教室)
TA Class: 週四 10:00-12:00 (福師大資工:  週五下午14:00-15:50)
TA Page:  http://acan.csie.ncu.edu.tw/alg2014/
Scoring:
TextBook:

Reference Books: Syllabus:  
A graph
D. 針對以下的給定圖,列出Bellman-Ford最短路徑演算 法執行過程, 說明Bellman -Ford最短路徑演算法如何檢查出一給定圖具有負循環(negative-weight cycle)。

E. 證明Bellman-Ford最短路徑演算法可以檢查出一給定圖具有負循環(negative-weight cycle),也就是累積邊加權為負的循環。
F. 藉由動態規劃演算法來替一矩陣鏈(其維度序列為 <5, 20, 8, 60, 10, 12> )加上括號來最佳化矩陣相乘次數。
G. 寫一個演算法來解決最長單調遞增子序列問題(the longest monotonically increasing subsequence problem),並分析演算法的時間複雜度。
H. (編輯成本問題)令兩字串為 A=a1a2...am 與 B=b1b2...bn,我們可以藉由以下三種編輯指令來將A字串轉換成B字串:
1.從A字串中刪除一個字元
2.從A字串中插入一個字元
3.將A字串中的其中一個字 元替換成另一個字元
假設上述指令分別花費成本3、2和 1,編寫一個動態規劃演算 法求出將字串A轉 換為字串B的最小成本。另外,根據這個演算法,寫出最小成本指令過程將字串GTXYT轉換成字串 TXGYCT。
Downloads:
Links:

Back to My Home