Binary file cws/cw01.pdf has changed
--- a/cws/cw01.tex Fri Jan 27 14:55:56 2017 +0000
+++ b/cws/cw01.tex Wed Feb 01 13:54:55 2017 +0000
@@ -16,13 +16,13 @@
\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. 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}
Binary file cws/cw02.pdf has changed
--- 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}
Binary file cws/cw03.pdf has changed
--- a/cws/cw03.tex Fri Jan 27 14:55:56 2017 +0000
+++ b/cws/cw03.tex Wed Feb 01 13:54:55 2017 +0000
@@ -15,17 +15,18 @@
\noindent
\textbf{Important:} Do not use any mutable data structures in your
-submission! They are not needed. This excludes the use of
+submission! They are not needed. This menas 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. 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!!!!!!!!}
+\subsection*{Disclaimer}
It should be understood that the work you submit represents
your own effort! You have not copied from anyone else. An
@@ -53,7 +54,7 @@
\end{center}
\noindent
-Why? Knowing how to match regular expressions and strings fast will
+Why? Knowing how to match regular expressions and strings will
let you solve a lot of problems that vex other humans. Regular
expressions are one of the fastest and simplest ways to match patterns
in text, and are endlessly useful for searching, editing and
Binary file cws/cw04.pdf has changed
--- a/cws/cw04.tex Fri Jan 27 14:55:56 2017 +0000
+++ b/cws/cw04.tex Wed Feb 01 13:54:55 2017 +0000
@@ -13,13 +13,13 @@
\noindent
\textbf{Important:} Do not use any mutable data structures in your
-submission! They are not needed. This excludes the use of
+submission! They are not needed. This menas 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. 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 will be
-restricted to a maximum of 360 seconds.
+restricted to a maximum of 360 seconds on my laptop.
\subsection*{Disclaimer}
@@ -43,7 +43,7 @@
\item[(1)] First write a polymorphic function that recursively
transforms a list of options into an option of a list. For example,
if you have the lists on the left-hand side, they should be transformed into
- the option on the right-hand side:
+ the options on the right-hand side:
\begin{center}
\begin{tabular}{lcl}