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月28日 星期三
2016年12月19日 星期一
2016年12月15日 星期四
2016/12/15 Formal Language
- 有一個Assignment 2 , 老師說上課會講解, 不知道要不要交? 目前沒說要交
- 複習ch11
- 上ch12
-----------------------------------------------
- The Chomsky Hierarchy [ pdf ]
- Assignment 2 [ pdf ]
- Chap 12 Limits of Algorithmic Computation
- Some problems that cannot be solved by TMs [ pdf ]
-----------------------------------------------
以下是自己錄的重點提示
雖說是重點提示, 但其實已經涵蓋了今天3小時的上課內容
其實幾分鐘就可以講完的東西....
有時真是由衷希望老師可以好好備一下課....@@
ch11.4
ch12
以下是自己錄的重點提示
雖說是重點提示, 但其實已經涵蓋了今天3小時的上課內容
其實幾分鐘就可以講完的東西....
有時真是由衷希望老師可以好好備一下課....@@
ch11.4
ch12
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月13日 星期二
2016/12/14 Meeting
11/30
串媒體(Transmedia)時代的遊戲學習
- Pro-consumer
- Convergence(匯流)
- 串媒體巡航: 主題明確,動機強烈,線索清楚 ->學習效果好
- 讓學生做自己感興趣的主題, 就可以主動學習
- 數位時代: muititasking
12/14
- AppInventor: 視覺化程式設計工具
- Computational thinking 運算思維 歐巴馬
- Digital literacy
2016/12/14 Algorithm (Flow&Cut)
今天續上ch26
內容參考:
http://www.csie.ntnu.edu.tw/~u91029/Flow.html
http://www.csie.ntnu.edu.tw/~u91029/Cut.html
發了期末考考古題, 該找個時間來做做看
內容參考:
http://www.csie.ntnu.edu.tw/~u91029/Flow.html
http://www.csie.ntnu.edu.tw/~u91029/Cut.html
發了期末考考古題, 該找個時間來做做看
2016年12月12日 星期一
2016年12月11日 星期日
2016/12/11 EngNovels
有感於練托福的時候一直覺得沒什麼進步,
最近又把Gone with the wind的英文小說拿出來看
裡面有些段落寫得非常棒, 完全讓我感受到英文構句之美
很想把那些段落拿出來當作材料, 好好拆解練習一下
開始EngNovels這一系列, (不定期更新)
基本上是把喜歡的段落念過一次然後嘗試中翻英
我英文並沒有太好, 但就只是練習~
- - -
Gone with the wind
Ch1
這一段是在形容女主角郝思嘉的長相, 用了非常生動的文學修辭
看完這段很有回到中學寫作課的fu
Delicate KK[ˋdɛləkət] 脆的，易碎的；嬌貴的
Aristocrat KK[æˋrɪstə͵kræt] 貴族
Descent KK[dɪˋsɛnt] 世系，血統[U]
florid /fl'ɔrəd/ (a.)華麗的,紅潤的
Irish KK[ˋaɪrɪʃ] 愛爾蘭人
Chin KK[tʃɪn] 頦，下巴
Jaw KK[dʒɔ] 下頜，下巴[C]
chin 通常是指最下方的那一小個特定區塊 而 jaw 大多是指兩側及整個區塊
hazel KK[ˋhez!] n.名詞 2. 淡褐色（尤指眼睛的顏色）[U]
bristly 1. 有鬃毛（如剛毛）的2. 林立的
starred vt.及物動詞 用星形物裝飾用星號標出
tilted IPA[ˈtɪltɪd] 傾斜的
thick KK[θɪk]
slanted KK[ˋslæntɪd] 1. 有傾向的，有偏向的
startling KK[ˋstɑrt!ɪŋ] 1. 令人吃驚的
oblique KK[əbˋlik] 斜的；傾斜的[Z]
magnolia KK[mægˋnolɪə] 1. 【植】木蘭；木蘭花[C]
women KK[ˋwɪmɪn]
bonnet KK[ˋbɑnɪt] n.[C] 可數名詞 （有帶子的）女帽，童帽
veil KK[vel] 面紗，面罩[C]
mitten n.[C] 可數名詞1. 連指手套
----
這一段是郝思嘉向衛希禮告白的經典橋段
(然而衛希禮即將要娶她的表妹了)
郝思嘉是個富有生命活力.驕傲.個性鮮明的女性,
她喜歡衛希禮, 也以為衛希禮一定同樣喜歡她(畢竟她這麼受歡迎)
衛希禮是個不切實際.充滿詩歌與幻夢的理想派
但她沒有任何靈性與慧根可以了解衛希禮的想法
但她不在乎----她只想要得到她要的, 像個任性的小孩
衛希禮能夠欣賞郝思嘉那與他截然不同的個性
但他也知道, 郝思嘉不是他想要共度一生的對象,
假如他們真的結婚, 雙方都不會開心的
2016/12/9 Machine Learning
7.1.5 Computational Learning
7.2 Relevance Vector Machine(RVM)
參考:
7.2 Relevance Vector Machine(RVM)
參考:
- http://vbie.eic.nctu.edu.tw/technical.php?index=41
- http://www.cmlab.csie.ntu.edu.tw/~cyy/learning/tutorials/RVM.pdf
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))
Floyd-Warshall是解決任意兩點間的最短路徑的一種演算法，可以正確處理有向圖或負權（但不可存在負權迴路)的最短路徑問題。
參考: http://www.csie.ntnu.edu.tw/~u91029/Path2.html
另從11:10開始有一堂助教講解 midterm考題
---
以下改寫自wikipedia:
最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖中兩結點之間的最短路徑。算法具體的形式包括：(前三個是Single Source(ch24), 最後一個是All Pairs(ch25))
- 確定起點的最短路徑問題 - 即已知起始結點，求最短路徑的問題。適合使用Dijkstra算法。
- 確定終點的最短路徑問題 - 該問題等同於把所有路徑方向反轉的確定起點的問題。
- 確定起點終點的最短路徑問題 - 即已知起點和終點，求兩結點之間的最短路徑。
- 全局(All Pairs)最短路徑問題 - 求圖中所有的最短路徑。適合使用Floyd-Warshall算法。
最常用的演算法有：
- Dijkstra算法 (Ch24.3)
- A*算法
- Bellman-Ford算法 (Ch24.1)
- SPFA算法（Bellman-Ford算法的改進版本）
- Floyd-Warshall算法 (Ch25.2) Time: O(n^3) Space:O(n^2)
---
以下改寫自 http://www.csie.ntnu.edu.tw/~u91029/Path2.html和wikipedia:
以下改寫自 http://www.csie.ntnu.edu.tw/~u91029/Path2.html和wikipedia:
Floyd-Warshall是解決任意兩點間的最短路徑的一種演算法，可以正確處理有向圖或負權（但不可存在負權迴路)的最短路徑問題。
2016年12月8日 星期四
2016/12/8 Formal Language
Algorithm hw#12
複習一下: 最小生成樹 (MST)
唯一性
最小生成樹在一些情況下可能會有多個。例如，當圖的每一條邊的權值都相同時，該圖的所有生成樹都是最小生成樹。
如果圖的每一條邊的權值都互不相同，那麼最小生成樹將只有一個。
proof:
唯一性
最小生成樹在一些情況下可能會有多個。例如，當圖的每一條邊的權值都相同時，該圖的所有生成樹都是最小生成樹。
如果圖的每一條邊的權值都互不相同，那麼最小生成樹將只有一個。
proof:
- 假設有兩個MST A,B, 有一條edge屬於A而不屬於B, 令為ek,
- (ek聯集B)必會形成一個cycle C, 此環C中, 任意取走一條邊, 仍然兩兩連通
- C中必存在一個邊em,權重大於ek,
- 表示B如果用ek取代em, 會形成一個更小的生成樹, 但這跟一開始的assumption相矛盾
環定理cycle property
對於連通圖中的任意一個環 C：如果 C中有邊 e的權值大於該環中任意一個其它的邊的權值，那麼這個邊不會是最小生成樹中的邊
| hw1 | hw2 | hw3 | hw4 | hw5 | hw6 |
| 70 | 100 | 100 | 100 | 85 | 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
參考:
- http://www.csie.ntnu.edu.tw/~u91029/Path.html#4
- https://zh.wikipedia.org/wiki/%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95
已知起始點, 由起始點慢慢長出最小生成樹
這個演算法是通過為每個頂點 v 保留目前為止所找到的從s到v的最短路徑來工作的。
對於不含負權的有向圖，這是目前已知的最快的單源最短路徑演算法。
演算法維護兩個頂點集合 S 和 Q。集合 S 保留所有已知最小 d[v] 值的頂點 v ，而集合 Q 則保留其他所有頂點。集合S初始狀態為空，而後每一步都有一個頂點從 Q 移動到 S。這個被選擇的頂點是 Q 中擁有最小的 d[u] 值的頂點。當一個頂點 u 從 Q 中轉移到了 S 中，演算法對 u 的每條外接邊 (u, v) 進行拓展。
2016/12/6 TOEFL
聊了很多，都沒練到題目啊啊啊。
聊完得到一個結論:
所有的煩惱都是自找的。
我們不需要菩提樹，去證明菩提的存在。
也不需要明鏡台，當然更不需要滿滿的大平台。
因為明鏡就在我們的心中。
「空」的境界，物我兩忘。
放下我執。
張懸的歌詞裡有一句: 「其實你擔心是你自己」
生命自有它的去處，其實真正令我們放不下的，
都不是別人，而是我們自己的執念。
聊完得到一個結論:
所有的煩惱都是自找的。
我們不需要菩提樹，去證明菩提的存在。
也不需要明鏡台，
因為明鏡就在我們的心中。
「空」的境界，物我兩忘。
放下我執。
張懸的歌詞裡有一句: 「其實你擔心是你自己」
生命自有它的去處，其實真正令我們放不下的，
都不是別人，而是我們自己的執念。
2016年12月4日 星期日
2016年12月3日 星期六
反省
我覺得在學校念書， 其實沒有什麼太花俏的技巧，就是能夠靜下心來， 不問結果的踏實準備。
我自己其實是有感覺到，隨著年紀增長，人其實是很難像年輕的時候那樣專心的。隨著年齡， 腦力有變差嗎? 我覺得沒有， 至少就我現在這個歲數沒有，但專注度絕對有差。
為了應付社會以及周遭人事的複雜，我們必須眼觀四面、耳聽八方， 思考變得比較周全(複雜)。而思考的複雜，會變得很難專心吞下接收到的東西。
對知識的功利心，讓我們去想：「學這個我可以賺到多少錢，可以獲得多少讚美? 有沒有更容易拿分的方法?」而不是想: 「不管我考幾分，理解這些真的很有趣」。
樂在其中的重點就是"無我"
拿掉自我批判，只享受當下。
在這個沒有過去也沒有未來的當下，在這個斷面所產生的心流，
就是專注力的泉源。
這學期，我忘記了這些我早就知道的事。
以上是我的反省。
生命是長期而持續的累積。
生命是長期而持續的累積。
2016年12月2日 星期五
2016/12/2 Machine Learning
今天上到7.1.4的部分,
講完SVM的數學, 再講到SVM和logistic regression的error function有很高的相似性
SVM是minitor那些分錯的點, 落在margin內的點, 讓他們最少化
logistic regression則是用現有數據點算一個迴歸線, 基本上概念是很像的,
因為迴歸線周圍的點也不會剛好在迴歸線上, 也可以視為, 迴歸線周圍有一個margin
講完SVM的數學, 再講到SVM和logistic regression的error function有很高的相似性
SVM是minitor那些分錯的點, 落在margin內的點, 讓他們最少化
logistic regression則是用現有數據點算一個迴歸線, 基本上概念是很像的,
因為迴歸線周圍的點也不會剛好在迴歸線上, 也可以視為, 迴歸線周圍有一個margin
2016/12/2 Algorithm
今天睡過頭...orz
看完ilms上的"期中教學調查建議與回覆"真的快被嚇死了
這個老師到底有多認真啊....讓我好慚愧@@
你寫一句他回3句...我覺得老師比我還要認真....
不拿出國高中時的念書態度真的不行了
machine learning...就先放著等興趣自然回復好了
本人玻璃心, 經不起低分的打擊啊~~!!
看完ilms上的"期中教學調查建議與回覆"真的快被嚇死了
這個老師到底有多認真啊....讓我好慚愧@@
你寫一句他回3句...我覺得老師比我還要認真....
不拿出國高中時的念書態度真的不行了
machine learning...就先放著等興趣自然回復好了
本人玻璃心, 經不起低分的打擊啊~~!!
2016年11月29日 星期二
2016/11/30 Algorithm
Hw 23-1, 23.2-4
想不到這麼快到了學期末，作業總成績要拿滿分似乎不是太難，只要有按時寫按時交
問題應該是考試，必須把除了作業以外的題目作熟才行，否則很難應付考試的變化。
然後，我說，為什麼不考多次一點呀。
2016/11/29 TOEFL
今天彈了一首風中奇緣的主題曲XDD
然後聊了一堆有的沒的, 像是movie Avatar
還有阿拉伯女孩的"超不"女權主義思想
I feel that her speaking is improving along with time, unlike me :(
And she said coming to the US broadened her vision.
That's not her original expectation,
but now she thinks it's is really helpful and even necessary.
I totally understood and couldn't help admiring her.
But I won't find a guy with green card to get married just because of that. XD
And she said coming to the US broadened her vision.
That's not her original expectation,
but now she thinks it's is really helpful and even necessary.
I totally understood and couldn't help admiring her.
But I won't find a guy with green card to get married just because of that. XD
Maybe I need another one to chat with,
I mean, like, language exchange, to catch up.
- - -
Section 2: TOEFL TPO 02 (from http://toefl.kmf.com/speaking/tpo-1)
TPO 02
Question 4
audience effect
1.
Put on shoes faster
2.
Learn Type faster
Question 5
Field trip
exhibition
1.
find a replacement
2. exhibition
first
2016年11月28日 星期一
2016/11/28 Pervasive Computing
今天開始分組上台報告
報告所涵蓋的內容大致如下:
老師會非常頻繁的打斷.問問題, 很像是在叮他研究生的報告
問題大致上都是長這樣:
報告所涵蓋的內容大致如下:
- 研究目的, 待解決問題
- 研究方法, 使用技術
- 使用的資料集(資料量,potential 問題)&前處理方式
- 實驗結果
老師會非常頻繁的打斷.問問題, 很像是在叮他研究生的報告
問題大致上都是長這樣:
- 用的資料有沒有問題? 是否有一些bias會造成結果不夠公正客觀?
- 使用技術是否可以達成研究目的? 為什麼用這個技術不用另外那個技術?
- 考驗講者對實驗流程和結果分析的理解程度 (就是在檢驗你有沒有認真看paper)
把paper看熟, 充分討論, 預想可能被問的問題, 這樣到時應該就ok
2016年11月26日 星期六
2016年11月25日 星期五
Formal Language_Assignment 1
其實作業都有解答了, 何必叫我們交呢?
1. hint: dfa的特色就是, 所有的{a,b}都要畫出來(即使是無意義的not-accepted),也就是一個state 都必須split出兩條線, 一條a一條b, 不能多也不能少
所以就連sink也要畫一條線寫a,b指向自己喔!!
(a)少畫了!!
2. hint:
(1) dfa不允許λ (2)dfa每條路都一定要走出去
8.
Pumpimg Lemma複習:
已知一個regular language L 有以下性質,
有一個數字m(此數字通常指dta的state數目)
若有一個string w屬於L且規定 |w| >= m
那麼w可以被拆成x,y,z三部分, let w=xyz
其中 |xy| <= m (規定的,這樣等下才能套用pigeon hole) 且 |y|>0 (y一定至少要一個字元)
則一個正規語言會滿足 : { w^i = x y^i z | i是任意正整數 } 全部必須屬於L
若違反了它, 就不是正規語言
Q. 證明L={a^nb^n}不是regular
(1) 假設L為regular
(2) 取一個m, 令m=n
(3) 因為|xy| 必須要<= m, 所以y落在a^n的區間
(4) 令y=a, x=a^5, z=a^(m-6)b^m
(5) w^i = x (y^i) z
(6) 當i>1時, 不符合language a^nb^n的形式, 違反Pumpimg Lemma, 所以L不是regular
所以簡單來說就是,
必須先找一個符合language格式的string w, 再取一個假設的正整數m
並且要保證 w的長度大於等於m, 再想辦法將w切成x,y,z 3部分, 改寫成wi = x y^i z的形式
最後只要能找到一個 i >=0 使得wi不符合 language的string格式,
就可以說它違反Pumpimg Lemma, 所以L不是regular
1. hint: dfa的特色就是, 所有的{a,b}都要畫出來(即使是無意義的not-accepted),也就是一個state 都必須split出兩條線, 一條a一條b, 不能多也不能少
所以就連sink也要畫一條線寫a,b指向自己喔!!
(a)少畫了!!
2. hint:
(1) dfa不允許λ (2)dfa每條路都一定要走出去
8.
Pumpimg Lemma複習:
已知一個regular language L 有以下性質,
有一個數字m(此數字通常指dta的state數目)
若有一個string w屬於L且規定 |w| >= m
那麼w可以被拆成x,y,z三部分, let w=xyz
其中 |xy| <= m (規定的,這樣等下才能套用pigeon hole) 且 |y|>0 (y一定至少要一個字元)
則一個正規語言會滿足 : { w^i = x y^i z | i是任意正整數 } 全部必須屬於L
若違反了它, 就不是正規語言
Q. 證明L={a^nb^n}不是regular
(1) 假設L為regular
(2) 取一個m, 令m=n
(3) 因為|xy| 必須要<= m, 所以y落在a^n的區間
(4) 令y=a, x=a^5, z=a^(m-6)b^m
(5) w^i = x (y^i) z
(6) 當i>1時, 不符合language a^nb^n的形式, 違反Pumpimg Lemma, 所以L不是regular
所以簡單來說就是,
必須先找一個符合language格式的string w, 再取一個假設的正整數m
並且要保證 w的長度大於等於m, 再想辦法將w切成x,y,z 3部分, 改寫成wi = x y^i z的形式
最後只要能找到一個 i >=0 使得wi不符合 language的string格式,
就可以說它違反Pumpimg Lemma, 所以L不是regular
2016/11/25 Machine Learning
有沒有"說一套做一套"的最佳典範?????!!!!!!
不是說觀念比較重要 推導細節不重要嗎???!!!!
那你的題目怎麼都是計算推導阿!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
怕影響GPA 目前正在考慮退選了....QQ
- - -
今天繼續上Ch6 Gaussian Process的Classification部分
Ch7.1 Maximum Margin Classifiers
不是說觀念比較重要 推導細節不重要嗎???!!!!
那你的題目怎麼都是計算推導阿!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
怕影響GPA 目前正在考慮退選了....QQ
- - -
今天繼續上Ch6 Gaussian Process的Classification部分
Ch7.1 Maximum Margin Classifiers
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. 結束時間的相反順序)
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月24日 星期四
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/22 TOEFL
Fang一早起來看起來很想睡的樣子 XD
所以我彈唱了一首 Bizarre Love Triangle給她聽
雖然彈得很不怎樣 (因為是我的晚上 我也很想睡 )
但她很捧場 說她醒了 還說早晨聽到很romantic XDD
今天練習了3題:
- - -
3. Read the passage and answer the question
The university has decided to cancel the student health center on campus.
The reason is that a new hospital has been opened recently in the local
community. Because the new hospital is very close to the campus and most
students can have convenient access to it, and also because the new hospital
comes with a lot of first class medical equipment, which the student health
center lacks, the student health center’s existence is not justified any more.
Also, the money saved by canceling the student health center will be used to
amplify the library storage
The woman expresses her opinion of the school’s cancellation of the
student health center. State her opinion and explain the reasons she gives for
holding that opinion. (60s)
2016年11月17日 星期四
Algorithm hw#10
| hw1 | hw2 | hw3 | hw4 | hw5 | hw6 |
| 70 | 100 | 100 | 100 | 85 | 100 |
| hw7 | hw8 | hw9 | hw10 | hw11 | hw12 |
| 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)
結束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)
Machine Learning hw#2
出了出了~~~~QQ
https://drive.google.com/open?id=0B57k_NHxboqhSFN0RUNiVGkwUEk
截止日期：2016/12/02 23:59
目前策略是先用sklearn寫一次跑答案, 再想辦法把它改成無sklearn的版本
助教說明錄音檔(.aac)
https://drive.google.com/open?id=0B57k_NHxboqhSVFCNnpDbWk1Vms
2016/11/17 Formal Language
今天的課程內容十分重要
- - -
8.1
{a^n b^n}{ww^R} 不是regular, 是context-free
{a^n b^n c^n}{ww} 不是context-free, 用pumping lemma證, 但可被turing machine所接受
9.1
所謂algorithm就是一個會停的turing machine
圖靈機: https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA
為一種數學邏輯機，可以看作等價於任何有限邏輯數學過程的終極強大邏輯機器。
現在電腦的組成就是一種圖靈機。
圖靈機是比pushdown automata更強的一種邏輯器,
它可以處理到REC Language以內的問題。
也就是說, REC Language以內的問題, 是電腦可以解的問題。(Fig 11.4,11.5)
| Machine | Language |
| finite state automata(nfa) | Regular |
| pushdown automata(npda) | Context-Free (CF) |
| turing machine | Recursively enumerable (RE) |
- 何謂deterministic?
指所有alphabet可能路徑, 最多都只有一條
例如 alphabet = {a,b}
每個state最多只會有一條a, 一條b
- 何謂halt?
在TM中, halt states 指的是到達了一個transition state沒有定義的state, 那麼就會終止了
2016/11/17 Formal Language
8.1
{a^n b^n}{ww^R} 不是regular, 是context-free
{a^n b^n c^n}{ww} 不是context-free, 用pumping lemma證, 但可被turing machine所接受
9.1
所謂algorithm就是一個會停的turing machine
圖靈機: https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA
為一種數學邏輯機，可以看作等價於任何有限邏輯數學過程的終極強大邏輯機器。
現在電腦的組成就是一種圖靈機。
圖靈機是比pushdown automata更強的一種邏輯器,
它可以處理到REC Language以內的問題。
也就是說, REC Language以內的問題, 是電腦可以解的問題。(Fig 11.4,11.5)
2016年11月16日 星期三
2016/11/15 TOEFL practice
2016.11.15
Section
one: A memorable trip.
Section two: TOFEL
exercise
1. Choose one of your favorite methods to relax and explain why it is
your favorite.
Please include specific details in your explanation. (45s)
2. Some students prefer the internet-based teaching. Others prefer to
study in traditional classrooms. Which method of studying do you prefer or why?
(45s)
訂閱：
文章 (Atom)