\documentclass[12pt]{course}
\usepackage[bf,up]{caption}
\usepackage{tikz}

\pgfdeclareimage[width=120pt, interpolate=true]{sudoku1}{images/sudoku1}
\pgfdeclareimage[width=120pt, interpolate=true]{sudoku2}{images/sudoku2}
\renewcommand\captionfont\slshape
\newcommand\KT{K\&T}

\begin{document}

\course{4820}{Introduction to Analysis of Algorithms}{Spring 2013}
\assign{Homework 1}{Due Thursday, January 31, 2013}

\maketitle

\noindent
\textbf{Instructions.}
Submit your solutions electronically to CMS.
Remember that when a problem asks you to design an
algorithm, you must also prove correctness and analyze its running time.

\begin{exercises}
\item (10 points)
In real life, there often arise computational problems that are underspecified, imprecise, sometimes even contradictory. Part of the task of good algorithm design is understanding the essence of the problem and stating it precisely.

The following problems are stated in English. Formalize them as matching problems on graphs. A solution to your graph problem should give a solution to the problem as stated here. Say what entities in the statement of the problem the nodes and edges of the graph represent, and explain how the constraints on the solution as expressed in English in the statement of the problem are captured by your formalization. You should not restrict to the problem sizes as given here, but try to formulate interesting versions of unbounded size. You do not need to give algorithms to solve the problems (unless you want to). 
\begin{enumerate}
\item
You are trying to arrange the fall schedule of an amateur football league in upstate New York.  The league consists of ten teams divided into two divisions, East and West, with five teams each.  During the season, each team is to play all other teams in its division twice, once at home and once away.  In addition, each team will play crossover games with two teams from the other division, one at home and one away. Each team plays at most one game each weekend. The schedule should take no more weekends than necessary.
\item
Sudoku is a popular puzzle in which the digits from 1 to 9 must be placed in a $9\times 9$ grid so that every digit appears exactly once in each row, column, and $3\times 3$ box as shown.
\begin{figure}[h]
\begin{center}
\begin{pgfpicture}
\pgftext[at=\pgfpoint{0pt}{0pt},left,bottom]{\pgfuseimage{sudoku1}}
\pgftext[at=\pgfpoint{150pt}{0pt},left,bottom]{\pgfuseimage{sudoku2}}
\end{pgfpicture}
\end{center}
\caption{A Sudoku puzzle and its solution}
\end{figure}
Given a partially filled-in Sudoku grid, the problem is to fill in the rest of the grid so as to satisfy all the constraints.
\end{enumerate}

\item (10 points)
In the stable matching problem presented in class, both the employers and the candidates specify their preferences by providing a linear ranking of the other group in the form of a total ordering.  Suppose we weaken the requirement to say that the preferences need not be a total order, but only a preorder (a reflexive and transitive binary relation $\leq$). We write $x < y$ if $x\leq y$ but not $y\leq x$. A finite preorder can be specified by a directed graph, where $x\leq y$ if there is a directed path of length $0$ or more from $x$ to $y$. In this situation, let us say that a matching $M$ is \emph{unstable} if there are matched pairs $(a,b),(a',b')\in M$ such that $a$ strictly prefers $b'$ to $b$ (that is, $b<b'$ in the preorder of $a$) and $b'$ strictly prefers $a$ to $a'$. Show how to solve the stable matching problem with this weakened definition of preference. (\emph{Hint}. Given the graphs specifying the preorders for the employers and candidates, do a precomputation that reduces the problem to the original version discussed in class. Your precomputation will involve concepts from \S3.5 and \S3.6 of \KT.)

\item (10 points)
\KT\ Ch.~1 Ex.~3.

\end{exercises}
\end{document}
