pep-material: comparison cws/cw02.tex

equal deleted inserted replaced

-:1347bbd86c52
+:780c40aaad27
 \documentclass{article}
 \usepackage{chessboard}
 \usepackage[LSBC4,T1]{fontenc}
 \let\clipbox\relax
 \usepackage{../style}
+\usepackage{disclaimer}
 \begin{document}
 \setchessboard{smallboard,
 zero,
 asked to implement Scala programs that solve various versions of the
 \textit{Knight's Tour Problem} on a chessboard. Note the second part
 might include material you have not yet seen in the first two
 lectures. \bigskip
-\noindent
+\IMPORTANT{}
-\textbf{Important:}
-\begin{itemize}
-\item Make sure the files you submit can be processed by just calling\\
-\mbox{\texttt{scala <<filename.scala>>}} on the commandline.
-\item Do not use any mutable data structures in your
-submissions! They are not needed. This means you cannot create new
-\texttt{Array}s or \texttt{ListBuffer}s, for example.
-\item Do not use \texttt{return} in your code! It has a different
-meaning in Scala, than in Java.
-\item Do not use \texttt{var}! This declares a mutable variable. Only
-use \texttt{val}!
-\item Do not use any parallel collections! No \texttt{.par} therefore!
-Our testing and marking infrastructure is not set up for it.
-\end{itemize}
-\noindent
 Also note that the running time of each part will be restricted to a
 maximum of 360 seconds on my laptop: If you calculate a result once,
 try to avoid to calculate the result again. Feel free to copy any code
 you need from files \texttt{knight1.scala}, \texttt{knight2.scala} and
 \texttt{knight3.scala}.
-\subsection*{Disclaimer}
+\DISCLAIMER{}
-It should be understood that the work you submit represents
-your \textbf{own} effort. You have not copied from anyone else. An
-exception is the Scala code I showed during the lectures or
-uploaded to KEATS, which you can freely use.
 \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
 \subsubsection*{Tasks (file knight1.scala)}
 \begin{itemize}
-\item[(1a)] Implement an \texttt{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
+dimension, a path and a position as arguments and tests whether the
 position is inside the board and not yet element in the
 path. \hfill[1 Mark]
-\item[(1b)] Implement a \texttt{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-o'clock'' following in clockwise order.  For example on an
-$8\times 8$ board for a knight on position $(2, 2)$ and otherwise
+$8\times 8$ board for a knight at position $(2, 2)$ and otherwise
 empty board, the legal-moves function should produce the onward
 positions in this order:
 \begin{center}
 \texttt{List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))}
 \begin{center}
 \texttt{List((6,5), (5,6))}
 \end{center}
 \mbox{}\hfill[1 Mark]
-\item[(1c)] Implement two recursive functions (count-tours and
+\item[(1c)] Implement two recursive functions (\texttt{count\_tours} and
-enum-tours). They each take a dimension and a path as
+\texttt{enum\_tours}). They each take a dimension and a path as
 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 tours in a list of paths.\hfill[2 Marks]
 \end{itemize}
 sure the list is not \texttt{Nil}).
 \subsubsection*{Tasks (file knight2.scala)}
 \begin{itemize}
-\item[(2a)] Implement a first-function. This function takes a list of
+\item[(2a)] Implement a \texttt{first}-function. This function takes a list of
-positions and a function $f$ as arguments. The function $f$ takes a
+positions and a function $f$ as arguments; $f$ is the name we give to
-position as argument and produces an optional path. So $f$'s type is
+this argument). The function $f$ takes a position as argument and
-\texttt{Pos => Option[Path]}. The idea behind the first-function is
+produces an optional path. So $f$'s type is \texttt{Pos =>
-as follows:
+Option[Path]}. The idea behind the \texttt{first}-function is as follows:
 \[
 \begin{array}{lcl}
 \textit{first}(\texttt{Nil}, f) & \dn & \texttt{None}\\
 \textit{first}(x\!::\!xs, f) & \dn & \begin{cases}
 \end{cases}
 \end{array}
 \]
 \noindent That is, we want to find the first position where the
