pep-material: comparison cws/cw02.tex

equal deleted inserted replaced

-:293ea84d82ca
+:62389faa66e4
 lectures.  Make sure the files you submit can be processed by just
 calling \texttt{scala <<filename.scala>>}.\bigskip
 \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
 copy any code you need from files \texttt{knight1.scala},
 \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}
 It should be understood that the work you submit represents
 uploaded to KEATS, which you can freely use.\medskip
 \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
+the knight visits every field on an $n\times n$ chessboard once. For
-a tour is called \emph{open} tour. For example on a $5\times 5$
+example on a $5\times 5$ chessboard, a knight's tour is:
-chessboard, an open  knight's tour is:
 \chessboard[maxfield=d4,
 pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
 text = \small 24, markfield=Z4,
 $2\times 2$, $3\times 3$ and $4\times 4$ chessboards, but for every
 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
-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
 example
 \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
 $8\times 8$ board for a knight on position $(2, 2)$ and otherwise
 empty board, the legal-moves function should produce the onward
 \end{center}
 \mbox{}\hfill[1 Mark]
 \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
+arguments. They exhaustively search for tours starting
-from the given path. The first function counts all possible open
+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.}
 \subsubsection*{Tasks (file knight2.scala)}
 point however you should take into account when implementing
 \textit{first}: you will need to calculate what the result of $f(x)$
 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}
 \noindent
 sizes of up to $8 \times 8$.
 \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
 a knight on field $(1, 3)$, the field $(0, 1)$ has the fewest possible
 onward moves, namely 2.
 the 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 $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}
 \end{document}

changeset 110	62389faa66e4
parent 86	f8a781322499
child 144	716042628398