% -*- compile-command: "rubber -d hw.4.tex" -*-
\documentclass{tufte-handout}
\usepackage{times,graphicx,epstopdf,fancyhdr,amsfonts,amsthm,amsmath,url,xspace,algorithm,algorithmic,enumitem,hyperref}

\pagestyle{fancy}

\lhead{CSCI 280: Algorithms -- Spring 2017}
\chead{}
\rhead{Brent Yorgey}
\lfoot{Homework 4}
\rfoot{Due: 4:00pm, Friday, February 17}
\cfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
%\renewcommand{\footwidth}{\textwidth}
%\addtolength{\headwidth}{\marginparwidth}
%\addtolength{\headwidth}{\marginparsep}
\renewcommand{\footrulewidth}{0.4pt}

\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}

\theoremstyle{definition}
\newtheorem{question}{Question}

\begin{document}

\textbf{Reminder}: as specified in the
\href{http://ozark.hendrix.edu/~yorgey/ac-integrity-policy.html}{Computer
  Science Academic Integrity Policy}, you should not \textbf{look
  at} any other student's code.  You are free to discuss data
structures, general approaches, and so on; for any specific
debugging help you should come to me.

\begin{question}
  On the course website you will find several data files describing
  directed graphs.  The format of each file is as follows:
  \begin{itemize}
  \item The first line contains a single integer $n$ giving the number
    of nodes in the graph.
  \item The second line contains a single integer $m$ giving the
    number of edges.
  \item Each of the following $m$ lines contains a pair of integers
    $x$ and $y$ separated by a space, indicating a directed edge from
    node $x$ to node $y$.  The nodes are numbered $0$ through $n-1$.
  \end{itemize}

  For example, \verb|demo-cycle.in| looks like this:
\begin{verbatim}
10
18
5 0
1 8
2 5
3 5
4 0
6 2
9 3
4 9
6 7
7 4
7 5
9 5
2 9
4 1
7 0
2 7
6 3
4 6
\end{verbatim}
  It describes a directed graph with $10$ nodes (numbered $0$ through
  $9$) and $18$ edges.  The edges are $(5,0)$, $(1,8)$, and so on.

  For each input graph, you should determine whether it is a DAG or
  not (that is, whether or not it is acyclic).  In addition:
  \begin{itemize}
  \item If it is a DAG, you should specify a topological ordering.
  \item If it is not a DAG, you should specify a directed cycle in the graph.
  \end{itemize}

  For each input graph, you should create an output file with the
  following format:
  \begin{itemize}
  \item For \verb|<FILENAME>.in| the corresponding output file should
    be called \verb|<FILENAME>.out|.
  \item The first line of the output file should contain either
    the string \verb|DAG| or the string \verb|cycle|, indicating
    whether or not the input graph is a DAG.
  \item If the first line contains \verb|DAG|, the remaining lines
    should list all the vertices of the graph in some topological
    ordering, with one vertex per line.
  \item If the first line contains \verb|cycle|, the remaining lines
    should list the vertices contained in some directed cycle.  The
    first vertex should \emph{not} be repeated at the end.
  \end{itemize}
  For example, one correct output for \verb|demo-cycle.in| is
  contained in \verb|demo-cycle.out|, and looks like this:
\begin{verbatim}
cycle
6
7
4
\end{verbatim}
  As you can verify, the graph described in \verb|demo-cycle.in| does
  indeed contain the edges $(6,7)$, $(7,4)$, and $(4,6)$, which form a
  directed cycle.

  Likewise, a correct output for \verb|demo-dag.in| (which is a DAG)
  is contained in \verb|demo-dag.out|.  Note that in general there may
  be many different correct output files, since a graph may contain
  many different cycles or many possible topological orderings.

  There are four sizes of graph: \verb|tiny| ($n = 10$), \verb|small|
  ($n = 10^3$), \verb|med| ($n = 10^5$) and \verb|big| ($n = 10^6$).
  The graphs are \emph{sparse} in the sense that they have only $O(n)$
  edges.  Note that a $\Theta(n^2)$ algorithm will probably work for
  \verb|tiny| and \verb|small| (and \emph{perhaps} even for \verb|med|
  if you are willing to wait long enough), but you will almost
  certainly need a $\Theta(m+n)$ algorithm (which is $\Theta(n)$ for
  these graphs) to solve the \verb|big| graphs.

  For each size, there are two graphs.  You should \textbf{not} assume
  that there is one DAG and one cyclic graph of each size!

  You can use the provided Python program \verb|check-graph.py| to
  check your answers.  Simply provide it with the name of the input
  graph file and the name of your output file, like this:
\begin{verbatim}
$ python check-graph.py demo-cycle.in demo-cycle.out
Checking cycle...
Cycle looks good!
\end{verbatim}
  If the output is incorrect, the tool will give a counterexample, for
  example:
\begin{verbatim}
$ python check-graph.py demo-cycle.in demo-dag.out
Checking DAG...
Found bad edge: 2 5
\end{verbatim}
  This means that although the output file claims to give a
  topological ordering for the DAG, the edge $(2,5)$ is contained in
  the graph and goes backwards from a later node in the ordering to an
  earlier one, so it is not in fact a topological ordering.

\paragraph{What to turn in}
  \begin{itemize}
  \item \textbf{Print out on paper} any program(s) you write and turn them in.
  \item \textbf{Electronically submit} the output files containing
    topological orderings.  Remember that the output file for
    \verb|<FILENAME>.in| should be named \verb|<FILENAME>.out|.

    % In S'17, Moodle allowed 20MB to be turned in, so this was not
    % necessary.  The "robotics lab" is now Drew Tomlin's office in
    % any case.
    %
    % \textbf{Special note}: although you should be able to turn in
    % output files for \verb|tiny|, \verb|small|, and \verb|med| via
    % Moodle, the output files for \verb|big| will be too big (around
    % 6 MB)!  If you want to submit \verb|big| output files, you can turn
    % them in to me on a USB flash drive (if you need one, there are a
    % bunch of random old ones sitting in the robotics lab across from
    % my office).
  \end{itemize}

\paragraph{Grading scheme}

Each input graph is worth a certain number of points as follows:
\begin{itemize}
\item \verb|tiny|: 2 points each
\item \verb|small|: 3 points each
\item \verb|med|: 3 points each
\item \verb|big|: 2 points each
\end{itemize}
giving a total of 20 possible points.  Full credit will be given for
any correct output file.  Half credit will be given for an output file
which correctly specifies \verb|DAG| or \verb|cycle| but does not give
correct evidence for it.  (For example, if you determine that an input
graph must have cycles but you do not know how to find one, you could
just turn in an output file containing the single line \verb|cycle|,
with no list of vertices following; this would earn half credit.)

You are not \emph{required} to write a program, but you will probably
not be able to get many points otherwise (you can certainly construct
correct \verb|tiny| outputs by hand---in fact, I recommend it, as a
way to determine whether your program is behaving correctly!---but
even the \verb|small| graphs, with $n = 10^3$, would probably be too
tedious to do by hand).  You \textbf{must} turn in any programs you
write, though the programs themselves will not be graded.

\end{question}

\begin{question}
  How hard was this assigment, on a scale of 1--10? How long would you
  estimate that you spent on it?
\end{question}

\end{document}




