CLRS Chapter 15-26 読んだ。Chapter27から選択的トピック。 CLRS Chapter 27 Multithreaded Algorithms Multithreaded Algorithmsまで辿りついたので、オライリーの『並行コンピューティング技法』も買ってきて一緒に読み始めた。並行コンピューティング技…

1528 -> 1673 250 「1, "11"」に引っかかって撃沈。 アルゴリズムの証明を頭の中でやれば、こんなミスもしなかっただろうに。 450 期待値の漸化式を立てて解く。 こういう問題ってDynamic Programmingに分類されるんだろうか？ 最適化問題以外はDPって呼ぶの…

したこと TopCoder SRM 461 Div1 300だけ通った。三回Challengeに失敗した。Rateは少し下がった。 CLRS Chapter 13 14 赤黒木とその拡張。あるノードの情報が自分自身と子だけに依存していれば、赤黒木を基本操作の計算量のオーダーを変えずにその情報を保持…

インタプリタでごにょごにょして、twitterのログをmecabでつっつき、よく使っている語を取ってきた。 ["関数", 9] ["レポート", 7] ["文鳥", 7] ["情報", 6] ["数学", 6] ["問題", 5] ["相撲", 5] ["試験", 4] ["時間", 4] ["処理", 4] ["明日", 4] ["テスト…

二分木 12.3-4 (左 親 右)と表す。 (nil 1 (5 10 15))で、1,10の順に削除すると(nil 5 15)、10,1の順に削除すると(5 15 nil)となる。 12.4-1 から導ける。

ハッシュテーブル 11.1-4 SmallArray = new Array; def insert ( x ) l = SmallArray.length + 1; HugeArray[x.key] = (x, l); SmallArray[l] = x.key; SmallArray.length++; end def search ( key ) (x, l) = HugeArray[key]; if SmallArray[l] == key retu…

スタック・キュー・木の簡単な説明。そんなに内容も無いよう。 10.2-3 環状リストを使う 10-1 usl ssl udl sdl search n n n n insert 1 n 1 n delete n n 1 1 succ n 1 n 1 pred n n n 1 min n 1 n 1 max n n n 1 or n 他にしたこと 『Learning Perl』を読…

『Learning Perl』を半分ほど読んだ。 『ゲノム』の3章を読んだ。 『Learning Perl』と『Introduction to Algorithm』をさっさと読み終えてテスト勉強に移行しないとならない。

順序統計量とメディアン 配列中のk番目の大きさの値は最悪でもO(n)で取れますよという話。このChapterでPart IIは終わり。Part IIIはデータ構造。 9.1-2 A:最小値の候補だが、最大値ではないもの B:最大値の候補だが、最小値ではないもの C:最大値・最小値の…

線形時間ソーティング。比較ソートがnlognかかることの証明と、その結果を利用した別のアルゴリズムの計算量の下界の証明。obliviousなsort。 Exercise 8.1-1 n-1 Exercise 8.2-4 def exercise_8_2_4(a,k) n = a.length c = Array.new(k+1) for i in 0..k c[…

(defun a () 0) (defvar b (let ((c #'a)) (defun a () 1) c)) (a) ;=> 1 (funcall b) ;=> ??? sbcl1.0.29だと(funcall b)に対して何故か1が返る。 alisp,eclでは0が返る。 ちなみに#'の代わりにsymbol-functionを使うと0が返る。 x86なLinux環境が今無いの…

Exercise 6.5-9 リストがヒープの根からそれぞれぶらさがったヒープを作る。根っこの付近は-Infを入れておく。そのあとExtractMinを繰り返す。 Exercise 7.1-2 r i,jの他に、kを導入。A[1..i]がpivotより小さいもの,A[i+1 .. k]がpivotと等しいもの,A[k+1 ..…

http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WH3-45MH2FH-1H&_user=136130&_coverDate=03%2F31%2F1996&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000010979&_version=1&_urlVersion=0&_userid=136130&md5=44b3849…

Introduction to Algorithms Exercise 6.1-1 minimum : maximum : Exercise 6.1-2 なので Exercise 6.1-3 全てのノードは根から辺を下にたどって行くことができるので、不等号の遷移律から正しいと示せる。 Exercise 6.1-4 葉 Exercise 6.1-5 yes Exercise 6…

アルゴリズムイントロダクション/Introduction to Algorithms Exercise 5.1-1 遷移律が満たされないとすると、a 反対称律と反射律は問題からして自明 全員比較される可能性があるので完全律もOK Exercise 5.1-2 lg(ceil(a-b))の長さの二進符号を作りa-bに対…

ゲノム第三版 Chapter2 DNA研究法まで