STAについて

前期の復習がてらついでに
Tel Aviv UnivのDana RonのLecture Noteも見ています。
Topics in Algorithms – Sublinear Algorithms 0510.7410
http://www.eng.tau.ac.il/~danar/TOP06/index.htm

こちらに載っていることも時間があればちょいちょい書いていこうかと思っています。

Lecture1のモチベーションの部分に自分の考えていなかったことが書いてあったので書きます。
正確な答えをえねばならないときに、その前処理として大きく外れた値を取り除くのにSublinear Time Algorithmsを用いる。
これは確かにそうだなーと思いました。とかlogn時間でε-farなものを取り除けられたらこれは効率的なことだと思いました。

Lecture2では与えられたグラフが連結成分であるかどうかをチェックするアルゴリズムが載っていました。