%% This LaTeX-file was created by <jl> Sun Feb  1 22:49:06 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}

day5 1/26/98 Quote of the day: ``Just leave it out.''


\section{Linear Programming}

The constraints can be divided into 3 sets:

\begin{itemize}
\item \( H^{+}=\{i:y\geq \alpha _{i}x+\beta _{i}\} \)
\item \( H^{-}=\{i:y\leq \alpha _{i}x+\beta _{i}\} \)
\item \( H^{0}=\{i:\alpha _{i}x=\beta _{i}\} \) (vertical line constraints)
\end{itemize}
In general only 2 of the constraints in \( H^{0} \) can be active at one time.

Define:

\begin{itemize}
\item \( l_{t}^{+}\in H^{+} \) with largest intersection on line \( x=t \)
\item \( l_{t}^{-}\in H^{-} \) with smallest intersection on line \( x=t \)
\end{itemize}
By looking at the slopes of \( l_{t}^{+} \) and \( l_{t}^{-} \) you can decide whether the solution must
lie to the left or to the right.


\subsection{Algorithm}

This algorithm is dual to the bridge finding algorithm in the convex hull problem.
 Start with a window(a,b) in which the solution must lie.

\begin{enumerate}
\item Pair up lines in \( H^{+} \), Pair up lines in \( H^{-} \).
\item compute \( \approx n/2 \) intersections
\item pick t = median x value from the intersections. Let \( l_{t}^{-}= \) the smallest y-value which
any solution must lie below and \( l_{t}^{+} \) = the largest y value which any solution must
lie above.
\item case 1: \( l_{t}^{-}>l_{t}^{+} \) (there exists a feasible region) if slope(\( l_{t}^{+} \))=0 then you are done,
else if slope(\( l_{t}^{+} \))>0, pick window(a,t) else pick window(t,b)
\item case 2: \( l_{t}^{-}<l_{t}^{+} \) if \( slope(l_{t}^{+})-slope(l_{t}^{-})>0 \) then pick window(t,b) else pick window(a,t). 
\item case 3: :\( l_{t}^{-}=l_{t}^{+} \) degenerate nastiness.
\item For each pair with an intersection outside the new window discard a constraint.
\item repeat with new window and remaining constraints.
\end{enumerate}

\subsection{Timing:}

Timing is the same as the bridge algorithm.

\( T(n)=T(3/4*n)+c*n \)


\section{Amortized analysis}


\subsection{Binary counter}

How many bits change on average? 

\begin{itemize}
\item Let \( C_{i} \) = counter at time \( i \). \( C_{0} \)= all zeros
\item potential function: \( \#(C_{i})=\# \) of ones in counter.
\item \( \widehat{cost_{i}}=cost_{i}+\#(C_{i+1})-\#(C_{i}) \) = amortized cost
\end{itemize}
To figure out the total cost, do \( (\sum \widehat{cost_{i}}+\#C_{begin}-\#C_{end})/n= \) amortized cost. The amortized cost for a
the binary counter is 2. One way to see this is to notice that when the counter
is updated there is a \( p=1 \) chance of 1 bit changing, a \( p=1/2 \) chance of another bit
changing, a \( p=1/4 \) chance of another bit changing.... the series sums to 2.


\subsection{Splay trees}


\subsubsection{binary search trees}

Common to all ordered trees

\begin{itemize}
\item each of the nodes stores at least one key.
\item keys are ``inorder''
\item member(i,S)
\item insert(i,S)
\item delete(i,S)
\item join(S,S')
\item split(i,S)
\end{itemize}

\paragraph{examples}

\begin{itemize}
\item AVL-trees (everything with log(n) or log(n)+1 trees)
\item 2-3-4 trees (similar)
\item red-black trees (depth varies between log(n) and 2{*}log(n))
\item splay trees (move interesting elements to the root of the tree)
\item random trees 
\end{itemize}
The important method of transforming a binary tree is rotation of a child to
a parent. Splay trees rotate any element looked at to the top of the tree.

\end{document}