久しぶりに Coursera で勉強したので、備忘を兼ねてメモを残しておきます。
アルゴリズムを勉強する上で、この専門講座が選択肢の1つになる方もいると思うので、参考になれば嬉しいです。
※ Courseraって何？という方は以下の記事が参考になるかと思います。
受講した専門講座
最初に、受講した専門講座の概要と特徴を説明します。
概要
Courseraの Algorithms Specialization という専門講座を受講しました。スタンフォード大学が提供しているコースで Tim Roughgarden 先生が教えてくれます。
この専門講座は以下の4つのコースを受講することで、修了となります。
- Divide and Conquer, Sorting and Searching, and Randomized Algorithms
- Graph Search, Shortest Paths, and Data Structures
- Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
- Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
分割統治法からはじまって、ソート・探索・最短経路・貪欲法・動的計画法などを学び、最後はNP完全まで扱うので、ある程度網羅的に、そして体系的に学べるかと思います。
特徴
オンライン動画で学べる
授業は先生のオンライン動画を視聴する形で進みます。オンライン動画は基本的に10分前後で、スライド資料はPDF形式でダウンロードすることもできます。
クイズと演習がある
各コースはそれぞれ4週間分の授業に分かれていて、各週分のオンライン動画・クイズ・演習が提供されています。またコース全体のクイズもあります。
これらのクイズや演習で、決められている以上の成績を取らないと修了することができないので、強制的にアウトプットの機会が与えられます。
字幕は残念ながら英語のみ
他のCourseraのコースだと、日本語字幕が付いているものもありますが、このコースでは英語字幕となります。また、クイズや演習の問題も英語となります。
時間の目安は「8時間/週」で4ヶ月
専門講座の紹介ページで上記のように書かれています。自分の場合も約130時間かかりました。ただ、アルゴリズムの基礎知識だったり、実装力、英語力によって多少前後するかと思います。
料金は月額のサブスクリプション型
自分の場合は「5296円/月」でした（料金が固定なのか、為替等によって変わるのか不明なので、ご自身で確認するようにしてください）。
無料の7日間トライアルがあったり、（修了証や演習なしでよいなら）無料で動画視聴だけできたりする場合もあるようですが、常にできるのかわかっていないので、こちらもご自身で確認するようお願いします。
受講しようと思った理由
実はこの授業を取り始める前に、別の本でアルゴリズムの学習を進めていたのですが、章末の演習問題をうまく消化できず悩んでいました（飛ばしすぎると理解が浅いし、かといって全部やるのもしんどいし、選んで解くにしてもどれを選べばいいか難しいし）。
そこで、問題数は少ないながらも基本的な演習問題を用意してくれるCourseraの授業を取ることにしました。
アルゴリズムを教えてくれるオンライン講座は他にも
- プリンストン大学が提供している Algorithms, Part I と Algorithms, Part II
- UCSDが提供している Data Structures and Algorithms
あたりが気になったのですが、今回取ったスタンフォード大学の講座は3年ほど前に少し受けたことがあって（その時は時間がなくて挫折しました…）、良かったのを覚えていたので、この講座を取ることにしました。
受講した感想
良かったところ
週ごとに演習が用意されている
ここは期待通り良かったです。少ない問題数でありながらも、演習があることで、実装しながら理解を深めていくことができます。どの問題も、その週に習ったアルゴリズムを正しく使えば解けるようになっているので、自分の理解度をチェックするのにちょうどよかったなと感じました（例えばカラツバ法を習った後は、64桁の整数が2つ与えられてその積を出力する問題でした）。
また、どうしても困った場合はフォーラムで相談することも可能ですし、以下のレポジトリで様々なテストケースが公開されているので、自力でデバッグしやすくなっています。
問題の分析とアルゴリズムの証明が丁寧
基本的には以下の流れでアルゴリズムが紹介されます。
- 問題の定義
- 単純なやり方だと難しいこと
- 効率的に解くためのキーポイント
- アルゴリズムの実装
- アルゴリズムが正しいことの証明
実装の部分だけでなく、「なぜ単純なやり方だと解けないのか」「この問題を解くためのキーポイントはどこか」が丁寧に説明されているので、アルゴリズムの実装だけでなく、考え方も含めて学習しやすかった気がします。
また、アルゴリズムが正しいことの証明も丁寧なので、納得感を持って学習を進めていくことができました。
自分のペースで学んでいける
自分の場合は、最初にスライドを確認した後、難しいところを動画で確認しながら勉強を進めていきました。さらにスクリプトも公開されているので、本当に難しいときは、スクリプトを1文ずつ追いながら理解を深めていくことができました。動画の再生速度を変更することも可能なので、各自のペースで学習を進めやすいかと思います。
また、発展的な内容の動画には "Advanced - Optional" の記載があるので、基本だけ学びたい方はスキップして進めることも可能です。
大変だったところ・改善されるといいなというところ
英語のみであること
良かったところとも言えますが、大変でもありました。特にクイズの問題がたまにトリッキーなので、正しく理解するためにけっこう時間を使ってしまった気がします。
逆に言うと、英語での表現もあわせて学べるので、そこは面白かったです。「ワーシャルフロイド法」は英語だと「Floyd-Warshall algorithm」なのか、と知って喜んでいました。
実装で詰まった時がつらい
1人で進めているので、詰まってしまった時はつらかったです。授業で習ったアルゴリズムの理解を間違えている時は直しやすいのですが、自分の場合は問題の理解を間違えて詰まった時が大変でした（小数点以下を切り捨てて出力するところを、小数点含めて出力してしまっていました）。
「良かったところ」で書いたように、様々なテストケースの入力・出力が公開されている レポジトリ があるので、うまく活用するようにしてから、ようやく詰まりにくくなりました。
スライドにたまに誤字がある
先生の板書が読みにくい、ということでスライドでは清書されたPDFが提供されているのですが、たまに誤字があるので、そういう時は動画内での板書を確認するようにしていました。スライドがダウンロードできるだけでとてもありがたいのですが、誤字が減ったらより嬉しいなと思います。
学習ログ
自分の学習ログは以下にアップしています。
各週のテーマとメモは以下となります。
Course 1: Divide and Conquer, Sorting and Searching, and Randomized Algorithms
- Part 1: Introduction
- Part 2: Asymptotic Analysis
- Part 3: Divide & Conquer Algorithms
- Part 4: The Master Method
- Part 5: Quicksort Algorithm
- Part 6: Quicksort Analysis
- Part 7: Probability Review
- Part 8: Linear-Time Selection
- Part 9: Graphs and The Contraction Algorithm
Course 2: Graph Search, Shortest Paths, and Data Structures
- Part 10: Graph Search and Connectivity
- Part 11: Dijkstra's Shortest-Path Algorithm
- Part 12: Heaps
- Part 13: Balanced Binary Search Trees
- Part 14: Hashing - The Basics
- Part 15: Universal Hashing
- Part 16: Bloom Filters
Course 3: Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
- Part 17: Two Motivating Applications
- Part 18: Introduction to Greedy Algorithms
- Part 19: A Scheduling Application
- Part 20: Prim's Minimum Spanning Tree Algorithm
- Part 21: Kruskal's Minimum Spanning Tree Algorithm
- Part 22: Clustering
- Part 23: Advanced Union-Find
- Part 24: Huffman Codes
- Part 25: Introduction to Dynamic Programming
- Part 26: The Knapsack Problem
- Part 27: Sequence Alignment
- Part 28: Optimal Binary Search Trees
Course 4: Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
- Part 29: The Bellman-Ford Algorithm
- Part 30: All-Pairs Shortest Paths
- Part 31: NP-Complete Problems
- Part 32: Faster Exact Algorithms for NP-Complete Problems
- Part 33: Approximation Algorithms for NP-Complete Problems
- Part 34: Local Search Algorithms
- Part 35: The Wider World of Algorithms
終わりに
なかなか時間はかかりましたが、久しぶりのCourseraは面白かったです。3年ほど前にやりきれなかった後悔が残っていたのですが、その思いを晴らすことができました。
アルゴリズム関連の学習は、他にもいい教科書がたくさんあったり、オンライン授業でもいいものがたくさんあるかと思いますが、この専門講座も選択肢の1つとしてありかと思うので、興味のある方はぜひ検討してみてください。
Share this post