Binary file cws/cw01.pdf has changed
--- a/cws/cw01.tex Fri Nov 17 14:11:58 2017 +0000
+++ b/cws/cw01.tex Tue Nov 21 16:31:11 2017 +0000
@@ -21,8 +21,8 @@
\mbox{\texttt{scala <<filename.scala>>}} on the commandline.
\item Do not use any mutable data structures in your
-submissions! They are not needed. This means you cannot use
-\texttt{ListBuffer}s, for example.
+submissions! 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.
Binary file cws/cw02.pdf has changed
--- a/cws/cw02.tex Fri Nov 17 14:11:58 2017 +0000
+++ b/cws/cw02.tex Tue Nov 21 16:31:11 2017 +0000
@@ -32,13 +32,9 @@
\item Make sure the files you submit can be processed by just calling\\
\mbox{\texttt{scala <<filename.scala>>}} on the commandline.
-%\item If you use \textbf{offending} words, like \texttt{var} or
-% \texttt{return}, in comments, please write them as \texttt{vvar},
-% \texttt{Var}, \texttt{rreturn}, \texttt{Return} or anything
-
\item Do not use any mutable data structures in your
-submissions! They are not needed. This means you cannot use
-\texttt{ListBuffer}s, for example.
+submissions! 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.
Binary file cws/cw03.pdf has changed
--- a/cws/cw03.tex Fri Nov 17 14:11:58 2017 +0000
+++ b/cws/cw03.tex Tue Nov 21 16:31:11 2017 +0000
@@ -8,22 +8,39 @@
This coursework is worth 10\%. It is about regular expressions,
pattern matching and polymorphism. The first part is due on 30
-November at 11pm; the second, more advanced part, is due on 7 December
-at 11pm. You are asked to implement a regular expression matcher. Make
-sure the files you submit can be processed by just calling
-\texttt{scala <<filename.scala>>}.\bigskip
+November at 11pm; the second, more advanced part, is due on 21
+December at 11pm. You are asked to implement a regular expression
+matcher based on derivatives of regular expressions. The reason is
+that regular expression matching in Java can be extremely slow
+sometimes.\bigskip
\noindent
-\textbf{Important:} Do not use any mutable data structures in your
-submission! They are not needed. This menas 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. 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 on my
-laptop.
+\textbf{Important:}
+
+\begin{itemize}
+\item Make sure the files you submit can be processed by just calling\\
+ \mbox{\texttt{scala <<filename.scala>>}} on the commandline. Use the
+ template files 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
+submissions! 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!
+ Our testing and marking infrastructure is not set up for it.
+\end{itemize}
+
+\noindent
+Also note that the running time of each part will be restricted to a
+maximum of 360 seconds on my laptop
\subsection*{Disclaimer}
@@ -54,12 +71,13 @@
\end{center}
\noindent
-Why? Knowing how to match regular expressions and strings will
-let you solve a lot of problems that vex other humans. Regular
-expressions are one of the fastest and simplest ways to match patterns
-in text, and are endlessly useful for searching, editing and
-analysing text in all sorts of places. However, you need to be
-fast, otherwise you will stumble over problems such as recently reported at
+Why? Knowing how to match regular expressions and strings will let you
+solve a lot of problems that vex other humans. Regular expressions are
+one of the fastest and simplest ways to match patterns in text, and
+are endlessly useful for searching, editing and analysing data in all
+sorts of places (for example analysing network traffic in order to
+detect security breaches). However, you need to be fast, otherwise you
+will stumble over problems such as recently reported at
{\small
\begin{itemize}
@@ -71,9 +89,10 @@
\subsubsection*{Tasks (file re.scala)}
\begin{itemize}
-\item[(1a)] Implement a function, called \textit{nullable}, by recursion over
- regular expressions. This function tests whether a regular expression can match
- the empty string.
+\item[(1a)] Implement a function, called \textit{nullable}, by
+ recursion over regular expressions. This function tests whether a
+ regular expression can match the empty string, that is given a
+ regular expression it either returns true or false.
\begin{center}
\begin{tabular}{lcl}
@@ -134,7 +153,8 @@
\begin{tabular}{lcll}
$\textit{der}\;a\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$ \\
$\textit{der}\;b\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$\\
- $\textit{der}\;c\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ONE$
+ $\textit{der}\;c\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ONE$ &
+ (is $\textit{nullable}$)
\end{tabular}
\end{center}
@@ -165,12 +185,12 @@
simplifies to just $r_1$. \textbf{Hints:} Regular expressions can be
seen as trees and there are several methods for traversing
trees. One of them corresponds to the inside-out traversal. Also
- remember numerical expressions from school: there you had exprssions
- like $u + \ldots + (1 \cdot x) * \ldots (z + (y \cdot 0)) \ldots$
+ remember numerical expressions from school: there you had expressions
+ like $u + \ldots + (1 \cdot x) - \ldots (z + (y \cdot 0)) \ldots$
and simplification rules that looked very similar to rules
above. You would simplify such numerical expressions by replacing
for example the $y \cdot 0$ by $0$, or $1\cdot x$ by $x$, and then
- look if more rules are applicable. If you organise this
+ look whether more rules are applicable. If you organise the
simplification in an inside-out fashion, it is always clear which
rule should applied next.\\\mbox{}\hfill[1 Mark]
@@ -333,7 +353,7 @@
Although easily implementable in Scala, the idea behind the derivative
function might not so easy to be seen. To understand its purpose
better, assume a regular expression $r$ can match strings of the form
-$c::cs$ (that means strings which start with a character $c$ and have
+$c\!::\!cs$ (that means strings which start with a character $c$ and have
some rest, or tail, $cs$). If you now take the derivative of $r$ with
respect to the character $c$, then you obtain a regular expressions
that can match all the strings $cs$. In other words, the regular
Binary file handouts/pep-ho.pdf has changed
--- a/handouts/pep-ho.tex Fri Nov 17 14:11:58 2017 +0000
+++ b/handouts/pep-ho.tex Tue Nov 21 16:31:11 2017 +0000
@@ -826,13 +826,13 @@
there have also been two forks of the Scala compiler.
It needs to be seen what the future brings for Scala.
-So all in all, Scala might not be a great teaching language,
-but I hope this is mitigated by the fact that I never require
-you to write any Scala code. You only need to be able to read
-it. In the coursework you can use any programming language you
-like. If you want to use Scala for this, then be my guest; if
-you do not want, stick with the language you are most familiar
-with.
+%So all in all, Scala might not be a great teaching language,
+%but I hope this is mitigated by the fact that I never require
+%you to write any Scala code. You only need to be able to read
+%it. In the coursework you can use any programming language you
+%like. If you want to use Scala for this, then be my guest; if
+%you do not want, stick with the language you are most familiar
+%with.
--- a/progs/lecture3.scala Fri Nov 17 14:11:58 2017 +0000
+++ b/progs/lecture3.scala Tue Nov 21 16:31:11 2017 +0000
@@ -1,6 +1,55 @@
// Scala Lecture 3
//=================
+// adding two binary strings very, very lazy manner
+
+def badd(s1: String, s2: String) : String =
+ (BigInt(s1, 2) + BigInt(s2, 2)).toString(2)
+
+
+// collatz function on binary numbers
+
+def bcollatz(s: String) : Long = (s.dropRight(1), s.last) match {
+ case ("", '1') => 1 // we reached 1
+ case (rest, '0') => 1 + bcollatz(rest) // even number => divide by two
+ case (rest, '1') => 1 + bcollatz(badd(s + '1', s)) // odd number => s + '1' is 2 * s + 1
+ // add another s gives 3 * s + 1
+}
+
+bcollatz(9.toBinaryString)
+bcollatz(837799.toBinaryString)
+bcollatz(100000000000000000L.toBinaryString)
+bcollatz(BigInt("1000000000000000000000000000000000000000000000000000000000000000000000000000").toString(2))
+
+def conv(c: Char) : Int = c match {
+ case '0' => 0
+ case '1' => 1
+}
+
+def badds(s1: String, s2: String, carry: Int) : String = (s1, s2, carry) match {
+ case ("", "", 1) => "1"
+ case ("", "", 0) => ""
+ case (cs1, cs2, carry) => (conv(cs1.last) + conv(cs2.last) + carry) match {
+ case 3 => badds(cs1.dropRight(1), cs2.dropRight(1), 1) + '1'
+ case 2 => badds(cs1.dropRight(1), cs2.dropRight(1), 1) + '0'
+ case 1 => badds(cs1.dropRight(1), cs2.dropRight(1), 0) + '1'
+ case 0 => badds(cs1.dropRight(1), cs2.dropRight(1), 0) + '0'
+ }
+}
+
+def bcollatz2(s: String) : Long = (s.dropRight(1), s.last) match {
+ case ("", '1') => 1 // we reached 1
+ case (rest, '0') => 1 + bcollatz2(rest) // even number => divide by two
+ case (rest, '1') => 1 + bcollatz2(badds(s + '1', '0' + s, 0)) // odd number => s + '1' is 2 * s + 1
+ // add another s gives 3 * s + 1
+}
+
+bcollatz2(9.toBinaryString)
+bcollatz2(837799.toBinaryString)
+bcollatz2(100000000000000000L.toBinaryString)
+bcollatz2(BigInt("1000000000000000000000000000000000000000000000000000000000000000000000000000").toString(2))
+
+
// One of only two places where I conceded to mutable
// data structures: The following function generates
--- a/testing1/alcohol.scala Fri Nov 17 14:11:58 2017 +0000
+++ b/testing1/alcohol.scala Tue Nov 21 16:31:11 2017 +0000
@@ -28,7 +28,6 @@
val alcs = get_csv_page(url_alcohol)
val pops = get_csv_file(file_population)
-
def process_alcs(lines: List[String]) : List[(String, Double)] =
for (l <- lines) yield {
val entries = l.split(",").toList
@@ -42,6 +41,9 @@
}).toMap
+process_alcs(alcs.drop(1))(1)
+process_pops(pops.drop(1))("Albania")
+
def sorted_country_consumption() : List[(String, Long)] = {
val alcs2 = process_alcs(alcs.drop(1))
val pops2 = process_pops(pops.drop(1))
--- a/testing2/knight1_test.sh Fri Nov 17 14:11:58 2017 +0000
+++ b/testing2/knight1_test.sh Tue Nov 21 16:31:11 2017 +0000
@@ -170,8 +170,8 @@
if [ $tsts1 -eq 0 ]
then
- echo " is first_tour(8, (0, 0)) ok? " >> $out
- echo " is first_tour(4, (0, 0)) == None " >> $out
+ echo " is first_tour(8, List((0, 0))) ok? " >> $out
+ echo " is first_tour(4, List((0, 0))) == None " >> $out
if (scala_assert "knight2.scala" "knight2b_test.scala")
then
--- a/testing2/knight2.scala Fri Nov 17 14:11:58 2017 +0000
+++ b/testing2/knight2.scala Tue Nov 21 16:31:11 2017 +0000
@@ -6,7 +6,7 @@
type Pos = (Int, Int) // a position on a chessboard
type Path = List[Pos] // a path...a list of positions
-def print_board(dim: Int, path: Path): Unit = {
+def print_board(dim: Int, path: Path) : Unit = {
println
for (i <- 0 until dim) {
for (j <- 0 until dim) {
@@ -16,21 +16,21 @@
}
}
-def add_pair(x: Pos)(y: Pos): Pos =
+def add_pair(x: Pos)(y: Pos) : Pos =
(x._1 + y._1, x._2 + y._2)
-def is_legal(dim: Int, path: Path)(x: Pos): Boolean =
+def is_legal(dim: Int, path: Path)(x: Pos) : Boolean =
0 <= x._1 && 0 <= x._2 && x._1 < dim && x._2 < dim && !path.contains(x)
-def moves(x: Pos): List[Pos] =
+def moves(x: Pos) : List[Pos] =
List(( 1, 2),( 2, 1),( 2, -1),( 1, -2),
(-1, -2),(-2, -1),(-2, 1),(-1, 2)).map(add_pair(x))
-def legal_moves(dim: Int, path: Path, x: Pos): List[Pos] =
+def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] =
moves(x).filter(is_legal(dim, path))
-def first(xs: List[Pos], f: Pos => Option[Path]): Option[Path] = xs match {
+def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = xs match {
case Nil => None
case x::xs => {
val result = f(x)
@@ -41,7 +41,7 @@
//first(List((1, 0),(2, 0),(3, 0),(4, 0)), (x => if (x._1 > 3) Some(List(x)) else None))
//first(List((1, 0),(2, 0),(3, 0)), (x => if (x._1 > 3) Some(List(x)) else None))
-def first_tour(dim: Int, path: Path): Option[Path] = {
+def first_tour(dim: Int, path: Path) : Option[Path] = {
if (path.length == dim * dim) Some(path)
else
first(legal_moves(dim, path, path.head), (x: Pos) => first_tour(dim, x::path))