--- a/cws/cw04.tex Thu Nov 29 17:15:11 2018 +0000
+++ b/cws/cw04.tex Fri Nov 30 03:44:27 2018 +0000
@@ -451,7 +451,8 @@
width=6cm,
height=5.5cm,
legend entries={Python, Java 8, JavaScript},
- legend pos=north west]
+ legend pos=north west,
+ legend cell align=left]
\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
Binary file pics/sahara.jpg has changed
--- a/progs/lecture4.scala Thu Nov 29 17:15:11 2018 +0000
+++ b/progs/lecture4.scala Fri Nov 30 03:44:27 2018 +0000
@@ -1,3 +1,54 @@
+// Scala Lecture 4
+//=================
+
+
+// Polymorphic Types
+//===================
+
+// You do not want to write functions like contains, first,
+// length and so on for every type of lists.
+
+
+def length_string_list(lst: List[String]): Int = lst match {
+ case Nil => 0
+ case x::xs => 1 + length_string_list(xs)
+}
+
+def length_int_list(lst: List[Int]): Int = lst match {
+ case Nil => 0
+ case x::xs => 1 + length_int_list(xs)
+}
+
+length_string_list(List("1", "2", "3", "4"))
+length_int_list(List(1, 2, 3, 4))
+
+//-----
+def length[A](lst: List[A]): Int = lst match {
+ case Nil => 0
+ case x::xs => 1 + length(xs)
+}
+length(List("1", "2", "3", "4"))
+length(List(1, 2, 3, 4))
+
+
+def map[A, B](lst: List[A], f: A => B): List[B] = lst match {
+ case Nil => Nil
+ case x::xs => f(x)::map(xs, f)
+}
+
+map(List(1, 2, 3, 4), (x: Int) => x * x)
+
+
+// Remember?
+def first[A, B](xs: List[A], f: A => Option[B]) : Option[B] = ...
+
+
+// distinct / distinctBy
+
+val ls = List(1,2,3,3,2,4,3,2,1)
+ls.distinct
+
+
def distinctBy[B, C](xs: List[B], f: B => C, acc: List[C] = Nil): List[B] = xs match {
case Nil => Nil
case (x::xs) => {
@@ -7,5 +58,383 @@
}
}
+distinctBy(ls, (x: Int) => x)
+
+
+val cs = List('A', 'b', 'a', 'c', 'B', 'D', 'd')
+
+distinctBy(cs, (c:Char) => c.toUpper)
+
+
+
+// Type inference is local in Scala
+
+def id[T](x: T) : T = x
+
+
+val x = id(322) // Int
+val y = id("hey") // String
+val z = id(Set(1,2,3,4)) // Set[Int]
+
+
+
+// The type variable concept in Scala can get really complicated.
+//
+// - variance (OO)
+// - bounds (subtyping)
+// - quantification
+
+// Java has issues with this too: Java allows
+// to write the following, but raises an exception
+// at runtime
+
+//Object[] arr = new Integer[10];
+//arr[0] = "Hello World";
+
+
+// Scala gives you a compile-time error
+
+var arr = Array[Int]()
+arr(0) = "Hello World"
+
+
+
+
+
+
+//
+// Object Oriented Programming in Scala
+//
+// =====================================
+
+abstract class Animal
+case class Bird(name: String) extends Animal
+case class Mammal(name: String) extends Animal
+case class Reptile(name: String) extends Animal
+
+println(new Bird("Sparrow"))
+println(Bird("Sparrow").toString)
+
+
+// you can override methods
+case class Bird(name: String) extends Animal {
+ override def toString = name
+}
+
+
+// There is a very convenient short-hand notation
+// for constructors
+
+class Fraction(x: Int, y: Int) {
+ def numer = x
+ def denom = y
+}
+
+
+case class Fraction(numer: Int, denom: Int)
+
+val half = Fraction(1, 2)
+
+half.denom
+
+
+// in mandelbrot.scala I used complex (imaginary) numbers and implemented
+// the usual arithmetic operations for complex numbers
+
+case class Complex(re: Double, im: Double) {
+ // represents the complex number re + im * i
+ def +(that: Complex) = Complex(this.re + that.re, this.im + that.im)
+ def -(that: Complex) = Complex(this.re - that.re, this.im - that.im)
+ def *(that: Complex) = Complex(this.re * that.re - this.im * that.im,
+ this.re * that.im + that.re * this.im)
+ def *(that: Double) = Complex(this.re * that, this.im * that)
+ def abs = Math.sqrt(this.re * this.re + this.im * this.im)
+}
+
+val test = Complex(1, 2) + Complex (3, 4)
+
+// this could have equally been written as
+val test = Complex(1, 2).+(Complex (3, 4))
+
+// this applies to all methods, but requires
+import scala.language.postfixOps
+
+List(5, 2, 3, 4).sorted
+List(5, 2, 3, 4) sorted
+
+
+// to allow the notation n + m * i
+import scala.language.implicitConversions
+object i extends Complex(0, 1)
+implicit def double2complex(re: Double) = Complex(re, 0)
+
+
+val inum1 = -2.0 + -1.5 * i
+val inum2 = 1.0 + 1.5 * i
+
+
+
+// all is public by default....so no public
+// you can have the usual restrictions about private values
+// and methods, if you are MUTABLE(!!!)
+
+case class BankAccount(init: Int) {
+
+ private var balance = init
+
+ def deposit(amount: Int): Unit = {
+ if (amount > 0) balance = balance + amount
+ }
+
+ def withdraw(amount: Int): Int =
+ if (0 < amount && amount <= balance) {
+ balance = balance - amount
+ balance
+ } else throw new Error("insufficient funds")
+}
+
+// BUT since we are IMMUTABLE, this is virtually of not
+// concern to us.
+
+
+
+
+
+// DFAs in Scala
+import scala.util.Try
+// A is the state type
+// C is the input (usually characters)
+
+case class DFA[A, C](start: A, // starting state
+ delta: (A, C) => A, // transition function
+ fins: A => Boolean) { // final states
+
+ def deltas(q: A, s: List[C]) : A = s match {
+ case Nil => q
+ case c::cs => deltas(delta(q, c), cs)
+ }
+
+ def accepts(s: List[C]) : Boolean =
+ Try(fins(deltas(start, s))) getOrElse false
+}
+
+// the example shown in the handout
+abstract class State
+case object Q0 extends State
+case object Q1 extends State
+case object Q2 extends State
+case object Q3 extends State
+case object Q4 extends State
+
+val delta : (State, Char) => State =
+ { case (Q0, 'a') => Q1
+ case (Q0, 'b') => Q2
+ case (Q1, 'a') => Q4
+ case (Q1, 'b') => Q2
+ case (Q2, 'a') => Q3
+ case (Q2, 'b') => Q2
+ case (Q3, 'a') => Q4
+ case (Q3, 'b') => Q0
+ case (Q4, 'a') => Q4
+ case (Q4, 'b') => Q4
+ case _ => throw new Exception("Undefined") }
+
+val dfa = DFA(Q0, delta, Set[State](Q4))
+
+dfa.accepts("abaaa".toList) // true
+dfa.accepts("bbabaab".toList) // true
+dfa.accepts("baba".toList) // false
+dfa.accepts("abc".toList) // false
+
+// another DFA test with a Sink state
+abstract class S
+case object S0 extends S
+case object S1 extends S
+case object S2 extends S
+case object Sink extends S
+
+// transition function with a sink state
+val sigma : (S, Char) :=> S =
+ { case (S0, 'a') => S1
+ case (S1, 'a') => S2
+ case _ => Sink
+ }
+
+val dfa2 = DFA(S0, sigma, Set[S](S2))
+
+dfa2.accepts("aa".toList) // true
+dfa2.accepts("".toList) // false
+dfa2.accepts("ab".toList) // false
+
+
+
+
+// NFAs (Nondeterministic Finite Automata)
+
+
+case class NFA[A, C](starts: Set[A], // starting states
+ delta: (A, C) => Set[A], // transition function
+ fins: A => Boolean) { // final states
+
+ // given a state and a character, what is the set of
+ // next states? if there is none => empty set
+ def next(q: A, c: C) : Set[A] =
+ Try(delta(q, c)) getOrElse Set[A]()
+
+ def nexts(qs: Set[A], c: C) : Set[A] =
+ qs.flatMap(next(_, c))
+
+ // depth-first version of accepts
+ def search(q: A, s: List[C]) : Boolean = s match {
+ case Nil => fins(q)
+ case c::cs => next(q, c).exists(search(_, cs))
+ }
+
+ def accepts(s: List[C]) : Boolean =
+ starts.exists(search(_, s))
+}
+
+
+
+// NFA examples
+
+val nfa_trans1 : (State, Char) => Set[State] =
+ { case (Q0, 'a') => Set(Q0, Q1)
+ case (Q0, 'b') => Set(Q2)
+ case (Q1, 'a') => Set(Q1)
+ case (Q2, 'b') => Set(Q2) }
+
+val nfa = NFA(Set[State](Q0), nfa_trans1, Set[State](Q2))
+
+nfa.accepts("aa".toList) // false
+nfa.accepts("aaaaa".toList) // false
+nfa.accepts("aaaaab".toList) // true
+nfa.accepts("aaaaabbb".toList) // true
+nfa.accepts("aaaaabbbaaa".toList) // false
+nfa.accepts("ac".toList) // false
+
+
+// Q: Why the kerfuffle about the polymorphic types in DFAs/NFAs
+// A: Subset construction
+
+def subset[A, C](nfa: NFA[A, C]) : DFA[Set[A], C] = {
+ DFA(nfa.starts,
+ { case (qs, c) => nfa.nexts(qs, c) },
+ _.exists(nfa.fins))
+}
+
+subset(nfa1).accepts("aa".toList) // false
+subset(nfa1).accepts("aaaaa".toList) // false
+subset(nfa1).accepts("aaaaab".toList) // true
+subset(nfa1).accepts("aaaaabbb".toList) // true
+subset(nfa1).accepts("aaaaabbbaaa".toList) // false
+subset(nfa1).accepts("ac".toList) // false
+
+
+
+
+
+
+
+// Cool Stuff in Scala
+//=====================
+
+
+// Implicits or How to Pimp my Library
+//=====================================
+//
+// For example adding your own methods to Strings:
+// Imagine you want to increment strings, like
+//
+// "HAL".increment
+//
+// you can avoid ugly fudges, like a MyString, by
+// using implicit conversions.
+
+
+implicit class MyString(s: String) {
+ def increment = for (c <- s) yield (c + 1).toChar
+}
+
+"HAL".increment
+
+
+
+
+// Regular expressions - the power of DSLs in Scala
+//==================================================
+
+abstract class Rexp
+case object ZERO extends Rexp // nothing
+case object ONE extends Rexp // the empty string
+case class CHAR(c: Char) extends Rexp // a character c
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative r1 + r2
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence r1 . r2
+case class STAR(r: Rexp) extends Rexp // star r*
+
+
+
+// (ab)*
+val r0 = STAR(SEQ(CHAR('a'), CHAR('b')))
+
+
+// some convenience for typing in regular expressions
+import scala.language.implicitConversions
+import scala.language.reflectiveCalls
+
+def charlist2rexp(s: List[Char]): Rexp = s match {
+ case Nil => ONE
+ case c::Nil => CHAR(c)
+ case c::s => SEQ(CHAR(c), charlist2rexp(s))
+}
+implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList)
+
+
+val r1 = STAR("ab")
+val r2 = STAR(ALT("ab", "baa baa black sheep"))
+val r3 = STAR(SEQ("ab", ALT("a", "b")))
+
+implicit def RexpOps (r: Rexp) = new {
+ def | (s: Rexp) = ALT(r, s)
+ def % = STAR(r)
+ def ~ (s: Rexp) = SEQ(r, s)
+}
+
+implicit def stringOps (s: String) = new {
+ def | (r: Rexp) = ALT(s, r)
+ def | (r: String) = ALT(s, r)
+ def % = STAR(s)
+ def ~ (r: Rexp) = SEQ(s, r)
+ def ~ (r: String) = SEQ(s, r)
+}
+
+//example regular expressions
+val digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
+val sign = "+" | "-" | ""
+val number = sign ~ digit ~ digit.%
+
+
+
+// Lazy Evaluation
+//=================
+//
+// do not evaluate arguments just yet
+
+def time_needed[T](i: Int, code: => T) = {
+ val start = System.nanoTime()
+ for (j <- 1 to i) code
+ val end = System.nanoTime()
+ (end - start)/(i * 1.0e9)
+}
+
+// same examples using the internal regexes
+val evil = "(a*)*b"
+
+("a" * 10 ++ "b").matches(evil)
+("a" * 10).matches(evil)
+("a" * 10000).matches(evil)
+("a" * 20000).matches(evil)
+
+time_needed(2, ("a" * 10000).matches(evil))
--- a/slides/slides04.tex Thu Nov 29 17:15:11 2018 +0000
+++ b/slides/slides04.tex Fri Nov 30 03:44:27 2018 +0000
@@ -4,6 +4,7 @@
\usepackage{../langs}
%%\usepackage{../data}
\usepackage[export]{adjustbox}
+\usetikzlibrary{shapes}
\hfuzz=220pt
@@ -16,10 +17,26 @@
numbers=none,
xleftmargin=0mm}
+\newcommand{\LEFTarrow}[3]{%
+\begin{textblock}{0}(#2,#3)%
+\onslide<#1>{%
+\begin{tikzpicture}%
+\node at (0,0) [single arrow, shape border rotate=180, fill=red,text=red]{a};%
+\end{tikzpicture}}%
+\end{textblock}}
+\newcommand{\DOWNarrow}[3]{%
+\begin{textblock}{0}(#2,#3)%
+\onslide<#1>{%
+\begin{tikzpicture}%
+\node at (0,0) [single arrow, shape border rotate=270, fill=red,text=red]{a};%
+\end{tikzpicture}}%
+\end{textblock}}
+
+
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
% beamer stuff
-\renewcommand{\slidecaption}{PEP (Scala) 03, King's College London}
+\renewcommand{\slidecaption}{PEP (Scala) 04, King's College London}
\begin{filecontents}{re3a.data}
1 0.00003
@@ -54,6 +71,20 @@
28 26.69
\end{filecontents}
+\begin{filecontents}{re-js.data}
+5 0.061
+10 0.061
+15 0.061
+20 0.070
+23 0.131
+25 0.308
+26 0.564
+28 1.994
+30 7.648
+31 15.881
+32 32.190
+\end{filecontents}
+
\begin{filecontents}{re-java.data}
5 0.00298
10 0.00418
@@ -73,23 +104,50 @@
28 29.81185
\end{filecontents}
+\begin{filecontents}{re-java9.data}
+1000 0.01410
+2000 0.04882
+3000 0.10609
+4000 0.17456
+5000 0.27530
+6000 0.41116
+7000 0.53741
+8000 0.70261
+9000 0.93981
+10000 0.97419
+11000 1.28697
+12000 1.51387
+14000 2.07079
+16000 2.69846
+20000 4.41823
+24000 6.46077
+26000 7.64373
+30000 9.99446
+34000 12.966885
+38000 16.281621
+42000 19.180228
+46000 21.984721
+50000 26.950203
+60000 43.0327746
+\end{filecontents}
+
+
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[5mm]
- \huge PEP Scala (3)
+ \huge PEP Scala (4)
\end{tabular}}
\normalsize
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
- Office: & N7.07 (North Wing, Bush House)\\
+ Office: & N\liningnums{7.07} (North Wing, Bush House)\\
Slides \& Code: & KEATS\medskip\\
- Scala Office & \\
- Hours: & Thursdays 11 -- 13\\
+ Office Hours: & Mondays 12:00 -- 14:00\\
\end{tabular}
\end{center}
@@ -97,85 +155,209 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\begin{frame}[c]
+\frametitle{Somewhere Remote}
+
+\begin{center}
+\includegraphics[scale=0.37]{../pics/sahara.jpg}
+\end{center}
+
+\end{frame}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\begin{frame}[t]
+\frametitle{This is a bit harsh\ldots}
+
+\mbox{}\\[-22mm]\mbox{}
+
+\begin{center}
+\begin{bubble}[10.5cm]
+ ...trying a new method because the fucking github reports dont tell me
+ which test failed. It's not really helpful when the inline tests work
+ and it compiles but all i get is 'one test failed'... really helpful my dude.
+\end{bubble}
+\end{center}
+
+\begin{center}
+\begin{bubble}[10.5cm]
+ ...Reverted back and finished part 5, this is ridiculous how one test works
+ and all I get is 'ONE TEST FAILED'. Fix your reports before giving us
+ assignments like this...
+\end{bubble}
+\end{center}
+
+
+\end{frame}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\begin{frame}[t,fragile]
+\frametitle{Needless to say I tried it out}
+
+\mbox{}\\[-7mm]\mbox{}\footnotesize
+
+\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-4mm]
+> legal_moves(8, Nil, (2,2))
+ = List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))
+
+> legal_moves(8, Nil, (7,7))
+ = List((6,5), (5,6))
+
+> legal_moves(8, List((4,1), (1,0)), (2,2))
+ = List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4))
+
+> legal_moves(1, Nil, (0,0))
+ = List((-1,-2), (-2,-1))
+
+> legal_moves(2, Nil, (0,0))
+ = List((1,-2), (-1,-2), (-2,-1), (-2,1))
+
+> legal_moves(3, Nil, (0,0))
+ = List((1,2), (2,1), (2,-1), (1,-2), (-1,-2), (-2,-1), (-2,1), (-1,2))
+\end{lstlisting}
+
+\LEFTarrow{1}{9}{9}
+\LEFTarrow{1}{12}{11}
+\DOWNarrow{1}{10}{13}
+
+\end{frame}
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
-
-\begin{textblock}{6}(0.5,0.5)
-\begin{bubble}[11.5cm]
-\footnotesize
-\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm]
-import java.util.concurrent._
-import java.util.concurrent.atomic._
+\small
+
+\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-7mm]
+def is_legal(dim: Int, p: Path, x: Pos): Boolean = {
+ if (......some_really_long_condition.....) false
+ else true
+}
+\end{lstlisting}
- def collatz(input:Int){
- CollatzConjecture(input);
- println(count.get());
- }
- def collatz_max(input:Int){
- val List = new Array[Int](input)
- for (i <- 0 to input-1){
- CollaĵConjecture(i);
- List(i)=count.get();
- count.set(0);
- }
- val max = new AtomicInteger();
- max.set(List(0));
- val index = new AtomicInteger();
- index.set(1);
-
-\end{lstlisting}
-\end{bubble}
-\end{textblock}
+\pause
+\bigskip
+\rule{11cm}{0.3mm}
+\bigskip
+
+\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-7mm]
+def is_legal(dim: Int, p: Path, x: Pos): Boolean =
+ ......some_really_long_condition.....
+\end{lstlisting}\pause
+
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c,fragile]
+\begin{frame}[c]
+\frametitle{DFAs}
+
+\begin{center}
+\begin{tikzpicture}[>=stealth',very thick,auto,
+ every state/.style={minimum size=0pt,inner sep=2pt,
+ draw=blue!50,very thick,fill=blue!20},]
+
+\only<1,3->{\node[state,initial] (Q_0) {$\mbox{Q}_0$};}
+\only<2>{\node[state,initial,fill=red] (Q_0) {$\mbox{Q}_0$};}
+\only<1,2,4->{\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};}
+\only<3>{\node[state,fill=red] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};}
+\only<-3,5->{\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};}
+\only<4>{\node[state,fill=red] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};}
+\only<-4,6->{\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};}
+\only<5>{\node[state,fill=red] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};}
+\only<-5>{\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};}
+\only<6->{\node[state, accepting,fill=red] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};}
+
+\path[->] (Q_0) edge node [above] {\alert{$a$}} (Q_1);
+\path[->] (Q_1) edge node [above] {\alert{$a$}} (Q_4);
+\path[->] (Q_4) edge [loop right] node {\alert{$a, b$}} ();
+\path[->] (Q_3) edge node [right] {\alert{$a$}} (Q_4);
+\path[->] (Q_2) edge node [above] {\alert{$a$}} (Q_3);
+\path[->] (Q_1) edge node [right] {\alert{$b$}} (Q_2);
+\path[->] (Q_0) edge node [above] {\alert{$b$}} (Q_2);
+\path[->] (Q_2) edge [loop left] node {\alert{$b$}} ();
+\path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (Q_0);
+\end{tikzpicture}
+\end{center}
-\begin{textblock}{6}(0.5,0.5)
-\begin{bubble}[11.5cm]
-\footnotesize
-\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm]
- for(i<-0 to input-1){
- val temp :Int=max.get();
- if (temp < List(i)){
- max.set(List(i));
- index.set(i);
- }
- }
- println("("+max.get() +","+ index.get()+ ")");
- }
+\begin{textblock}{9}(4,12)
+\LARGE{}
+\only<3->{\boldmath\alert{$a$}}%
+\only<4->{\boldmath\alert{$b$}}%
+\only<5->{\boldmath\alert{$a$}}%
+\only<6->{\boldmath\alert{$a$}}%
+\only<7->{\boldmath\alert{$a\quad\Rightarrow \textbf{yes}$}}%
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{DFAs}
- def CollatzConjecture(n: Long): Long = {
- count.incrementAndGet();
- if (n <= 1)
- 1
- else if (n\%2 ==0)
- CollatzConjecture(n/2);
- else
- CollatzConjecture((3*n)+1);
- }
- }
-\end{lstlisting}
-\end{bubble}
-\end{textblock}
+A \alert{\bf deterministic finite automaton}, DFA, consists of
+5 things:
+
+\begin{itemize}
+\item an alphabet \bl{$\varSigma$}
+\item a set of states \bl{$\mbox{Qs}$}
+\item one of these states is the start state \bl{$\mbox{Q}_0$}
+\item some states are accepting states \bl{$F$}, and
+\item there is transition function \bl{$\delta$}\bigskip
+
+\small
+which takes a state and a character as arguments and produces a
+new state; this function might not be everywhere defined
+\end{itemize}
+
+\begin{center}
+\bl{$A(\varSigma, \mbox{Qs}, \mbox{Q}_0, F, \delta)$}
+\end{center}
\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{NFAs}
+\begin{center}
+\begin{tikzpicture}[>=stealth',very thick, auto,
+ every state/.style={minimum size=0pt,inner sep=3pt,
+ draw=blue!50,very thick,fill=blue!20},scale=2]
+\node[state,initial] (Q_0) {$\mbox{Q}_0$};
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
+\node[state, accepting] (Q_2) [right=of Q_1] {$\mbox{Q}_2$};
+\path[->] (Q_0) edge [loop above] node {\alert{$b$}} ();
+\path[<-] (Q_0) edge node [below] {\alert{$b$}} (Q_1);
+\path[->] (Q_0) edge [bend left] node [above] {\alert{$a$}} (Q_1);
+\path[->] (Q_0) edge [bend right=45,looseness=1.3] node [below] {\alert{$a$}} (Q_2);
+\path[->] (Q_1) edge [loop above] node {\alert{$a,b$}} ();
+\path[->] (Q_1) edge node [above] {\alert{$a$}} (Q_2);
+\end{tikzpicture}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
- \frametitle{CW3 (1 Part): Regexes}
+ \frametitle{CW\liningnums{9} (\liningnums{1} Part): Regexes}
\begin{center}
Graphs: $(a^*)^* b$ and strings $\underbrace{\;a\ldots a\;}_{n}$\bigskip
\begin{tabular}[t]{@{\hspace{-8mm}}c@{\hspace{-4mm}}c@{}}
-\raisebox{6mm}{\begin{tikzpicture}
+\only<1>{\raisebox{6mm}{\begin{tikzpicture}
\begin{axis}[
xlabel={$n$},
x label style={at={(1.05,0.0)}},
@@ -189,15 +371,36 @@
axis lines=left,
width=5.5cm,
height=5cm,
- legend entries={Python, Java 8},
+ legend entries={\small{}Python, \small{}Java 8, \small{}JavaScript},
legend pos=north west,
legend cell align=left]
\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
\end{axis}
-\end{tikzpicture}}
+\end{tikzpicture}}}%
+\only<2>{\raisebox{0mm}{\begin{tikzpicture}
+\begin{axis}[
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
+ ylabel={time in secs},
+ %y label style={at={(0.06,0.5)}},
+ enlargelimits=false,
+ %xtick={0,30000,...,60000},
+ xmax=65000,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=true,
+ axis lines=left,
+ width=5.5cm,
+ height=5cm,
+ legend entries={\small{}Java 9},
+ legend pos=north west]
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java9.data};
+\end{axis}
+\end{tikzpicture}}}
&
-\onslide<2>{\begin{tikzpicture}
+\onslide<1-2>{\begin{tikzpicture}
\begin{axis}[
xlabel={$n$},
x label style={at={(1.05,0.0)}},
@@ -210,7 +413,7 @@
width=5.5cm,
height=5cm]
%%\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data};
-\addplot[red,mark=square*,mark options={fill=white}] table {re3a.data};
+\addplot[magenta,mark=square*,mark options={fill=white}] table {re3a.data};
\end{axis}
\end{tikzpicture}}
\end{tabular}
@@ -221,16 +424,12 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{Where to go on from here?}
+\frametitle{Hint}
-\begin{itemize}
-\item Martin Odersky (EPFL)\ldots he is currently throwing out everything
- and starts again with the dotty compiler for Scala\medskip
+\begin{center}
+\LARGE\textbf{\alert{Pattern-Matching}}
+\end{center}
-\item Elm (\url{http://elm-lang.org})\ldots web applications with style\medskip
-
-\item Haskell, Ocaml, Standard ML, Scheme, \ldots
-\end{itemize}
\end{frame}
@@ -240,81 +439,9 @@
\begin{frame}[c,fragile]
\frametitle{\alert{Questions?}}
-{\tiny
-\begin{verbatim}
- *
- * *
- * *
- * * * *
- * *
- * * * *
- * * * *
- * * * * * * * *
- * *
- * * * *
- * * * *
- * * * * * * * *
- * * * *
- * * * * * * * *
- * * * * * * * *
- * * * * * * * * * * * * * * * *
- * *
- * * * *
- * * * *
- * * * * * * * *
- * * * *
- * * * * * * * *
- * * * * * * * *
- * * * * * * * * * * * * * * * *
- * * * *
- * * * * * * * *
- * * * * * * * *
- * * * * * * * * * * * * * * * *
- * * * * * * * *
- * * * * * * * * * * * * * * * *
- * * * * * * * * * * * * * * * *
-* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
-\end{verbatim}}
-
-
-\begin{textblock}{6}(8.5,3.5)
-\begin{bubble}[5cm]
-\footnotesize
-\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm]
-++++++++[>+>++++<<-]>++>>
-+<[-[>>+<<-]+>>]>+[-<<<[-
->[+[-]+>++>>>-<<]<[<]>>++
-++++[<<+++++>>-]+<<++.[-]
-<<]>.>+[>>]>+]
-\end{lstlisting}
-\end{bubble}
-\end{textblock}
-
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-\begin{frame}[c]
-\frametitle{Marks for CW6 (Part 1 + 2)}
-
-Raw marks:
-
-\begin{itemize}
-\item 6\%: 154 students
-\item 5\%: 66
-\item 4\%: 18
-\item 3\%: 13
-\item 2\%: 2
-\item 1\%: 1
-\item 0\%: 21
-\end{itemize}
-\end{frame}
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-\end{document}
\end{document}
--- a/testing3/knight1.scala Thu Nov 29 17:15:11 2018 +0000
+++ b/testing3/knight1.scala Fri Nov 30 03:44:27 2018 +0000
@@ -7,39 +7,44 @@
// at the end are of any help.
+
type Pos = (Int, Int) // a position on a chessboard
type Path = List[Pos] // a path...a list of positions
//(1) Complete the function that tests whether the position x
// is inside the board and not yet element in the path.
-def is_legal(dim: Int, path: Path, x: Pos) : Boolean = ((!(path.contains(x))) && (x._1 < dim) && (x._2 < dim))
+def is_legal(dim: Int, path: Path, x: Pos) : Boolean = {
+ if ((x._1 < dim && x._2 < dim) && !(path.contains(x)))
+ true
+ else
+ false
+}
//(2) Complete the function that calculates for a position x
// all legal onward moves that are not already in the path.
// The moves should be ordered in a "clockwise" manner.
+
+def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] = {
+ val legalMovesList = List((x._1 + 1, x._2 + 2), (x._1 + 2, x._2 + 1), (x._1 + 2, x._2 - 1), (x._1 + 1, x._2 - 2), (x._1 - 1, x._2 - 2), (x._1 - 2, x._2 - 1), (x._1 - 2, x._2 + 1), (x._1 - 1, x._2 + 2))
-def legal_moves(dim: Int, path: Path, x: Pos) : List[Pos] ={
- val y = List((x._1 + 1, x._2 + 2),
- (x._1 + 2, x._2 + 1),
- (x._1 + 2, x._2 - 1),
- (x._1 + 1, x._2 - 2),
- (x._1 - 1, x._2 - 2),
- (x._1 - 2, x._2 - 1),
- (x._1 - 2, x._2 + 1),
- (x._1 - 1, x._2 + 2)
- )
- y.filter(next => is_legal(dim, path, next))
+ for (i <- legalMovesList
+ if (is_legal(dim, path, i)))
+ yield i
+
}
+
//some test cases
//
-//assert(legal_moves(8, Nil, (2,2)) == List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
+//assert(legal_moves(8, Nil, (2,2)) ==
+// List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4)))
//assert(legal_moves(8, Nil, (7,7)) == List((6,5), (5,6)))
-//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) == List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
+//assert(legal_moves(8, List((4,1), (1,0)), (2,2)) ==
+// List((3,4), (4,3), (3,0), (0,1), (0,3), (1,4)))
//assert(legal_moves(8, List((6,6)), (7,7)) == List((6,5), (5,6)))
@@ -49,35 +54,43 @@
// and the second collects all tours in a list of paths.
def count_tours(dim: Int, path: Path) : Int = {
- if(path.length == dim*dim) 1 else
- (for(i <- legal_moves(dim, path, path.head)) yield
- count_tours(dim, i :: path)
- ).sum
+ if (path.size == (dim ^ 2)){
+ List(path).size
+ } else {
+ val totalTours = legal_moves(dim, path, path.head)
+ totalTours.map(element => count_tours(dim, element :: path)).sum
+ }
}
-def enum_tours(dim: Int, path: Path) : List[Path] ={
- if(path.length == dim*dim) List(path) else
- (for(i <- legal_moves(dim, path, path.head)) yield
- enum_tours(dim, i :: path)
- ).flatten
+def enum_tours(dim: Int, path: Path) : List[Path] = {
+ if (path.size == (dim ^ 2)){
+ List(path)
+ } else {
+ val totalEnums = legal_moves(dim, path, path.head)
+ totalEnums.map(element => enum_tours(dim, element :: path)).flatten
+ }
}
+
//(5) Implement a first-function that finds the first
// element, say x, in the list xs where f is not None.
// In that case Return f(x), otherwise None. If possible,
// calculate f(x) only once.
def first(xs: List[Pos], f: Pos => Option[Path]) : Option[Path] = {
- if(xs == Nil) None
- else(
- for(x <- xs) yield{
- val a = f(x)
- if(a != None) a
- else first(xs.drop(1), f)
+ if (xs eq Nil) {
+ None
+ } else {
+ if (f(xs.head) != None) {
+ f(xs.head)
+ } else {
+ first(xs.tail, f)
}
- ).head
+ }
+
}
+
// test cases
//def foo(x: (Int, Int)) = if (x._1 > 3) Some(List(x)) else None
//
@@ -92,10 +105,13 @@
// knight tour on a dim * dim-board.
-// def first_tour(dim: Int, path: Path) : Option[Path] = {
-// first(legal_moves(dim, path, path.head), (x : Pos => ))
-// }
+//def first_tour(dim: Int, path: Path) : Option[Path] = ...
+
+
+
+
+
/* Helper functions
