# HG changeset patch # User Christian Urban # Date 1485957295 0 # Node ID 62389faa66e431a04cf5d8d074fa1f2d061fec51 # Parent 293ea84d82cafa8d3a4f4939711b8f9fb4a1be54 updated diff -r 293ea84d82ca -r 62389faa66e4 cws/cw01.pdf Binary file cws/cw01.pdf has changed diff -r 293ea84d82ca -r 62389faa66e4 cws/cw01.tex --- 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} diff -r 293ea84d82ca -r 62389faa66e4 cws/cw02.pdf Binary file cws/cw02.pdf has changed diff -r 293ea84d82ca -r 62389faa66e4 cws/cw02.tex --- 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} diff -r 293ea84d82ca -r 62389faa66e4 cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r 293ea84d82ca -r 62389faa66e4 cws/cw03.tex --- 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 diff -r 293ea84d82ca -r 62389faa66e4 cws/cw04.pdf Binary file cws/cw04.pdf has changed diff -r 293ea84d82ca -r 62389faa66e4 cws/cw04.tex --- 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}