% Mandatory class specification
\documentclass[a4paper]{article}

% Additional packages
\usepackage{a4wide}
\usepackage{algorithmic}
\usepackage{listings}
\usepackage{amsthm}
% Some package configuration
\lstset{basicstyle=\ttfamily, keywordstyle=\bfseries}

% Document info: title, author and date
\title{Algorithms and Data Structures for Biology\\ \textbf{1 April 2019 --- Lab Session}}
\author{Ugo Dal Lago \and Thomas Leventis}
\date{}



% Beginning description of the actual content of the document. It will end at "\end{document}".
\begin{document}

\maketitle  % This command displays the info given above (title, author, date).

% Documents are structured using "\section{...}", "\subsection{...}", "\subsubsection{...}".
\section{Solution: An Efficient Algorithm to Check Lists}

Given a sorted list $L$ of integers and an integer $x$, we want to check if $x$ is in $L$ in $O(\log(|L|)$.  % The symbol "$" is used to enter or exit math mode. Everything between two "$" will be treated as a mathematical expression.
We use the following algorithm.

\subsection{The Algorithm}
% There exists many different environments in LaTex. They are used with the commands "\begin{...}" and "\end{...}".
% The "algorithmic" environment is useful to write pseudo-code.
% The commands "\REQUIRE", "\ENSURE", "\STATE", "\WHILE{...}", "\ENDWHILE", etc. are specific to this environment.
\begin{algorithmic}
  \REQUIRE $L$ is a sorted list of integers, $x$ is an integer.
  \ENSURE Returns the Boolean stating whether $x$ is in $L$.
  \STATE $l \leftarrow 0$
  \STATE $r \leftarrow$ length of $L$
  \WHILE{$l<r$}
    \STATE $i \leftarrow (l+r)//2$
    \IF{$L[i] = x$}
      \RETURN \texttt{True}
    \ELSIF{$L[i] < x$}
      \STATE $l \leftarrow i+1$
    \ELSE
      \STATE $r \leftarrow i$
    \ENDIF
  \ENDWHILE
  \RETURN \texttt{False}
\end{algorithmic}


\subsection{The Implementation}

The following Python function \texttt{InSorted} implements the above algorithm.

% The "lstlisting" environment is used to display raw code.
\begin{lstlisting}[language=Python]
def InSorted(L,x):
	l = 0
	r = len(L)
	while l < r:
		i = (l+r)//2
		if L[i] == x:
			return True
		elif L[i] < x:
			l = i+1
		else:
			r = i
	return False
\end{lstlisting}

Remark that in this case the algorithm is quite simple and its implementation is straightforward. This is not always the case, see for example the second assignment (18/03/2019).

\subsection{Proof of Correctness}

We will prove that once the variables $l$ and $r$ are defined, the following invariant holds.
% The "center" environment is used to display content at the centre of the document.
\begin{center}
  $x$ is in $L$ if and only if $x$ is in $L[l:r]$.
\end{center}
Additionally we check that $l \leq r$ and every index $i$ with $l \leq i < r$ is a valid index of $L$.  % The command "\leq" is only available in math mode, and writes the symbol for "lesser or equal".

% The "\paragraph{...}" command is used to create paragraph with a given title.
\paragraph{Initialisation.}
At first we have $L = L[l:r]$ so the invariant holds, and the valid indices of $L$ are exactly the $i$s such that $l \leq i < r$.

\paragraph{Preservation.}
Let us assume that the invariant holds when entering the \texttt{while} loop. Remark that if $l < r$ then $i = (l+r)//2$ is such that $l \leq i < r$ and by hypothesis $i$ is a valid index of $L$. We distinguish three cases:
% The "itemize" environment is used in conjunction with the "\item" command to write down lists.
\begin{itemize}
  \item if $L[i] = x$ then $x$ is both in $L$ and in $L[l:r]$;
  \item if $L[i] < x$ then for all $j \leq i$, as $L$ is sorted we have $L[j] \leq L[i]$, hence $L[j] < x$ and in particular $L[j] \neq x$; by hypothesis $x$ is in $L$ if and only if it is in $L[l:r]$, and we know $x$ is not in $L[l:i+1]$ so $x$ is in $L[l:r]$ if and only if it is in $L[i+1:r]$;
  \item otherwise $x < L[i]$ and by a similar reasoning we have that $x$ is not in $L[i:r]$ so it is in $L[l:r]$ if and only if it is in $L[l:i]$.
\end{itemize}
Remark that in the last two cases the inequality $l \leq r$ is
preserved, and in any case the set of indices between $l$ and $r$ is
made smaller, so we never leave the scope of $L$.

Now our algorithm only returns \texttt{True} is $L[i] = x$ for some
valid index $i$ of $L$, in which case $x$ is indeed in $L$. On the
other hand it only returns \texttt{False} when $l \geq r$; we proved
that $x$ is in $L$ if and only if it is in $L[l:r]$, but in this case
$L[l:r]$ is empty so $x$ is neither in $L[l:r]$ nor in $L$.

This concludes the proof that \emph{if} our algorithm returns a result, then this result is correct. Next we will prove that it always returns a result.

\subsection{Proof of Termination and Complexity}

We want to prove that for any list $L$ our algorithm terminates in at most $5\log_2(|L|) + 6$ operations. To do so, we prove that whenever we reach the \texttt{while} instruction then the algorithm terminates in at most $5\log_2(r-l) + 4$ operations. Remark that we already know we always have $l \leq r$.

\paragraph{Initialisation.}
If $l = r$ then $\log_2(r-l) = 0$, and the test $l < r$ fails (first operation) and the algorithm returns \texttt{False} (second operation).

\paragraph{Preservation.}
If $l < r$ then we enter the loop, $i$ is defined and we check the equality $L[i] = x$ (three operations). Then there are three different cases.
\begin{itemize}
  \item If $L[i] = x$ then the algorithm return \texttt{True}, for a total of four operations.
  \item If $L[i] < x$ then after five operations $l$ has taken a new value $l' = (l+r)//2 + 1$ and we go back to the \texttt{while} instruction, and by hypothesis the program terminates after at most $5\log_2(r-l') + 4$ more operations. Since $2(r-l') \leq r-l$ we have $\log_2(r-l') + 1 \leq \log_2(r-l)$, hence $5\log_2(r-l') + 9 \leq 5\log_2(r-l) + 4$.
  \item Otherwise after five operations $r$ has taken the value $r' = (l+r)//2$, hence $2(r'-l) \leq r-l$ and conclude in a similar way.
