アラフォー大学院生のHiroshiです。
今日は、今学期(2023 Fall)に取っている授業の1つはAnalysis of Algorithmsについて紹介したいと思います。

主に学ぶことは下記でした。
Algorithmic Thinking
Timing Analysis
Mathematical Proofs
Runtime Analysis
Amortized Analysis
Advanced Heaps
Greedy Algorithms
Divide-and-Conquer Algorithms. Master Theorem
Dynamic Programming
Network Flow
Flow Circulation
Linear Programming
NP-Completeness
Reduction
Approximation Algorithms
Randomized Algorithms

13 weeksに渡って上記の内容について講義を聞き、2週間に1回のペースで、合計5回のQuizを解き、5回の宿題と2回のPaper examを行うという内容です。

このコースでは、一通りのアルゴリズムを学べるので、コンピュータサイエンスの基礎は網羅していると思います。また、特徴的だった部分は、コードを全く書かないという点です。

宿題はハンドライティングはNGなので全てTypeしてLatexで提出しましたが、基本的に紙と鉛筆でロジックを学べというスタイル。アルゴリズムの正当性を数学的帰納法や必要十分条件を使って証明していくような感じです。
それが良かったのか、アルゴリズムを理解しやすかったです。

一般的な問題を、グラフ理論、Network Flowにどのように落とし込んで問題を解くのか、コンピュータで解ける問題にReductionするのか、といった点は良い学びになりました。

この授業を取れば、Machine Learningの理論の授業も取れるとProfessorは仰っていたので、残りのSemesterでそちらも学んでみたいと思います。
※写真はFinal Examの時の写真。