アルゴリズムイントロダクション Chapter 6

Introduction to Algorithms

Exercise 6.1-1

minimum : $2^h$
maximum : $2^{h+1} - 1$

Exercise 6.1-2

$height = h \;\Leftrightarrow\; 2^h \leq \;n \;<\, 2^{h+1} \;\Leftrightarrow\; h \leq \; \lg n \;<\, h+1$
なので

Exercise 6.1-3

全てのノードは根から辺を下にたどって行くことができるので、不等号の遷移律から正しいと示せる。

Exercise 6.1-4

葉

Exercise 6.1-5

yes

Exercise 6.1-6

6,7が違う

Exercise 6.1-7

nが葉なのは明らか。n から nの親+1 (= floor(n/2) + 1) までは全て葉なので正しい。

Exercise 6.2-1

紙に書いた

Exercise 6.2-2

不等号をひっくり返す

Exercise 6.2-3

なにもしない

Exercise 6.2-4

なにもしない

Exercise 6.2-5

書き直すだけ

Exercise 6.2-6

葉まで値がいくときがあり、
$T(n) \leq T(n/2) + \Theta(1)$
なので、master法よりO(lg n)

Exercise 6.3-1

紙に書いた

Exercise 6.3-2

Max-Heapifyは子がヒープだと仮定しているから。
または、親からheapifyしても結局最後にheapになっていない場合があるから。

Exercise 6.3-3

帰納法で示せる。

Exercise 6.4-1

書いた

Exercise 6.4-2

最初は、Build-Max-Heapを呼んだあとなのでOK
途中は、帰納法の仮定によりA[1..i]の最大要素を外にだし、子はheapのままMax-Heapifyを呼んでいるのでOK

Exercise 6.4- 3 4 5

明日解く

Exercise 6.5-9

明日解く

Problem 6-1

a

1,2,3

b

increasing orderで来た場合がworst
$\sum_{i=0}^n \lfloor \lg i \rfloor$
計算すると $\Theta(n\lg n)$

Problem 6-3

c

def Extract-Min ( A )
   (x, y) <- (1, 1)
   loop
      smaller <- (x+1, y) と (x, y+1) のうち、Aでの値が大きくない方。
      swap A smaller (x, y)
      if A[x,y] = Inf
         break
   return A(1, 1)の最初の値

d

def Insert ( A )
   (x, y) <- (m+n, m+n)
   loop
      largest <- (x, y) と (x-1, y) と (x, y-1) のうち、Aでの値が最大のもの。
      if (x, y) = largest
         break
      else
         swap A largest (x, y)
         (x, y) <- largest

e

Insertを繰り返してExtract-Minを繰り返せば良い
2n * n^2しかかからない

f

def Search ( A v )
   p <- m+n
   if p < c
      return Brute-Force-Search( A )
   i <- Aの対角線をBinarySearchしてA[i, i] <= v <= A[i+1, i+1]となるiを探す。
   if A[i, i] = v or A[i+1, i+1] = v
      return (i, i) or (i+1, i+1)
   else
      return Search( A[(i, i) の右上] ) or Search( A[(i, i) の左下] )