\end{itemize}

The algorithm always reaches the \texttt{while} loop for the first time after two operations, with $r-l = |L|$, so the algorithm always terminates in at most $5\log_2(|L|) + 6$ operations.

\subsection{Important Remark}

Before proving the complexity of our algorithm we did not define what
an ``operation'' is. In our reasoning we assume that an operation is
the execution of a single line of code, but this is not very
precise. For instance the computation of $(l+r)//2$ can be described
not as one but as two operations, one addition and one division. But
such a refinement would only change the constants ($5$ and $4$), not
the fact that the complexity is in $O(\log(|L|)$.

Nevertheless this approximation of the notion of operation is only
valid when our lines of code always execute in constant time. The
whole reason behind this work is that computing the simple expression
\texttt{x in L} in Python is linear in $|L|$. Consider the following
Python function \texttt{InList}.
\begin{lstlisting}[language=Python]
def InList(L,x):
	return x in L
\end{lstlisting}
It is much shorter than our function \texttt{InSorted} and always execute
a single line of code, but it is much less efficient on sorted lists.
As another example note that slicing a list is \emph{not} performed
in constant time either.

This is where \texttt{cProfile} intervenes: you can check whether your
theoretical complexity actually matches the real complexity of your
program.


\section{First Work in \LaTeX}

Following the example above, write a report in \LaTeX on last week's
second exercise (find the number of element o a list $X$ which also
belong to another list $L$).


\end{document}
