顯示具有 Algorithm 標籤的文章。 顯示所有文章
顯示具有 Algorithm 標籤的文章。 顯示所有文章

2016年12月28日 星期三

Final 日期

Pervasive Computing, 1/2放假, 所以應該是 1/9
1. Apriori
2. Prefix-Span
3. Decision Tree
4. Session06_SpatialData.pdf (pages 104~130)

5. Session07_MobileSpatial.pdf (all)

Formal Language, 1/12
全範圍

Algorithm, 1/11
全範圍

2016年12月14日 星期三

Algorithm hw#13



Prob. 25-1
Transitive Closure: 參考 http://acm.nudt.edu.cn/~twcourse/TransitiveClosure.html
簡言之就是走得到的所有連結, 所構成的一張圖

a. 當加進一條邊時,要怎樣更新Transitive Closure的boolean matrix, 在O(V^2)時間內
b. 舉例說明當加入一條邊到一張圖裡時, 不管用什麼演算法, update Transitive Closure的時間下限是V^2
c. 針對更新Transitive Closure給一個有效的演算法, 對一系列的n個insertion來說, 證明時間可以維持在O(V^3)

Prob. 31-1
大部分的電腦實施減法操作來驗證一個二進位整數是奇數或偶數, 且比"算餘數"的方法還快了一倍(時間減半)
此問題牽涉到binary gcd algorithm, 避免了在Euclid’s algorithm裡的餘數計算
a. 證明當a,b都是偶數時, (a,b)的gcd是(a/2,b/2) gcd的兩倍
b. 證明當a是奇數,b是偶數時, (a,b)的gcd是(a,b/2) 的gcd
c. 證明當a,b都是奇數時, (a,b)的gcd是((a-b)/2,b) 的gcd
d. 設計一個有效的binary gcd algorithm, 滿足a>=b, O(lg a)







2016年12月11日 星期日

2016/12/9 Algorithm (Floyd-Warshall)

Ch25. All-Pairs Shortest Paths 結束
參考: http://www.csie.ntnu.edu.tw/~u91029/Path2.html

另從11:10開始有一堂助教講解 midterm考題

---
以下改寫自wikipedia:

最短路徑問題是圖論研究中的一個經典算法問題,旨在尋找圖中兩結點之間的最短路徑。算法具體的形式包括:(前三個是Single Source(ch24), 最後一個是All Pairs(ch25))

  • 確定起點的最短路徑問題 - 即已知起始結點,求最短路徑的問題。適合使用Dijkstra算法。
  • 確定終點的最短路徑問題 - 該問題等同於把所有路徑方向反轉的確定起點的問題。
  • 確定起點終點的最短路徑問題 - 即已知起點和終點,求兩結點之間的最短路徑。
  • 全局(All Pairs)最短路徑問題 - 求圖中所有的最短路徑。適合使用Floyd-Warshall算法。

最常用的演算法有:

---
以下改寫自 http://www.csie.ntnu.edu.tw/~u91029/Path2.html和wikipedia:

Floyd-Warshall是解決任意兩點間的最短路徑的一種演算法,可以正確處理有向圖或負權(但不可存在負權迴路)的最短路徑問題。



2016年12月8日 星期四

Algorithm hw#12

複習一下: 最小生成樹 (MST)

唯一性
最小生成樹在一些情況下可能會有多個。例如,當圖的每一條邊的權值都相同時,該圖的所有生成樹都是最小生成樹。
如果圖的每一條邊的權值都互不相同,那麼最小生成樹將只有一個。
proof:

  1. 假設有兩個MST A,B, 有一條edge屬於A而不屬於B, 令為ek, 
  2. (ek聯集B)必會形成一個cycle C, 此環C中, 任意取走一條邊, 仍然兩兩連通
  3. C中必存在一個邊em,權重大於ek, 
  4. 表示B如果用ek取代em, 會形成一個更小的生成樹, 但這跟一開始的assumption相矛盾

環定理cycle property

對於連通圖中的任意一個環 C:如果  C中有邊  e的權值大於該環中任意一個其它的邊的權值,那麼這個邊不會是最小生成樹中的邊







hw1hw2hw3hw4hw5hw6     
7010010010085        
100



hw7          
hw8
hw9
hw10
hw11
hw12     
95*0.7
=67
100
100
80
87



2016年12月7日 星期三

