text:
% -*- mode: latex; tab-width: 2; indent-tabs-mode: nil; -*-
%------------------------------------------------------------------------------
% MRISC32 ISA Manual - Opcode list.
%
% This work is licensed under the Creative Commons Attribution-ShareAlike 4.0
% International License. To view a copy of this license, visit
% http://creativecommons.org/licenses/by-sa/4.0/ or send a letter to
% Creative Commons, PO Box 1866, Mountain View, CA 94042, USA.
%------------------------------------------------------------------------------

\chapter{Opcode list}

This non-normative section lists all the opcodes, used and vacant, of the
MRISC32 ISA.

Legend:
\begin{bulletitems}
  \item{\textbf{OP} --- The instruction operation identifier}
  \item{\textbf{FN} --- The instruction function identifier (extended operation)}
  \item{\hyperref[module:Base]{Base} --- Part of the Base architecture}
  \item{\hyperref[module:PM]{PM} --- Requires the Packed operation module}
  \item{\hyperref[module:FM]{FM} --- Requires the Floating-point module}
  \item{\hyperref[module:SM]{SM} --- Requires the Saturating and halving arithmetic module}
\end{bulletitems}

\input{build/gen-opcode-list}


text:
%Applications that make heavy use of big data application frameworks require intensive reasoning of the system architecture.
We set out to assist the continuous architecting of big data streaming designs by OSTIA, a toolkit to assist designers and developers to facilitate static analysis of the architecture and provide automated constraint verification in order to identify design anti-patterns and provide structural refactorings. OSTIA helps designers and developers by recovering and analysing the architectural topology on-the-fly, assisting them in: (a) reasoning on the topological structure and how to refine it; (b) export the topological structure consistently with restrictions of their reference development framework so that further analysis (e.g., formal verification) may ensue. In addition, while performing on-the-fly architecture recovery, the analyses that OSTIA is able to apply focus on checking for the compliance to essential consistency rules specific to targeted big data frameworks. Finally, OSTIA allows to check whether the recovered topologies contain occurrences of key anti-patterns. By running a case-study with a partner organization, we observed that OSTIA assists designers and developers in establishing and continuously improving the quality of topologies behind their big data applications. We confirmed this result running OSTIA on several open-source applications featuring streaming technologies. We released OSTIA as an open-source software~\cite{ostia}. % \url{https://github.com/maelstromdat/OSTIA}.

In the future we plan to further elaborate the anti-patterns,
%that may emerge across big data topologies
exploiting graphs analysis techniques inherited from social-networks analysis. Also, we plan to expand OSTIA to support further technologies beyond the most common application framework for streaming, i.e., Storm. Finally, we plan to further evaluate OSTIA using empirical evaluation.

{\small\subsubsection*{Acknowledgment} The Authors' work is partially supported by the European Commission grant no. 644869 (EU H2020), DICE.}

%{\small\subsubsection*{Appendix} Please follow the link to navigate to the appendices: \url{http://tinyurl.com/zco4sdz}.}

ext: tex

max_stars_repo_path: [after-JSS] OSTIA/conc.tex

max_stars_repo_name: maelstromdat/OSTIA

max_issues_repo_path: [after-JSS] OSTIA/conc.tex

max_issues_repo_name: maelstromdat/OSTIA

max_forks_repo_path: [after-JSS] OSTIA/conc.tex

max_forks_repo_name: maelstromdat/OSTIA


text:
\section{Foreign Function Interface}
\label{ffi}

In the attempt to have a performant scripting language (luajit) in oure case
with a performant language (C) we need a way for the two to communicate.
For our specific usecase we have the informal line set as ``Smart but slow lua,
and fast but dumb C''.
To achieve this we require a foriegn function interface (ffi) to allow lua to
inform C of what to do.
We compare many ffi implementations, namely:
\begin{itemize}
  \item {\bf Lua C API}: Lua comes with a default Lua C API. Using this method
    requires modification to the C code, but from a Lua perspective the C
    library seems like just another Lua module.
  \item {\bf luaFFI}: The library provides the ability to use the same ffi as
    luajit and requires not modification to the C libraries included.
  \item {\bf dyncall}: Dyncall\cite{dyncall} Is a generic ffi library that has
    bindings to many other languages and enables us to call C functions.
\end{itemize}

\subsection{What and how to measure}
\begin{figure}[h]
\caption{Measuring FFI performance}
\centering
\includegraphics{figs/luac_time.pdf}
\label{ffi_fig}
\end{figure}

The FFI library consists of mainly three parts.
The steps involved are a. load the libraries, b. finding the function, and c. executing the found function.
Step a. is not considered by us because this is more of a startup cost, and does not impact the true execution of the ffi modlue selected
 b. and c. on the otherhand are overheads spent int every execution and hence part of our measurement (steps 3, 4, and 5 in Figure~\ref{ffi_fig}).
We would like to keep the c functions essentially no-ops as we are interested in the finding time and the transit time for C to Lua and vice versa.
By performing no-ops we risk thejust in time(JIT) compiler optimizing out that Lua to C code path entirely..
Lastly measuring the start and end times of the test also introduce a point of uncertainity. To minimize this, we measure the time taken by $1$ million transitions between the Lua and C code, where the results of the code is being accumulated and printed at the end of the process.
We present our results in Table~\ref{ffi_bench}. Note that the results are presented as speedup factors instead of absolute numbers (the devision of the absolute number by the baseline). The baseline is se to {\bf lua + luaFFI}.

\begin{tabular}{|l|l|l|l|l|l|l} \hline \hline
\label{ffi_bench}
lua + Lua C API & Luajit + Lua C API & lua + luaffi & luajit & lua + dyncall & luajit + dyncall \\
1.85 & 4.35 & 1.00 & 52.08 & 0.47 & 0.70 \\
\hline
\end{tabular}
% to rebuild these results go to experimental/dyntest and exec ./setup.sh
Based on Table~\ref{ffi_bench} we picked luajit's native ffi routine as our choice.

max_stars_repo_name: subramon/qlu

max_issues_repo_name: subramon/qlu

max_forks_repo_name: subramon/qlu


text:
\chapter{Link-Cut Trees}

In this chapter, we will learn about a dynamic data structure that allows us to speed-up Dinic's algorithm even more: \emph{Link-Cut Trees}.

\section{Overview}

\paragraph{Model.} We consider a directed graph $G=(V,E)$ that is undergoing \emph{updates} in the form of edge insertions and/or deletions. We number the graph in its different \emph{versions} $G^0, G^1, G^2, \dots$ such that $G^0$ is the initial input graph, and $G^i$ is the initial graph after the first $i$ updates were applied. Such a graph is called a \emph{dynamic} graph.

In this lecture, we restrict ourselves to \emph{dynamic rooted forests} that is we assume that every $G^i$ forms a directed forest where in each forest a single root vertex is reached by every other vertex in the tree. For simplicity, we assume that $G^0 = (V, \emptyset)$ is an empty graph.

\begin{figure}[!ht]
    \centering
    \includegraphics[scale=0.2]{./fig/InsertionDynamicTree_lectureDynamicTree.jpeg}
    \caption{The $i^{th}$ version of $G$ is a rooted forest. Here, red vertices are roots and there are two trees. The $(i+1)^{th}$ version of $G$ differs from $G^i$ by a single edge that was inserted (the blue edge). Note that edge insertions are only valid if the tail of the edge is a root.}
    \label{fig:my_label}
\end{figure}

\paragraph{The Interface.} Let us now describe the interface of our data structure that we call a link-cut tree. We want to support the following operations:
\begin{itemize}
    \item $\textsc{Initialize}(G)$: Creates the data structure initially and returns a pointer to it. Each vertex is initialized to have an associated cost $cost(v)$ equal to $0$.
    \item $\textsc{FindRoot}(v)$: Returns the root of vertex $v$.
    \item $\textsc{AddCost}(v, \Delta)$: Add $\Delta$ to the cost of every vertex on the path from $v$ to the root vertex $\textsc{FindRoot}(v)$.
    \item $\textsc{FindMin}(v)$: Returns tuple $(w, cost(w))$ where $w$ is the (first) vertex on the path from $v$ to $\textsc{FindRoot}(v)$ of lowest cost.
    \item $\textsc{Link}(u,v)$: Links two trees that contain $u$ and $v$ into a single tree by inserting the edge $(u,v)$. This assumes that $u, v$ are initially in different trees and $u$ was a root vertex.
    \item $\textsc{Cut}(u,v)$: Cuts the edge $(u,v)$ from the graph which causes the subtree rooted at $u$ to become a tree and $u$ to become a root vertex. Assumes $(u,v)$ is in the current graph.
\end{itemize}

\paragraph{Main Result.} The following theorem is the main result of today's lecture.

\begin{theorem}\label{thm:mainTheoremLinkCutTree}
We can implement a link-cut tree such that any sequence of $m$ operations takes total expected time $O(m \log^2 n + |V|)$.
\end{theorem}

\section{A Data Structure for Path Graphs}

Before we prove \Cref{thm:mainTheoremLinkCutTree} in its full generality, let us reason about implementing a link-cut tree data structure in a weaker setting: we assume that every version $G^i$ of $G$ is just a collection of rooted vertex-disjoint paths.

\paragraph{Representing Paths via Balanced Binary Search Trees.} It turns out that paths can be represented rather straight-forwardly via Balanced Binary Search Trees. For the sake of concreteness, we here use \emph{treaps} to represent paths\footnote{If you have not seen treaps before, don't worry, they are simple enough to understand them from our application here. }.

Let us now describe how to represent a path $P$ in $G$. First, we pick for each vertex $v$, a random natural number $ranNum(v)$ uniformly at random from a large universe, say $[1, n^{100})$. We assume henceforth that $ranNum(v) \neq ranNum(w)$ for all $v,w\in V$.

Then, for each path $P$ in $G$, we store the vertices in $P$ in a binary tree $\mathcal{P}$ and enforce the invariants:
\begin{itemize}
    \item \textbf{Heap-Order}: for each vertex $v \in P$, its parent $w = parent_{\mathcal{P}}(v)$ in $\mathcal{P}$ is either $NULL$ (if $v$ is the root) or has $ranNum(v) > ranNum(w)$.
    \item \textbf{Search-Property}: for all $v$, $left_{\mathcal{P}}(v)$ precedes $v$ on $P$ and $right_{\mathcal{P}}(v)$ appears later on $P$ than $v$. See the picture below for an illustration.
\end{itemize}

\begin{figure}[!ht]
    \centering
    \includegraphics[scale=0.2]{./fig/PathRepTreap_lectureDynamicTree.jpeg}
    \caption{In the upper half of the picture, the original path $P$ in $G$ is shown, along with the random numbers $ranNum(v)$ for each $v$. The lower half depicts the resulting treap with vertices on the same vertical line as before.}
    \label{fig:my_label}
\end{figure}

\paragraph{Depth of Vertex in a Treap.} Let us next analyze the expected depth of a vertex $v$ in a treap $\mathcal{P}$ representing a path $P$. Let $P = \langle x_1, x_2, \dots, x_k = v, \dots, x_{|P|}\rangle$, i.e. $v$ is the $k^{th}$ vertex on the path $P$. Observe that a vertex $x_i$ with $i < k$ is an ancestor of $v$ in $\mathcal{P}$ if and only if no vertex $\{x_{i+1}, x_{i+2}, \dots, x_k\}$ has received a smaller random number than $ranNum(x_i)$. Since we sample $ranNum(w)$ uniformly at random for each $w$, we have that $\mathbb{P}[x_i \text{ ancestor of } v] = \frac{1}{k-i+1}$. The case where $i > k$ is analogous and has $\mathbb{P}[x_i \text{ ancestor of } v] = \frac{1}{i-k+1}$. Letting $X_i$ be the indicator variable for the event that $x_i$ is an ancestor of $v$, it is straight-forward to calculate the expected depth of $v$ in $\mathcal{P}$:
\[
    \mathbb{E}[depth(v)] = \sum_{i \neq k} \mathbb{E}[X_i] =  \sum_{i = 1}^{k-1}\frac{1}{k-i+1} + \sum_{i = k+1}^{|P|} \frac{1}{i-k+1} = H_k + H_{|P|-k+1} - 2 = O(\log |P|)
\]
It is straight-forward to see that the operation $\textsc{FindRoot}(v)$ can thus be implemented to run in expected $O(\log n)$ time by just iteratively following the parent pointers starting in $v$.

\paragraph{Implementing $\textsc{FindRoot}(v)$.} From any vertex $v$, we can simply follow the parent pointers in $\mathcal{P}$ until we are at the root of $\mathcal{P}$. Then, we find the right-most child of $\mathcal{P}$ by following the $left_{\mathcal{P}}$ pointers. Finally, we return the left-most child which is the root.

\paragraph{Implementing $\textsc{AddCost}(v, \Delta)$ and $\textsc{FindMin}(v)$.} The key trick to do the operations above efficiently is to store the change to subtrees instead of updating $cost(v)$ for each affected vertex.

To this end, we store two fields $\Delta cost(v)$ and $\Delta min(v)$ for every vertex $v$. We let $cost(v)$ be the cost of each vertex, and $mincost(v)$ denote the minimum cost of any descendant of $v$ in $\mathcal{P}$. Then, we maintain for each $v$
\[
    \Delta cost(v) = cost(v) - mincost(v)
\]
\[
    \Delta min(v) = \begin{cases}
    mincost(v) & parent_{\mathcal{P}}(v) = NULL, \\
    mincost(v) - mincost(parent_{\mathcal{P}}(v)) & otherwise\end{cases}
\]
It is not hard to see that with these definitions, we obtain $mincost(v) = \sum_{w \in \mathcal{P}[v]} \Delta min(v)$ where $\mathcal{P}[v]$ is the $v$-to-root path in $\mathcal{P}$. We can then recover $cost(v) = mincost(v) + \Delta cost(v)$.

To enforce this invariant, when $\textsc{AddCost}(v, \Delta)$ is invoked, we can simply manipulate the fields of vertices that are adjacent to the $v$-to-root path in $\mathcal{P}$ (This depends on whether the path takes a right or left turn). This can be done in expected $O(\log n)$ time.

To implement the operation $\textsc{FindMin}(v)$ efficiently, we can use binary search to visit a child $w$ (the left one if both are eligible) where $mincost(v) = mincost(w)$. It is not hard to see that each $mincost(w)$ can be found in $O(1)$ given the $mincost$ of its parent. Thus, one can implement $\textsc{FindMin}(v)$ again in $O(\log n)$ expected time.

\paragraph{Implementing $\textsc{Link}(u,v)$ and $\textsc{Cut}(u,v)$.} We start by showing how to implement $\textsc{Cut}(u,v)$. Therefore, we assume that we have a dummy node $d_0$ with $ranNum(d_0) = 0$ in the vertex set. The trick is to first treat the operation as splitting the edge $(u,v)$ into $(u,d_0)$ and $(d_0,v)$ by inserting the vertex $d_0$ in between $u$ and $v$ in the tree $\mathcal{P}$ as a leaf (this is always possible). Then, we can do standard binary tree rotations to re-establish the heap-order invariant (here we have to also carefully recompute the new fields we introduce but this can again be done in $O(1)$ time per rotation). It is not hard to see that after $O(\log n)$ tree rotations in expectation, the heap-order is re-established and $d_0$ is at new root of $\mathcal{P}$. It remains to remove $d_0$ and make $left_{\mathcal{P}}(d_0)$ and $right_{\mathcal{P}}(d_0)$ tree roots.

\begin{figure}[!ht]
    \centering
    \includegraphics[scale=0.2]{./fig/PathCutOperation_lectureDynamicTree.jpeg}
    \caption{For $\textsc{Cut}(u,v)$, we insert a vertex $d_0$ as a leaf of either $u$ or $v$ to formally split $(u,v)$ into $(u,d_0)$ and $(d_0,v)$ (this is shown on the left). While this preserves that Search-Property, it will violate the Heap-Order. Thus, we need to use tree rotations (shown on the left) to push $d_0$ to the top of the tree $\mathcal{P}$ (the arrow between the tree rotations should point in both ways).}
\end{figure}

Implementing $\textsc{Link}(u,v)$ could be done by reversing the process described above. We choose however a slightly different strategy: we insert a vertex $d_{\infty}$ with $ranNum(d_{\infty}) = n^{100}$ and make it a right child of $u$. We then find the root $r$ of the tree over the path containing $v$ (as a tail). Finally, we make $r$ a right child of $d_{\infty}$. It remains to use tree rotations to make $d_{\infty}$ a leaf in the tree.  Once this is accomplished, one can simply remove $d_{\infty}$ from the tree entirely (which can be seen as un-splitting two edges into $(u,v)$).

\paragraph{Notes.} The operations $\textsc{Link}/ \textsc{Cut}$ can be implemented for almost all Balanced Binary Search Trees (especially the ones you have seen in your first courses on data structures). Thus, it is not hard to get a $O(\log n)$ worst-case time bound for all operations discussed above.

\section{Implementing Trees via Paths}

We now use the result from last section as a black box to obtain \Cref{thm:mainTheoremLinkCutTree}.

\paragraph{Path Decomposition.} For each rooted tree $T$, the idea is to decompose $T$ into paths. In particular, we decompose each $T$ into a collection of vertex-disjoint paths $P_1, P_2, \dots, P_k$ such that each internal vertex $v$ in $T$ has exactly one incoming edge in some $P_i$. We call the edges on some $P_i$  \emph{solid} edges and say that the other edges are \emph{dashed}.

We maintain the paths $P_1, P_2, \dots, P_k$ using the data structure described in the last section. To avoid confusion, we use the prefix $P$ when we invoke operations of the path data structure, for example $\textsc{PFindRoot}(v)$ finds the root of $v$ in the path graph consisting of all the $P_i$'s.

\begin{figure}[!ht]
    \centering
    \includegraphics[scale=0.20]{./fig/HeavyLightDecomposition_lectureDynamicTree.jpeg}
    \caption{The dashed edges are the edges not on any path $P_i$. The collection of (non-empty) paths $P_1, P_2, \dots, P_k$ can be seen to be the maximal path segments of solid edges.}
\end{figure}

\paragraph{The $\textsc{Expose}(v)$ Operation.} We now discuss the most important operation of the data structure that will be used by all other operations internally: the operation $\textsc{Expose}(v)$. This operation flips solid/dashed edges such that after the procedure the path from $v$ to its tree root in $G$ is solid (possibly as a subpath in the path collection). Below you can find an implementation of the procedure $\textsc{Expose}(v)$.

\begin{algorithm}
  \SetAlgoLined
  $w \gets v$.\\
  \While{$(w' = parent_G(\textsc{PFindRoot}(w))) \neq NULL$}{
    Invoke $\textsc{PCut}(z,w')$ for the solid edge $(z,w')$ incoming to $w'$.\\
    $\textsc{PLink}(w,w')$.\\
    $w \gets w'$.\\
  }
  \caption{\textsc{Expose}(v)}
\end{algorithm}

\paragraph{Implementing Operations via $\textsc{Expose}(v)$.} We can now implement link-cut tree operations by invoking $\textsc{Expose}(v)$ and then forwarding the operation to the path data structure.
\begin{algorithm}[H]
  \SetAlgoLined
  $\textsc{Expose}(v)$; $\textsc{PAddCost}(v, \Delta)$
  \caption{$\textsc{AddCost}(v, \Delta)$}
\end{algorithm}
\begin{algorithm}[H]
  \SetAlgoLined
  $\textsc{Expose}(v)$; \Return $\textsc{PFindMin}(v)$
  \caption{\textsc{FindMin}(v)}
\end{algorithm}
\begin{algorithm}[H]
  \SetAlgoLined
  $parent_G(u) \gets v$\;
  \lIf{$v$ has an incoming solid edge $(z,v)$}{
    $\textsc{PCut}(z,v)$
  }
  $\textsc{PLink}(u,v)$
  \caption{\textsc{Link}(u,v)}
\end{algorithm}
\begin{algorithm}[H]
  \SetAlgoLined
  $\textsc{Expose}(u)$; $parent_G(u) \gets NULL$; $\textsc{PCut}(u,v)$\;
   \lIf{$v$ has other incoming edge $(z,v)$}{$\textsc{PLink}(z,v)$}
  \caption{\textsc{Cut}(u,v)}
\end{algorithm}

\paragraph{Analysis.} All of the operations above can be implemented using a single $\textsc{Expose}(\cdot)$ operation plus $O(1)$ operations on paths. Since path operations can be executed efficiently, our main task is to bound the run-time of $\textsc{Expose}(\cdot)$. More precisely, since each iteration of $\textsc{Expose}(\cdot)$ also runs in time $O(\log n)$, the total number of while-loop iterations in $\textsc{Expose}(\cdot)$.

To this end, we introduce a dichotomy over the vertices in $G$. We let $parent_G(v)$ denote the unique parent of $v$ in $G$ and let $size_G(v)$ denote the number of vertices in the subtree rooted at $v$ (including $v$).

\begin{definition}
Then, we say that an edge $(u,v)$ is \emph{heavy} if $size_G(u) > size_G(v)/2$. Otherwise, we say $(u,v)$ is \emph{light}.
\end{definition}

It can now be seen that the number of \emph{light} edges on the $v$-to-root path for any $v$ is at most $\lg n$: every time we follow a light edge $(w,w')$, i.e. when $size_G(w') > 2 size_G(w)$, we double the size of the subtree so after taking more than $\lg n$ such edges, we have $> 2^{\lg n} = n$ vertices in the graph (which is a contradiction).

Thus, when $\textsc{Expose}(\cdot)$ runs for many iterations, it must turn many \emph{heavy} edges \emph{solid} (this is also since each vertex has at most one incoming heavy edge, so when we make a heavy edge solid, we also don't make any other heavy edge solid).

\begin{claim}
Each update can only increase the number of dashed, heavy edges by $O(\log n)$.
\end{claim}
\begin{proof}
First observe that every time $\textsc{Expose}(\cdot)$ is invoked, it turns at most $\lg n$ heavy edges from solid to dashed (since it has to visit a light edge to do so).

The only two operations that can cause additional dashed, heavy edges are $\textsc{Link}(u,v)$ and $\textsc{Cut}(u,v)$ by toggling heavy/light. For $\textsc{Link}(u,v)$, we observe that only the vertices on the $v$-to-root path increase their sizes. Since there are at most $\lg n$ light edges on this path that can turn heavy, this increases the number of dashed, heavy edges by at most $\lg n$.

The case for $\textsc{Cut}(u,v)$ is almost analogous: only vertices on the $v$-to-root path decrease their sizes which can cause any heavy edge on such a path to become light, and instead for a sibling of such a vertex might becomes heavy. But there can be at most $\lg n$ such new heavy edges, otherwise the total size of the tree must exceed again $n$ which leads to a contradiction.
\end{proof}

We conclude that the while-loop in $\textsc{Expose}(\cdot)$ runs for at most $O(m \log n)$ iterations after $m$ updates. Each iteration can be implemented in $O(\log n)$ expected time. This dominates the total running time and proves \Cref{thm:mainTheoremLinkCutTree}.

\section{Fast Blocking Flow via Dynamic Trees}

Recall from \Cref{sec:findBlockingFlows} that computing blocking flows in a level graph $L$ from a vertex $s$ to $t$ can be done by successively running $\textsc{DFS}(s)$ and routing flow along the $s$-$t$ path found if one such path exists and otherwise we know that we have found a blocking flow.

We can now speed-up this procedure by storing the DFS-tree explicitly as a dynamic tree. To simplify exposition, we transform $L$ to obtain a graph $\textsc{Transform}(L)$ that has capacities on vertices instead of edges. To obtain $\textsc{Transform}(L)$, we simply split each edge in $L$ and assign the edge capacity to the mid-point vertex while assigning capacity $\infty$ to all vertices that were already in $L$. This creates an identical flow problem with at most $O(m)$ vertices and edges.

\begin{figure}[!ht]
    \centering
    \includegraphics[scale=0.2]{./fig/TransformToVertCaps_lectureDynamicTree.jpeg}
    \caption{Each edge $(u,v)$ with capacity $c(u,v)$ is split into two edges $(u,m)$ and $(m,v)$. The capacity is then on the vertex $m$.}
    \label{fig:my_label}
\end{figure}

Finally, we give the new pseudo-code for the blocking flow procedure below.

\begin{algorithm}[H]
  \SetAlgoLined
  $H \leftarrow \textsc{Transform}(L)$\;
  $\textsc{LC-Tree} \gets \textsc{Initialize}(H)$\;

  \While{$s \in H$}{
    $u \gets \textsc{LC-Tree}.\textsc{FindRoot}(s)$\;
    \eIf{there is an edge $(u,v) \in H$}{
        $\textsc{LC-Tree}.\textsc{Link}(u,v)$\;
        \If{$v = t$}{
            $(w, c) \gets \textsc{LC-Tree}.\textsc{FindMin}(s)$\;
            $\textsc{LC-Tree}.\textsc{AddCost}(s, - c)$\;
            Remove $w$ and all its incident edges from $H$ and $\textsc{LC-Tree}$ (via $\textsc{Cut}(\cdot)$).
        }
    }{
        Remove $u$ and all its incident edges from $H$ and $\textsc{LC-Tree}$ (via $\textsc{Cut}(\cdot)$).
    }
  }
  Construct $\ff$ by setting for each edge $(u,v)$ of $L$, with mid-point $m$ in $\textsc{Transform}(L)$, the flow equal to $c(m)$ minus the cost on $m$ just before it was removed from $H$.
  \caption{\textsc{FindBlockingFlow}(s, t, L)}
\end{algorithm}

\begin{claim}
The running time of $\textsc{FindBlockingFlow}(s, t, L)$ is $O(m \log^2 n + |V|)$.
\end{claim}
\begin{proof}
Each edge $(u,v)$ in the graph $\textsc{Transform}(L)$ enters the link-cut tree at most once (we only invoke $\textsc{Cut}(u,v)$ when we delete $(u,v)$ from $H$).

Next, observe that the first $if$-case requires $O(1 + \#edgesDeletedFromH)$ many tree operations. The $else$-case requires $O(\#edgesDeletedFromH)$ many tree operations.

But each edge is only deleted once from $H$, thus we have a total of $O(m)$ tree operations over all iterations. Since each link-cut tree operation takes amortized expected time $O(\log^2 n)$, we obtain the bound on the total running time.
\end{proof}

The correctness of this algorithm follows almost immediately using that the level graph $L$ (and therefore $\textsc{Transform}(L)$) is an ayclic graph.

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "agao21_script"
%%% End:


text:
\documentclass[notitlepage]{revtex4-1}
\usepackage{graphicx}
\graphicspath{{validation_data/1.1.2-64-g0d0fc6f/}}

\begin{document}
\title{DSMTS Validation results for \textit{stocal} samplers}
\author{version: \VAR{version}}
\maketitle{}

For each algorithm and model, figures show:
\begin{itemize}
\item on the left averaged trajectories of all system species over time
obtained by simulation (green) versus reported values from the DSMTS
repository (blue);

\item in the center the absolute standard error of sample averages
($\bar X_{t}$) from the reported mean ($\mu_{t}$) as a function of
sample size $N$:
\[
	\left|\frac{\bar X_{t}-\mu_{t}}{\sigma_{t}^{2}}\right| \sim \mathcal{N}\left(0, \frac{1}{\sqrt{N}}\right),
\]
where $\sigma_{t}$ is the reported standard deviation.
The red line ($3/\sqrt{N}$) is an upper bound for the error scaling
at three times the reported standard deviation and should be only
occasionally exceeded;

\item on the right the relative standard error between sampled
($\bar S_{t}^{2}$) and reported standard deviation ($\sigma_{t}^{2}$)
as a function of sample size:
\[
	\left|\frac{\bar S_{t}^{2}}{\sigma_{t}^{2}} - 1\right| \sim \mathcal{N}\left(0, \frac{2}{N}\right) .
\]
The red line ($5/\sqrt{N/2}$) is an upper bound for the error scaling
at five times the reported standard deviation and should be only
occasionally exceeded.
\end{itemize}

\BLOCK{ for method_name, figures in methods.items() }
\section{\VAR{method_name}}
\BLOCK{ for figure in figures }
\includegraphics[width=\textwidth]{\VAR{figure}}
\BLOCK{ endfor }
\BLOCK{ endfor }
\end{document}

max_stars_repo_name: Maxoyd/stocal

max_issues_repo_name: Maxoyd/stocal

max_forks_repo_name: Maxoyd/stocal


text:
\section{Orders Modulo a Prime and Related Stuffs}

	\faka
	\begin{myitemize}{}
		\item \href{http://web.evanchen.cc/handouts/ORPR/ORPR.pdf}{Order Modulo a Prime - Evan Chen}
		\item \href{https://proofwiki.org/wiki/Zsigmondy's_Theorem}{Another source of the proof of Zsigmondy's Theorem}
	\end{myitemize}
	\faka

\subsection{Cyclotomic Polynomials}

	\begin{myitemize}
		\item \href{https://pdfs.semanticscholar.org/1445/5f5fbff56e403f72a6f4efad7e1e82b17f49.pdf}{Elementary Properties of Cyclotomic Polynomials - Yimin Ge}
	\end{myitemize}

	\den{Cyclotomic Formulas}{
		For any integer $n$, we have
		\[ X^n - 1 = \prod_{d \mid n} \Phi_d(X)\]
		In particular, if $p$ is a prime then
		\[ \Phi_p(X) = \frac{X^p-1}{X-1} = X^{p-1} + X^{p-2} + \dots + 1\]
	}
	\faka

	\den{Mobius Function}{The Mobius function $ \mu $ maps the natural numbers to the set $ \{-1, 0, 1\} $. $ \mu $ can be defined in multiple ways:
		\begin{itemize}
			\item Let $ \zeta_i $ be the primitive roots of $ n^{th} $ cyclotomic polynomial, then $ \displaystyle\mu (n) = \sum{\zeta_i} $
			\item \[\mu(n)=
			\begin{cases}
			1	&  \text{ if }	n \text{ is square free and has an even number of prime divisors}\\
			-1	&  \text{ if }	n \text{ is square free and has an odd number of prime divisors}\\
			0	&  \text{ if }	n \text{ has a prime square divisor}
			\end{cases}\]
	\end{itemize}}

	\lem{Sum of Mobius functions of divisors}{Let $ n $ be a positive integer. Then
		\[\sum_{d|n} \mu(d) =
			\begin{cases}
			1 & \text{ if }n=1\\
			0 & \text{ if }n\ge 2
			\end{cases}
		\]
	}

		\proof{The divisors of $ n $ with a prime square divisor will contribute $ 0 $. If $ n=1 $ it's trivial. So let $ n=p_1^{\a_1}p_2^{\a_2}\dots p_k^{\a_k} $. Then,
			\begin{align*}
				\sum_{d|n} \mu(d) &= \sum_{\{b_{1}\dots b_{t}\} \subseteq \{1, 2 \dots k\}} p_{b_1}\dots p_{b_t}\\[1em]
				&= \binom{k}{0} - \binom{k}{1} + \dots + (-1)^k\binom{k}{k}\\[.5em]
				&=0
			\end{align*}
		}

	\thmbox{https://en.wikipedia.org/wiki/Mobius_inverison_formula}{Mobius Inverison Formula}{Suppose $ F, f:\Z^+ \rightarrow \Z^+ $ are functions such that
		\[F(n)=\sum_{d|n} f(d)\ \implies \ f(n)=\sum_{d|n} \mu(d)\ F\left(\tfrac{n}{d}\right)\]
		\[F(n)=\prod_{d|n} f(d) \ \implies \ f(n)=\prod_{d|n}F\left(\tfrac{n}{d}\right)^{\mu(d)}\]
	}

		\proof{
			\begin{align*}
				\sum_{d|n} \mu(d)\ \sum_{t|\tfrac{n}{d}} f(t) &= \sum_{t|n} f(t) \sum_{d|n,\  t|\tfrac{n}{d}} \mu(d)\\[.5em]
				&=\sum_{t|n} f(t) \sum_{d|\tfrac{n}{t}} \mu(d)\\[.5em]
				&=f(n)\quad [\because \autoref{lemma:Sum of Mobius functions of divisors}]
			\end{align*}
		}

	\lem{Prime Divisors of Cyclotomic Polynomials}{If $ a\in \Z $ such that $ \Phi_n(a)\neq 0 $ and for some prime $ p $, \[\Phi_n(a)\equiv 0\ (\text{mod} \ p)\]
		Then either
		\begin{itemize}
			\item $ p\equiv 1\ (\text{mod} \ n) $, or
			\item $ p|n $
	\end{itemize}}

	\lem{}{If $ p $ does not divide $ m $, then\[\Phi_{pm}(x)\Phi_m(x)=\Phi_m(x^p)\]}

\subsection{Quadratic Residue}

	\theo{https://en.wikipedia.org/wiki/Quadratic_reciprocity}{Quadratic Reciprocity}{Let $ p $ and $ q $ be two prime numbers. Then using \href{https://en.wikipedia.org/wiki/Legendre_symbol}{Legendre symbol}, we have \[\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\tfrac{p-1}{2}\tfrac{q-1}{2}}\]}

	\lem{2 is a quadratic residue}{\[\left(\frac{2}{p}\right)=\left(-1\right)^{\tfrac{p^2-1}{8}}\]}

		\proof{Take $ a\not\equiv 0 \pmod p $. Let $ t_i \equiv ia \pmod p $ the least positive residues for $ 1\le i\le \dfrac{p-1}{2} $. Let $ r_1, r_2\dots r_m $ be the $ t_i $'s that are smaller than $ \dfrac{p-1}{2} $, and let $ s_1, s_2 \dots s_n $ be the $ t_i $'s that are larger than $ \dfrac{p-1}{2} $. Then we have,
				\[\{r_1, r_2,\dots r_m, p-s_1, p-s_2, \dots p-s_n\} = \{1, 2, \dots \dfrac{p-1}{2}\}\]
			So, multiplying gives us,
				\[a^{\tfrac{p-1}{2}}\equiv (-1)^n =\left(\frac{a}{p}\right) \pmod p\]
			Plugging in $ a=2 $, we get \autoref{lemma:2 is a quadratic residue}.
		}

%		\proof{Let $ s=\frac{p-1}{2} $. Consider the equations:
%			\begin{align*}
%			1& = (-1) (-1)\\
%			2& = 2 (-1)^2\\
%			3& = (-3) (-1)^3\\
%			\vdots\\
%			s&=(\pm s)(-1)^s
%			\end{align*}
%
%			Multiplying all of them gives us:
%			\begin{align*}
%			s!=(-1)2(-3)\dots (\pm s) \times (-1)^{\tfrac{s(s+1)}{2}}
%			\end{align*}
%			From the fact that $ -1 \equiv 2s $ and $ -3 \equiv 2(s-1)\ (mod\ p)$, the right side becomes,
%			\begin{align*}
%			(-1)2(-3)\dots (\pm s) \times (-1)^{\tfrac{s(s+1)}{2}}\equiv 2^s s! (-1)^{\tfrac{s(s+1)}{2}}\ (mod\ p)
%			\end{align*}
%			Which implies after dividing both sides by $ s! $,
%			\begin{align*}
%			1&\equiv 2^s (-1)^{\tfrac{s(s+1)}{2}}\ (mod\ p)\\
%			2^s&\equiv (-1)^{\tfrac{s(s+1)}{2}}\ (mod\ p)
%			\end{align*}
%			And since $ \dfrac{s(s+1)}{2} = \dfrac{p^2-1}{8} $, the lemma is proved.
%		}

	\lem{Quadratic non-residue mod infitely many primes}{There are infinitely many primes $p$ for every non-square integers $a$ such that $a$ is a non-quadratic residue $\left(\bmod\ p\right)$}

		\proof{We can assume that $ a $ is square free. So $ a=2^sp_1p_2\dots p_r $ for some $ s\in \{0, 1\} \text{ and } r\ge 0 $. Assume the contrary, that there are only finitely many primes, namely $ q_1, q_2 \dots q_m $ for which $ a $ is a quadratic non residue. We have three cases:\\

		\textbf{\textit{Case 1:}} $ s=1, r=0 $. In that case, we have infinitely many prime number, $ q $ such that $ q\equiv 3 \pmod 8 $, and $ x^2\not\equiv a \pmod q $ using \autoref{lemma:2 is a quadratic residue}.\\

		\textbf{\textit{Case 2:}} $ s=1, r>0 $. Take $ t $, a quadratic non-residue $ \pmod p_r $. Consider the following congruences:
			\begin{align*}
				x&\equiv 1 \pmod {q_i}	\text{ for all } q_i\\
				x&\equiv 1 \pmod 8\\
				x&\equiv 1 \pmod {p_i}	\text{ for } i=1, 2\dots r-1\\
				x&\equiv t \pmod {p_r}
			\end{align*}
		By Chinese Remainder Theorem and Dirichlet theorem, it follows that there exists infinitely many prime numbers $ N $ that satisfies all of the congruences. Now using Jacobi symbol and Law of Reciprocity, it follows that,
			\begin{align*}
				\left(\frac{2}{N}\right)&=1\\
				\left(\frac{p_i}{N}\right)&=1 \text{ for } i=1, 2\dots r-1\\
				\left(\frac{q_i}{N}\right)&=1 \text{ for all } q_i\\
				\left(\frac{p_r}{N}\right)&=-1
			\end{align*}
		Therefore, $ \displaystyle \left(\frac{a}{N}\right)=-1 $
		Which is a contradiction, since $ q_i \not| N $.\\

		\textbf{Case 3:} $ s=0, r>0 $, this is similar to the above case.}

	\newpage\subsubsection{Quadratic Residue}

	\theo{}{}{Let $ p $ be an odd prime. Then,

		\begin{enumerate}
			\item The product of two quadratic residue is a quadratic residue.
			\item The product of two quadratic non-residue is a quadratic residue.
			\item The product of a qudratic residue and a quadratic non-residue is a quadratic non-residue
	\end{enumerate}}

	\theo{}{}{For an odd prime $ p $ and any two integers $ a, b $, we have $  \left( \frac{ab}{p} \right) =  \left( \frac{a}{p} \right)  \left( \frac{b}{p} \right) $}

	\theo{}{Euler's Criterion}{Let $ p $ be an odd prime. Then, \[a^\frac{p-1}{2} \equiv  \left( \frac{a}{p} \right) (mod\ p)\]}

	\theo{}{}{Let $ (a, b)=1 $. Then every prime divisors of $ a^2+b^2 $ is either $ 2 $ or a prime of the form $ 4k+1 $.}

	\theo{}{Gauss's Criterion}{Let $ p $ be a prime number and $ a $ be an integer coprime to $ p $. Let $ \mu(a) $ be the number of integers $ x \in \{a, a*2, \dots a*\frac{p-1}{2}\} $ such that $ x (mod\ p) > \frac{p}{2} $. Then \[ \left( \frac{a}{p} \right) = -1^{\mu(a)} \]}

	\theo{}{}{The smallest quadratic non-residue of an odd prime $ p $ is a prime which is less than $ \sqrt{p} + 1 $}

	\theo{}{Quadratic Residue Law}{Using the usual Legendre Symbol, for two prime numbers $p,q$ we have: \[\left( \frac{p}{q}\right)\left( \frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\]}

	\den{Jacobi Symbol}{Let $ a, n=p_1^{\a_1}\dots p_k^{\a_k} $. We define Jacobi symbol as
		\[\left( \frac{a}{n} \right) = \prod_{i=1}^{k} \left( \frac{a}{p_i} \right)^{\a_i}\]}

	\begin{note}
		Jacobi symbol is not as accurate as Legendre symbol. $ \left( \frac{a}{n} \right) = -1 $ means that $ a $ is a quadratic non-residue of $ n $, but $ = 1 $ doesnt necessarily mean that $ a $ is a quadratic residue of $ n $.
	\end{note}

	\theo{}{}{Let $ a, n=p_1^{\a_1}\dots p_k^{\a_k} $, then $ a $ is a quadratic residue of $ n $ iff it is a quaadratic residue of every $ p_i^{\a_i} $.}

	\theo{}{}{\hl{If an integer is a quadratic residue of every prime, then it is a square.}}

	\subsection{Zsigmondy's Theorem}

		\begin{myitemize}
			\item \href{http://pommetatin.be/files/zsigmondy_en.pdf}{Zsigmondy's Theorem's Proof, has some useful lemmas}
		\end{myitemize}

		\theo{}{Zsigmondy's Theorem}{Let $ a, b\in \N $ such that $ \gcd(a, b)=1 $ and $ n\in \N, n>1 $. Then there exists a prime division of $ a^n-b^n $ that does not divide $ a^k-b^k $ for all $ 1\le k< n $ \emph{except} in the following cases:
			\begin{itemize}
				\itemsep-.5em
				\item $ 2^n-1^n $
				\item $ n=2 $ and $ a+b $ is a power of $ 2 $.
			\end{itemize}}

\subsection{Problems}

	\prob{https://artofproblemsolving.com/community/c6h1288391}{CGMO 2016 P3}{E}{Let $m$ and $n$ are relatively prime integers and $m>1,n>1$. Show that:There are positive integers $a,b,c$ such that $m^a=1+n^bc$ , and $n$ and $c$ are relatively prime.}

	\prob{https://artofproblemsolving.com/community/c6h33810p209770}{ISL 2004 N4}{EM}{Let $k$ be a fixed integer greater than 1, and let ${m=4k^2-5}$. Show that there exist positive integers $a$ and $b$ such that the sequence $(x_n)$ defined by \[x_0=a,\quad x_1=b,\quad x_{n+2}=x_{n+1}+x_n\quad\text{for}\quad n=0,1,2,\dots,\] has all of its terms relatively prime to $m$.}

		\solu{\input{dump/isl2004n4}}


text:
\chapter{Organization of the software}
\label{ch:design-philosophy}

Currently, data from the following stations are included:\\
\\
\begin{longtable}[htb]{ll}
\caption{List of radar stations}
\hline
\textbf{station code} & \textbf{full name}\\
\hline
\endhead
CZBRD & Brdy-Praha, Czech Republic\\
CZSKA & Skalky, Czech Republic \\
FIANJ & Anjalankoski, Finland \\
FIIKA & Ikaalinen, Finland \\
FIKOR & Korpo, Finland \\
FIKUO & Kuopio, Finland \\
FILUO & Luosto, Finland \\
FIUTA & Utaj\"{a}rvi, Finland \\
FIVAN & Vantaa, Finland \\
FIVIM & Vimpeli, Finland \\
FRABB & Abbeville, France \\
FRALE & Al\'{e}ria, France \\
FRAVE & LAvesnois, France \\
FRBLA & Blaisy-Haut, France \\
FRBOL & Boll\`{e}ne, France \\
FRBOR & Bordeaux, France \\
FRBOU & Bourges, France \\
FRCAE & Falaise, France \\
FRCHE & Cherves, France \\
FRCOL & Collobri\`{e}res, France \\
FRGRE & Gr\`{e}zes, France \\
FRMCL & Montclar, France \\
FRMOM & Momuy, France \\
FRMTC & Montancy, France \\
FRNAN & Nancy, France \\
FRNIM & N\^{i}mes, France \\
FRTRO & Arcis-sur-Aube, France \\
HRBIL & Bilogora, Croatia \\
IEDUB & Dublin, Ireland  \\
IESHA & Shannon, Ireland  \\
NLDBL & De Bilt, The Netherlands     \\
NLDHL & Den Helder, The Netherlands \\
NOAND & Andoya, Norway \\
NOBML & Boemlo, Norway \\
NOHAS & Hasvik, Norway \\
NOHGB & Haegebostad, Norway \\
NOHUR & Hurum, Norway \\
NORSA & Rissa, Norway \\
NORST & Rost, Norway \\
NOSTA & Stad, Norway \\
PLBRZ & Brzuchania, Poland \\
PLGDA & Gdansk, Poland \\
PLLEG & Legionowo, Poland \\
PLPAS & Pastewnik, Poland \\
PLPOZ & Pozna\'{n}, Poland \\
PLRAM & Ram\.{z}a, Poland \\
PLRZE & Rzesz\'{o}w, Poland \\
PLSWI & \'{S}widwin, Poland \\
SEANG & \"{A}ngelholm, Sweden \\
SEARL & Stockholm-Arlanda, Sweden \\
SEASE & Ase, Sweden \\
SEHUD & Hudiksvall, Sweden \\
SEKIR & Kiruna, Sweden \\
SEKKR & Karlskrona, Sweden \\
SELEK & Leksand, Sweden \\
SELUL & Lulue\r{a}, Sweden \\
SEOSU & \"{O}stersund, Sweden \\
SEOVI & \"{O}rnsk\"{o}ldsvik, Sweden \\
SEVAR & Vara, Sweden \\
SEVIL & Vilebo, Sweden \\
SILIS & Lisca, Slovenia \\
SKKOH & Kojsovska hola, Slovakia \\
SKMAJ & Maly Javornik, Slovakia\\
\end{longtable}

\needspace{10em}
\section{Directory structure}
The following table lists a selection of the most important files and directories as used in the \mbox{`ENRAMVM'} Virtual Machine.

\begin{longtable}[htb]{lp{7cm}}
\hline
\textbf{Location} & \textbf{Description}\\
(relative to \texttt{/home/wbouten/enram/}) & \\
\hline
\endhead
\texttt{data/}  & conbtains the radar data and derived products \\
\texttt{data/harmonized/bird/}  & contains radar data as HDF5 files after harmonization from zip, gz.tar, gif, etc. \\
\texttt{data/harmonized/cluttermaps/}  & contains cluttermaps for a given station, at different threshold levels of clutter \\
\texttt{data/harmonized/odim/}  & radar data for all stations for the period 15-Aug-2011 to 16-Sep-2011 in ODIM-HDF5 format. \\
\texttt{data/harmonized/statistics/}  & contains output from \texttt{src/process/statistics.pro} \\
\texttt{data/raw/}  & radar data for most stations for the period 15-Aug-2011 to 16-Sep-2011 as provided by individual weather services \\
\texttt{data/stations.txt}  & configuration file containing a list of stations that are part of the data set to be analyzed \\
\texttt{doc/}  & some relevant literature\\
\texttt{doc/readme/}  & the latex files needed for compiling this document\\
\texttt{log/stderr.txt}  &  standard error log\\
\texttt{log/stderr.txt}  & standard output log\\
\texttt{other-data/}  & miscellaneous data (currently not used)\\
\texttt{src/}  & source code main directory\\
\texttt{src/io}  & country-specific i/o routines written in IDL\\
\texttt{src/lib}  & programs and functions from external libraries, written in IDL\\
\texttt{src/process/bird\_call.pro} & IDL program that reads the radial velocity, reflectivity, and cluttermap. and then calls various procedures from Adriaan's library, ultimately resulting in profiles of bird density around a given station.  \\
\texttt{src/process/cluttermap.pro}\footref{fnlabel}  & IDL program that calculates cluttermaps at various thresholds of the statistics data.  Output is written to \texttt{data/harmonized/cluttermaps/}.  \\
\texttt{src/process/flysafe2.pro}  & IDL program that loops over a range of dates and various clutter threshold levels, and then calls \texttt{bird\_call.pro}. \\
\texttt{src/process/histogram.pro}\footref{fnlabel}  & IDL program that loops over a range of dates and stations, and then calls \texttt{statistics.pro}. \\
\texttt{src/process/statistics.pro}  & IDL program that calculates a histogram that serves as a base for constructing cluttermaps later. Output is written to \texttt{data/harmonized/statistics/} \\
\multicolumn{2}{l}{\texttt{src/raw-to-odim-conversion-tools}}\\
 & (incomplete) collection of conversion scripts, mostly written in Bash and C, with which the initial conversion was performed to convert the data from \texttt{data/raw} to the ODIM-HDF5 format in \texttt{data/harmonized/odim}.\\
\multicolumn{2}{l}{\texttt{src/visualization/make\_bird\_density\_profiles.pro}\footref{fnlabel}}\\
   & IDL program that creates figures of bird density as a function of time and altitude.\\
\multicolumn{2}{l}{\texttt{src/visualization/make\_colored\_donut\_maps.pro}\footref{fnlabel}} \\
 & IDL program that creates a figure in which the bird density around each radar is plotted as a colored  donut.\\
\multicolumn{2}{l}{\texttt{src/visualization/make\_ppi\_time\_space\_bird\_rain.pro}\footref{fnlabel}}  \\
& IDL program that creates a map of distributed PPI's of rain and of bird density, at given time intervals. \\
\multicolumn{2}{l}{\texttt{src/visualization/multi\_ppi.pro}\footnote{\label{fnlabel}This program is part of the main data processing pipeline, as defined in the Bash script \texttt{start-processing.sh}.}} \\
   & IDL program that visualizes multiple PPI's.\\
\texttt{src/visualization}  & figure-generating programs\\
\texttt{src/vol2bird} & stores Adriaan Dokter's C language program \\
\texttt{testdata/} & subset of \texttt{data/}, used in integration testing\\
\texttt{visualization-output/}  & directory where all visualization programs place their output figure files\\
\end{longtable}

max_stars_repo_name: NLeSC/enram

max_issues_repo_name: NLeSC/enram

max_forks_repo_name: NLeSC/enram


text:
\documentclass[a4paper]{article}

\usepackage{pdfpages}
\usepackage{verbatim}
\usepackage{listings}

\title{Example Document}
\author{Draget\\draget@speciesm.net}
\date{\today}

\begin{document}
\maketitle
\newpage

\tableofcontents
\newpage

\section{About}
This is a very simple TeX document. It does not use many TeX packages and is easy to build.

\section{The GitHub README.md}
\lstinputlisting[breaklines]{README.md}
\newpage

\section{Lore Ipsum Text}
\input{include/loreipsum}

\end{document}


text:
\documentclass[aspectratio=169]{beamer}

\usepackage{microtype}
\usepackage{tikzpeople}
\usepackage{drawstack}
\usepackage{graphicx}
\usepackage{fontawesome}
\usepackage{multirow}
\usepackage{fancyvrb}
\usepackage{listings}
\usepackage{siunitx}
\usepackage{tikz}
\usetikzlibrary{calc}
\usetikzlibrary{arrows.meta}
\usetikzlibrary{positioning}
\tikzstyle{block} = [draw, rectangle,
    minimum height=2em, minimum width=2em]

\newcommand{\cipher}[1]{\texttt{#1}}
\newcommand\presdate{June 18, 2020}

\setbeamercovered{transparent}

\usetheme[]{metropolis}
\metroset{block=fill}

\title{Android: Notifier (Server)}
\date{\presdate}

\author{Marcel Nageler, Sebastian Knoll, Martin Unterguggenberger}
\institute{}

\setbeamertemplate{frame footer}{Android: Notifier (Server) --- Graz, \presdate}

\definecolor{links}{HTML}{2A1B81}
\hypersetup{colorlinks,linkcolor=,urlcolor=links}

\begin{document}
  \maketitle

  %\begin{frame}
  %  \begin{figure}
  %    \centering
  %    \includegraphics[width=\textwidth]{figures/...}
  %    %\caption{}
  %  \end{figure}
  %\end{frame}

\section{Introduction}
  \begin{frame}{Motivation}
    \begin{itemize}
      \item Sending notifications from a phone to a PC
      \pause
      \item We do not trust the server
    \end{itemize}
  \end{frame}

  \begin{frame}{Security Goals}
    \begin{itemize}
      \item \textbf{Confidentialty}
        \setbeamercovered{invisible}
        \onslide<1>{$\rightarrow$ Third parties cannot read any messages}
        \setbeamercovered{transparent}
      \pause
      \item \textbf{Integrity}
        \setbeamercovered{invisible}
        \onslide<2>{$\rightarrow$ Third parties cannot alter or forge messages}
        \setbeamercovered{transparent}
      \pause
      % \item \textbf{Availability}
      %   \setbeamercovered{invisible}
      %   \onslide<3>{$\rightarrow$ Timely and reliable access to the information}
      %   \setbeamercovered{transparent}
      % \pause
      \item \textbf{Authencity}
        \setbeamercovered{invisible}
        \onslide<3>{$\rightarrow$ The sender is who they claim to be}
        \setbeamercovered{transparent}
      \pause
      \item \textbf{Forward Secrecy}
        \setbeamercovered{invisible}
        \onslide<4>{$\rightarrow$ Leak of a private key does not affect past communication}
        \setbeamercovered{transparent}
      \pause
      \item \textbf{Identity Hiding}
        \setbeamercovered{invisible}
        \onslide<5>{$\rightarrow$ Third parties do not see the public key of the sender}
        \setbeamercovered{transparent}
    \end{itemize}
  \end{frame}

\section{Implementation}

  \begin{frame}{Implementation}
    \begin{figure}
      \centering
      \only<1|handout:0>{\includegraphics[width=0.7\textwidth]{figures/anim1}}%
      \only<2|handout:0>{\includegraphics[width=0.7\textwidth]{figures/anim2}}%
      \only<3>{\includegraphics[width=0.7\textwidth]{figures/anim3}}%
      %\caption{}
    \end{figure}
  \end{frame}

  \begin{frame}{Implementation (cont.)}
    \begin{itemize}
      \item Server $\leftrightarrow$ PC
      \begin{itemize}
        \item Websockets for realtime communication
      \end{itemize}
      \item Server $\leftrightarrow$ smartphone
      \begin{itemize}
        \item Certificate Pinning
        \item plain \texttt{GET} and \texttt{POST} requests
      \end{itemize}
    \end{itemize}
  \end{frame}

  \begin{frame}{Curve25519}
    Popularity increased considerably after 2013 when it was discovered that the NSA had potentially implemented a backdoor into \texttt{Dual\_EC\_DRBG}
    \begin{itemize}
      \item \texttt{Curve25519} implemented in Go standard library
      \item Server and Client written in Go
      \item Android application uses Bouncy Castle library
    \end{itemize}
  \end{frame}

  \begin{frame}{Asymmetric cryptography}
    \cipher{Curve25519} is designed for use with the elliptic curve Diffie–Hellman (\texttt{ECDH})
    \begin{itemize}
      \item Digital Signature Algorithm \cipher{Ed25519}
      \item Key Exchange Algorithm \cipher{X25519}
      \item Shared \cipher{AES-256-GCM} key for message encryption
    \end{itemize}
  \end{frame}

  \begin{frame}{Android Keystore}
    Store cryptographic keys in a container to make it more difficult to extract from the device
    \begin{itemize}
      \item Key material remaining non-exportable
      \item Android Keystore System does not support \cipher{Curve25519}
      \item Asymmetric keys stored in encrypted file
      \item Android Keystore \cipher{AES-128-GCM} to encrypt file
    \end{itemize}
  \end{frame}

  \begin{frame}{Live Demo}
    \centering
    You've been watching it the whole time
    \begin{figure}
      \includegraphics[width=0.3\textwidth]{figures/live}
    \end{figure}
  \end{frame}

  \maketitle
%  \nocite{*}
%  \begin{frame}{References}
%    %\printbibliography
%    \bibliographystyle{alpha}
%    \bibliography{references}
%  \end{frame}
\end{document}

max_stars_repo_name: fanosta/secure-notifier

max_issues_repo_name: fanosta/secure-notifier

max_forks_repo_name: fanosta/secure-notifier