Fall-2019-ITCS-8114-Algods
このリポジトリには、もちろん「ITCS 6114/8114：アルゴリズムとデータ構造」のプロジェクトと割り当てが含まれています。このコースは、UNCシャーロットの博士号の学位の一環として、2019年秋学期に撮影されました。
プロジェクトリスト
- プロジェクト1：比較ベースのソートアルゴリズム
- プロジェクト2：グラフアルゴリズム（シングルソース最短パスと最小スパニングツリー）
- プロジェクト3：パターンマッチングアルゴリズム
以下に、プロジェクトの説明と要件があります。詳細を取得するには、対応するプロジェクトディレクトリにアクセスしてください。
プロジェクト1：比較ベースのソートアルゴリズム
次のソートアルゴリズムを実装し、それらを比較します。任意のプログラミング言語（例：C/C ++、Java、Python、C＃）を使用できます。このプロジェクトでは、単独で、または2人のチームとして作業することができます。
- 挿入ソート
- ソートをマージします
- heapsort [ベクトルベース、および一度に1つのアイテムを挿入]
- インプレースクイックソート（ランダムアイテムまたは入力の最初または最後のアイテムはピボットになります）。
- 修正されたクイックソート
- 3つの中央値をピボットとして使用します。
- サイズ<= 10のわずかなサブ問題については、挿入ソートを使用します。
実行手順：
- さまざまな入力サイズでこれらのアルゴリズムを実行します（例：n = 1000、2000、4000、5000、10000 .. 40000、50000）。入力配列の数値をランダムに生成します。実行時間を記録し（クラスで説明したように平均を取る必要があります）、入力サイズに対してすべてを単一のグラフでプロットします。これらのソートアルゴリズムを同じデータセットで比較することに注意してください。
- また、次の2つの特別なケースのパフォーマンスを観察して提示します。
- 入力配列はすでにソートされています。
- 入力配列は逆にソートされます。
グレーディングスキーム：
提出手順：
- キャンバスアップロード
- 選択されたデータ構造、複雑さ分析、結果、およびコードをカバーする適切にフォーマットされたレポート。
- 実行のためのプログラムコードをアップロードします。 TAにReadMeを提供してください。
- さらに、クラスで私にコードなしでレポートのハードコピー。
プロジェクト2：グラフアルゴリズム（シングルソース最短パスと最小スパニングツリー）
このプロジェクトでは、2つのグラフアルゴリズムを以下に実装します。注：一人で、または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
ここで、最初の2つの数値は、頂点とエッジの数を表します。文字uは、無向グラフ（指向のd）の略です。 2行目から、すべてのエッジとその重量（例えば????（？、？？）とその重量が1です。最後の行はオプションです。与えられた場合、ソースノードを表します。
提出手順：
- 各アルゴリズム、選択されたデータ構造、コードのランタイム、サンプル入力/出力、プログラムを簡単に実行するための命令をカバーする適切にフォーマットされたレポート。
- 各問題について、選択した4つの異なるグラフのプログラムを実行します。あなたの判断を使用して、あなたが面白くて合理的だと思うテストグラフを定義してください。例えば：
- 無向グラフ：少なくとも7つのノードと12のエッジ
- 指示グラフ：少なくとも7つのノードと15のエッジ
- TAが実行するためのクリーンコード。
- 任意のプログラミング言語（C/C ++、Java、Pythonなど）を使用できます。
- チームで働いている場合、両方のメンバーはすべてを個別に提出する必要があります。
- 私にあなたのレポートのハードコピー。チームごとに1つのコピー。
グレーディングスキーム：
プロジェクト3：パターンマッチングアルゴリズム
注：一人で、または3マックスのチームで作業することができます。
この割り当てでは、以下のリストから選択した3つのパターンマッチングアルゴリズムのみを実装します。
- ブルートフォースアルゴリズム
- Boyer-Moore-Horspoolアルゴリズム
- Knuth-Morris-Prattアルゴリズム
- ボイヤームーアアルゴリズム
- パターンマッチング用の有限自動化
実験：
- いくつかの異なる入力テキストとパターンについて、3つのアルゴリズムを比較します。少なくとも10の異なるケース
- 各ケースのテーブルに必要な比較の数について、各アルゴリズムについて言及してください
提出：
- 各アルゴリズムの短い説明、使用されているデータ構造、コードのランタイム、サンプル入力/出力、プログラムを簡単に実行するための命令をカバーする適切なレポート。
- TAが実行するためのクリーンコード。
- 任意のプログラミング言語（C/C ++、Java、Pythonなど）を使用できます。
- チームで働いている場合でも、両方のメンバーはすべてを個別に提出する必要があります。
- あなたのレポートのハードコピー私に直接。チームごとに1つのコピー。
グレーディングスキーム：
- 3 x 15 = 45ポイント：3つのアルゴリズムを実装するため
- 20ポイント：実験用
- 10ポイント：レポート
