102-2 PDSA HW4

HW4要讓大家畫畫圖，應該會很有趣!

1. 利用二維座標畫點

[goal]：利用StdRandom產生N個2D points (用Point2D的array來儲存)，再搭配StdDraw把這個N個點畫出來(radius= 0.01)

• 請大家練習使用Point2D這個物件，可以先宣告一個array來用

Point2D[] a = new Point2D[N];

• 利用for loop產生N個點的x,y座標：呼叫StdRandom.uniform();
• 練習用StdDraw畫圖 (把作者提供的StdDraw.java好好看看，有很多methods可以用來畫圖)，如：

StdDraw.filledCircle(a[i].x(), a[i].y(), 0.01);

• N=10的結果範例：

作者有幫大家寫一個存讀檔的功能：

按下File->Save，取檔名的時候加上合適的副檔名即可，如：e1.png

2. 將y座標最小的點用紅色標示

[goal]：練習使用compareTo，以及更換畫筆的顏色

• HW4的第二小題是要練習呼叫sort，請在Point2D物件中尋找合適的compareTo()或Comparator使用，目的是要找到y座標最小的點
• 改用紅色標示，可用StdDraw的setPenColor改顏色：

StdDraw.setPenColor(StdDraw.RED);

• 結果範例：

3. 將所有的點，用其與紅點的角度排序

[goal]：練習comparator的使用

• 參考作者投影片 p45-p47
• 輸出範例 (請注意此時的點編號，後續輸出繳交批改系統的時候，請用此時的點編號)

• 利用StdDraw.text()標數字的時候，可將y軸向上提高約0.03，避開黑點

4. 找出convex hull

• 參考作者投影片 p58, p59, p60, p61
• 畫圖範例

• 請將能產生上圖的程式(MyConvexHull.java)，繳交至ceiba
• MyConvexHull這個class的main function會從args[0]得到N，然後產生亂數 + 畫圖
• 上傳批改系統的MyConvexHull.java必須額外有以下function，這個function會吃進一個Point2D的陣列，回傳字串：0 1 2 4 7 9

public static String ConvexHullVertex(Point2D[] a) {}

Bonus

[goal]：Find the convex hull for each of the connected components (CC) in a set of N points

• 綠線：兩點之間的距離<0.1 (表示兩個點之間距離太窄，無法通過)
• 紅點：尋找convec hull時所用的p點 (y座標最小)
• 黑線：convex hull (只有CC內的點個數>=3的時候才需要找convex hull)

102-2 PDSA HW3

HW3-1. (30 points)

[題目] Write a stack client Parentheses that reads in a text file (file name is specified through standard input, args[0] ) and uses a stack to determine whether its parentheses are properly balanced.

先開一個新專案(HW3)，將作者提供的library加進來 (more)。

接著新增一個新的java source file (Parentheses.java)，題目已經明說要用stack來處理這個問題，可以直接使用作者提供的stacks (e.g. LinkedStack, ResizingArrayStack)，也就是說，這個作業直接寫main就好(把自己想成clients)。稍微比較一下LinkedStack.java與ResizingArrayStack.java的程式碼，兩個物件在宣告的時候都不用事先給stack size，也都接受generics (Generics: An essential characteristic of collection ADTs is that we should be able to use them for any type of data. more)。乍看之下，兩種implementation都不錯，優劣之處可參考作者的投影片p24)

就弄個String stack來用用吧! (也可以用Character stack試試)

接下來，從args[0]吃進檔名，開檔。檔案中應該只有一行，讀進來之後要切成一個個char。我是使用String物件中的toCharArray()，應該還有很多其他好方法。

實作過程中發現有幾個需要注意的地方：

1. 程式離開前要檢查一下stack是否清空? 會影響true/false
2. pop之前要檢查stack中是否有東西，避免產生exception

HW3-2. (55 points)

來到有名的Josephus problem。(可閱讀中文版比較有趣)

在這個作業中，要同時練習implementation (實作 circular queue)，也要練習當clients (寫main)。

BLAST revisit

上星期(2014/2/26)又到醫學院講述序列比對的重要觀念與操作細節
回想起去年上完課後寫下的文章，把它翻出來與大家分享。

