アルゴリズムの知識を強化するために、coursera Algorithms PartⅠを受講しました

Algorithms, Part I | coursera

TopCoder対策の方法を探していたら、オンライン大学 courseraの存在を知り、アルゴリズムのコースを受講してみた。初の受講ということで、感想を書いてみようと思います。

２つの壁

２つの言語の壁があっだ。EnglishとJavaだ。

英語はできないので、そもそもLectureを聞き取れるのかという疑問はあったものの、意外に大丈夫だった。たぶん、Sedgewick先生の英語がゆっくりでわかりやすかったからだと思う。これはけっこう自信がついた。

どちらかというと、Javaのほうが初めはけっこうきつかった。コンパイルの方法がわからん。Assignmet以前に、開発環境をEclipseで整えるのにアタフタ。でも、慣れてくればC++と大して変わらないことに気づく。これも自信がついた。内容的には、Javaの実装に関することも取り上げられていて、勉強になる。たとえばイテレータの使い方とか、汎用的なインターフェースに対する考察（Comparable型）など。

TopCoder対策

TopCoderの対策になったかというと、これはなったとは言えるものの効果的な方法ではなかった。

  • TopCoderは道具を使っていかにして問題を解くかが求められる。
  • Lectureでは道具そのものがどういうふうにできているかが説明される

とはいえ、Lectureの中でもアルゴリズムの使われ方の事例だったり、Assignmentではアルゴリズムを応用して問題を解いたりするので、全く一辺倒ではない。大学のLectureということもあるのだろう、比重は基礎よりだ。

Assignmentの内容が充実していて面白かった。

学習のススメ方について

ブリンストン大学のSedgewick先生による講義。

Lectureの動画をみて、Excerciseの問題を解いて、Assignmentを解くという繰り返し。Lectureを見るためのiPhone/iPadアプリがあるが、これはバグってて使えなかった。Chromeからいつでもどこでも動画を見れた。これが、Online大学の素晴らしいところだ。地獄の満員電車のなかでさえ、ジムのランニングマシンの上でさえ、Lectureを聴くことができる。

学習時間は、平均が週10時間とは書いてあったものの、自分の場合は週15時間(Lecture 5時間/Assignment 10時間）かかった。土日のうち、必ずどちらか1日はcourseraの勉強で潰れた。場合によっては、休日は土日の両方か潰れた(ノД｀)

参考書籍は以下。買わなくても講義のスライドでなんとかなる。1000ページ！！

内容について

毎週の内容はこんな感じ。

  • week1 UnionFind いきなり知らないアルゴリズムがでてきたけれども、難しいことはなかかった。あとメモリと実行速度の計算。Assignmentはモンテカルロ・シミュレーションをつかった数値実験。
  • week2 スタックとキュー。それから、選択ソート、挿入ソート、シェルソートなどの簡単ソートアルゴリズムの紹介。このへんはまだ優しい。
  • week3 マージソートとクイックソート。そしてその発展形。再帰関数の紹介がマージソートでされる。このあたりから難しくなってきて追い詰められてくる。Assignmentは、パターン認識。
  • week4 ヒープ構造やヒープソートの紹介。BST。Assignmentは8puzzleというパズルをアルゴリズムで解く。キューを利用した幅優先探索。
  • week5 Sedgewick先生が考えた、Red-Black BSTが解説される。本人から解説されると、おおすげえとおもった。テクニックとしては、ここで深さ優先探索が出てくる。AssignmentはKd-treeの実装。
  • week6 ハッシュデータ構造と探索。あと、setをつかった検索方法も応用として紹介される。インデックス検索の仕組みが解説されていて、なるほどと思う。Assginmentはなくて、FinalExamがある。

全体として、自分にはレベルが高く、半分くらいしかワカラなかったし、問題も解けなかった。最後の方はなかなかグロッキー。

終わりに

学生のころはあまりまじめに勉強しなかったし、頭も成績も悪くて院には進まずに就職した。学生のころに勉強していなかったのをとても後悔している。とくに、今の仕事では、ハードウェアに関する知識が必須だけれども、自分は情報系を専攻したのでまったくない。また、統計をしっかり勉強しなかったことにも後悔している。

courseraは教育の格差をなくし、全ての学ぶ意欲のあるひとに機会を与えてくれる。社会人の自分にも、courseraを通じて再び学問に触れることができることはとても嬉しいことだ。

理想的には、1度に２つのコースを受講したいが、勉強時間の確保が難しいかな。。週20~30時間。定時退社したい。とりあえず、生活と人格が破綻するまで頑張る。

次は、Algorithms PartⅡに挑戦！