\documentclass[12pt]{article}

\usepackage{graphicx}

\newfont{\bssdoz}{cmssbx10 scaled 1200}
\newfont{\bssten}{cmssbx10}


\oddsidemargin  0in \evensidemargin 0in \topmargin -0.5in
\headheight 0.25in \headsep 0.25in
\textwidth   6.5in \textheight 9in %\marginparsep 0pt \marginparwidth 0pt
\parskip 1.5ex  \parindent 0ex \footskip 20pt

\begin{document}
\parindent 0ex
\thispagestyle{empty} \vspace*{-0.75in}
{\bssdoz CME 305: Discrete Mathematics and Algorithms}
{\\ \bssten Instructor: Professor Amin Saberi (saberi@stanford.edu) }
{\\ \bssten HW\#3 --  Due 03/12/09}
\vspace{5pt}

\begin{enumerate}

\item Kleinberg and Tardos Problem 8.28

\item Let $A$ be a $n \times n$ matrix, $B$ a $n \times n$ matrix and $C$ 
a $n \times n$ matrix. We want to design an algorithm that checks whether 
$AB = C$ without calculating the product $AB$. Provide a randomized algorithm
that accomplishes this in $O(n^2)$ time with high probability.

\item A tournament is a complete directed graph i.e. a directed graph
which has exactly one edge between each pair of vertices. A Hamiltonian
path is a path that traverses each vertex exactly once. A random
tournament, is a tournament in which the direction of all edges is
selected independently and uniformly at random.
\begin{enumerate}
\item What is the expected value of the number Hamiltonian paths in a 
random tournament?
\item Use part $(a)$ to show that for every n, there is a tournament with 
$n$ players and at least \[\frac{n!}{2^{n-1}}\] Hamiltonian paths.
\end{enumerate}

\item In class we proved that the presorted Longest Processing Time (LPT)
minimum makespan approximation algorithm gives a $3/2$-approximation, but noted
that this is not the best bound possible.

Show that LPT is a $4/3$-approximation. Give an example to show this bound is tight.

\item Kleinberg and Tardos Problem 11.10

\item The final expectations for the project are $(1)$ a literature survey,
$(2)$ understanding of chosen topic and an exposition of current state
of the art $(3)$ some type of extension e.g. coding up an algorithm,
proving a lemma missing from the paper, solving an open problem etc...

Submit a small write up (one per group) describing what your extension 
will be. 

\item Extra Credit: Solve Problem $3$ from the midterm.

\end{enumerate}


\end{document}