Algorithm hw#7

Prob. 15-5
Ex. 15.4-5

繳交期限是 11/04 下午五點前
本次作業遲交, 會打7折...@@

太晚開始念了, 覺得應付期中考有點來不及
明天早上要去清大交作業和拿回改完的hw6

Ex 15.4-5

這題首先要了解什麼是Longest Common Subsequence （ LCS ）演算法:

http://www.csie.ntnu.edu.tw/~u91029/LongestCommonSubsequence.html

這個演算法主要是用動態規劃(DP)去做, 可以找出"兩段序列"的"最長共同子序列"

應用在像是DNA比對等領域

本題要求出一個序列的"最長單調遞增"子序列

做法是將該序列S進行sorting(O(nlogn))得到S', 

再將S與S'去跑LCS(O(n^2))即可求得

參考網址:

https://sites.google.com/site/clrssolutions/home/chapter15

http://www.roading.org/algorithm/introductiontoalgorithm/%E6%9C%80%E9%95%BF%E5%8D%95%E8%B0%83%E5%AD%90%E5%BA%8F%E5%88%97%E9%97%AE%E9%A2%98.html

Prob 15-5

這題題目很長,我先參考了LCS教學視頻和Edit Distance教學視頻:

還有參考這個pdf

大概心理有個底之後才開始寫, 然後大概寫了2-3個小時