cws/cw02.tex
changeset 110 62389faa66e4
parent 86 f8a781322499
child 144 716042628398
--- a/cws/cw02.tex	Fri Jan 27 14:55:56 2017 +0000
+++ b/cws/cw02.tex	Wed Feb 01 13:54:55 2017 +0000
@@ -27,7 +27,7 @@
 
 \noindent
 \textbf{Important:} Do not use any mutable data structures in your
-submissions! They are not needed. This excludes the use of
+submissions! They are not needed. This means you cannot use
 \texttt{ListBuffer}s, for example. Do not use \texttt{return} in your
 code! It has a different meaning in Scala, than in Java.
 Do not use \texttt{var}! This declares a mutable variable. Feel free to
@@ -35,7 +35,8 @@
 \texttt{knight2.scala} and \texttt{knight3.scala}. Make sure the
 functions you submit are defined on the ``top-level'' of Scala, not
 inside a class or object. Also note that the running time of
-each part will be restricted to a maximum of 360 seconds. 
+each part will be restricted to a maximum of 360 seconds on my
+laptop.
 
  
 \subsection*{Disclaimer}
@@ -48,9 +49,8 @@
 \subsection*{Background}
 
 The \textit{Knight's Tour Problem} is about finding a tour such that
-the knight visits every field on an $n\times n$ chessboard once. Such
-a tour is called \emph{open} tour. For example on a $5\times 5$
-chessboard, an open  knight's tour is:
+the knight visits every field on an $n\times n$ chessboard once. For
+example on a $5\times 5$ chessboard, a knight's tour is:
 
 
 \chessboard[maxfield=d4, 
@@ -90,7 +90,7 @@
 
 A knight's tour is called \emph{closed}, if the last step in the tour
 is within a knight's move to the beginning of the tour. So the above
-knight's tour is \underline{not} closed (it is open) because the last
+knight's tour is \underline{not} closed because the last
 step on field $(0, 4)$ is not within the reach of the first step on
 $(4, 4)$. It turns out there is no closed knight's tour on a $5\times
 5$ board. But there are on a $6\times 6$ board and on bigger ones, for
@@ -199,12 +199,12 @@
 \subsubsection*{Tasks (file knight1.scala)}
 
 \begin{itemize}
-\item[(1a)] Implement an is-legal-move function that takes a
+\item[(1a)] Implement an \texttt{is-legal-move} function that takes a
   dimension, a path and a position as argument and tests whether the
   position is inside the board and not yet element in the
   path. \hfill[1 Mark]
 
-\item[(1b)] Implement a legal-moves function that calculates for a
+\item[(1b)] Implement a \texttt{legal-moves} function that calculates for a
   position all legal onward moves. If the onward moves are
   placed on a circle, you should produce them starting from
   ``12-oclock'' following in clockwise order.  For example on an
@@ -227,19 +227,19 @@
 
 \item[(1c)] Implement two recursive functions (count-tours and
   enum-tours). They each take a dimension and a path as
-  arguments. They exhaustively search for {\bf open} tours starting
-  from the given path. The first function counts all possible open
+  arguments. They exhaustively search for tours starting
+  from the given path. The first function counts all possible 
   tours (there can be none for certain board sizes) and the second
-  collects all open tours in a list of paths.\hfill[2 Marks]
+  collects all tours in a list of paths.\hfill[2 Marks]
 \end{itemize}
 
 \noindent \textbf{Test data:} For the marking, the functions in (1c)
 will be called with board sizes up to $5 \times 5$. If you search
-for open tours on a $5 \times 5$ board starting only from field $(0, 0)$,
+for tours on a $5 \times 5$ board starting only from field $(0, 0)$,
 there are 304 of tours. If you try out every field of a $5 \times
-5$-board as a starting field and add up all open tours, you obtain
+5$-board as a starting field and add up all tours, you obtain
 1728. A $6\times 6$ board is already too large to be searched
-exhaustively.\footnote{For your interest, the number of open tours on
+exhaustively.\footnote{For your interest, the number of tours on
   $6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320,
   19591828170979904, respectively.}
 
@@ -271,7 +271,7 @@
   is; your code should do this only \textbf{once}!\\\mbox{}\hfill[1 Mark]
   
 \item[(2b)] Implement a first-tour function that uses the
-  first-function from (2a), and searches recursively for an open tour.
+  first-function from (2a), and searches recursively for a tour.
   As there might not be such a tour at all, the first-tour function
   needs to return an \texttt{Option[Path]}.\\\mbox{}\hfill[2 Marks]
 \end{itemize}
@@ -283,9 +283,9 @@
 
 \subsection*{Part 2 (3 Marks)}
 
-As you should have seen in Part 1, a naive search for open tours
+As you should have seen in Part 1, a naive search for tours
 beyond $8 \times 8$ boards and also searching for closed tours
-takes too much time. There is a heuristic (called Warnsdorf's rule)
+takes too much time. There is a heuristic, called Warnsdorf's rule
 that can speed up finding a tour. This heuristic states that a knight
 is moved so that it always proceeds to the field from which the
 knight will have the \underline{fewest} onward moves.  For example for
@@ -331,7 +331,7 @@
   position $(dimension / 2, dimension / 2)$). \hfill[1 Mark]
 
 \item[(3c)] Implement a first-tour-heuristic function for boards up to $50\times 50$.
-  It is the same function  as in (3b) but searches for \textbf{open} tours. You have
+  It is the same function  as in (3b) but searches for tours. You have
   to be careful to write a tail-recursive version of the first-tour-heuristic
   function otherwise you will get problems with stack-overflows. \hfill[1 Mark]
 \end{itemize}