-result of $f$ is not \texttt{None}, if there is one. Note that you
+result of $f$ is not \texttt{None}, if there is one. Note that
-do not (need to) know anything about the function $f$ except its
+`inside' \texttt{first}, you do not (need to) know anything about
-type, namely \texttt{Pos => Option[Path]}. There is one additional
+the argument $f$ except its type, namely \texttt{Pos =>
-point however you should take into account when implementing
+Option[Path]}. There is one additional point however you should
-\textit{first}: you will need to calculate what the result of $f(x)$
+take into account when implementing \texttt{first}: you will need to
-is; your code should do this only \textbf{once}!\\\mbox{}\hfill[1 Mark]
+calculate what the result of $f(x)$ is; your code should do this
+only \textbf{once} and for as \textbf{few} elements in the list as
+possible! Do not calculate $f(x)$ for all elements and then see which
+is the first \texttt{Some}.\\\mbox{}\hfill[1 Mark]
-\item[(2b)] Implement a first-tour function that uses the
+\item[(2b)] Implement a \texttt{first\_tour} function that uses the
-first-function from (2a), and searches recursively for a tour.
+\texttt{first}-function from (2a), and searches recursively for a tour.
-As there might not be such a tour at all, the first-tour function
+As there might not be such a tour at all, the \texttt{first\_tour} function
-needs to return an \texttt{Option[Path]}.\\\mbox{}\hfill[2 Marks]
+needs to return a value of type
+\texttt{Option[Path]}.\\\mbox{}\hfill[2 Marks]
 \end{itemize}
 \noindent
-\textbf{Testing:} The first tour function will be called with board
+\textbf{Testing:} The \texttt{first\_tour} function will be called with board
 sizes of up to $8 \times 8$.
 \bigskip
 \noindent
 \textbf{Hints:} a useful list function: \texttt{.filter(..)} filters a
 \texttt{.isDefined} returns true, if an option is \texttt{Some(..)};
 anonymous functions can be constructed using \texttt{(x:Int) => ...},
 this functions takes an \texttt{Int} as an argument.
-\newpage
+%%\newpage
 \subsection*{Part 2 (3 Marks)}
 As you should have seen in Part 1, a naive search for tours beyond
 $8 \times 8$ boards and also searching for closed tours even on small
-boards takes too much time. There is a heuristic, called Warnsdorf's
+boards takes too much time. There is a heuristic, called \emph{Warnsdorf's
-rule that can speed up finding a tour. This heuristic states that a
+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
 a knight on field $(1, 3)$, the field $(0, 1)$ has the fewest possible
 onward moves, namely 2.
 text = \small 5, markfield=b1,
 text = \small 2, markfield=Z1,
 setpieces={Na3}]
 \noindent
-Warnsdorf's rule states that the moves on the board above should be
+Warnsdorf's Rule states that the moves on the board above should be
 tried in the order
 \[
 (0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2)
 \]
 do not count moves that revisit any field already visited.
 \subsubsection*{Tasks (file knight3.scala)}
 \begin{itemize}
-\item[(3a)] Write a function ordered-moves that calculates a list of
+\item[(3a)] Write a function \texttt{ordered\_moves} that calculates a list of
 onward moves like in (1b) but orders them according to the
-Warnsdorf’s rule. That means moves with the fewest legal onward moves
+Warnsdorf’s Rule. That means moves with the fewest legal onward moves
 should come first (in order to be tried out first). \hfill[1 Mark]
-\item[(3b)] Implement a first-closed-tour-heuristic function that searches for a
+\item[(3b)] Implement a \texttt{first\_closed-tour\_heuristic}
+function that searches for a
 \textbf{closed} tour on a $6\times 6$ board. It should use the
-first-function from (2a) and tries out onward moves according to
+\texttt{first}-function from (2a) and tries out onward moves according to
-the ordered-moves function from (3a). It is more likely to find
+the \texttt{ordered\_moves} function from (3a). It is more likely to find
 a solution when started in the middle of the board (that is
 position $(dimension / 2, dimension / 2)$). \hfill[1 Mark]
-\item[(3c)] Implement a first-tour-heuristic function for boards up to
+\item[(3c)] Implement a \texttt{first\_tour\_heuristic} function
+for boards up to
 $40\times 40$.  It is the same function as in (3b) but searches for
 tours (not just closed tours). You have to be careful to write a
-tail-recursive version of the first-tour-heuristic function
+tail-recursive function of the \texttt{first\_tour\_heuristic} function
 otherwise you will get problems with stack-overflows.\\
 \mbox{}\hfill[1 Mark]
 \end{itemize}
 \bigskip

changeset 166	780c40aaad27
parent 163	84917f2e16cd
child 202	f7bcb27d1940