# HG changeset patch # User Christian Urban # Date 1526343247 -3600 # Node ID 90e0b1cc460b4fc0a1c7ef0a26e42ad5ff58f4f1 # Parent 2de1f79dedf0986e7d055ab4bc0f686c2c4db74f updated diff -r 2de1f79dedf0 -r 90e0b1cc460b LINKS --- a/LINKS Mon Mar 12 12:11:50 2018 +0000 +++ b/LINKS Tue May 15 01:14:07 2018 +0100 @@ -5,7 +5,10 @@ http://queue.acm.org/detail.cfm?id=2038036 ============= +some examples +https://wibisono.github.io/fp-oops/docs/redbook/monoid.html +============= BufferOverflow http://seclists.org/oss-sec/2017/q2/344 diff -r 2de1f79dedf0 -r 90e0b1cc460b cws/cw06.tex --- /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: diff -r 2de1f79dedf0 -r 90e0b1cc460b cws/disclaimer.sty --- a/cws/disclaimer.sty Mon Mar 12 12:11:50 2018 +0000 +++ b/cws/disclaimer.sty Tue May 15 01:14:07 2018 +0100 @@ -27,12 +27,51 @@ \end{itemize} } +\newcommand{\IMPORTANTEXAM}{% +\noindent +\subsubsection*{Important} + +\begin{itemize} +\item Make sure the files you submit can be processed by just calling\\ + \mbox{\texttt{scala <>}} on the commandline. Use the + template file provided and do not make any changes to arguments of + functions or to any types. You are free to implement any auxiliary + function you might need. + +\item Do not use any mutable data structures in your +submission! 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! +\end{itemize} +} + \newcommand{\DISCLAIMER}{% -\subsection*{Disclaimer} +\subsubsection*{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.\bigskip +} + +\newcommand{\DISCLAIMEREXAM}{% +\subsubsection*{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.\medskip + +\noindent +During the exam you may \textbf{not} communicate with other people: no email, +instant messaging, discussion forums, use of mobile phones, etc. +\bigskip } \ No newline at end of file diff -r 2de1f79dedf0 -r 90e0b1cc460b progs/lecture2.scala --- a/progs/lecture2.scala Mon Mar 12 12:11:50 2018 +0000 +++ b/progs/lecture2.scala Tue May 15 01:14:07 2018 +0100 @@ -452,6 +452,12 @@ // function in which return appears." def sq1(x: Int): Int = x * x +def sumq(ls: List[Int]): Int = + ls.map(x => x * x).sum + + + + def sq2(x: Int): Int = return x * x def sumq(ls: List[Int]): Int = { @@ -467,6 +473,7 @@ sqs.sum } +sumq(List(1, 2, 3, 4)) diff -r 2de1f79dedf0 -r 90e0b1cc460b progs/mandelbrot.scala --- 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)) diff -r 2de1f79dedf0 -r 90e0b1cc460b slides/slides01.tex --- a/slides/slides01.tex Mon Mar 12 12:11:50 2018 +0000 +++ b/slides/slides01.tex Tue May 15 01:14:07 2018 +0100 @@ -75,6 +75,19 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Why Scala?} + +In the last few years there is a ``Cambrian explosion'' of +languages from both academia and industry. + +It is essential for students to have skills to pick up new languages +quickly. + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -123,6 +136,18 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] +\frametitle{Scala (imperative) vs Scala (functional)} + +Reham's example + + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] \frametitle{First Steps: Scala Tools} \begin{itemize}