%-*- LaTeX -*-

\NeedsTeXFormat{LaTeX2e}
\documentclass{assign}
\usepackage{newcent}
\usepackage{amsmath,amssymb}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Start reading here
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% The four commands below are used to define the ordinal number of the
% lecture (can be found on the lecture syllabus), the title of the lecture
% (formulate the best description you can come up with; you can always
% resort to the tentative title on the lecture syllabus if you have
% difficulty), the date of the lecture (in this format: DD Month YYYY),
% and the name of the scribe (that's you).
%
% Please supply correct arguments for the four commands below:
%

    \lecturenumber{0}
    \lecturetitle{Homework\ }
    \lecturedate{Aug 20, 2007}
    \duedate{Aug 27, 2007}
    \lecturescribe{}

%
% In the space indicated below, please type out your lecture notes.  You
% should use all the standard LaTeX typesetting conventions, plus a couple
% of additional commands described below.  If you are unfamiliar with using
% LaTeX to typeset technical documents, please read the very useful summary
% entitled ``The Not So Short Introduction to LaTeX2e'' which is available
% on BlackBoard.  You can also examine the source files for the scribed
% lecture notes from lectures 1, 2, and 3 for some formatting ideas. 
%
% Use the standard commands \section{}, \subsection{}, and \subsubsection{}
% to format your document logically into sections, subsections, and 
% subsubsections (as needed). 
%
% If you reference a URL anywhere, use the provided command \urlclick{}
% like this: \urlclick{http://www.web.com/foo.html}.  This will create a
% clickable hyperlink in the resulting .pdf file. 
%
% To add a figure to your notes, use the provided command \figureadd{}
% like this: \figureadd{basename}{label}{caption}.  In this command,
% basename is the base name of your figure, which must exist in both .eps
% and .jpg formats.  For example, if you have created a figure named both
% foo.jpg and foo.eps, then the basename is simply foo.  The label field
% creates a label which you can reference elsewhere using the standard
% command \ref{}.  Please use the caption field to provide a descriptive
% caption for any figure you create.  When you submit your scribed notes,
% please also submit all your figure files in both .eps and .jpg formats.
%
% For a theorem, corollary, lemma, claim, fact, definition, assumption,
% observation, or example, consider using these provided commands to set it
% apart from other text: 
%     \theorem{...}
%     \corollary{...} 
%     \lemma{...}
%     \claim{...}
%       etc.
%
% For proofs, or sketches of proofs, use these provided environments: 
%     \begin{proof}        ... \end{proof}
%     \begin{proof_sketch} ... \end{proof_sketch}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\reals}{{\mathbb R}}
\newcommand{\integers}{{\mathbb Z}}
\newcommand{\ch}{\ensuremath\mathcal{CH}}
% \newtheorem{theorem}{Theorem}[section]
% \newtheorem{lemma}{Lemma}[section]
% \newtheorem{corollary}{Corollary}[section]
% \newtheorem{claim}{Claim}[section]
% \newtheorem{prop}{Proposition}[section]
% \newtheorem{fact}{Fact}[section]
% \newtheorem{problem}{Problem}[section]
% \numberwithin{equation}{section}
\newtheorem{defn}{Definition}[section]
\newenvironment{proofsketch}{\par{\textbf{Proof Sketch:}}}{\(\qed\) \par}

\begin{document}
\label{begin}



\section{O() notation}
\label{sec:o-notation}

Order the following list of functions in increasing asymptotic value. In
other words, if $f(n) = O(g(n))$, then $f(n)$ must be placed before
$g(n)$ in the ordering. You need not show detailed proofs of the ordering.

\[ 2^{n^2}, \log^{100} n, n^{2.5}, 100^n, \sqrt{2n}, 10^{n}, n^2\log n, n^{\log n},
2^{2n} \]


\section{The $n^\text{th}$ day of Christmas}
\label{sec:ntextth-day-christm}

The Christmas carol, 'The Twelve Days of Christmas', starts like this:

\begin{quotation}
\it
\noindent On the first day of Christmas, my true love gave to me,\\
A partridge in a pear tree.

\noindent On the second day of Christmas, my true love gave to me,\\
Two purple doves,\\
and a partridge in a pear tree.

\noindent On the third day of Christmas, my true love gave to me,\\
Three french hens, \\
Two purple doves,\\
and a partridge in a pear tree.\\
\ldots
\end{quotation}

Suppose our lucky protagonist's true love starts giving gifts on the
$n^\text{th}$ day of Christmas (we will assume that there are always $n$
different kinds of gifts to give). How many gifts do they receive ? 


\section{Coloring A Graph (KT 13.1)}
\label{sec:coloring-graph}

A coloring of a graph $G = (V,E)$ is an assignment of colors to vertices
such that no edge is \emph{monochromatic} (is assigned the same color on both
of its endpoints). We know (or will know soon!) that finding the minimum
number of colors required to color a graph is NP-hard.

Suppose we're cut some slack, and are told that we don't have to make sure
that all edges are bichromatic (have different colors on the two
endpoints). Show how we can randomly color a graph with three colors and
ensure that in expectation, at least two-thirds of the edges are
bichromatic.

\section{Butterfly Classification (KT 3.4)}
\label{sec:butt-class-kt}

Suppose we're given $n$ butterfly specimens, and we believe that each
comes from one of two species (call them \emph{black} and
\emph{white}). We have a number of experts who come in and classify the
specimens, in the following manner. They take two specimens, and declare
them to be either \emph{same} or \emph{different}. 

This is done $m$ times. At the end of this process, we have a collection
of classification of pairs. We'd like to check whether this classification
is \emph{consistent} i.e, is there a way of assigning specimens to species
in such a way that no pair of specimens from the same species was declared
to be \emph{different}, and no pair of specimens declared \emph{different}
were from the same species. 

Present an algorithm to check consistency that runs in time $O(m+n)$. 

\textbf{HINT:} Read Chapter 3.


\section{Checkers*}
\label{sec:checkers-the-easy}

Researchers from the University of Alberta recently announced that they
had cracked the game of checkers, determining that it always ends in a
draw. In this assignment, we're going to solve a much simpler problem on a
checkerboard. 

A variant of checkers (where all pieces are ``kings'') works as follows:
On an $8\times 8$ board, white and black pieces are placed in the
configuration given below. 

\begin{center}
  \includegraphics[width=2in]{checkers1}
\end{center}

A move consists of one of the following options:

\begin{itemize}
\item A player moves a piece to an empty adjacent spot of the same
  color.
\item A player \emph{jumps}, by moving to a position two steps away in a
  particular direction, as long as there's an opposing piece in
  between. This piece is said to be \emph{captured}  and is removed from
  the field of play. A multiple-jump move is permitted. 
\end{itemize}

A player wins if they are able to capture all opposing pieces. Note that
the way the pieces are placed, only squares of a single color on the
checkerboard are used. 

The question is this: given an initial configuration of $n$ pieces on a
checkerboard of size $m$, can White win in a single move ? Your answer
should run in time linear in $n, m$, and partial credit will be given for
more inefficient algorithms. If you wish, you may assume that you are also
told which white piece to use, although the problem can be solved within
the desired time bounds without this assumption.

\begin{center}
  \includegraphics[width=2in]{checkers3}
\end{center}


\textbf{HINT:} Construct an appropriate graph.
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "0"
%%% End: