這裡是我做102-2 PDSA HW2的筆記，一共有三個部分：
HW2-1 Perform doubling test on 3-sum algorithms
- 先開啟一個NetBeans Project (需要幫助者，請參考 HW1的筆記)
- 先加入作者的library files (建議使用這個方式)
- 開一個新的source檔(MyDoublingRatio.java)
- copy作者提供的程式碼來進行修改
- 修改重點：class name需與檔名一致，constructor的function name也要一致)
- 照理說，這樣就可以直接執行了，可在MyDoublingRatio.java的視窗中，點選右鍵，執行'Run File'，就會看到如下的畫面：
[註：'Run File'的意思就是執行這個java檔的main function，請注意，'Run File'無法吃進command arguments，如果有參數要用args傳進來，只能改用'Run Project')
如果你已經成功跑出類似的畫面，這時請注意看一下程式碼，main function中的for loop，理論上不會停止.....所以，等你覺得執行夠了，就按終止按鈕停下程式。
從上面的執行結果看來，所呼叫的ThreeSum的確是個N^3的演算法。這時或許你會覺得奇怪，你又沒有實做ThreeSum的演算法，這個東西打哪來的?
請打開作者提供的library瞧瞧：
往下一直看，應該能順利看到ThreeSum.java，不僅如此，作者還實做了進階版的ThreeSum，也就是ThreeSumFast.java，把它打開來好好讀懂程式碼。對HW2-2與HW2-3的程式撰寫會有很大的幫助。
找到ThreeSumFast.java之後，請修改MyDoublingRatio.java來看看ThreeSumFast的時間複雜度吧!
Note 1: 過程中可沒想像中的順利，你應該和我一樣，碰到 "array contains duplicate integers"的exception的吧!? 仔細看一下作者寫的ThreeSumFast，的確有做duplicates的檢查，
請思考一下為何需要做檢查? 在HW2-1的繳交報告中討論。
Note 2: 為了能順利進行ThreeSumFast的時間分析，請利用作者準備的測試資料：
- http://algs4.cs.princeton.edu/14analysis/1Kints.txt
- http://algs4.cs.princeton.edu/14analysis/2Kints.txt
- http://algs4.cs.princeton.edu/14analysis/4Kints.txt
- http://algs4.cs.princeton.edu/14analysis/8Kints.txt
請修改你的MyDoublingRatio.java，不要讓程式自動產生資料(a[i] = StdRandom.uniform(-MAX, MAX);)，
改成用讀檔的方式吧! 你在HW1中學過了!
Note 3: 過程中，你將會非常訝異地發現，1Kints.txt還是有duplicates (至少我真的非常驚訝，承認這個事實之後，只好將其中重覆的數字找出來，修改一下)。請用編輯器打開它，將其中一個320032改成320033，應該就可以順利執行了。
Note 4: 撰寫HW2-1的過程中，可以特別練習一下static的用法，思考一個function加了static之後的意義為何? 使用上有何差異?
HW2-1需以報告的方式繳交到ceiba。報告請以word撰寫，內容以不超過一頁為限，
請將執行結果數據做成圖表(log-log plot)後呈現並討論。
HW2-2 Develop a liner algorithm for 2-sum problem
- 新增一個新的source檔 (MyTwoSumFast.java)
- Your class should have the following API:
public class MyTwoSumFast {
private static boolean haveNotSorted(int[] a) { }
private static boolean containsDuplicates(int[] a) { }
public static int count(int[] a) { }
public static void main(String[] args) { }
}
Note 1: 如果
count函式發現讀進來的數字
並未從小到大排列，請丟出exception (優先於下一個exception):
throw new IllegalArgumentException("array has not sorted in ascending order");
Note 2: 如果
count函式發現讀進來的數字
有重覆，請丟出exception:
throw new IllegalArgumentException("array contains duplicate integers");
