cws/cw06.tex
changeset 486 9c03b5e89a2a
parent 485 19b75e899d37
child 487 efad9725dfd8
equal deleted inserted replaced
485:19b75e899d37 486:9c03b5e89a2a
     1 \documentclass{article}[11pt]
       
     2 \usepackage{../style}
       
     3 \usepackage{../graphics}
       
     4 \usepackage{disclaimer}
       
     5 
       
     6 \begin{document}
       
     7 
       
     8 \section*{Resit Exam}
       
     9 
       
    10 The Scala part of the exam is worth 50\%. It is about `jumps'
       
    11 within lists.
       
    12 
       
    13 \IMPORTANTEXAM{}
       
    14 
       
    15 \DISCLAIMEREXAM{}
       
    16  
       
    17 %%\newpage
       
    18 
       
    19 \subsection*{Task}
       
    20 
       
    21 \noindent
       
    22 Suppose you are given a list of numbers. Each number indicates how many
       
    23 steps can be taken forward from this element. For example in the
       
    24 list 
       
    25 
       
    26 \begin{center}
       
    27 \begin{tikzpicture}[scale=0.8]
       
    28   \draw[line width=1mm,cap=round] (0,0) -- (5,0);
       
    29   \draw[line width=1mm,cap=round] (0,1) -- (5,1);
       
    30 
       
    31   \draw[line width=1mm,cap=round] (0,0) -- (0,1);
       
    32   \node at (0.5,0.5) {\textbf{\Large 3}};
       
    33 
       
    34   \draw[line width=1mm,cap=round] (1,0) -- (1,1);
       
    35   \node at (1.5,0.5) {\textbf{\Large 4}};
       
    36 
       
    37   \draw[line width=1mm,cap=round] (2,0) -- (2,1);
       
    38   \node at (2.5,0.5) {\textbf{\Large 2}};
       
    39 
       
    40   \draw[line width=1mm,cap=round] (3,0) -- (3,1);
       
    41   \node at (3.5,0.5) {\textbf{\Large 0}};
       
    42   
       
    43   \draw[line width=1mm,cap=round] (4,0) -- (4,1);
       
    44 
       
    45   \node at (4.5,0.5) {\textbf{\Large 1}};
       
    46   
       
    47   \draw[line width=1mm,cap=round] (5,0) -- (5,1);
       
    48 
       
    49   \draw[->,line width=0.5mm,cap=round,out=90,in=90,relative] (0.5,1) to (1.5,1);
       
    50   \draw[->,line width=0.5mm,cap=round,out=90,in=90,relative] (0.5,1) to (2.5,1);
       
    51   \draw[->,line width=0.5mm,cap=round,out=90,in=90,relative] (0.5,1) to (3.5,1);
       
    52 
       
    53   \draw[->,line width=0.5mm,cap=round,out=-90,in=-90,relative] (2.5,0) to (3.5,0);
       
    54   \draw[->,line width=0.5mm,cap=round,out=-90,in=-90,relative] (2.5,0) to (4.5,0);
       
    55 
       
    56   \draw[->,line width=0.5mm,cap=round,out=90,in=90,relative] (4.5,1) to (5.7,1);
       
    57   \node at (5.7, 0.8) {End};
       
    58 \end{tikzpicture}
       
    59 \end{center}  
       
    60 
       
    61 \noindent
       
    62 the first 3 indicates that you can step to the next three elements,
       
    63 that is 4, 2, and 0. The 2 in the middle indicates that you can step
       
    64 to elements 0 and 1.  From the final 1 you can step to the End of the
       
    65 list. You can also do this from element 4, since the end of this list
       
    66 is reachable from there. A 0 always indicates that you cannot
       
    67 step any further from this element.\medskip
       
    68 
       
    69 \noindent
       
    70 The problem is to calculate a sequence of steps to reach the end of
       
    71 the list by taking only steps indicated by the integers. For the list
       
    72 above, possible sequences of steps are 3 - 2 - 1 - End, but also 3 - 4
       
    73 - End.  This is a recursive problem that can be thought of as a tree
       
    74 where the root is a list and the children are all the lists that are
       
    75 reachable by a single step. For example for the list above this gives a
       
    76 tree like
       
    77 
       
    78 \begin{center}
       
    79   \begin{tikzpicture}
       
    80     [grow=right,level distance=30mm,child anchor=north,line width=0.5mm]
       
    81   \node {[3,4,2,0,1]}
       
    82      child {node {[0,1]}}
       
    83      child {node {[2,0,1]}
       
    84         child {node {[1]} child [level distance=13mm] {node {End}}}
       
    85         child {node {[0,1]}}
       
    86      }
       
    87      child {node {[4,2,0,1]\ldots}};
       
    88 \end{tikzpicture}
       
    89 \end{center}
       
    90 
       
    91 \subsubsection*{Tasks}
       
    92 
       
    93 \begin{itemize}
       
    94 \item[(1)] Write a function, called \texttt{steps}, that calculates
       
    95   the children of a list. This function takes an integer as one argument
       
    96   indicating how many children should be returned. The other argument is a list
       
    97   of integers.  In case of 3 and the list [4,2,0,1], it should produce
       
    98   the list
       
    99 
       
   100   \begin{center}
       
   101   {\large[}\;[4,2,0,1],\; [2,0,1],\; [0,1]\;{\large]}
       
   102   \end{center}  
       
   103 
       
   104   Be careful to account properly for the end of the list. For example
       
   105   for the integer 4 and the list [2,0,1], the function should return the list
       
   106 
       
   107   \begin{center}
       
   108   {\large[}\;[2,0,1], [0,1],\; [1]\;{\large]}
       
   109   \end{center}  
       
   110 
       
   111 
       
   112   \mbox{}\hfill[Marks: 12\%]
       
   113  
       
   114 \item[(2)] Write a function \texttt{search} that tests whether there
       
   115   is a way to reach the end of a list.  This is not always the
       
   116   case, for example for the list
       
   117 
       
   118   \begin{center}
       
   119     [3,5,1,0,0,0,0,0,0,0,0,1]
       
   120   \end{center}
       
   121 
       
   122   \noindent
       
   123   there is no sequence of steps that can bring you to the end of the list.
       
   124   If there is a way, \texttt{search} should return true, otherwise false.
       
   125   In case of the empty list, \texttt{search} should return true since the
       
   126   end of the list is already reached.
       
   127   
       
   128   \mbox{}\hfill\mbox{[Marks: 18\%]}
       
   129 
       
   130 \item[(3)] Write a function \texttt{jumps} that calculates the
       
   131   shortest sequence of steps needed to reach the end of a list. One
       
   132   way to calculate this is to generate \emph{all} sequences to reach
       
   133   the end of a list and then select one that has the shortest length.
       
   134   This function needs to return a value of type
       
   135   \texttt{Option[List[Int]]} because for some lists there does not
       
   136   exists a sequence at all. If there exists such a sequence,
       
   137   \texttt{jumps} should return \texttt{Some(\ldots)}; otherwise
       
   138   \texttt{None}. In the special case of the empty list, \texttt{jumps}
       
   139   should return \texttt{None}
       
   140 
       
   141   \mbox{}\hfill\mbox{[Marks: 20\%]}
       
   142   
       
   143 \end{itemize}\bigskip
       
   144 
       
   145 
       
   146 \noindent
       
   147 \textbf{Hints:} useful list functions: \texttt{.minBy(..)} searches for
       
   148 the first element in a list that is the minimum according to
       
   149 a given measure; \texttt{.length} calculates the length of a list;
       
   150 \texttt{.exists(..)} returns true when an element in a list
       
   151 satisfies a given predicate, otherwise returns false;
       
   152 \texttt{.map(..)} applies a given function to each element
       
   153 in a list; \texttt{.flatten} turns a list of
       
   154 lists into just a list; \texttt{\_::\_} puts an element on the head of
       
   155 the list.
       
   156 
       
   157 
       
   158 \end{document}
       
   159 
       
   160 
       
   161 %%% Local Variables: 
       
   162 %%% mode: latex
       
   163 %%% TeX-master: t
       
   164 %%% End: