Algorithm lecture 4

這章節主要在探討Recurrence 和 Divide and Conquer的關係

divide and conquer有三部曲，顧名思義 divide conquer 還有一個combine。

Divide -> partition array into 2 subarrays around pivot x.

Conquer -> recursively sort 2 subarrays
Combine -> Trivial
這時一定很好奇與recurrence有什麼關係。這關係可大的。以merge sort 做例子。首先，先把一個array拆成兩個array。再把拆出來的array再一次做分解。一直分解到最底層之後開始比較。比較完之後將結果回傳。回傳之後的值再做結合與整理。最後得到由小到大或由大到小整理好的一個array。
解決recurrences有三種方法。

1.substitution method
step1:
Guess the form of the solution.
step2:Use mathematical induction to find the constants and show that the solution works.

2.recursion-tree

3.master method

T(n) = aT(n/b) + f(n)

在課本4.1中，舉了一個生活中的例子，用divide and conquer來解決。寫了兩個function。前面那個沒有用到遞迴的概念，但後面的有。然後分析了用遞迴的比較迅速。4.2是說matrix multiplication 與 Strassen’s algorithm的關係。這部份在我下面附上的筆記裡有。後面就講上面所說的三個方法。第一個substitution method。重點就是在「猜」。猜出答案當然也需要經驗跟一些判斷的依據。這部份有舉一個例子來表現他猜的功力。畫遞迴樹這部份在我下列附的筆記裡有詳細說明。最後的master method，根本是數學的套公式。配對的功力，筆記也寫的很詳細，沒什麼特別技巧。

以上小弟分享心得，大大們請多多指教。

徵才講座 麥肯錫 微軟

上個月，學校辦了很多徵才活動的演講。雖然我才大二，離我要畢業還有兩年。但兩年很快就到了。一個優秀的人才是需要未雨稠繆的！才別人都還在玩耍時，我需要快快為自己的未來做規劃。

麥肯錫是一家我很嚮往的公司。他主要是一家顧問公司。提供顧問給他的顧客們。幫他的顧客規劃出一套經營方式或是分析市場趨勢...等。這家公司以前是大學生們畢業之後最想要加入的公司。為什麼我說是以前呢？因為現在最夯的是Google。前陣子，我非常著迷大前延一的書。這位大前先生的生活讓我很嚮往。在國際間飛來飛去，見識到不同的人，看到許多平常人沒看過的事情。雖然他擅長的是理工方面，但他還是勇於挑戰自己不熟悉的一個領域。這股勇氣讓我十分欣賞跟敬佩。讓我也開始研究什麼事麥肯錫。

這場講座，麥肯錫清楚的表達了他們需要的人才。最重要的是「解決問題的能力」。這十分的抽象，也不是容易理解的。對一個大學生來說，什麼是好的解決問題的能力。顯然成績代表了一切。唯有從這個可以判斷一個大學生的能力。成績好代表你有良好解決問題能力。成績不好，除非有驚人的課外活動表現，不然也很難說服別人錄取你。當天麥肯錫也有很多他們的員工來跟我們分享他們在麥肯錫裡的工作心得。在介紹自己的背景時，清一色都是台大的學生。不只是台大生，每個在台大裡還名列前茅，書卷獎、雙主修...等。看來我的夢想不是短時間可以達成的。我沒有念台大，功課也不是名列前茅，更沒有優秀的課外表現。我還需要多多磨練。

另一場微軟的實習講座，就沒有這麼嚴苛的篩選條件。他們只看你的履歷表，六百字之內你要說服他讓你參加他們的實習。他們實習的工作內容有分三項，行政，促銷，技術研發。一個禮拜至少要到公司兩天。對我來說是非常困難的。因為轉學的關係，我的學分數超少。大三一定要面臨超修的問題。每個禮拜還要撥出兩天實習，幾乎是不可能。不過這也讓我有個目標，今年繼續努力，期許自己明年可以參加。微軟表達，他們所做的是種社會責任。幫這個社會培育人才。不像其他公司只有短短兩個月的暑期實習。取而代之的是長時間的教學，一套完整的訓練內容。在一年之後他們的實習生都會有顯著的成長。對未來的履歷表也會是一大加分，因為有微軟幫你背書。

聽完這兩家外商公司的講座。我覺得很快就要面臨就業問題了。還需要多加把勁才能進這些厲害的公司實習，甚至是去工作。加油！