%% This LaTeX-file was created by <jl> Mon Feb 16 11:53:21 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}

day 11 2/16/98 ``Shouldn't ask questions that you don't want to know the answer.''


\section{Dynamic programming}


\subsection{Optimal Binary Search Trees}


\subsubsection{given}

\begin{itemize}
\item keys \( \{a_{1},...,a_{n}\}=S \)
\item \( a_{i}<a_{i+1} \)
\item \( p_{1},...,p_{n} \) where \( Prob(search(a_{i},S))=p_{i} \)
\item \( q_{i}=Prob(Search(a,S)\wedge a_{i}<a<a_{i+1}) \)
\item \( q_{0}= \)\( Prob(Search(a,S)\wedge a<a_{0}) \)
\item \( q_{n}= \)\( Prob(Search(a,S)\wedge a_{n}<a) \)
\end{itemize}

\subsubsection{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 = \( \sum _{i}p_{i}(D(a_{i})+1)+\sum _{i}q_{i}D(i) \)


\subsubsection{definitions}

\( T_{ij}= \) min cost tree \( \{a_{i+1},...,a_{j}\} \), \( 1\leq i<j\leq n \)

\begin{itemize}
\item \( T_{ii+1}=a_{i} \)
\item \( C_{ij}=cost(T_{ij}) \)
\item \( V_{ij}=root \)
\item \( W_{ij}=\sum _{k=i}^{j}q_{k}+\sum _{k=i+1}^{j}p_{k} \)
\end{itemize}
Suppose we want to compute \( T_{ij} \) and all subintervals have been calculated. Pick
a key \( a_{k}:i+1\leq k\leq j \). Lookup the cost of \( T_{ik-1} \) and \( T_{kj} \). 
\[
Cost(T)=Cost(T_{ik-1})+w_{ik-1}+Cost(T_{kj})+w_{kj}+p_{k}\]
 
\[
=Cost(T_{ik-1})+Cost(T_{kj})+w_{ij}\]


Then, 


\[
c_{ij}=min_{i+1<k<j}\{C_{ik+1}+C_{kj}\}+w_{ij}\]


This is formula involves exponential computation without memoization. With memoization
it is \( O(n^{3}) \) because there are \( O(n^{2}) \) \( c_{ij} \) and each \( c_{ij} \) costs \( O(n) \) to calculate.


\subsection{Huffman codes}


\subsubsection{givens}

\begin{itemize}
\item alphabet \( \sum =\{0,...,\sigma -1\} \) = \( \{0,1\} \) for us
\item code words \( w=a_{i}...a_{l}\in \sum ^{l} \)
\item set of words = code = \( \{w_{1},...,w_{k}\} \)
\end{itemize}

\subsubsection{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.


\paragraph{Define: W codeword w=ps, p = prefix and s = suffix}


\paragraph{Define: \protect\( c_{1}...c_{k}\protect \) = code words}


\paragraph{Define: non-empty word t is tail if \protect\( \exists \protect \) messages \protect\( c_{1}...c_{m}\protect \) and \protect\( c^{'}_{1}...c^{'}_{n}\protect \) s.t. \protect\( c_{1}\neq c^{'}_{1}\protect \), t is a suffix
of \protect\( c^{'}_{n}\protect \), \protect\( c_{1}...c_{m}t=c^{'}_{1}...c^{'}_{n}\protect \)}


\paragraph{Lemma: A code, C is uniquely decipherable iff no tail is a code word.}


\subsubsection{Algorithm}

\( tails=\emptyset  \)

Generate-tails

\begin{enumerate}
\item \( \forall c_{i}\&c_{j} \) \( i\neq j \).
\end{enumerate}
\begin{itemize}
\item if \( c_{i}=c_{j} \) return ``not UD''
\item if \( \exists s \) s.t. \( c_{i}s=c_{j} \) or \( c_{i}=c_{j}s \) then \( tail=tails\cup \{s\} \)
\end{itemize}
\begin{enumerate}
\item \( \forall c,\forall t\in tails \)
\end{enumerate}
\begin{itemize}
\item if \( t=c \) return ``not UD''
\item \( \exists s \) \( ts=c \) or \( cs=t \) then \( tails=tails\cup \{s\} \)
\end{itemize}
\begin{enumerate}
\item return ``C is UD''
\end{enumerate}

\subsubsection{Analysis}

\begin{itemize}
\item \( l= \) number of code words
\item \( \#Tails\leq nl \)
\item \( case1:n^{2}l \)
\item \( case2:\#tails=n^{2}l*l=n^{2}l^{2} \)
\end{itemize}
So \( O(n^{2}l^{2}) \)


\subsubsection{Algorithm correctness}


\paragraph{Lemma 1: Algorithm generates only tails.}

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.


\paragraph{Lemma 2: Algorithm generates all tails}

Proof by induction.

base case: let t, a tail \( M(t)= \)minimal n+m s.t. \( c_{1}...c_{m}t=c^{'}_{1}...c^{'}_{n} \)

when \( M(t)=n+m=2 \), \( c_{1}t=c_{1}^{'} \) which is covered by the first step in the algorithm.

Inductive case: \( M(t)>2 \) with \( c_{1}...c_{m}t=c_{1}^{'}...c_{n}^{'} \). Assume \( pt=c_{n}^{'} \)

\begin{itemize}
\item \( p=c_{m} \) then not UD
\item \( p \) suffix of \( c_{m} \), then \( c_{1}...c_{m-1}=c_{1}^{'}...c_{n-1}^{'}p \) because \( p \) is a tail.
\item \( c_{m} \) is a suffix of p, then \( t'=c_{m}t \) is a tail. so \( c_{1}...c_{m-1}t'=c_{1}^{'}...c_{n}^{'} \)
\end{itemize}
\end{document}