今年，想藉機會進一步討論BLAST的e-values。

讓我們先用以下序列(query)做個試驗：

>FASTA format

MAHTTSLLSGASSAAASPLSSRQYSVASSPRLSGDIGRGLFAIVVLLLRMSSVYGVIDRL VVQTSSGPVRGRSVTVQGREVHVYTGIPYAKPPLDDLRFRKPVPAEPWHGVLDATRLPAT CVQERYEYFPGFSGEEIWNPNTNVSEDCLYINVWAPAKARLRHGRGANGGEHSNKADTDH LIHNGNPQNTTNGLPVLIWIYGGGFMTGTATLDIYNADIMSAVGNVIVASFQYRVGAFGF LHLSPAMPGYEEEAPGNVGLWDQALAIRWLKTNAHAFGGNPEWMTLFGESAGSSSVNAQL VSPVTAGLVKRGMMQSGTMNAPWSHMTSEKAVEIGKALINDCNCNASLLSENPQAVMACM RAVDAKTISVQQWNSYSGILSFPSAPTIDGAFLPDHPMKMMETADLRGYDILMGNVRDEG TYFLLYDFIDYFDKDEATSLPRDKYLEIMNNIFGKVTQAEREAIIFRHTSWVGNPGLENQ QQIGRAVGDHFFTCPTNEYAQALAERGASVHYYYFTHRTSTSLWGEWMGVLHGDEIEYFF GQPLNTSLQYRQVERELGKRMLNAVIEFAKTGNPATDGEEWPNFTKKDPVYYVFSTDDKE EKLQRGPLEGRCAFWNEYLREVRKWGSQCELKPSSASSLQQKQQHLLLQQRSIVTFMLTL

SLVLGIPSVNAFF 

1. 首先選擇 blastp + nr (13,279,552,322 bps)
2. 再選擇 blastp + swiss-prot (170,826,989 bps)
3. 再選擇 blastp + pdb (16,752,417 bps)

以搜尋結果中的human Acylcholine acylhydrolase (Swiss-prot ID: P06276, PDB ID: 2WIF:A)為例：

Score	E-value	Ident	Accession	Database
397	8e-127	39%	2WIF_A (length: 529)	nr
397	2e-127	38%	P06276.1 (length: 602)	swiss-prot
397	1e-129	39%	2WIF_A (length: 529)	pdb

可以看出，雖然alignment score都一樣(397)，但e-value卻有數十倍到數百倍的差異。其差異主要來自於database的大小(nr > swiss-prot > pdb)，一般而言，較小的database (e.g. pdb)會得到較小的e-value!

當然，如果看到上述這麼小的e-values，自然沒什麼好擔心的。但如果得到像0.01這樣的e-value，就要稍微注意一下。

接下再做另一個測試，假設我們只有局部的序列：

>FASTA format

CVQERYEYFPGFSGEEIWNPNTNVSEDCLYINVWAPAKARLRHGRGANGGEHSNKADTDH LIHNGNPQNTTNGLPVLIWIYGGGFMTGTATLDIYNADIMSAVGNVIVASFQYRVGAFGF

同樣用blastp對swiss-prot進行序列比對，這次對P06276的結果變成：

Score	E-value	Ident	Accession	Database
103	5e-25	45%	P06276.1	swiss-prot

這次，e-value變大的主因來自於score變小!

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");

如何讓NetBeans IDE進行除錯時看到作者提供的libraries中的程式碼

上一篇文章提到如何在NetBeans中開啟一個新專案，其中有提到如何加入Algorithms一書中，作者提供的libraries (stdlib.jar 與 algs4.jar)。今天來進一步說明一下，加入libraries時，可使用另一種方法，讓NetBeans IDE在進行除錯時，可以step into作者提供的libraries中的程式碼。

在NetBeans開好新專案後，一樣在專案名稱上按右鍵，進入Properites中修改，這次改選Add Library：

按下Create，然後鍵入一個新的library名稱，如algo4。然後利用"Add JAR/Folder"將兩個事先從作者網頁下載好的libraries選進來：

其實這兩個*.jar檔中還包括有source檔，因此，可到Sources的tab去做一樣的設定：

最後將algo4加入專案中：

