1.  Dynamic programming

1.1  Optimal Binary Search Trees

1.1.1 given

• keys {a₁,...,a_n} = S
• a_i < a_i+1
• p₁,...,p_n where Prob(search(a_i,S)) = p_i
• q_i = Prob(Search(a,S)Ùa_i < a < a_i+1)
• q₀ = Prob(Search(a,S)Ùa < a₀)
• q_n = Prob(Search(a,S)Ùa_n < a)

1.1.2 analysis

The cost of a search for a_i is equal to Depth(a_i)+1 if the search is succesful, otherwise the cost is Depth(newleaf) .

Expected cost = å_ip_i(D(a_i)+1)+å_iq_iD(i)

1.1.3 definitions

T_ij = min cost tree {a_i+1,...,a_j} , 1 £ i < j £ n

• T_ii+1 = a_i
• C_ij = cost(T_ij)
• V_ij = root
• W_ij = å_{k = i}^jq_k+å_{k = i+1}^jp_k

Suppose we want to compute T_ij and all subintervals have been calculated. Pick a key a_k:i+1 £ k £ j . Lookup the cost of T_ik-1 and T_kj .

Then,

This is formula involves exponential computation without memoization. With memoization it is O(n³) because there are O(n²) c_ij and each c_ij costs O(n) to calculate.

1.2  Huffman codes

1.2.1 givens

• alphabet å = {0,...,s-1} = {0,1} for us
• code words w = a_i...a_l Î å^l
• set of words = code = {w₁,...,w_k}

1.2.2 Unique decipherability

The code {10,0,01} is not uniquely decipherable. 010 can be parsed as: 0(10) and as (01)0 . An algorithm which determines unique decipherability would be worthwhile.

1.2.3 Algorithm

tails = Æ

Generate-tails

1. "c_i&c_j i ¹ j .

• if c_i = c_j return ``not UD''
• if $s s.t. c_is = c_j or c_i = c_js then tail = tailsÈ{s}

1. "c,"t Î tails

• if t = c return ``not UD''
• $s ts = c or cs = t then tails = tailsÈ{s}

1. return ``C is UD''

1.2.4 Analysis

• l = number of code words
• #Tails £ nl
• case1:n²l
• case2:#tails = n²l*l = n²l²

So O(n²l²)

1.2.5 Algorithm correctness

The tails in case 1 are obvious. Those generated in case 2 are of the form ts = c or cs = t where a new tail is {s} . s is indeed a tail here.

Proof by induction.

base case: let t, a tail M(t) = minimal n+m s.t. c₁...c_mt = c^¢₁...c^¢_n

when M(t) = n+m = 2 , c₁t = c₁^¢ which is covered by the first step in the algorithm.

Inductive case: M(t) > 2 with c₁...c_mt = c₁^¢...c_n^¢ . Assume pt = c_n^¢

• p = c_m then not UD
• p suffix of c_m , then c₁...c_m-1 = c₁^¢...c_n-1^¢p because p is a tail.
• c_m is a suffix of p, then t¢ = c_mt is a tail. so c₁...c_m-1t¢ = c₁^¢...c_n^¢