Binary file cws/cw02.pdf has changed
--- a/cws/cw02.tex Fri Nov 25 12:10:00 2016 +0000
+++ b/cws/cw02.tex Sat Nov 26 17:02:52 2016 +0000
@@ -26,7 +26,7 @@
\noindent
\textbf{Important:} Do not use any mutable data structures in your
-submissions! They are not needed. This excluded the use of
+submissions! They are not needed. This excludes the use of
\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
@@ -45,8 +45,9 @@
\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. For
-example on a $5\times 5$ chessboard, a knight's tour is:
+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:
\chessboard[maxfield=d4,
@@ -82,7 +83,7 @@
The tour starts in the right-upper corner, then moves to field
$(3,2)$, then $(4,0)$ and so on. There are no knight's tours on
$2\times 2$, $3\times 3$ and $4\times 4$ chessboards, but for every
-bigger board there is.
+bigger board there is.
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
@@ -172,7 +173,7 @@
\noindent
Let us first fix the basic datastructures for the implementation. The
board dimension is an integer (we will never go beyond board sizes of
-$100 \times 100$). A \emph{position} (or field) on the chessboard is
+$50 \times 50$). A \emph{position} (or field) on the chessboard is
a pair of integers, like $(0, 0)$. A \emph{path} is a list of
positions. The first (or 0th move) in a path is the last element in
this list; and the last move in the path is the first element. For
@@ -244,7 +245,7 @@
\begin{itemize}
\item[(2a)] Implement a first-function. This function takes a list of
positions and a function $f$ as arguments. The function $f$ takes a
- position as argument and produces an optional path. So its type is
+ position as argument and produces an optional path. So $f$'s type is
\texttt{Pos => Option[Path]}. The idea behind the first-function is
as follows:
@@ -322,7 +323,9 @@
position $(dimension / 2, dimension / 2)$).
\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.
+ It is the same function as in (3b) but searches for \textbf{open} 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.
\end{itemize}
\end{document}
Binary file cws/cw03.pdf has changed
--- a/cws/cw03.tex Fri Nov 25 12:10:00 2016 +0000
+++ b/cws/cw03.tex Sat Nov 26 17:02:52 2016 +0000
@@ -16,7 +16,7 @@
\noindent
\textbf{Important:} Do not use any mutable data structures in your
-submission! They are not needed. This excluded the use of
+submission! They are not needed. This excludes the use of
\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. Make sure the