2016/12/7 Algorithm (Bellman-Ford & Dijkstra's Algorithm)


Ch24.3 Bellman–Ford algorithm
參考: 
https://zh.wikipedia.org/wiki/%E8%B4%9D%E5%B0%94%E6%9B%BC-%E7%A6%8F%E7%89%B9%E7%AE%97%E6%B3%95



它的原理是對圖進行V-1次鬆弛操作,得到所有可能的最短路徑。其優於Dijkstra's Algorithm的方面是邊的權值可以為負數、實作簡單,缺點是時間複雜度過高,高達。

以鬆弛操作為基礎,估計的最短路徑值漸漸地被更加準確的值替代,直至得到最優解。
在兩個演算法中,計算時每個邊之間的估計距離值都比真實值大,並且被新找到路徑的最小長度替代。 

然而,Dijkstra's演算法以Greedy策略選取未被處理的具有最小權值的節點,然後對其的出邊進行鬆弛操作;而Bellman–Ford 演算法簡單地對所有邊進行鬆弛操作,共|V | − 1次,其中 |V |是圖的點的數量。在重複地計算中,已計算得到正確的距離的邊的數量不斷增加,直到所有邊都計算得到了正確的路徑。這樣的策略使得Bellman–Ford 演算法比Dijkstra's演算法適用於更多種類的輸入。

Ch24.3 Dijkstra's Algorithm
參考: 


已知起始點, 由起始點慢慢長出最小生成樹
這個演算法是通過為每個頂點 v 保留目前為止所找到的從s到v的最短路徑來工作的。
對於不含負權的有向圖,這是目前已知的最快的單源最短路徑演算法。

演算法維護兩個頂點集合 S 和 Q。集合 S 保留所有已知最小 d[v] 值的頂點 v ,而集合 Q 則保留其他所有頂點。集合S初始狀態為空,而後每一步都有一個頂點從 Q 移動到 S。這個被選擇的頂點是 Q 中擁有最小的 d[u] 值的頂點。當一個頂點 u 從 Q 中轉移到了 S 中,演算法對 u 的每條外接邊 (u, v) 進行拓展。



2016年12月2日 星期五

2016/12/2 Algorithm

今天睡過頭...orz

看完ilms上的"期中教學調查建議與回覆"真的快被嚇死了
這個老師到底有多認真啊....讓我好慚愧@@
你寫一句他回3句...我覺得老師比我還要認真....
不拿出國高中時的念書態度真的不行了

machine learning...就先放著等興趣自然回復好了
本人玻璃心, 經不起低分的打擊啊~~!!

2016年11月29日 星期二

2016/11/30 Algorithm

Hw 23-1, 23.2-4

想不到這麼快到了學期末,作業總成績要拿滿分似乎不是太難,只要有按時寫按時交

問題應該是考試,必須把除了作業以外的題目作熟才行,否則很難應付考試的變化。

然後,我說,為什麼不考多次一點呀。

2016年11月25日 星期五

Algorithm hw#11








2016/11/25 Algorithm

今天上22.3~22.4


22.3
DFS有四種edge類型, 分別是Tree,Back,Forward,Cross edge四種, 它有其priority

灰: 已有起始時間, 沒有結束時間(已起始, 未結束)
黑: 已結束
白: 未走到

當你由灰看到白, 那是tree edge
當你由灰看到灰, 是Back edge (其祖先尚未結束)
當你由灰看到黑, 可能是 Forward edge 或 Cross edge
比較起始時間, 較晚是Forward edge, 較早是Cross edge

以上是對有向圖而言,
對無向圖, 只有Tree,Back edge兩種

因為Back edge基本等同於Forward edge, 定義為Back edge
Cross edge不會存在, (這需要proof)
因為假若Cross edge存在, 表示這兩點在最一開始就是連通的,(因為無向)
那麼怎麼可能之前在拜訪黑點時, 沒有找到現在的這個灰點呢?
by contradiction 得證


22.4
Topological sort是一種排程方法, 描述一種"滿足等待關係"
其方法很簡單, 在做DFS時maintain一個stack, 對每一個結束的node,  當記錄結束時間時, 將此node丟進stack中, 再依序pop出來即是答案(i.e. 結束時間的相反順序)






2016年11月22日 星期二

2016/11/23 Algorithm

Ch21 Ackermann's function, g函數, 是一個成長率極高的函數, 它的反函數就是一個almost constant

Ch22 review graph, data structure of graph storage, BFS, DFS,
...

2016年11月17日 星期四

Algorithm hw#10

hw1hw2hw3hw4hw5hw6     
7010010010085        
100

hw7          hw8hw9hw10hw11hw12     
95*0.7
=67
100?




還差2次



Prob21-1,21-3




2016/11/18 Algorithm

今天上課2hrs
結束ch17, 開始ch21 data structure for disjoint set, 這章並不難
應用: 找出connected component

Original Disjoint
Make() => O(1) *n
Find()  => O(1) *f
Union() =>worst O(n) *(n-1)
=>worst O(n^2)

Weighted Disjoint
Make() => O(1) *n
Find()  => O(1) *f
Union() =>O(nlgn)
=>worst O(m+nlgn)
where m=n+f+(n-1), n:#Make f:#Find, m: #(Make,Find,Union)


2016年11月11日 星期五

Algorithm hw#9


17.2-3
9.1-1
deadline  11/18





9.1-1

參考: 

17.2-3

參考: 



寫了1.5hr


2016/11/11 Algorithm

今天繼續上ch17 Amortized Analysis
17.4 Dynamic Table
這節主要講一個動態的陣列, 它的容量會隨儲存量的多寡, 而有size上的自動變化
雖然看起來這種"動態"好像要花不少時間,
但它可以證明, 透過本章的"先付款"方法
(假設中線是最prefer的狀態, 超過中線付$2, 低於中線付$1)
可以控制每一步成本約是O(1),
其中Insert的成本小於等於3, Delete的成本小於等於2
而存款永遠都是正的(圖Figure 17.4)

2016年11月8日 星期二

2016/11/9 Algo midterm

今天考題,當然我沒猜到題目,但跟我在應考策略裡預估的狀況差不多。

有比去年考古題簡單,只是要拿高分還是很不容易。我空了第七題沒寫。第三題是最後五分鐘憑資料結構的印象盡量掰的。加分題沒準備到,沒有寫。

不確定會拿幾分。我自己估,大概是全班平均分數而已。

坐我隔壁的一直在打噴涕,好可怕。希望不要感冒。



Algo Midtrem考試策略

事前準備:

  • 根據有一堂助教講解課的補充, ch16 greedy可能會考跟OBST有關的問題
  • 作業題: 作業要做, 但不要走火入魔, 只有10%
  • Bonus: 應該考ch10-12自己讀部分, 但其實重要的只有ch12, 考你有沒有讀而已
  • Design的部分非常重, 幾乎占了50%以上, 無法穩穩拿分, 要靠臨場反應
  • 睡飽

其實我沒有花很多時間念

以這個老師的個性, 我推測不會考太多重複或過於類似的題目
所以念考古題應該會有用, 但也僅止於對考試模式的熟悉

雖然說細節扣分扣很重, 可是對我這種沒念得很細的人來說
反而是解題方向比較重要

換言之, 我覺得題目有"先看過, 先想過"
這件事情可能比花時間在追究細節還重要得多
畢竟是演算法"設計"
設計理念比表達方式重要

根據考古題的配分如下:
25% ch1-4 (big-O和解recurrence, 這個地方的分數一定要把握住)
30% ch6-9 (Sorting, 這裡會出現一些不在課本內的應用問題, 但是不算難!重點在分析time)
25% ch15-16 (DP和greedy, 這裡出現的多是課本後的例題, 但是很難, 不太容易想到)
10% hw 二選一 (個人覺得不會出太過複雜hw題,畢竟只是要考我們是否是自己寫的)
10% self-taught (ch10-12, 不難但是要看過, 否則沒分)

由此可以看出拿分的重點在25% ch1-4+10% hw
其他部分都要靠臨場,
10% self-taught則要靠運氣

- - -

考試策略:

  • 字寫得少而清楚, 能用數學表達盡量用數學表達
  • 多花時間理解題目和想演算法, 少花時間寫字
  • 任何演算法,  都要寫出(1)作法 (2)說明正確性, 以及(3)時間複雜度
  • 每一個chapter都有它的核心精神和概念, 想演算法的時候, 注意跟chapter主題的連結
  • 想的時候, 盡量簡化問題,不要複雜化問題
  • 細節可以最後再補, main idea要先有


- - -
以下為考古題題目&自己練習的解答




2016年11月6日 星期日

Algorithm hw#8





Ex. 16.1-4

Ex. 16.3-6

- - - 
這次作業比較簡單(Ex都比Prob簡單)
所以2個小時就寫完
其中16.1-4有參考:

- - - 




- - -


hw1hw2hw3hw4hw5hw6     
7010010010085        
100

hw7hw8hw9hw10hw11hw12     
70以下?





還差3次

2016年11月4日 星期五

Algorithm hw#7

Prob. 15-5
Ex. 15.4-5

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

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











Ex 15.4-5
這題首先要了解什麼是Longest Common Subsequence ( LCS )演算法:
這個演算法主要是用動態規劃(DP)去做, 可以找出"兩段序列"的"最長共同子序列"
應用在像是DNA比對等領域

本題要求出一個序列的"最長單調遞增"子序列
做法是將該序列S進行sorting(O(nlogn))得到S', 
再將S與S'去跑LCS(O(n^2))即可求得

參考網址:




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

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