--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/cws/cw06.tex Tue May 15 01:14:07 2018 +0100
@@ -0,0 +1,163 @@
+\documentclass{article}[11pt]
+\usepackage{../style}
+\usepackage{../graphics}
+\usepackage{disclaimer}
+
+\begin{document}
+
+\section*{Resit Exam}
+
+The Scala part of the exam is worth 30\%. It is about `jumps'
+within lists.
+
+\IMPORTANTEXAM{}
+
+\DISCLAIMEREXAM{}
+
+%%\newpage
+
+\subsection*{Task}
+
+\noindent
+Suppose you are given a list of numbers. Each number indicates how many
+steps can be taken forward from this element. For example in the
+list
+
+\begin{center}
+\begin{tikzpicture}[scale=0.8]
+ \draw[line width=1mm,cap=round] (0,0) -- (5,0);
+ \draw[line width=1mm,cap=round] (0,1) -- (5,1);
+
+ \draw[line width=1mm,cap=round] (0,0) -- (0,1);
+ \node at (0.5,0.5) {\textbf{\Large 3}};
+
+ \draw[line width=1mm,cap=round] (1,0) -- (1,1);
+ \node at (1.5,0.5) {\textbf{\Large 4}};
+
+ \draw[line width=1mm,cap=round] (2,0) -- (2,1);
+ \node at (2.5,0.5) {\textbf{\Large 2}};
+
+ \draw[line width=1mm,cap=round] (3,0) -- (3,1);
+ \node at (3.5,0.5) {\textbf{\Large 0}};
+
+ \draw[line width=1mm,cap=round] (4,0) -- (4,1);
+
+ \node at (4.5,0.5) {\textbf{\Large 1}};
+
+ \draw[line width=1mm,cap=round] (5,0) -- (5,1);
+
+ \draw[->,line width=0.5mm,cap=round,out=90,in=90,relative] (0.5,1) to (1.5,1);
+ \draw[->,line width=0.5mm,cap=round,out=90,in=90,relative] (0.5,1) to (2.5,1);
+ \draw[->,line width=0.5mm,cap=round,out=90,in=90,relative] (0.5,1) to (3.5,1);
+
+ \draw[->,line width=0.5mm,cap=round,out=-90,in=-90,relative] (2.5,0) to (3.5,0);
+ \draw[->,line width=0.5mm,cap=round,out=-90,in=-90,relative] (2.5,0) to (4.5,0);
+
+ \draw[->,line width=0.5mm,cap=round,out=90,in=90,relative] (4.5,1) to (5.7,1);
+ \node at (5.7, 0.8) {End};
+\end{tikzpicture}
+\end{center}
+
+\noindent
+the first 3 indicates that you can step to the next three elements,
+that is 4, 2, and 0. The 2 in the middle indicates that you can step
+to elements 0 and 1. From the final 1 you can step to the End of the
+list. You can also do this from element 4, since the end of this list
+is reachable from there. A 0 always indicates that you cannot
+step any further from this element.\medskip
+
+\noindent
+The problem is to calculate a sequence of steps to reach the end of
+the list by taking only steps indicated by the integers. For the list
+above, possible sequence of steps are 3 - 2 - 1 - End, but also 3 - 4
+- End. This is a recursive problem that can be thought of as a tree
+where the root is a list and the children are all the lists that are
+reachable by a single step. For example for the list above this gives a
+tree like
+
+\begin{center}
+\begin{tikzpicture}[grow=right,level distance=30mm,child anchor=north]
+ \node {[3,4,2,0,1]}
+ child {node {[0,1]}}
+ child {node {[2,0,1]}
+ child {node {[1]} child [level distance=13mm] {node {End}}}
+ child {node {[0,1]}}
+ }
+ child {node {[4,2,0,1]\ldots}};
+\end{tikzpicture}
+\end{center}
+
+\subsubsection*{Tasks}
+
+\begin{itemize}
+\item[(1)] Write a function, called \texttt{steps}, that calculates
+ the children of a list. This function takes an integer as one argument
+ indicating how many children should be returned. The other argument is a list
+ of integers. In case of 3 and the list [4,2,0,1], it should produce
+ the list
+
+ \begin{center}
+ {\large[}\;[4,2,0,1],\; [2,0,1],\; [0,1]\;{\large]}
+ \end{center}
+
+ Be careful to account properly for the end of the list. For example
+ for the integer 4 and the list [2,0,1], the function should return the list
+
+ \begin{center}
+ {\large[}\;[2,0,1], [0,1],\; [1]\;{\large]}
+ \end{center}
+
+
+ \mbox{}\hfill[Marks: 8\%]
+
+\item[(2)] Write a function \texttt{search} that tests whether there
+ is a way to reach the end of a list. This is not always the
+ case, for example for the list
+
+ \begin{center}
+ [3,5,1,0,0,0,0,0,0,0,0,1]
+ \end{center}
+
+ \noindent
+ there is no sequence of steps that can bring you to the end of the list.
+ If there is a way, \texttt{search} should return true, otherwise false.
+ In case of the empty list, \texttt{search} should return true since the
+ end of the list is already reached.
+
+ \mbox{}\hfill\mbox{[Marks: 10\%]}
+
+\item[(3)] Write a function \texttt{jumps} that calculates the
+ shortest sequence of steps needed to reach the end of a list. One
+ way to calculate this is to generate \emph{all} sequences to reach
+ the end of a list and then select one that has the shortest length.
+ This function needs to return a value of type
+ \texttt{Option[List[Int]]} because for some lists there does not
+ exists a sequence at all. If there exists such a sequence,
+ \texttt{jumps} should return \texttt{Some(\ldots)}; otherwise
+ \texttt{None}. In the special case of the empty list, \texttt{jumps}
+ should return \texttt{None}
+
+ \mbox{}\hfill\mbox{[Marks: 12\%]}
+
+\end{itemize}\bigskip
+
+
+\noindent
+\textbf{Hints:} useful list functions: \texttt{.minBy(..)} searches for
+the first element in a list that is the minimum according to
+a given measure; \texttt{.length} calculates the length of a list;
+\texttt{.exists(..)} returns true when an element in a list
+satisfies a given predicate, otherwise returns false;
+\texttt{.map(..)} applies a given function to each element
+in a list; \texttt{.flatten} turns a list of
+lists into just a list; \texttt{\_::\_} puts an element on the head of
+the list.
+
+
+\end{document}
+
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
--- a/progs/mandelbrot.scala Mon Mar 12 12:11:50 2018 +0000
+++ b/progs/mandelbrot.scala Tue May 15 01:14:07 2018 +0100
@@ -113,7 +113,7 @@
val exb1 = Complex(-0.37465401, 0.659227668)
val exb2 = Complex(-0.37332410, 0.66020767)
-//time_needed(mandelbrot(exb1, exb2, 1000))
+time_needed(mandelbrot(exb1, exb2, 1000))
// example 3
val exc1 = Complex(0.435396403, 0.367981352)
@@ -127,7 +127,9 @@
time_needed(
for (i <- (0 to 12))
mandelbrot(exc1 + delta * i,
- exc2 - delta * i, 1000))val exc1 = Complex(0.435396403, 0.367981352)
+ exc2 - delta * i, 1000))
+
+val exc1 = Complex(0.435396403, 0.367981352)
val exc2 = Complex(0.451687191, 0.380210061)
//time_needed(mandelbrot(exc1, exc2, 1000))