\documentclass[11pt]{article}
\usepackage{fullpage}

\usepackage{amsmath,amssymb,color,amsthm,graphicx}

\usepackage[]{algorithm2e}

\usepackage{color}
\pagestyle{empty}

\begin{document}
\begin{center}
CS 763 Fall 2018 \hfill due Friday October 30\\
{A.~Lubiw \hfill \quad}
\end{center}

\begin{center}
\large\bf ASSIGNMENT 5
\end{center}

\noindent
ACKNOWLEDGE YOUR SOURCES.

\bigskip
\noindent
\begin{enumerate}

\item{} [10 marks] {\bf A literature search question.}  

\begin{enumerate}
\item What is the best upper bound (known so far) on the number of triangulations of $n$ points in the plane?
\item What is the best algorithm (known so far) to find the number of triangulations of a given set of $n$ points in the plane.
\end{enumerate}

For the bound, just state it.  For the algorithm, describe the approach in a sentence of two and quote the runtime.
In both cases, give the references.

Your sources should be reliable and first-hand.  By ``first-hand'' I mean that if you refer to a paper, 
then it must be one you have looked at (at least the first page), rather than just one that some other source refers to.  ``Reliable'' is a judgement call, but 
research papers in respectable journals are better than wikipedia or course notes you find on the web or queries on StackExchange.  In computational geometry (and theoretical computer science more generally) a conference paper is often followed by a more detailed journal paper.  Make sure you refer to the journal paper if there is one, rather than the conference or arxiv papers.  Google Scholar is an excellent tool, and note that you can find all later papers that cite a given paper.

{\bf Important.}  Give your reference list the way research papers in CS do. Latex and Bibtex are great for this task, although you are not required to use them.  Be sure to put papers in alphabetical order by author name and to include all author names.

[I do not expect a long answer here, just a very brief outline.  The point is for 
you to search out the information.  I don't expect you to read technical details, or 
to understand how the solutions work.]
 

\item{[10 marks]}  
\begin{enumerate}
\item Recall the definitions of \emph{flips} and \emph{illegal edges} from the lecture.  During the process of flipping illegal edges, is it possible for a legal edge to become illegal? Prove your answer.
\item The \emph{flip graph} of a set of points has a vertex for every triangulation of the point set, and an edge $(T_1,T_2)$ when triangulation $T_2$ is obtained by flipping one edge in $T_1$.  (This was called the \emph{reconfiguration graph} of flips in class.) Can the flip graph contain a triangle?  Is the flip graph bipartite?  Prove your answers.
\end{enumerate}

\end{enumerate}


\end{document}

