Fall 2019 ITCS 8114 AlgoDS

2019年秋季-ITCS-8114-Algods

該存儲庫當然包含“ ITCS 6114/8114：算法和數據結構”的項目和作業。本課程是在2019年秋季學期的，作為我在夏洛特UNC的博士學位的一部分。

項目清單

• 項目1：基於比較的排序算法
• 項目2：圖形算法（單源源最短路徑和最小跨越樹）
• 項目3：圖案匹配算法

在下面，您將找到項目的描述和要求。要獲取詳細信息，請轉到相應的項目目錄。

項目1：基於比較的排序算法

---

實現以下排序算法並比較它們。您可以使用任何編程語言（例如C/C ++，Java，Python，C＃）。在這個項目中，您可以獨自工作，也可以作為兩個人的團隊工作。

1. 插入排序
2. 合併排序
3. heapsort [基於向量，一次插入一個項目]
4. 就地QuickSort（任何隨機項目或輸入的最後一個或最後一個項目都可以是樞軸的）。
5. 修改後的QuickSort
   • 使用三個中位數作為樞軸。
   • 對於大小<= 10的小子問題，請使用插入排序。

執行說明：

1. 為不同的輸入大小運行這些算法（例如n = 1000，2000，4000，5000，10000 .. 40000，50000）。您將隨機生成輸入數組的數字。記錄執行時間（需要按照班級討論的平均值），並在單個圖中繪製它們，以針對輸入大小進行繪製。請注意，您將比較相同數據集的這些排序算法。
2. 還觀察和現在的表現以下兩個特殊情況：
   • 輸入陣列已經排序。
   • 輸入數組反向分類。

評分方案：

提交說明：

• 畫布上傳
  1. 涵蓋選擇的數據結構，複雜性分析，結果和代碼的良好形式報告。
  2. 上傳程序代碼進行執行。確保您為ta提供了讀數。
• 此外，在班上沒有代碼的報告中沒有報告的硬拷貝。

項目2：圖形算法（單源源最短路徑和最小跨越樹）

---

在此項目中，您將實現下面提到的兩種圖形算法。注意：您可以單獨工作或最多兩個團隊。

問題1：在給定的源頂點中找到有向和無方向的加權圖中的最短路徑樹。假設圖表中沒有負面邊緣。您將打印給定來源的每條路徑和路徑成本。

問題2：給定一個連接的，無方向性的加權圖，使用將總重量最小化的邊緣找到一個生成樹？ （？）= ∑ _{（u，v）∈T} ？ （？，？）。使用Kruskal算法找到最小跨越樹（MST）。您將打印樹的邊緣和答案的總成本。

輸入格式：對於每個問題，您將從文本文件中獲取輸入。假設您想在以下無向圖上運行算法。相應的文件格式將是：

 6  10 U
A  B  1
A  C  2
B  C  1
B  D  3
B  E  2
C  D  1
C  E  2
D  E  4
D  F  3
E  F  3
A

在這裡，前兩個數字代表頂點和邊緣的數量。字母u代表無方向的圖（d用於指示）。從第二行中，它提到了所有邊緣及其重量（例如???（？） ，其權重為1。最後一行是可選的。如果給出，則表示源節點。

提交說明：

• 一個格式的報告涵蓋了每種算法，選擇的數據結構，代碼的運行時，示例輸入/輸出，可以輕鬆運行程序的指令。
• 對於每個問題，請為您選擇的四個不同圖表運行程序。利用您的判斷來定義您認為有趣和合理的測試圖。例如：
• 無向圖：至少7個節點和12個邊緣
• 定向圖：至少7個節點和15個邊緣
• 清潔代碼以供ta執行。
• 您可以使用任何編程語言（例如C/C ++，Java，Python等）
• 如果在團隊中工作，則要求兩個成員分別提交所有內容。
• 您的報告直接向我報告；每個團隊一份副本。

評分方案：

項目3：圖案匹配算法

---

注意：您可以獨自工作或最多三個團隊。

對於此作業，您將僅在下面給出的列表中實現您選擇的三種模式匹配算法。

• 蠻力算法
• Boyer-Moore-Horspool算法
• Knuth-Morris-Pratt算法
• Boyer-Moore算法
• 圖案匹配的有限自動化

實驗：

• 比較幾種不同輸入文本和模式的三種算法；至少10種不同的情況
• 提及每種情況表所需的比較數量，每種算法

提交：

• 一個良好的報告，涵蓋了每種算法的簡短描述，所使用的數據結構，代碼的運行時，示例輸入/輸出，可以輕鬆運行程序的指令。
• 清潔代碼以供ta執行。
• 您可以使用任何編程語言（例如C/C ++，Java，Python等）
• 如果在團隊中工作，仍然需要兩個成員分開提交所有內容。
• 您的報告直接給我；每個團隊一份副本。

評分方案：

• 3 x 15 = 45分：用於實施三種算法
• 20分：用於實驗
• 10分：報告