ジョージア工科大学 OMSCSで６つ目となるクラスを完了した。CS6515 - Intro to Graduate Algorithms (アルゴリズム入門)というクラスである.
1. CS6515 Intro to Graduate Algorithms
このアルゴリズムのクラスは、非常に難しいプログラムとされていた。 omscentral.comというジョージア工科大学OMSCSのクラスのレビューサイトでは、難易度が4.28（1から5のスケールで）と評価され、週に20時間以上のワークロードが必要とされている。（2020年11月時点）
ちなみに、このクラスは、ジョージア工科大学OMSCSの多くの専攻分野で必須の授業になっている。そのため、非常に人気がありすぐ満員になってしまうので、履修登録が非常に難しい。 OMSCSで取得した単位が増えていくと優先的に履修登録できるため（より早い時間のタイムスロットが割り当てられるので）、単位をある程度そろえた人がようやく受講できるという状況だ。 しかし、幸運なことに、誰かがキャンセルしたスポットの取り合いで運良く滑り込むことができ、自分は今回受講することができた。
2. Covering Contents
アルゴリズムの主要なトピックをすべてカバーしている。
- Dynamic Programming (DP) 動的計画法
- LIS (Longest Increasing Subsequence), LCS (Longest Common Subsequence)
- Knapsack ナップサック問題
- Chain Multiply
- Shortest Paths 最短経路問題
- Divide and Conquer（分割統治法）
- Multiplication
- Complex Numbers 複素数
- Median
- FFT (Fast Fourier Transform) 高速フーリエ変換
- Randomized Algorithms
- Modular Arithmetic 剰余計算
- RSA cryptosystem, primality testing
- Graph Algorithm グラフ・アルゴリズム
- SCC (Strongly Connected Components)
- 2-SAT (2-Satisfiability Problem)
- MST (Minimum Spanning Tree)
- Max-Flow Algorithm
- Ford-Fulkerson algorithm for Max-Flow
- Max-Flow=Min-Cut
- Image Segmentation
- Flow Variant: Demands
- Edmonds-Karp algorithm for Max-Flow
- LP (Linear Programming)
- LP Introduction
- Duality and Geometry
- Max-SAT approximation algorithm
- NP
- P, NP, NP-Complete, Reductions
- 3-SAT
- Graph Problems
- Knapsack
- Halting Problem
このコースは入門（Intro）とされているものの、大学院レベルの入門という事のようだ。 というのは、いくつかの基礎的なアルゴリズムがクラスでは教えられていないのだ。
このクラスのウェブサイトにも明記されているが、学部レベルのアルゴリズムについての 知識があることが期待されている。 例えば、BFS（幅優先探索）、DFS（深さ優先探索）、 二分探索、ダイクストラのアルゴリズムなどは授業で説明されていなかったように思う。
3. My Thoughts
過去にアルゴリズムについて一通り学んだことがあったので、 正直授業内容にはあまり期待していなかった。 しかし、授業が進むにつれて、このコースの内容と講義がどんどん好きになった。 例えば、動的計画法（DP）は知っていたし、それで問題を解いたこともあったが、 計算量の理論や背景を深く知る事ができたし、未知の問題であってもどのようにアプローチするか（考えるか）を 深く理解できたので、自信を持って問題に臨めるようになった。
グラフ問題では、自分の浅い理解を痛感させられた。 DPなどとは違い、グラフ問題の回答ではPseudo コードは必要なかったのだが、 その代わりに既知のグラフ・アルゴリズムをどのように適用して問題を解くかについて答えられるようになる必要があった。 したがって、アルゴリズムを知っているだけでなく、それらを新しい問題に適用する方法、及び、そのための理解が求められた。
NP問題については、NP完全性を証明する必要がある。 証明の鍵はReductionだ。 既知のNP完全問題というのがいくつもあるのだが、 解こうとしている問題にReductionできそうな問題を見つけるのだ。 次に、それを解きたい問題にReduceする（既知の問題->新しい問題）。 正しくReduceするためには、インプットの収束、アウトプットの変換、 および “iff” 条件（if-and-only-if）の解の存在を示す必要がある。 チャレンジングではあったが、とても価値がある。
このNP完全性の証明をマスターすることで、問題がNP完全であるかどうかを証明できる。 次に、NP完全問題である場合、その問題は多項式時間(Polynomial time)で解決できない。 そのため、NP完全問題への近似アルゴリズムに取り組むというのが次のステップになってくる。
なお、宿題はほぼ毎週課される。 課題はとてもいい問題ばかりで、 きちんと理解して解けるようになれば、試験で高得点を取ることができる。 努力はきっと報われるはずだ。
長くなったが、このコースはとてもおすすめだ。 ただし、アルゴリズムの事前知識がない場合は、追いつくのが少々大変かもしれない。 とは言え、頑張れば大丈夫なはずだ。 （自信がなければクラスが始まる前にBFS, DFSなどの基礎的アルゴリズムは復習しておくのが良いかもしれない） TAは非常に協力的なので、つまづいたらどんどん質問すると良い。
References:
by @takp