好了! 回到專案中來，可以看到libraries被成功的加入了：

這樣就可以寫作頁了。今天我要做HW1-2，也就是WeightedQuickUnionWithCompression這一題。

先把之前寫好的HW1-1的程式碼copy過來，稍微修改一下，然後加入path compression的程式碼。 執行前，記得到Properties去設定要執行哪一個class的main function，也要設arguments。此外，藉機會補充說明一下，這裡還可以指定工作目錄，也就是放有輸入檔的地方：

102-2 PDSA HW1

執行NetBeans：

先開一個新的專案：

選Java Application，按Next：

取名字(e.g. HW1)，設定專案目錄，不要自動產生Main Class：

新增一個java source檔：

取Class名字：

開始編輯WeightedQuickUF.java：

1. 先到課程網頁去 (http://algs4.cs.princeton.edu/code/)
2. 找到WeightedQuickUnionUF.java
3. 可直接將程式碼copy and paste到你自己的WeightedQuickUF.java

複製完之後，你會發現大部分的程式碼都沒問題，只有main function中出現一些錯誤警告

這些錯誤的原因是因為作者使用了一些自己寫的libraries，因此，你會需要兩個作者寫好的library檔：

1. stdlib.jar 
2. algs4.jar

先將它們下載到你的電腦上，再從NetBeans中將它們放進你的HW1 project中：

增加library路徑：

過程中要選擇你剛剛存好的*.jar檔：

弄好之後，基本上程式就可以執行了。

但我們要稍微修改一下程式，讓它可以從檔案讀入資料，而不是等待你在執行視窗中一一敲入：

此外，你還需要解決另一個問題，才能順利地使用NetBeans IDE進行執行和除錯。因為剛剛加進來的libraries當中也剛好有WeightedQuickUnionUF，以至於debuging的時候，事先compiled好的WeightedQuickUnionUF反而被優先使用。因此請大家在class的命名時，加上My來區隔。

class更名的方法：請先將檔案中的WeightedQuickUnionUF反白，然後點選Refactor -> Rename，修改成MyWeightedQuickUnionUF，再按下Refactor，就能將檔案中該修改的地方修改掉：

除了修改class名稱之外，還有另一個解決方法，就是告訴NetBeans要優先使用我們自己寫的class，如：

大家可以試試看。

最後，為了能從指令列將檔名傳進去，請到Properties去設定專案的執行環境，提供程式所需的參數，也就是輸入檔的檔名，這裡也可以設定工作目錄，也就是放輸入檔的地方：

測試資料可從ceiba的作業區HW1中下載。

最後，請依規定繳交*.java檔到批改系統。

如果，未來有機會要與別人分享你編譯好的檔案的話(如*.jar檔)，可考慮build project的時候，把*.java檔也一併包進來：

編譯好之後，*.jar檔(e.g. HW1.jar)會在你的專案中(e.g. HW1)的dist目錄中。拿到*.jar的人，不僅可以執行你的程式，也可以看到source code。

NetBeans IDE

這學期的"資料結構與演算法實務"，我希望修課同學能使用Java programming練習所學的資料結構與演算法，為了讓大家(包括我自己)有效學習，絕對需要一個好的開發工具。

今天就先來試試NetBeans IDE，首先，NetBeans官方網頁(https://netbeans.org/)說：
NetBeans IDE is FREE, open source, and has a worldwide community of users and developers.

如果你同我一樣，還沒有JDK的話，直接下載有包含JDK的NetBeans IDE會比較方便，因此在這裡比較推薦Oracle網頁中提供的下載：

http://www.oracle.com/technetwork/java/javase/downloads/index.html

請在上方連結的頁面中找到：

JDK 7u51 with NetBeans 7.4

This distribution of the JDK includes the NetBeans IDE, which is a powerful integrated development environment for developing applications on the Java platform. 

點選右方的下載鍵：
http://www.oracle.com/technetwork/java/javase/downloads/jdk-7-netbeans-download-432126.html

在這個頁面中，你可選擇自己需要的platform，比如說，我選的是Windows x86:
http://download.oracle.com/otn-pub/java/jdk-nb/7u51-7.4/jdk-7u51-nb-7_4-windows-i586.exe

順利下載後就安裝吧!!