CourseraでStanfordのAlgorithms Specializationを修了した

CourseraでStanfordのAlgorithms Specializationを昨日、修了しました。

www.coursera.org

修了するとこんな感じで修了書がもらえます。でーん。

Algorithms Specializationとは

Stanford大学がCourseraが提供しているアルゴリズムのオンラインコースです。 以下の計4クラスからなる授業です。

1. Divide and Conquer, Sorting and Searching, and Randomized Algorithms
2. Graph Search, Shortest Paths, and Data Structures
3. Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
4. Shortest Paths Revisited, NP-Complete Problems and What To Do About Them

1クラス、およそ一か月かかり、合計4ヵ月～5ヵ月かかります。

Stanford大学ではおそらく「Algorithms: Design And Analysis Part 1 and 2」という名前でSemi Quarter x 2かQuarter x 2で提供しているコースだと思います。 内容もソーティングや乱択アルゴリズム、DFS、BFS、最後はNP完全問題まで、一般的にアルゴリズムというと人々が想起する内容が網羅されています。

なぜアルゴリズムを学ぼうと思ったのか

自分は大学は情報工学の出です。ただ、アルゴリズムに関しては学習した記憶がありません。 成績表にも「アルゴリズム: B」と載っているのですが、学生時代のアルゴリズムの記憶はバブルソートぐらいしかないです。

おそらく、平均的な大学生と同じく真面目に大学時代勉強せずに、バンドにかまけていたため、アルゴリズムの授業は全く聞かずにテストだけ受けて単位を取得していたものと推測されます。

そのため、今回、アルゴリズムを体系的に学んでみることにしました。

話が完全に逸れますが、理系・情報工学の出身でも、こんな感じで知識の抜け漏れは多いにあります。（単純に自分の怠慢が原因ではありますが。） 「文系出身だからソフトウェアエンジニアは無理」とか「おっさんからのエンジニア転職は無理」という言説はあまり意味がないと思っています。（逆に「文系出身なのにすごい」も然り）

文系出身でもソフトウェアエンジニアとして活かせることはあるでしょうし、逆に足りなければ今から学びなおせばいいと思います。 出身大学やファーストキャリアで人生が決まってしまう、という社会の底意地の悪さを感じる言い方なので、あまり好きではないです。

Algorithms Specializationを修了するのに必要なもの

Algorithms Specializationを修了するのに必要なものは以下です。

• 前提知識
  • 高校数学ぐらいまでの数学力
  • 確率論の知識
  • 離散数学の知識
  • 英語のリスニング力
  • プログラミング力（何か一つのプログラミング言語で簡単なファイルの入出力や基礎構文がわかればOK）
• 毎週 土日 合計 8~10時間程度の空き時間
• 4か月アルゴリズムを週末を潰して学ぶという根気・やる気

前提知識 - 数学力

本コースでは、アルゴリズムの証明を頻繁に扱います。そのため帰納法や背理法などの証明法やlog、指数などの高校数学までの基礎的な数学力が必要です。 特に、乱択アルゴリズムの証明では、確率の知識も必要です。ただ、コース内でも簡単におさらいをしてくれるので、大学・高校時代に学んだ、ぐらいではあればそのまま理解できると思います。 離散数学の知識もあると、より理解は進むと思いますが必須ではないと思います。¹

前提知識 - 英語のリスニング力

また、本コースの特徴として、動画・教材に日本語字幕がありません。そして、教授のTim Roughgarden先生は、バンバンに早口 & ネイティブレベルの言い回しや難しい単語を多用します。 そのため、ある程度の英語リスニング力が必要です。

自分は、動画を何回も見返すことで、理解していました。ちなみに、日本語に訳しても何言ってるのかわからない（そもそも概念が理解できない）ことが3回ぐらいありました。たまに、非常に難しいコンセプトの説明を図なしで説明したりします（笑）

前提知識 - プログラミング力

この授業はプログラミングの授業ではありませんので、特定の言語に依存するような内容は一切ありません。 しかし、プログラミングの課題が週に1回出るので、自力でコードを書いて回答を作成することが必要です。 そのため、プログラミング言語はなんでもいいので、一つの言語でコードを自力で書く力が要求されます。

だいたい、以下がわかればよいのではないでしょうか。

• ファイルの入出力
• 基礎的な制御構文
  • for文
  • if文
• 変数
• 演算子
  • 四則演算
  • ビット演算
• データ構造
  • ベクタ（配列）
  • ハッシュマップ
  • セット

具体的な課題の内容は、以下です。

• インプットとしてtxtファイルが与えられる
• それに基づいて授業中のアルゴリズムを実装し、所定のアウトプットを計算
• Webフォームで計算結果を入力
• 計算結果が正しければ合格
• 正しくなければやりなおし

フォーラムに有志がテストケースを公開しているので、事前にそれらのテストケースを設定しておき アルゴリズムを実装してそのテストケースが通るか確認するのがおすすめです。 そのため、テストが実装しやすい言語を利用するのがおすすめです。

自分は、Rustの学習がてらほとんどRustで書きました。その点、非常に良かったです。 以下にリポジトリがあります。

github.com

毎週 土日 合計 8~10時間程度の空き時間・やる気

Courseraは毎週、課題（小テスト・プログラミング課題）が出され締め切りが設定されます。 そのため、一度始めると、少なくとも1か月は課題を出し続ける必要があります。²

