%---TeX-start-of-header---
\documentclass[titlepage]{article}
\usepackage{epsfig,mathematica,figi}
%\mmanobreak

\begin{comment}

\begin{mathematica}
<<tek.m;
\end{mathematica}

\begin{mathematica}
<<Combinatorica.m
\end{mathematica}

\begin{mathematica}
SetOptions["stdout", PageWidth->Infinity];
zero = 0.00001;
ohide = DisplayFunction->Identity;
oshow = DisplayFunction -> $DisplayFunction;
ojoin = PlotJoined -> True;
oall = PlotRange->All;
osurf = HiddenSurface->False;
deg = N[Degree];
pi = N[Pi];
\end{mathematica}

\begin{mathematica}
<<Miscellaneous`Units`;
\end{mathematica}

\end{comment}

\begin{document}
\psfiginit
%---TeX-end-of-header---

\author{Tomasz J.\ Cholewo}
\title{Design and Analysis of Computer Algorithms, EMCS\,619\\
Homework \#3}
\maketitle
%====================================================================
\section{Problem 4}

Function \texttt{maxpos} returns an index of the first largest element of
a list \texttt{l}.
\begin{mathematica}
maxpos[l_List] := Module[{i, mpos = 1},
  For[i = 2, i <= Length[l], i++,
    If[ l[[i]] > l[[mpos]], mpos = i]
  ];
  mpos
];
\end{mathematica}
Function \texttt{OptimalSearchTree} returns a list consisting of
matrices \texttt{A} and \texttt{root} defining an optimal binary search
tree for a sorted list of elements described by a given probability list
\texttt{p}.
\begin{mathematica}
OptimalSearchTree[p_List] := Module[
  {A, root, n = Length[p], i, j, k, diag},
  A = Table["-", {i, 1, n + 1}, {j, 0, n}];
  root = Table["-", {i, 1, n}, {j, 1, n}];
  For[i = 1, i <= n, i++,
    A[[i, i + 1]] = p[[i]];
    A[[i, i]] = 0;
    root[[i, i]] = i;
  ];
  A[[n + 1, n + 1]] = 0;
  For[diag = 1, diag < n, diag++,
    For[i = 1, i <= n - diag, i++,
      j = i + diag;
      root[[i, j]] = k =
        maxpos[ -Table[ A[[i, k]] + A[[k + 1, j + 1]], {k, i, j}] ] + i - 1;
      A[[i, j + 1]] = A[[i, k]] + A[[k + 1, j + 1]] + Sum[ p[[k]], {k, i, j}];
    ]
  ];
  Return[{A, root}];
]
\end{mathematica}

%====================================================================
\newpage
\section{Problem 5}

Function \texttt{ShowTree} returns an actual configuration of a tree
described by the \texttt{root} table (\verb+{}+ denotes an empty tree).
\begin{mathematica}
ShowTree[root_List] := (
  ST[i_Integer, j_Integer] :=
    If[i > j,
      {},
      Module[{k = root[[i, j]]},
        List[ ST[i, k - 1], k, ST[k + 1, j] ]
      ]
    ];
  ST[1, Length[root]]
);
\end{mathematica}


%====================================================================
\newpage
\section{Tests for Problem 4 and 5 algorithms}

The given probabilities:
\begin{mathematica}
p = { 0.2, 0.24, 0.16, 0.28, 0.12};
\end{mathematica}

Calculate both matrices:
\begin{mathematica}
{A, root} = OptimalSearchTree[p];
\end{mathematica}

Partial search times array:
\begin{mathematica}
A//TableForm
.
Out[35]//TableForm= 0   0.2   0.64   0.96   1.68   2.04

                    -   0     0.24   0.56   1.2    1.48

                    -   -     0      0.16   0.6    0.84

                    -   -     -      0      0.28   0.52

                    -   -     -      -      0      0.12

                    -   -     -      -      -      0
\end{mathematica}
Root positions array:
\begin{mathematica}
root//TableForm
.
Out[36]//TableForm= 1   2   2   2   2

                    -   2   2   3   4

                    -   -   3   4   4

                    -   -   -   4   4

                    -   -   -   -   5
\end{mathematica}

The resulting tree:
\begin{mathematica}
ShowTree[root]
.
Out[57]= {{{}, 1, {}}, 2, {{{}, 3, {}}, 4, {{}, 5, {}}}}
\end{mathematica}

%====================================================================


\end{document}