# HG changeset patch # User Christian Urban # Date 1417110737 0 # Node ID 3cb200fa6d6a78a4edf74a74fe1eff41af2fe3d2 # Parent 06d5fc15594dd0a7b19becd2c29ffe35006a17b9 updated diff -r 06d5fc15594d -r 3cb200fa6d6a handouts/ho01.pdf Binary file handouts/ho01.pdf has changed diff -r 06d5fc15594d -r 3cb200fa6d6a handouts/ho01.tex --- a/handouts/ho01.tex Wed Nov 26 10:15:43 2014 +0000 +++ b/handouts/ho01.tex Thu Nov 27 17:52:17 2014 +0000 @@ -286,14 +286,25 @@ problem). So encryption seems to not solve the problem we face with the integrity of our counter. -Fortunately, \emph{hash functions} seem to be more suitable -for our purpose. Like encryption, hash functions scramble data -in such a way that it is easy to calculate the output of a -hash function from the input. But it is hard (i.e.~practically -impossible) to calculate the input from knowing the output. -Therefore hash functions are often called \emph{one-way -functions}\ldots you cannot go back from the output to the -input (without some tricks, see below). There are several such +Fortunately, \emph{cryptographic hash functions} seem to be +more suitable for our purpose. Like encryption, hash functions +scramble data in such a way that it is easy to calculate the +output of a hash function from the input. But it is hard +(i.e.~practically impossible) to calculate the input from +knowing the output. This is often called \emph{preimage +resistance}. Cryptographic hash functions also ensure that +given a message and a hash, it is computationally infeasible to +find another message with the same hash. This is called +\emph{collusion resistance}. Because of these properties hash +functions are often called \emph{one-way functions}\ldots you +cannot go back from the output to the input (without some +tricks, see below). + + + + + +There are several such hashing function. For example SHA-1 would hash the string \pcode{"hello world"} to produce the hash-value diff -r 06d5fc15594d -r 3cb200fa6d6a handouts/ho08.pdf Binary file handouts/ho08.pdf has changed diff -r 06d5fc15594d -r 3cb200fa6d6a handouts/ho08.tex --- a/handouts/ho08.tex Wed Nov 26 10:15:43 2014 +0000 +++ b/handouts/ho08.tex Thu Nov 27 17:52:17 2014 +0000 @@ -5,7 +5,7 @@ \begin{document} -\section*{Handout 7 (Bitcoins)} +\section*{Handout 8 (Bitcoins)} In my opinion Bitcoins are an elaborate Ponzi scheme\footnote{\url{http://en.wikipedia.org/wiki/Ponzi_scheme}}---still @@ -758,7 +758,7 @@ \noindent Finally, a government would potentially not really need to follow up with such threads. Just the rumour that it would, could be enough to get the Bitcoin-house-of-cards to -tumble. Some governments have already such a ``impressive'' +tumble. Some governments have already such an ``impressive'' trackrecord in this area, such a thread would be entirely credible. Because of all this, I would not have too much hope that Bitcoins are free from government \& Co interference when @@ -781,11 +781,10 @@ the UN, say, would find the money and incentivise people to, for example, solve protein folding puzzles?\footnote{\url{http://en.wikipedia.org/wiki/Protein_folding}} -There are projects like -Folding@home\footnote{\url{http://folding.stanford.edu}} which have +For this there are projects like +Folding@home\footnote{\url{http://folding.stanford.edu}}. This might help with curing diseases such as Alzheimer or -diabetes, which to a large portion baddies and goodies will -suffer at some point. The same point is made in the article +diabetes. The same point is made in the article \begin{center}\small \url{http://gizmodo.com/the-worlds-most-powerful-computer-network-is-being-was-504503726} @@ -794,8 +793,6 @@ \end{document} bit coin -https://bitcoin.org/bitcoin.pdf -https://bitcoin.org/bitcoin.pdf A fistful of bitcoins http://cseweb.ucsd.edu/~smeiklejohn/files/imc13.pdf diff -r 06d5fc15594d -r 3cb200fa6d6a langs.sty --- a/langs.sty Wed Nov 26 10:15:43 2014 +0000 +++ b/langs.sty Thu Nov 27 17:52:17 2014 +0000 @@ -8,28 +8,10 @@ \definecolor{codepurple}{rgb}{0.5,0,0.35} % keywords \definecolor{codedocblue}{rgb}{0.25,0.35,0.75} % doc \definecolor{codeblue}{rgb}{0.25,0.35,0.75} % types -\definecolor{darkgray}{rgb}{.4,.4,.4} \BeforeBeginEnvironment{lstlisting}{\par\noindent\begin{minipage}{\linewidth}} \AfterEndEnvironment{lstlisting}{\end{minipage}\par} -\lstdefinelanguage{JavaScript}{ - keywords={break,case,catch,continue,debugger,default,% - delete,do,else,false,finally,for,function,if,in,instanceof,% - new,null,return,switch,this,throw,true,try,typeof,var,void,while,with}, - morecomment=[l]{//}, - morecomment=[s]{/*}{*/}, - morestring=[b]', - morestring=[b]", - ndkeywords={class,export,boolean,throw,implements,import,this}, - keywordstyle=\color{codepurple}\bfseries, - ndkeywordstyle=\color{darkgray}\bfseries, - identifierstyle=\color{black}, - commentstyle=\color{codegreen}\ttfamily, - stringstyle=\color{codegreen}\ttfamily, - sensitive=true -} - \lstdefinelanguage{Scala}{ morekeywords={abstract,case,catch,class,def,% do,else,extends,false,final,finally,% @@ -38,28 +20,28 @@ private,protected,requires,return,sealed,% super,this,throw,trait,true,try,% type,val,var,while,with,yield},% - otherkeywords={=>,<-,<\%,<:,>:,\#,@},% + otherkeywords={=>,<-,<\%,<:,>:,\#},% sensitive=true,% %directives={Int,Char,Rexp,String,Boolean,BigInt,Unit,List,Set},% %moredelim=*[directive]:,% morecomment=[l]{//},% morecomment=[n]{/*}{*/}, + morestring=[s]{"""}{"""}, morestring=[b]", morestring=[b]', - morestring=[b]""" }[keywords,comments,strings] \lstdefinelanguage{While}{ - morekeywords={if,then,else,while,do,true,false,write,upto,for,skip}, - otherkeywords={=,!=,:=,<,>,;}, - sensitive=true, + morekeywords={if,then,else,while,do,true,false,write,upto,read,for,skip}, + morecomment=[l]{//}, morecomment=[n]{/*}{*/}, -} + morestring=[b]", + otherkeywords={=,!=,:=,<,>,\%;*,/}, +}[keywords,comments,strings] \lstdefinestyle{mystyle} {basicstyle=\ttfamily, keywordstyle=\color{codepurple}\bfseries, - %directivestyle=\color{codeblue}\bfseries, stringstyle=\color{codegreen}, commentstyle=\color{codegreen}, morecomment=[s][\color{codedocblue}]{/**}{*/}, @@ -72,7 +54,8 @@ showstringspaces=false, xleftmargin=8mm, emphstyle=\color{codeblue}\bfseries, - keepspaces} + keepspaces +} \lstset{language=Scala, style=mystyle} @@ -80,4 +63,5 @@ \newcommand{\code}[1]{{\lstinline{#1}}} \newcommand{\pcode}[1]{\mbox{\lstset{language={},keywordstyle=\color{black}}\lstinline!#1!}} +\newcommand{\scode}[1]{\mbox{\lstset{language={},basicstyle=\ttfamily\color{codegreen}}\lstinline!#1!}} \makeatother diff -r 06d5fc15594d -r 3cb200fa6d6a slides/slides09.pdf Binary file slides/slides09.pdf has changed diff -r 06d5fc15594d -r 3cb200fa6d6a slides/slides09.tex --- a/slides/slides09.tex Wed Nov 26 10:15:43 2014 +0000 +++ b/slides/slides09.tex Thu Nov 27 17:52:17 2014 +0000 @@ -3,29 +3,16 @@ \usepackage{../langs} \usepackage{../graphics} \usepackage{../grammar} + %\usepackage{soul} -\makeatletter -\newenvironment<>{btHighlight}[1][] -{\begin{onlyenv}#2\begingroup\tikzset{bt@Highlight@par/.style={#1}}\begin{lrbox}{\@tempboxa}} -{\end{lrbox}\bt@HL@box[bt@Highlight@par]{\@tempboxa}\endgroup\end{onlyenv}} - -\newcommand<>\btHL[1][]{% - \only#2{\begin{btHighlight}[#1]\bgroup\aftergroup\bt@HL@endenv}% -} -\def\bt@HL@endenv{% - \end{btHighlight}% - \egroup -} -\newcommand{\bt@HL@box}[2][]{% - \tikz[#1]{% - \pgfpathrectangle{\pgfpoint{1pt}{0pt}}{\pgfpoint{\wd #2}{\ht #2}}% - \pgfusepath{use as bounding box}% - \node[anchor=base west, fill=orange!30,outer sep=0pt,inner xsep=1pt, inner ysep=0pt, rounded corners=3pt, minimum height=\ht\strutbox+1pt,#1]{\raisebox{1pt}{\strut}\strut\usebox{#2}}; - }% -} -\makeatother - +%\newcommand\hl[1]{% +% \tikz[baseline,% +% outer sep=-15pt, inner sep = 0pt% +% ]% +% \node[decorate,rectangle,fill=yellow,anchor=text]{#1};% +%}% +\newcommand{\hl}[1]{#1} % beamer stuff \renewcommand{\slidecaption}{APP 09, King's College London} @@ -864,7 +851,7 @@ | \meta{var}\\ : \meta{Stmt} ::= \meta{label} : | \meta{var} := \meta{Exp} - | jump? \meta{Exp} \meta{label} + | jmp? \meta{Exp} \meta{label} | goto \meta{label}\\ : \meta{Prog} ::= \meta{Stmt} \ldots\\ \end{plstx}} @@ -884,7 +871,7 @@ | \meta{var}\\ : \meta{Stmt} ::= \meta{label} : | \meta{var} := \meta{Exp} - | jump? \meta{Exp} \meta{label} + | jmp? \meta{Exp} \meta{label} | goto \meta{label}\\ : \meta{Prog} ::= \meta{Stmt} \ldots\\ \end{plstx}} @@ -897,7 +884,7 @@ language={},xleftmargin=3mm] a := 1 n := 5 -top: jump? n = 0 done +top: jmp? n = 0 done a := a * n n := n + -1 goto top @@ -970,13 +957,13 @@ \end{center} \footnotesize -\begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-5mm] +\begin{lstlisting}[numbers=none,xleftmargin=-5mm] def eval_exp(e: Exp, env: Env) : Int = e match { - case Num(n) & n - case Var(x) & env(x) - case Plus(e1, e2) & eval_exp(e1, env) + eval_exp(e2, env) - case Times(e1, e2) & eval_exp(e1, env) * eval_exp(e2, env) - case Equ(e1, e2) & + case Num(n) => n + case Var(x) => env(x) + case Plus(e1, e2) => eval_exp(e1, env) + eval_exp(e2, env) + case Times(e1, e2) => eval_exp(e1, env) * eval_exp(e2, env) + case Equ(e1, e2) => if (eval_exp(e1, env) == eval_exp(e2, env)) 1 else 0 } \end{lstlisting} @@ -1088,14 +1075,14 @@ \begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-5mm] def eval(sn: Snips) : Env = { def eval_stmts(sts: Stmts, env: Env) : Env = sts match { - case Nil & env - case Label(l)::rest & eval_stmts(rest, env) - case Assign(x, e)::rest & + case Nil => env + case Label(l)::rest => eval_stmts(rest, env) + case Assign(x, e)::rest => eval_stmts(rest, env + (x -> eval_exp(e, env))) - case Jump(b, l)::rest & + case Jmp(b, l)::rest => if (eval_exp(b, env) == 1) eval_stmts(sn(l), env) else eval_stmts(rest, env) - case Goto(l)::rest & eval_stmts(sn(l), env) + case Goto(l)::rest => eval_stmts(sn(l), env) } eval_stmts(sn(""), Map()) @@ -1138,12 +1125,12 @@ language={}, basicstyle=\ttfamily, xleftmargin=1mm, - escapeinside={(*@}{@*)}] - a := (*@\hl{'+'}@*) - n := (*@\hl{'+'}@*) -top: jmp? n = (*@\hl{'0'}@*) done + escapeinside={(*}{*)}] + a := (*\hl{'+'}*) + n := (*\hl{'+'}*) +top: jmp? n = (*\hl{'0'}*) done a := a * n - n := n + (*@\hl{'-'}@*) + n := n + (*\hl{'-'}*) goto top done: \end{lstlisting}