よって、毎週土日の時間確保とやる気は絶対に必要だと思います。軽いノリで始めると、たぶん簡単に挫折します。

自分は、おおよそ以下の形でスケジュールを組んでいました。

• 平日
  • 仕事後か仕事前に30分程度、授業のビデオを閲覧する。(30分/日 × 4日程度)
• 週末
  • ビデオが残っていたら、残りをすべて閲覧する。(土曜日に4時間)
  • ミニテスト・プログラミング課題を提出する。（土曜日に3時間 日曜に5時間）

仕事が忙しいときは平日はビデオが見れないときもあったので、その時は土日に詰め込んでやっていました。 幸いにも（？）コロナ禍が続いたことで、土日は外に出れなかったので、勉強時間が確保できました。

それでも、たまにアルゴリズムの勉強に飽きてしまうことがあったので、まあ大変でした。

これは余談なのですが、「自粛疲れ」って言いますが、自分は休みの日は勉強しているか、コードを書いているか、Youtubeを見ているか、映画を見ているか、楽器を弾いているかのどれかでだいたい家で事足りるので、自粛疲れというか自粛天国でした。

Algorithms Specializationの面白いところ・良かったところ

上記の必要なものさえそろっていれば、このAlgorithms Specialization非常に面白くておすすめです。面白い理由は以下です。

• アルゴリズムのGreatest Hitsを体系的に学べる
• プログラミングの課題はアウトプットしか聞かれないので言語はなんでもいい
• 課題のインプットの数がmillion単位だったりするので、アルゴリズム・実装を間違えるとマジで終わらない

アルゴリズムのGreatest Hitsを体系的に学べる

このコースの最初に先生であるTim Roughgarden先生からも言われますが、アルゴリズムのGreatest Hitsを一通り体系的に学べるのは面白かったです。

「なぜアルゴリズムを学ぼうと思ったのか」にも書いた通り、アルゴリズムは大学時代は全く学んでなかったこともあり、ソフトウェアエンジニアとして負い目でした。 なので、時々、蟻本を読んだり、LeetCode/AtCoderをやったりしてアルゴリズムの勉強はしていました。

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

blog.pco2699.net

ただ、特にLeetCodeとかの勉強だとアルゴリズムの知識は断片的にしか集まらないため、体系的に学びたいと思っていました。 その点、本コースでは一部学んでいたものもありましたが、以下のような知らない知識も学べたのがよいことだと思っています。

• Greedy アルゴリズム・その証明方法
• 最短経路問題のアルゴリズム・その違い（ダイクストラ法・ベルマンフォード法・ワーシャルフロイド法）
• NP完全について、またNP完全問題をどうやって取り扱うか

プログラミングの課題はアウトプットしか聞かれないので言語はなんでもいい

前提知識の項でも説明しましたが、課題のプログラミング言語はなんでもいいのが良いです。

Courseraのアルゴリズム講座でもう一つ有名なのがPrinston大学のものだと思います。 www.coursera.org

こちらは3年ほど前に最初の授業だけ受けたのですが、言語がJava指定で、課題もテンプレートが与えられていたと思います。 まあ、アルゴリズムなので、確かに言語はなんでもいいっちゃいいのですが、個人的には今年Rustを学びたい、という思いがあり、アルゴリズムの課題をRustで書けたのは良かったです。

アルゴリズムの課題をRustで書いたことで、Rustの以下を学べました。

• 借用・ライフタイムの考え方
• 並列処理の実装方法
• 独自のデータ構造の実装方法（mod/pubおよびそれを取り込む方法）
• 標準ライブラリにあるデータ構造・ないデータ構造およびそのAPI（BinaryHeapにdelete, insertがなかったりする）

課題のインプットの数がmillion単位だったりするので、アルゴリズム・実装を間違えるとマジで終わらない

このStanfordの授業、とにかく課題が鬼畜です。プログラミング課題のテキストファイルはmillion単位だったりします。
さらに最後の方の課題だと「授業の通りのアルゴリズムを実装しても計算量は間に合いません」や、「授業では取り扱ってないですがこのアルゴリズムを実装してください」と言われます。ヤバすぎです。

ただ、自分で考えたり、実装したり、工夫したりできますし非常にやりごたえのある課題だと言えます。

例えば、「グラフの最小カットアルゴリズム」では、同じ計算を何百回も繰り返し、その計算結果を集計して値を計算するアルゴリズムを実装します。 自分は、その計算を並列処理化して高速化しました。

github.com

もし、自力では解決方法が思いつかなくても、フォーラムで様々な改善法が議論されているので、もし詰まったらとりあえずフォーラムに目を通すとよいと思います。

Algorithms Specializationを終えてみて

一通り体系的にアルゴリズムを学べたので、達成感はあります。ただ、これで例えばAtCoderやLeetCodeがズバズバ解けるようになったか、というとそういうわけではないです。 なんとか解き方へのINDEXは貼られている気がしますが、まだまだ解き方を導くのに時間はかかります。

今後は、アルゴリズム検定の対策³などを通して、実践的なアルゴリズムの力を身につけようと思います！目指せPAST 中級！

---

1. 特に毎週出されるテストは、離散数学に関する問題・証明があり離散数学を学んでおくとスムーズかもしれない。自分は忘れていたので苦しんだ。↩

2. 締め切りを守らないとどうなるのかは不明↩

3. AtCoderはコンテストで土曜の夜に時間を取られるのがつらいので…↩