pep-material: comparison cws/cw03.tex

equal deleted inserted replaced

-:438459a8e48b
+:8c868feb917b
 setpieces={Ng7, Nb2},
 boardfontsize=12pt,labelfontsize=9pt]}
 \subsection*{Reference Implementation}
-The Scala assignment comes with reference implementations in form of
+This Scala assignment comes with three reference implementations in form of
-a \texttt{jar}-files. This allows you to run any test cases on your own
+\texttt{jar}-files. This allows you to run any test cases on your own
 computer. For example you can call Scala on the command line with the
 option \texttt{-cp knight1.jar} and then query any function from the
-template file.
+\texttt{knight1.scala} template file. As usual you have to
+prefix the calls with \texttt{CW8a}, \texttt{CW8b} and \texttt{CW8c}.
+Since some of the calls are time sensitive, I included some timing
+information. For example
 \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
 $ scala -cp knight1.jar
 scala> CW8a.enum_tours(5, List((0, 0))).length
 Time needed: 1.722 secs.
 res0: Int = 304
 scala> CW8a.print_board(8, CW8a.first_tour(8, List((0, 0))).get)
 lists into just a list, \texttt{\_::\_} puts an element on the head of
 the list, \texttt{.head} gives you the first element of a list (make
 sure the list is not \texttt{Nil}); a useful option function:
 \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.\medskip
+this function takes an \texttt{Int} as an argument.\medskip
 \noindent
 \textbf{Part 2} a useful list function: \texttt{.sortBy} sorts a list
 according to a component given by the function; a function can be
-tested to be tail recursive by annotation \texttt{@tailrec}, which is
+tested to be tail-recursive by annotation \texttt{@tailrec}, which is
-made available by importing \texttt{scala.annotation.tailrec}.
+made available by importing \texttt{scala.annotation.tailrec}.\medskip
 \subsection*{Part 1 (6 Marks)}
 \item[(3)] Implement two recursive functions (\texttt{count\_tours} and
 \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]
+collects all tours in a list of paths. These functions will be
+called with a path containing a single position---the starting field.
+They are expected to extend this path so as to find all tours starting
+from the given position.\\
+\mbox{}\hfill[2 Marks]
 \end{itemize}
 \noindent \textbf{Test data:} For the marking, the functions in (3)
 will be called with board sizes up to $5 \times 5$. If you search
 for tours on a $5 \times 5$ board starting only from field $(0, 0)$,
 \subsubsection*{Tasks (file knight2.scala)}
 \begin{itemize}
 \item[(6)] Write a function \texttt{ordered\_moves} that calculates a list of
-onward moves like in (2) but orders them according to the
+onward moves like in (2) but orders them according to
 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[(7)] Implement a \texttt{first\_closed\_tour\_heuristic}
 function that searches for a single
 \item[(8)] Implement a \texttt{first\_tour\_heuristic} function
 for boards up to
 $30\times 30$.  It is the same function as in (7) but searches for
 tours (not just closed tours). It might be called with any field on the
-board as start.\\
+board as starting field.\\
 %You have to be careful to write a
 %tail-recursive function of the \texttt{first\_tour\_heuristic} function
 %otherwise you will get problems with stack-overflows.\\
 \mbox{}\hfill[1 Mark]
 \end{itemize}
 \subsubsection*{Task (file knight3.scala)}
 \begin{itemize}
 \item[(9)] Implement a function \texttt{tour\_on\_mega\_board} which is
-the same function as (7), \textbf{but} can deal with boards up to
+the same function as in (8), \textbf{but} should be able to
-$70\times 70$ \textbf{within 30 seconds}. This will be tested
+deal with boards up to
+$70\times 70$ \textbf{within 30 seconds} (on my laptop). This will be tested
 by starting from field $(0, 0)$. You have to be careful to
 write a tail-recursive function otherwise you will get problems
 with stack-overflows. Please observe the requirements about
 the submissions: no tricks involving \textbf{.par}.\medskip
-The timelimit of 30 secs is with respect to the laptop on which the
+The timelimit of 30 seconds is with respect to the laptop on which the
-marking will happen. You can estimate how well your
+marking will happen. You can roughly estimate how well your
 implementation performs by running \texttt{knight3.jar} on your
-computer. For example:
+computer. For example the reference implementation shows
+on my laptop:
 \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
 $ scala -cp knight3.jar
 scala> CW8c.tour_on_mega_board(70, List((0, 0)))

changeset 216	8c868feb917b
parent 213	f968188d4a9b
child 265	59779ce322a6