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

二分木 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』を読…

順序統計量とメディアン 配列中の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[…

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に対…

Introduction to Algorithms / アルゴリズムイントロダクション 分割統治法。Strassenの行列積のアルゴリズム。再帰方程式の解き方。 Exercise 4.2-1 紙に書いた Exercise 4.2-2 本の通りに計算するだけ Theta(n^3)の普通の分割統治法行列積アルゴリズムと実…

Introduction to Algorithms / アルゴリズムイントロダクション Exercise 4.1-1 最大要素一つのみの配列 Exercise 4.1-2 def BruteForceMaximumSubarray ( A ) max <- -1 r <- 0 l <- 0 loop for i from 0 below A.length sum <- 0 loop for j from i below …

ビール飲んできた。うまかった。 Introduction to Algorithms / アルゴリズムイントロダクション Theta,Big-O,Omega表記の定義、floor,ceiling,...などの表記の定義 Exercise 3.1-1 とすればよい Exercise 3.1-2 とすればよい Exercise 3.1-3 だから Exercis…

ドラクエ6もう発売してたのか・・・ ゲノム Chapter 1 ゲノム・トランスクリプトーム・プロテオーム 論述式問題 1.4 「トランスクリプトーム」・「プロテオーム」という単語は包括的な意味合いを持つので、ゲノム発現を細胞全体を系として見て理解するときに…

An Introduction to Algorithms Exercise 1.1-1 sort : 山ほどある。 検索結果の表示とか、最大値を調べるときとか。 convex hull : 監視カメラとかアンテナとか壁とか設置するとき Exercise 1.1-2 空間・表示方法・アルゴリズムの再利用のしやすさ。 Exerci…