102-2 PDSA HW2

這裡是我做102-2 PDSA HW2的筆記，一共有三個部分：

HW2-1 Perform doubling test on 3-sum algorithms

1. 先開啟一個NetBeans Project (需要幫助者，請參考 HW1的筆記)
2. 先加入作者的library files (建議使用這個方式)
3. 開一個新的source檔(MyDoublingRatio.java)
4. copy作者提供的程式碼來進行修改
5. 修改重點：class name需與檔名一致，constructor的function name也要一致)
6. 照理說，這樣就可以直接執行了，可在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");