text:
\chapter{Appendix: LazySP Proofs and Timing Results}
\label{sec:appendix-proofs}

\section{LazySP Proofs}

\subsection{Theoretical Properties of LazySP}

\begin{proof}[Proof of Theorem \ref{thm:lazy-optimality}]
Let $p^*$ be an optimal path w.r.t. $w$,
with $\ell^* = \mbox{len}(p^*, w)$.
Since $w_{\ms{est}}(e) \leq \epsilon \, w(e)$ and $\epsilon \geq 1$,
it follows that regardless of which edges are stored in $W_{\ms{eval}}$,
$w_{\ms{lazy}}(e) \leq \epsilon \, w(e)$,
and therefore
$\mbox{len}(p^*, w_{\ms{lazy}}) \leq \epsilon \, \ell^*$.
Now,
since the inner \textsc{ShortestPath} algorithm terminated with
$p_{\ms{ret}}$,
we know that
$\mbox{len}(p_{\ms{ret}}, w_{\ms{lazy}}) \leq \mbox{len}(p^*, w_{\ms{lazy}})$.
Further,
since the algorithm terminated with $p_{\ms{ret}}$,
each edge on $p_{\ms{ret}}$ has been evaluated;
therefore,
$\mbox{len}(p_{\ms{ret}}, w) = \mbox{len}(p_{\ms{ret}}, w_{\ms{lazy}})$.
Therefore,
$\mbox{len}(p_{\ms{ret}}, w) \leq \epsilon \, \ell^*$.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm:lazy-completeness}]
In this case,
the algorithm will evaluate at least unevaluated edge at
each iteration.
Since there are a finite number of edges,
eventually the algorithm will terminate.
\end{proof}

\subsection{A* Equivalence}

\begin{proof}[Proof of Invariant \ref{inv:astar-cundisc-popen}]
If $v$ is discovered, then it must either be on OPEN or CLOSED.
$v$ can be on CLOSED only after it has been expanded,
in which case $s$ would be discovered (which it is not).
Therefore, $v$ must be on OPEN.
\end{proof}

\begin{proof}[Proof of Invariant \ref{inv:astar-wless-popen}]
Clearly the invariant holds at the beginning of the algorithm,
with only $v_{\ms{start}}$ on OPEN.
If the invariant were to no longer hold after some iteration,
then there must exist some pair of discovered vertices $v$ and $v'$
with $v$ on CLOSED and $g[v] + w(v,v') < g[v']$.
Since $v$ is on CLOSED,
it must have been expanded at some previous iteration,
immediately after which the inequality could not have held
because $g[v']$ is updated upon expansion of $v$.
Therefore,
the inequality must have newly held after some intervening iteration,
with $v$ remaining on CLOSED.
Since the values $g$ are monotonically non-increasing and $w$ is fixed,
this implies that $g[v]$ must have been updated (lower).
However,
if this had happened,
then $v$ would have been removed from CLOSED and placed on OPEN.
This contradiction implies that the invariant holds at every iteration.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm:astar-equiv-from-lazy}]
Consider path $p^*_{\ms{lazy}}$ with length $\ell^*_{\ms{lazy}}$
yielding frontier vertex $v_{\ms{frontier}}$ via \textsc{SelectExpand}.
Construct a vertex sequence $s$ as follows.
Initialize $s$ with the vertices on $p^*_{\ms{lazy}}$
from $v_{\ms{start}}$ to $v_{\ms{frontier}}$, inclusive.
Let $N$ be the number of consecutive vertices at the start of $s$
for which $f(v) = \ell^*_{\ms{lazy}}$
(Note that the first vertex on $p^*_{\ms{lazy}}$, $v_{\ms{start}}$,
must have $f(v_{\ms{start}}) = \ell^*_{\ms{lazy}}$,
so $N \geq 1$.)
Remove from the start of $s$ the first $N-1$ vertices.
Note that at most the first vertex on $s$ has
$f(v) = \ell^*_{\ms{lazy}}$,
and the last vertex on $s$ must be $v_{\ms{frontier}}$.

Now we show that each vertex in this sequence $s$,
considered by A* in turn,
exists on OPEN with minimal $f$-value.
Iteratively consider the following procedure for sequence $s$.
Throughout,
we know that there must not be any vertex with
$f(v) < \ell^*_{\ms{lazy}}$,
that would imply that a different path through $v_b$ shorter than
$\ell^*_{\ms{lazy}}$ exists,
in which case $p^*_{\ms{lazy}}$ could not have been chosen.

If the sequence has length $>1$,
then consider the first two vertices on $s$, $v_a$ and $v_b$.
By construction,
$f(v_a) = \ell^*_{\ms{lazy}}$
and
$f(v_b) \neq \ell^*_{\ms{lazy}}$.
In fact, from above
we know that $f(v_b) > \ell^*_{\ms{lazy}}$.
Therefore,
we have that $f(v_a) < f(v_b)$,
therefore and $g[v_a] + w(v_a,v_b) < g[v_b]$.
By Invariant~\ref{inv:astar-wless-popen},
$v_a$ must be on OPEN,
and with $f(v_a) = \ell^*_{\ms{lazy}}$,
it can therefore be considered by A*.
After it is expanded,
$f(v_b) = \ell^*_{\ms{lazy}}$,
and we can repeat the above procedure
with the sequence formed by removing the $v_a$ from $s$.

If instead the sequence has length $1$,
then it must be exactly $(v_{\ms{frontier}})$,
with $f(v_{\ms{frontier}}) = \ell^*_{\ms{lazy}}$.
Since the edge after $f(v_{\ms{frontier}})$ is not
evaluated,
then by Invariant~\ref{inv:astar-cundisc-popen},
$v_{\ms{frontier}}$ must be on OPEN,
and will therefore be expanded next.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm:astar-equiv-to-lazy}]
Given that all vertices in $s_{\ms{candidate}}$ besides the last
are re-expansions,
they can be expanded with no edge evaluations.
Once the last vertex,
$v_{\ms{frontier}}$,
is to be expanded by A*,
suppose it has $f$-value $\ell$.

First,
we will show that there exists a path with length $\ell$ w.r.t.
$w_{\ms{lazy}}$
wherein all edges before $v_{\ms{frontier}}$ have been evaluated,
and the first edge after $v_{\ms{frontier}}$ has not.
Let $p_a$ be a shortest path from $v_{\ms{start}}$
to $v_{\ms{frontier}}$ consisting of only evaluated edges.
The length of this $p_a$ must be equal to $g[v_{\ms{frontier}}]$;
if it were not,
there would be some previous vertex on $p_a$ with lower $f$-value
than $v_{\ms{frontier}}$,
which would necessarily have been expanded first.
Let $p_b$ be the a shortest path from $v_{\ms{frontier}}$
to $v_{\ms{goal}}$.
The length of $p_b$ must be $h_{\ms{lazy}}(v_{\ms{frontier}})$
by definition.
Therefore, the path $(p_a, p_b)$ must have length $\ell$,
and since $v_{\ms{frontier}}$ is a new expansion,
the first edge on $p_b$ must be unevaluated.

Second,
we will show that there does not exist any path shorter than $\ell$
w.r.t. $w_{\ms{lazy}}$.
Suppose $p'$ were such a path, with length $\ell' < \ell$.
Clearly, $v_{\ms{start}}$ would have $f$-value $\ell'$ (although
it may not be on OPEN).
Consider each pair of vertices $(v_a, v_b)$ along $p'$ in turn.
In each case,
if $v_b$ were either undiscovered,
or if $g[v_a] + w(v_a, v_b) < g[v_b]$,
then $v_a$ would be on OPEN
(via Invariants \ref{thm:lazy-completeness}
and \ref{inv:astar-wless-popen}, respectively)
with $f(v_a) = \ell'$,
and would therefore have been expanded before $v_{\ms{frontier}}$.
Otherwise,
we know that $f(v_b) = \ell'$,
and we can continue to the next pair on $p'$.
\end{proof}

\subsection{LWA* Equivalence}

\begin{proof}[Proof of Invariant \ref{inv:lwastar}]
Clearly the invariant holds at the beginning of the algorithm
with only $g[v_{\ms{start}}] = 0$,
since the inequality holds only for the out-edges of $v_{\ms{start}}$,
with $v_{\ms{start}}$ on $Q_v$.
Consider each subsequent iteration.
If a vertex $v$ is popped from $Q_v$,
then this may invalidate the invariant for all successors of $v$;
however,
since all out-edges are immediately added to $Q_e$,
the invariant must hold.
Consider instead if an edge $(v, v')$ which satisfies the inequality
is popped from $Q_e$.
Due to the inequality,
we know that $g[v']$ will be recalculated as
$g[v'] = g[v] + w(v,v')$,
so that the inequality is no longer satisfied for edge $(v,v')$.
However,
reducing the value $g[v']$ may introduce satisfied inequalities across
subsequent out-edges of $v'$,
but since $v'$ is added to $Q_v$,
the invariant continues to hold.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm:lwastar-equiv-from-lazy}]
In the first component of the equivalence,
we will show that for any path $p$ minimizing $w_{\ms{lazy}}$
allowable to LazySP-Forward,
with $(v_a, v_b)$ the first unevaluated edge on $p$,
there exists a sequence of vertices and edges on
$Q_v$ and $Q_e$ allowable to LWA*
such that edge $(v_a, v_b)$ is the first to be newly evaluated.
Let the length of $p$ w.r.t. $w_{\ms{lazy}}$ be $\ell$.'

We will first show that no vertex on $Q_v$ or edge on $Q_e$
can have $f(\cdot) < \ell$.
Suppose such a vertex $v$, or edge $e$ with source vertex $v$,
exists.
Then $g[v] + h(v) < \ell$,
and there must be some path $p'$ consisting of an evaluated segment
from $v_{\ms{start}}$ to $v$ of length $g[v]$,
followed a segment from $v$ to $v_{\ms{goal}}$ of length $h(v)$.
But then this path should have been chosen by LazySP.

Next, we will show a procedure for generating an allowable
sequence for LWA*.
We will iteratively consider a sequence of path segments,
starting with the segment from $v_{\ms{start}}$ to $v_a$,
and becoming progressively shorter at each iteration by removing the
first vertex and edge on the path.
We will show that the first vertex on each segment $v_f$
has $g[v_f] = \ell - h(v_f)$.
By definition,
this is true of the first such segment, since $g[v_{\ms{start}}] = 0$.
For each but the last such segment,
consider the first edge, $(v_f, v_s)$.
If $v_s$ has the correct $g[\cdot]$,
we can continue to the next segment immediately.
Otherwise,
either $v_f$ is on $Q_v$ or $(v_f, v_s)$ is on $Q_e$ by
Invariant~\ref{inv:lwastar}.
If the former is true,
then $v_f$ can be popped from $Q_v$ with $f = \ell$,
thereby adding $(v_f, v_s)$ to $Q_e$.
Then,
$(v_f, v_s)$ can be popped from $Q_e$ with $f = \ell$,
resulting in $g[v_s] = \ell - h(v_s)$.
We can then move on to the next segment.

At the end of this process,
we have the trivial segment $(v_a)$,
with $g[v_a] = \ell - h(v_a)$.
If $v_a$ is on $Q_v$, then pop it (with $f(v_a) = \ell$),
placing $e_{ab}$ on $Q_e$;
otherwise, since $e_{ab}$ is unevaluated,
it must already be on $Q_e$.
Since $f(e_{ab}) = \ell$, we can pop and evaluate it.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm:lwastar-equiv-to-lazy}]
Given that all vertices in $s_{\ms{candidate}}$ entail no edge evaluations,
and all edges therein are re-expansions,
they can be considered with no edge evaluations.
Once the last edge $e_{xy}$ is to be expanded by LWA*,
suppose it has $f$-value $\ell$.

First,
we will show that there exists a path with length $\ell$ w.r.t.
$w_{\ms{lazy}}$
which traverses unevaluated edge $e_{xy}$
wherein all edges before $v_x$ have been evaluated.
Let $p_x$ be a shortest path segment from $v_{\ms{start}}$
to $v_x$ consisting of only evaluated edges.
The length of $p_x$ must be equal to $g[v_x]$;
if it were not,
there would be some previous vertex on $p_x$ with lower $f$-value
than $v_x$,
which would necessarily have been expanded first.
Let $p_y$ be the a shortest path from $v_y$
to $v_{\ms{goal}}$.
The length of $p_y$ must be $h_{\ms{lazy}}(v_y)$
by definition.
Therefore, the path $(p_x, e_{xy}, p_y)$ must have length $\ell$.

Second,
we will show that there does not exist any path shorter than $\ell$
w.r.t. $w_{\ms{lazy}}$.
Suppose $p'$ were such a path, with length $\ell' < \ell$,
and with first unevaluated edge $e'_{xy}$.
Clearly, $v_{\ms{start}}$ has
$g[v_{\ms{start}}] = \ell' - h(v_{\ms{start}})$.
Consider each evaluated edge $e'_{ab}$ along $p'$ in turn.
In each case,
if $g[v'_b] \neq \ell' - h(v'_b)$,
then either $v'_a$ or $e'_{ab}$ would be on $Q_v$ or $Q_e$
with $f(\cdot) = \ell'$,
and would therefore be expanded before $e_{xy}$.
Therefore,
$e'_{xy}$ would then be popped from $Q_e$ with $f(e'_{xy}) = \ell'$,
and it would have been evaluated before $e_{xy}$ with $f(e_{xy}) = \ell$.
\end{proof}

\section{LazySP Timing Results}
\label{sec:appendix-timing}

We include an accounting of the cumulative computation time taken by
each component of LazySP for each of the seven selectors
for each problem class (Figure~\ref{fig:table-timing-results}).

\begin{figure*}
   \begin{widepage}%
   \centering%
   {\small%
   \setlength{\tabcolsep}{0.06cm}%
   \begin{tabular}{l@{\hskip 9pt}rc@{\hskip 0pt}r@{\hskip 9pt}rc@{\hskip 0pt}r@{\hskip 9pt}rc@{\hskip 0pt}r@{\hskip 9pt}rc@{\hskip 0pt}r@{\hskip 9pt}rc@{\hskip 0pt}r@{\hskip 9pt}rc@{\hskip 0pt}r@{\hskip 9pt}rc@{\hskip 0pt}r}
      \toprule
         & \multicolumn{3}{c}{Expand} & \multicolumn{3}{c}{Forward} & \multicolumn{3}{c}{Reverse} & \multicolumn{3}{c}{Alternate}
         & \multicolumn{3}{c}{Bisect} & \multicolumn{3}{c}{WeightSamp} & \multicolumn{3}{c}{Partition} \\
      \midrule
      \addlinespace[0.5em]
      PartConn & & & & & & & & & & & & & & & & & & & & & \\
      \;\;\emph{total (ms)}    &\bf1.22 &$\pm$&   0.04 &    1.96 &$\pm$&  0.06 &    1.86 &$\pm$&  0.06 &\bf1.20 &$\pm$& 0.03 &  2.41 &$\pm$& 0.06 & 4807.19 &$\pm$& 135.22 &   15.81 &$\pm$&  0.16 \\
      \;\;\emph{sel-init (ms)} & --\;\; &     &        &  --\;\; &     &       &  --\;\; &     &       & --\;\; &     &      &--\;\; &     &      &  --\;\; &     &        &   12.49 &$\pm$&  0.11 \\
      \;\;\emph{online (ms)}   &\bf1.22 &$\pm$&   0.04 &    1.96 &$\pm$&  0.06 &    1.86 &$\pm$&  0.06 &\bf1.20 &$\pm$& 0.03 &  2.41 &$\pm$& 0.06 & 4807.19 &$\pm$& 135.22 &    3.32 &$\pm$&  0.10 \\
      \;\;\emph{search (ms)}   &   0.48 &$\pm$&   0.01 &    1.12 &$\pm$&  0.03 &    1.05 &$\pm$&  0.03 &   0.68 &$\pm$& 0.02 &  1.38 &$\pm$& 0.04 &    0.70 &$\pm$&   0.02 &    0.68 &$\pm$&  0.02 \\
      \;\;\emph{sel (ms)}      &   0.02 &$\pm$&   0.00 &    0.01 &$\pm$&  0.00 &    0.01 &$\pm$&  0.00 &   0.01 &$\pm$& 0.00 &  0.03 &$\pm$& 0.00 & 4805.64 &$\pm$& 135.18 &    2.07 &$\pm$&  0.06 \\
      \;\;\emph{eval (ms)}     & --\;\; &     &        &  --\;\; &     &       &  --\;\; &     &       & --\;\; &     &      &--\;\; &     &      &  --\;\; &     &        &  --\;\; &     &       \\
      \;\;\emph{eval (edges)}  &  87.10 &$\pm$&   2.39 &   35.86 &$\pm$&  1.04 &   34.84 &$\pm$&  1.04 &  22.23 &$\pm$& 0.60 & 44.81 &$\pm$& 1.11 &\bf20.66 &$\pm$&   0.57 &\bf20.39 &$\pm$&  0.56 \\
      \addlinespace[0.5em]
      UnitSquare & & & & & & & & & & & & & & & & & & & & & \\
      \;\;\emph{total (ms)}    &\bf0.91 &$\pm$&   0.03 &    1.47 &$\pm$&  0.06 &    1.49 &$\pm$&  0.06 &\bf0.94 &$\pm$& 0.03 &  1.71 &$\pm$& 0.04 & 3864.95 &$\pm$& 117.66 &   15.13 &$\pm$&  0.14 \\
      \;\;\emph{sel-init (ms)} & --\;\; &     &        &  --\;\; &     &       &  --\;\; &     &       & --\;\; &     &      &--\;\; &     &      &  --\;\; &     &        &   13.41 &$\pm$&  0.12 \\
      \;\;\emph{online (ms)}   &\bf0.91 &$\pm$&   0.03 &    1.47 &$\pm$&  0.06 &    1.49 &$\pm$&  0.06 &\bf0.94 &$\pm$& 0.03 &  1.71 &$\pm$& 0.04 & 3864.95 &$\pm$& 117.66 &    1.72 &$\pm$&  0.06 \\
      \;\;\emph{search (ms)}   &   0.35 &$\pm$&   0.01 &    0.79 &$\pm$&  0.03 &    0.82 &$\pm$&  0.03 &   0.51 &$\pm$& 0.02 &  0.92 &$\pm$& 0.02 &    0.75 &$\pm$&   0.02 &    0.45 &$\pm$&  0.01 \\
      \;\;\emph{sel (ms)}      &   0.01 &$\pm$&   0.00 &    0.01 &$\pm$&  0.00 &    0.01 &$\pm$&  0.00 &   0.01 &$\pm$& 0.00 &  0.02 &$\pm$& 0.00 & 3863.49 &$\pm$& 117.62 &    0.87 &$\pm$&  0.03 \\
      \;\;\emph{eval (ms)}     & --\;\; &     &        &  --\;\; &     &       &  --\;\; &     &       & --\;\; &     &      &--\;\; &     &      &  --\;\; &     &        &  --\;\; &     &       \\
      \;\;\emph{eval (edges)}  &  69.21 &$\pm$&   2.55 &   27.29 &$\pm$&  1.03 &   27.69 &$\pm$&  1.02 &  17.82 &$\pm$& 0.60 & 32.62 &$\pm$& 0.72 &   15.58 &$\pm$&   0.47 &\bf14.08 &$\pm$&  0.46 \\
      \addlinespace[0.5em]
      ArmPlan (avg) & & & & & & & & & & & & & & & & & & & & & \\
      \;\;\emph{total (s)}    &  269.82 &$\pm$&  17.95 &\bf 5.90 &$\pm$&  0.46 &    8.22 &$\pm$&  0.53 &\bf5.96 &$\pm$& 0.31 &  7.34 &$\pm$& 0.43 & 3402.21 &$\pm$& 172.20 &  496.57 &$\pm$&  5.53 \\
      \;\;\emph{sel-init (s)} &  --\;\; &     &        &  --\;\; &     &       &  --\;\; &     &       & --\;\; &     &      &--\;\; &     &      &  --\;\; &     &        &  490.77 &$\pm$&  5.51 \\
      \;\;\emph{online (s)}   &  269.82 &$\pm$&  17.95 &\bf 5.90 &$\pm$&  0.46 &    8.22 &$\pm$&  0.53 &\bf5.96 &$\pm$& 0.31 &  7.34 &$\pm$& 0.43 & 3402.21 &$\pm$& 172.20 &\bf 5.80 &$\pm$&  0.28 \\
      \;\;\emph{search (s)}   &    0.02 &$\pm$&   0.00 &    0.02 &$\pm$&  0.00 &    0.02 &$\pm$&  0.00 &   0.02 &$\pm$& 0.00 &  0.02 &$\pm$& 0.00 &    0.02 &$\pm$&   0.00 &    0.04 &$\pm$&  0.00 \\
      \;\;\emph{sel (s)}      &    0.00 &$\pm$&   0.00 &    0.00 &$\pm$&  0.00 &    0.00 &$\pm$&  0.00 &   0.00 &$\pm$& 0.00 &  0.00 &$\pm$& 0.00 & 3392.76 &$\pm$& 171.74 &    1.54 &$\pm$&  0.09 \\
      \;\;\emph{eval (s)}     &  269.78 &$\pm$&  17.95 &    5.87 &$\pm$&  0.45 &    8.20 &$\pm$&  0.52 &   5.94 &$\pm$& 0.31 &  7.31 &$\pm$& 0.43 &    9.39 &$\pm$&   0.57 &    4.21 &$\pm$&  0.22 \\
      \;\;\emph{eval (edges)} &  949.05 &$\pm$&  63.46 &   63.62 &$\pm$&  4.15 &   74.94 &$\pm$&  5.07 &  55.48 &$\pm$& 2.95 & 68.01 &$\pm$& 3.86 &   56.93 &$\pm$&   3.37 &\bf48.07 &$\pm$&  2.44 \\
      \addlinespace[0.25em]
      ArmPlan1 & & & & & & & & & & & & & & & & & & & & & \\
      \;\;\emph{total (s)}    &  109.09 &$\pm$&  14.15 &\bf 4.81 &$\pm$&  0.49 &   14.81 &$\pm$&  1.45 &   7.03 &$\pm$& 0.63 &  7.91 &$\pm$& 0.70 & 3375.35 &$\pm$& 319.81 &  496.74 &$\pm$&  8.22 \\
      \;\;\emph{sel-init (s)} &  --\;\; &     &        &  --\;\; &     &       &  --\;\; &     &       & --\;\; &     &      &--\;\; &     &      &  --\;\; &     &        &  489.49 &$\pm$&  8.18 \\
      \;\;\emph{online (s)}   &  109.09 &$\pm$&  14.15 &\bf 4.81 &$\pm$&  0.49 &   14.81 &$\pm$&  1.45 &   7.03 &$\pm$& 0.63 &  7.91 &$\pm$& 0.70 & 3375.35 &$\pm$& 319.81 &    7.25 &$\pm$&  0.66 \\
      \;\;\emph{search (s)}   &    0.02 &$\pm$&   0.00 &    0.02 &$\pm$&  0.00 &    0.03 &$\pm$&  0.00 &   0.02 &$\pm$& 0.00 &  0.02 &$\pm$& 0.00 &    0.02 &$\pm$&   0.00 &    0.04 &$\pm$&  0.00 \\
      \;\;\emph{sel (s)}      &    0.00 &$\pm$&   0.00 &    0.00 &$\pm$&  0.00 &    0.00 &$\pm$&  0.00 &   0.00 &$\pm$& 0.00 &  0.00 &$\pm$& 0.00 & 3358.82 &$\pm$& 318.17 &    1.61 &$\pm$&  0.16 \\
      \;\;\emph{eval (s)}     &  109.07 &$\pm$&  14.15 &    4.78 &$\pm$&  0.49 &   14.77 &$\pm$&  1.44 &   7.01 &$\pm$& 0.63 &  7.88 &$\pm$& 0.70 &   16.47 &$\pm$&   1.68 &    5.59 &$\pm$&  0.51 \\
      \;\;\emph{eval (edges)} &  344.74 &$\pm$&  39.63 &\bf49.72 &$\pm$&  4.25 &   95.58 &$\pm$&  9.67 &  59.44 &$\pm$& 5.06 & 58.90 &$\pm$& 4.74 &   73.72 &$\pm$&   7.63 &\bf50.66 &$\pm$&  4.43 \\
      \addlinespace[0.25em]
      ArmPlan2 & & & & & & & & & & & & & & & & & & & & & \\
      \;\;\emph{total (s)}    &  166.19 &$\pm$&   9.29 &\bf 3.27 &$\pm$&  0.25 &    7.36 &$\pm$&  0.69 &   5.95 &$\pm$& 0.52 &  5.63 &$\pm$& 0.45 & 4758.04 &$\pm$& 407.56 &  495.21 &$\pm$& 12.65 \\
      \;\;\emph{sel-init (s)} &  -    - &     &        &  --\;\; &     &       &  --\;\; &     &       & --\;\; &     &      &--\;\; &     &      &  --\;\; &     &        &  489.22 &$\pm$& 12.64 \\
      \;\;\emph{online (s)}   &  166.19 &$\pm$&   9.29 &\bf 3.27 &$\pm$&  0.25 &    7.36 &$\pm$&  0.69 &   5.95 &$\pm$& 0.52 &  5.63 &$\pm$& 0.45 & 4758.04 &$\pm$& 407.56 &    5.99 &$\pm$&  0.48 \\
      \;\;\emph{search (s)}   &    0.01 &$\pm$&   0.00 &    0.01 &$\pm$&  0.00 &    0.02 &$\pm$&  0.00 &   0.01 &$\pm$& 0.00 &  0.01 &$\pm$& 0.00 &    0.02 &$\pm$&   0.00 &    0.03 &$\pm$&  0.00 \\
      \;\;\emph{sel (s)}      &    0.00 &$\pm$&   0.00 &    0.00 &$\pm$&  0.00 &    0.00 &$\pm$&  0.00 &   0.00 &$\pm$& 0.00 &  0.00 &$\pm$& 0.00 & 4750.16 &$\pm$& 406.98 &    2.03 &$\pm$&  0.22 \\
      \;\;\emph{eval (s)}     &  166.17 &$\pm$&   9.28 &\bf 3.26 &$\pm$&  0.25 &    7.34 &$\pm$&  0.69 &   5.93 &$\pm$& 0.52 &  5.61 &$\pm$& 0.45 &    7.82 &$\pm$&   0.61 &    3.91 &$\pm$&  0.27 \\
      \;\;\emph{eval (edges)} &  657.02 &$\pm$&  29.24 &\bf62.24 &$\pm$&  6.12 &   98.54 &$\pm$& 10.89 &  69.96 &$\pm$& 6.98 & 75.88 &$\pm$& 7.47 &\bf66.24 &$\pm$&   6.36 &\bf62.16 &$\pm$&  6.10 \\
      \addlinespace[0.25em]
      ArmPlan3 & & & & & & & & & & & & & & & & & & & & & \\
      \;\;\emph{total (s)}    &  534.16 &$\pm$&  55.64 &    9.61 &$\pm$&  1.33 &\bf 2.50 &$\pm$&  0.23 &   4.91 &$\pm$& 0.56 &  8.47 &$\pm$& 0.99 & 2073.23 &$\pm$& 198.75 &  497.76 &$\pm$& 10.27 \\
      \;\;\emph{sel-init (s)} &  --\;\; &     &        &  --\;\; &     &       &  --\;\; &     &       & --\;\; &     &      &--\;\; &     &      &  --\;\; &     &        &  493.59 &$\pm$& 10.21 \\
      \;\;\emph{online (s)}   &  534.16 &$\pm$&  55.64 &    9.61 &$\pm$&  1.33 &\bf 2.50 &$\pm$&  0.23 &   4.91 &$\pm$& 0.56 &  8.47 &$\pm$& 0.99 & 2073.23 &$\pm$& 198.75 &    4.17 &$\pm$&  0.43 \\
      \;\;\emph{search (s)}   &    0.02 &$\pm$&   0.01 &    0.02 &$\pm$&  0.00 &    0.02 &$\pm$&  0.00 &   0.02 &$\pm$& 0.00 &  0.02 &$\pm$& 0.00 &    0.03 &$\pm$&   0.01 &    0.04 &$\pm$&  0.00 \\
      \;\;\emph{sel (s)}      &    0.00 &$\pm$&   0.00 &    0.00 &$\pm$&  0.00 &    0.00 &$\pm$&  0.00 &   0.00 &$\pm$& 0.00 &  0.00 &$\pm$& 0.00 & 2069.29 &$\pm$& 198.53 &    0.98 &$\pm$&  0.13 \\
      \;\;\emph{eval (s)}     &  534.10 &$\pm$&  55.63 &    9.58 &$\pm$&  1.33 &    2.48 &$\pm$&  0.23 &   4.89 &$\pm$& 0.56 &  8.44 &$\pm$& 0.99 &    3.90 &$\pm$&   0.31 &    3.15 &$\pm$&  0.32 \\
      \;\;\emph{eval (edges)} & 1845.38 &$\pm$& 195.57 &   78.90 &$\pm$& 10.36 &\bf30.70 &$\pm$&  3.62 &  37.04 &$\pm$& 4.59 & 69.26 &$\pm$& 7.97 &\bf30.82 &$\pm$&   3.60 &\bf31.38 &$\pm$&  3.80 \\
      \addlinespace[0.25em]
      \bottomrule
   \end{tabular}%
   }%
   \caption[Detailed timing results for each selector.
      The actual edge weights for the illustrative
      PartConn and UnitSquare problems were pre-computed,
      and therefore their timings are not included.
      The Partition selector requires initialization of the $Z$-values
      (\ref{eqn:partitionfn}) for the graph using only the estimated
      edge weights.
      Since this is not particular to either the actual edge weights
      (e.g. from the obstacle distribution)
      or the start/goal vertices from a particular instance,
      this initialization (\emph{sel-init}) is considered separately.
      The online running time (\emph{online}) is broken into LazySP's
      three primary steps: the inner search (\emph{search}),
      invoking the edge selector (\emph{sel}),
      and evaluating edges (\emph{eval}).
      We also show the number of edges evaluated.][99in]{x}%
   \label{fig:table-timing-results}%
   \end{widepage}%
   \vspace{0.05in}
   \smallskip\noindent\footnotesize Figure \ref{fig:table-timing-results}:
      Detailed timing results for each selector.
      The actual edge weights for the illustrative
      PartConn and UnitSquare problems were pre-computed,
      and therefore their timings are not included.
      The Partition selector requires initialization of the $Z$-values
      (\ref{eqn:partitionfn}) for the graph using only the estimated
      edge weights.
      Since this is not particular to either the actual edge weights
      (e.g. from the obstacle distribution)
      or the start/goal vertices from a particular instance,
      this initialization (\emph{sel-init}) is considered separately.
      The online running time (\emph{online}) is broken into LazySP's
      three primary steps: the inner search (\emph{search}),
      invoking the edge selector (\emph{sel}),
      and evaluating edges (\emph{eval}).
      We also show the number of edges evaluated.
\end{figure*}

ext: tex


text:
\documentclass[numbers=noenddot, 12pt, a4paper, oneside]{scrbook}
\usepackage{blindtext}
\usepackage[utf8]{inputenc}
\usepackage{float}
\usepackage{tabularx}
\usepackage{graphicx}
\def\Plus{\texttt{+}}
\usepackage{listings}
\usepackage{color}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}

\lstset{frame=tb,
	language=Java,
	aboveskip=3mm,
	belowskip=3mm,
	showstringspaces=false,
	columns=flexible,
	basicstyle={\small\ttfamily},
	numbers=none,
	numberstyle=\tiny\color{gray},
	keywordstyle=\color{blue},
	commentstyle=\color{dkgreen},
	stringstyle=\color{mauve},
	breaklines=false,
	breakatwhitespace=true,
	tabsize=3
}

\begin{document}

\begin{titlepage}
	\centering
	{\scshape\LARGE Politecnico di Milano \par}
	\vspace{1cm}
	\includegraphics[width=0.35\textwidth]{polimi-logo}\par
	\vspace{1cm}

	{\scshape\Large Software Engineering 2 Course\par}
	\vspace{1.5cm}
	{\huge\bfseries Travlendar \Plus \par}
	\vspace{1cm}
	{\Large\bfseries Design Document \par}
	\vspace{3cm}
	{\Large\itshape di\par}
	{\Large\itshape Gianluigi Oliva, Marco Mussi e Lukasz Moskwa\par}
	\vspace{1.5cm}
	Github: https://github.com/Gigioliva/OlivaMussiMoskwa\\
	Heroku: http://travlendarmom.herokuapp.com/
	\vfill

	\vfill

	% Bottom of the page
	{\large \today\par}
\end{titlepage}

\newpage
\tableofcontents
\newpage

\chapter{Introduction}

\section{Purpose}

The purpose of this document is to provide technical details about the information contained in
RASD of Travelandar+ Application and lead the developers that viewing this document can develop the application in the correct way.\\

The output of this document is an architectural description that shows all the critical feature of the
problem taken into account.
In particular in this document will be treated:
\begin{itemize}
	\item The high architectural level;
	\item The design patterns;
	\item The main component and the interface that the application provides;
	\item The runtime behavior;
	\item The data structure used for the developing;
\end{itemize}

The relation among the different models is represented by using UML diagram and other useful
kind of diagram that show the structure of the system (Entity – Relation diagram).

\section{Scope}

The scope of this application (Travlendar \Plus) is provide a tool for the target users to schedule in an effective way their time optimizing the travels.\\

Travlendar+ allows to create a calendar which fits the meetings and other kind of commitments.
The key feature of this application is to determine if the meeting location is reachable in the scheduled time and then provide a fast way to get to the destination, otherwise it notify the user that it is not possibile by any mean to fullfill the request. Furthermore the application also arranges the schedule in a flexible way, taking into account weather condition and user's preferences as well, for some kind of events (like the lunch) and offers the possibility to slightly change its time.\\

With Travlendar+ is possible as well to buy public transport's tickets on the fly for the journey. If the user requires often the same path, he is suggested by the application to buy the best offered subscription.\\

The architecture must be designed with the intent of being maintainable and extensible. For this purpose, we will implement some known design patterns which will facilitate the development of the system.

\section{Definitions, Acronyms, Abbreviations}

\subsection*{Definitions}
\begin{itemize}
	\item \textbf{Platform}: system/application as a whole.
	\item \textbf{User}: An end user who is currently registered to the Travlendar+ application and has credentials to access.
	\item \textbf{Guest}: Person not registered yet and with limited access to features.
	\item \textbf{Event}: A scheduled meeting or other kind of appointment a user has to attend.
	\item \textbf{Journey}: The path chosen by the application as the one with all the fullfilled requirements.
	\item \textbf{Bad Weather}: A weather that prevents the user from choosing some path options. The listed bad weathers are snow, rain, storm and others.
	\item \textbf{Framework}: Reusable set of libraries or classes for a software system.
	\item \textbf{Cross-Platform}: software able to run on different platforms with same code.
	\item \textbf{Port}: in the internet protocol suite, it is an endpoint of communication in operating system
	\item \textbf{Web-Socket}:is a computer communications protocol, providing full-duplex communication channels over a single TCP connection
	\item \textbf{REST}: is a way of providing interoperability between computer systems on the Internet.
	\item \textbf{RESTful}: a system using REST
	\item \textbf{Client Server Architecture}:  is a distributed application structure that partitions tasks or workloads between the providers of a resource or service, called servers, and service requesters, called clients.
	\item \textbf{Client Tier}: is the tier/layer involving the client.
	\item \textbf{Fat Client}: is a client computer in client–server architecture or networks that typically provides rich functionality independent of the central server.
	\item \textbf{Layer}:In a logical multilayered architecture for an information system with an object-oriented design, the main layers are Presentation layer, Application layer and Data access layer.
\end{itemize}

\subsection*{Acronyms}

\begin{itemize}
	\item \textbf{RASD}: Requirements Analysis and Specification Document
	\item \textbf{DB}: Database
	\item \textbf{DBMS}: Database Management System
	\item \textbf{OS}: Operating System
	\item \textbf{HTML}: HyperText Markup Language
	\item \textbf{CSS}: Cascading Style Sheets
	\item \textbf{JS}: JavaScript
	\item \textbf{JSON}: JavaScript Object Notation
	\item \textbf{API}: Application Programming Interface
	\item \textbf{IDE}: Integrated Development Environment
	\item \textbf{RAM}: Random Access Memory
	\item \textbf{HTTP}: HyperText Transfer Protocol
	\item \textbf{HTTPS}: HyperText Transfer Protocol Secure
	\item \textbf{TCP}: Transmission Control Protocol
	\item \textbf{ACID}: Atomicity Consistency Isolation and Durability
	\item \textbf{DD}: Design Document
	\item \textbf{MVC}: Model View Component
	\item \textbf{UX}: User Experience
	\item \textbf{URL}: Uniform Resource Locator
	\item \textbf{OLTP}: On Line Transaction Processing

\end{itemize}

\subsection*{Abbreviations}
\begin{itemize}
	\item \textbf{Gn}: n-th goal
	\item \textbf{Rn}: n-th functional requirement
	\item \textbf{Dn}: n-th domain
	\item \textbf{Mn}: n-th mockup
	\item \textbf{WebApp}: WebApplication
\end{itemize}

\section{Revision History}

Version, date and summary\\

\begin{tabular}{|p{0.2\textwidth}|p{0.3\textwidth}|p{0.4\textwidth}|}
	\hline
	\parbox[c][6ex]{6ex}{\centering \textbf{Version}} & \textbf{Date} & \textbf{Summary}\\
	\hline
	\parbox[c][6ex]{6ex}{\centering 1.0.0} & \today & First release of this document\\
	%	\parbox[c][6ex]{6ex}{\centering \textbf{Goal}} & 2 \\
	\hline

\end{tabular}

\section{Reference Documents}

We used the following documents:
\begin{enumerate}
	\item The orginal Travlendar application: \\
	\textbf{http://score-contest.org/2018/projects/travlendar.php}
	\item The revised document of the assignment:\\
	\textbf{https://goo.gl/9m1ojy}

	\item IEEE Std 830-1998 IEEE Recommended Practice for Software Requirements Specifications.

	\item IEEE Std 1016tm-2009 Standard for Information Tecnology-System Design-Software Design Descriptions.
\end{enumerate}

\section{Document Structure}

\begin{itemize}
	\item \textbf{Introduction}: This section provides a general introduction and overview of the Design Document
	\item \textbf{Architectural Design}: Overall description of the main system component and relationship between them. This part is divided in various subsection in which are show the main component view, deployment view, runtime view, component interface and design patterns.
	\item \textbf{Algorithm Design}: Overall description of the high level details about the most critical part of the algorithms that must be implemented for the system.
	\item \textbf{User Interface Design}: Overview of the way the user can interact with the system and the response of the application to the user input.
	\item \textbf{Requirements Traceability}: Overview of how the design part descripted in this document
	satisfy the functional requirement and the constraints explain the RASD.
	\item \textbf{Implementation, Integration and Test Plan}: Identification of the order we will use to realize the subcomponents of the system and how we will integrate and test them together.
	\item \textbf{Effort Spent}: Time and resource effort during the development of the application.
	\item \textbf{References}: References and software used during the process of creation of the system.
\end{itemize}

\chapter{Architectural Design}

\section{Overview: Highlevel components	and their interaction}

The Travlander+ system has a three tier architecture:

\begin{figure}[H]
	\centering
	\includegraphics[width=0.7\textwidth]{images/HighLevelArchitecture}
	\caption{Graphical description of the High Level Architecture and relationship of the tiers}
\end{figure}

The client has only the presentation layer realized with a dynamic GUI, created due to information retrieved by the server. The communication between client and server happens due to REST calls and JSON response.\\

The second tier contains the application logic layer and the methods for the communication with the Database Server.\\

The third layer stores all the usefull data to the user which allows the system to perform operations and manage separatly different users.

\begin{figure}[H]
	\centering
	\includegraphics[width=0.2\textwidth]{images/ArchitectureLayer}
	\caption{Graphical representation of the position of the firewalls in our network}
\end{figure}

Between all the layers there are firewalls in order to increase the safety of communication and increase the reliability of the overall system.

\subsection*{High level component}

The high level components architecture is composed of four different elements
types. The main element is a singleton, the web server.
Clients communicate only with the web application server and this kind of communication can be performed throught a PC, a mobile device and all devices which allow the execution of JavaScript.\\

When the client has to perform a request, it sends a well formatted JSON string to the web application that will computate it, interacting as well with third part services and with the database if needed to save or to request usefull information, and provide a response.\\

The client and the server communicate using both synchronous messages and asynchronous ones based on the purpose. For example, if the user wants to save some information, a synchronous communication will be done. Otherwise if, for example, a client requires the information of a map (that is retrieved with the Google's API) an asynchronous communication will be done.\\

\begin{figure}[H]
	\centering
	\includegraphics[width=1.1\textwidth]{images/HighLevelComponent}
	\caption{Graphical representation of the High Level components}
\end{figure}

\section{Component View}

In this section we will explain in detail all the major sub-part of the system and the way they interact each other.

\subsection*{DBMS Server}

Into the database server we want to use a relational DBMS component, like MySQL, to manage the interaction with the database. In that way we can guarantee the ACID properties of the transactions executed.\\

As seen in the previous schema (Fig 2.2) the DBMS server can communicate only with the Application server through a firewall. Sensible data such as passwords and personal information must be encrypted properly before being stored. Users must be granted access only upon provision of correct and valid credentials.\\

The DBMS will use a high level schema like the one represented in the following Entity-Relationship diagram.\\

The main components of the DBMS server are:
\begin{itemize}
	\item \textbf{DBMS}:\\\newline
	This component deals with the operations of read and write of the data stored into the Database. It's implemented as OLTP, which is used to refer to processing in which the system responds immediately to user requests.\\

	\item \textbf{DBRequestHandler}:\\\newline
	This module converts requests from the Application Server into SQL queries which are executed by the DBMS.\\

\end{itemize}

\begin{figure}[H]
	\centering
	\includegraphics[width=1.1\textwidth]{images/ER}
	\caption{E-R Diagram of the DBMS}
\end{figure}

\subsection*{Application and Web Server}

For our purpose we decided to merge together the Application and Web server. This choice is based on the three-tier architecture model. The Application server is the middle-tier which implements the business logic of the WebApp. It also uses a Script Engine mechanism to provide dynamic real-time contents to the users.\\

In this layer we can also find a Web Server which is the component that handles the requests from the clients. These requests are based both on HTTP standard protocol and on the Web-Socket protocol. Once the page request is completed, a connection is estabilished with the Web-Socket protocol in order to have a full-duplex communication and refresh the web page content without reloading the whole page.\\

The system must also provide a way to communicate with external systems with the purpose of collecting important data and information which will allow the correct execution of operations.\\

The main components are:
\begin{itemize}
	\item \textbf{UserManager}:\\\newline
	This module will manage all the sensitive information about the users. It will also allow the users to see and modify them when requested. It mananages as well the Login and Registration procedures.\\

	\item \textbf{ScheduleManager}:\\\newline
	This module contains the business and application logic that performs the computation of the best travel path and also verifies the schedule can fit in the user's timetable. In order to provide the best journey path, this module takes into account the weather forecast as well through the ExternalRequestManager.\\

	\item \textbf{ExternalRequestManager}:\\\newline
	This module handles all the communications with third part services and retrives from them important information which will be passed to other system's modules. \\

	\item \textbf{PaymentHandler}:\\\newline
	This module deals with all the procedures necessary to perform a payment. This occurs every time a user wants to purchase a ticket or a subscription for a specific journey in his schedule. In some cases, with third part services like car sharing or bike sharing, this module redirects those information directly to the required service page.\\

	\item \textbf{SecurityAuthenticator}:\\\newline
	This module manages all the security policies in order to prevent fraudulent accesses and guarantee the privacy of the users. It also provide a secure way to connect to the web application using a token-based mechanism in a Web-Socket context. \\

	\item \textbf{NotificationManager}:\\\newline
	The Notification Manager purpose is to handle all the notifications to the user and communicate them even when the application is closed or in background. It also report the information on different priority levels.\\

	\item \textbf{RequestController}:\\\newline
	This module has the task of managing all the user's requests and handle them to the proper system modules in order to fullfill their queries.\\

	\item \textbf{DataHandler}:\\\newline
	This module allows the exchange of data and information between the Application/WebServer and the Database Server. While the communication between the Client and the Web Application is made through a HTTPS standard protocol to ensure the connection safety, the communication between the Application Server and the Database is realized with HTTP. In fact, the firewall is configured to deny all the possible connections coming from sources different than the WebApp.\\

\end{itemize}

\subsection*{Client}

The client in our model architecture is a Thin Client, as the whole business logic and calculations are made on the Application Server side. Therefore the client realizes only the Presentation Layer.\\

The Client side is meant for the mobile and desktop users and, in order to access to all the system features, it has to have implemented necessary methods to retrieve information from its GPS hardware component.\\

The client's main components are:

\begin{itemize}

	\item \textbf{PositionController}:\\\newline
	This module takes into account the position of the used device when the ApplicationController needs it. The user is asked either to insert manually his position or grant to the device the permission of using GPS position data.\\

	\item \textbf{UIManager}:\\\newline
	This module is used to manage all the contents displayed to the user in a certain page he visits. It takes data from the ApplicationController and show them. It is also responsible for the handling of user's input and form fullfilling.\\

	\item \textbf{NotificationMonitor}:\\\newline
	This software component has the purpose of listen the Application server notifications and display them immediatly or, if expected, store them for a while and then display them when scheduled.\\

	\item \textbf{ApplicationController}:\\\newline
	This module acts as core of our client implementation. It contains the client's logic and allows an efficent communication between modules listed above.\\

	This software component deals with all the user's request and forward them through a specific protocol in a public network to the Application Server.
	It also handles the retrived data received as responses from the Server side, and send them to the ApplicationController to be shown.\\

\end{itemize}

\begin{figure}[H]
	\centering
	\includegraphics[width=0.95\textwidth]{images/ComponentView}
	\caption{Component View of the System}
\end{figure}

\section{Deployment View}

\begin{figure}[H]
	\centering
	\includegraphics[width=0.80\textwidth]{images/DeploymentView}
	\caption{Deployment View of the system}
\end{figure}

\section{Runtime View}

This section represents the dynamic behaviour of the system in the most
relevant and already seen cases. The purpose of each of the following sequence diagrams is to explain as much as possibile in the detail, the workflow inside the Application Server and its communication with the Client and the Database Server.

\subsection*{Registration to Travlendar+ application}

\begin{figure}[H]
	\centering
	\includegraphics[width=1.1\textwidth,angle=-0]{images/Goal1}
	\caption{Sequence Diagram of the guest's registration to the application}
\end{figure}

As we can see in this Diagram, the guest can send a Serialized Form from the Application Controller module to the Request Controller, which will entrust the Data Handler of making a request to the Database Sever in order to know if a user with same data already exists.\\

If not, the guest is added to the Database server and is sent an e-mail for account verification. Otherwise, the guest is notified that someone with the same data already exists.

\subsection*{Schedule Creation}

\begin{figure}[H]
	\centering
	\includegraphics[width=1.1\textwidth,angle=-0]{images/Goal2}
	\caption{Sequence Diagram of the schedule creation}
\end{figure}

In this diagram is possible to see how the components interact between them in order to create a new schedule. Once the request reaches the Application server, several control are made and the External Request Manager grants information about the Weather and path to be chosen.

\subsection*{Manage User's information}

\begin{figure}[H]
	\centering
	\includegraphics[width=1.1\textwidth,angle=-0]{images/Goal3}
	\caption{Sequence Diagram of the managing of users' information}
\end{figure}

In this diagram it is possible to see how the Data Handler module deals with a request of the user to modify his data and preferences. All the changes are stored in the DB Server.

\subsection*{Retrieve Weather Forecast information}

\begin{figure}[H]
	\centering
	\includegraphics[width=1.1\textwidth,angle=-0]{images/Goal4}
	\caption{Sequence Diagram of the retrieving of Weather Forecast information}
\end{figure}

Both the guests and users can actually retrieve information about the Weather Forecast. This is done by the External Request Manager that collect data from the Openweather external API. Then these information are sent to the Notification Manager module.

\subsection*{Buy tickets and subscription for public transport}

\begin{figure}[H]
	\centering
	\includegraphics[width=1.1\textwidth,angle=-0]{images/Goal5}
	\caption{Sequence Diagram of the purchase of tickets and subscription for public transport}
\end{figure}

Here we can observe the procedure that deals with the purchase of tickets by the user. If the transaction done due to the Payment Handler goes well, the information about the bought ticket are saved to the Database Server using the submitQuery method.

\subsection*{Share user's schedule}

\begin{figure}[H]
	\centering
	\includegraphics[width=1.1\textwidth,angle=-0]{images/Goal6}
	\caption{Sequence Diagram of sharing user's schedule}
\end{figure}

Whenever a user wants to share his own schedule of a given day of his choice, the username of the second user is saved to the Database Server. Then the first user is notified by the Notification Manager.

\subsection*{Update user's schedule}

\begin{figure}[H]
	\centering
	\includegraphics[width=1.1\textwidth,angle=-0]{images/Goal7}
	\caption{Sequence Diagram of updating user's schedule}
\end{figure}

As the preferences of every user are stored in the Database Server, whenever they want to change them the Data Handler's method submitQuery is called. Then the modifications are saved and updated immediatly in the DB server.

\subsection*{Manage user's preference about time for break}

\begin{figure}[H]
	\centering
	\includegraphics[width=1.1\textwidth,angle=-0]{images/Goal8}
	\caption{Sequence Diagram of managing user's preference about time for break}
\end{figure}

If a user decides to modify his break preferences, they are modified for all the upcoming schedules he decides to create. Already created schedules are not modified.

\subsection*{User wants to see a schedule for specified day}

\begin{figure}[H]
	\centering
	\includegraphics[width=1.1\textwidth,angle=-0]{images/Goal9}
	\caption{Sequence Diagram of a user wants to see a schedule for specified day}
\end{figure}

If a user decides to see a schedule of his, he has just to insert the data of the day and thus it will be passed to the Application Controller. Then, after a query is successfully executed passing from the Request Controller and Data Handler, the result is shown to the user by the UI Manager.

\subsection*{Other considerations}

In all the diagrams above the procedure which check the correctness of the token and the one that explain the submitQuery method to the Database server where deliberately omitted. The reason is mainly redundancy and thus they are explained in the following diagrams.\\

\subsection*{Check token procedure}

\begin{figure}[H]
	\centering
	\includegraphics[width=1.1\textwidth,angle=-0]{images/checkToken}
	\caption{The procedure of checking the token}
\end{figure}

This particular procedure is called every time the user makes a request to the server. The validity of the token is then increased to permit the user an easy flow in browsing contents.

\subsection*{Query DBMS procedure}

\begin{figure}[H]
	\centering
	\includegraphics[width=0.7\textwidth,angle=-0]{images/QueryDBMS}
	\caption{The procedure of sending a query to the DBMS}
\end{figure}

\subsection*{Login procedure}

\begin{figure}[H]
	\centering
	\includegraphics[width=1\textwidth,angle=-0]{images/Login}
	\caption{The procedure of logging in}
\end{figure}

\section{Component Interfaces}

This sections includes further details on the interfaces between different components of the system.

\subsection*{Component Interface of the client}

\begin{figure}[H]
	\centering
	\includegraphics[width=1\textwidth]{images/ClientInterface}
	\caption{Component Interface of the client}
\end{figure}

\subsection*{Component Interface of the Application \& Web Server}

\begin{figure}[H]
	\centering
	\includegraphics[width=1\textwidth]{images/ApplicationInterface}
	\caption{Component Interface of the Application \& Web Server}
\end{figure}

\subsection*{Component Interface of the Database Server}

\begin{figure}[H]
	\centering
	\includegraphics[width=1\textwidth]{images/DatabaseInterface}
	\caption{Component Interface of the Database Server}
\end{figure}

\section{Selected Architectural styles and patterns}

We decided to use a three-tier architecture. The client will be represented by the application installed on the device of the user or his web browser, which only contains the presentation layer. Therefore it is a so called Thin-Client.\\

On the other hand, the server is represented by a mainframe which computate all the business logic and computation to fullfill the users' requests. The reason behind this choice are the willing of keeping thin the client to improve the user experience and the reserved channel on which communicate the Application server and the Database server. As there is only this single channel, we can guarantee the confidentiality and privacy of the users. \\

Here are listed the main pattern we chose to implement:
\begin{itemize}
	\item \textbf{Model View Controller}:\\\newline
	The model role is covered by the Data center which mantains the data related to the users. The controller instead is covered by the Application \& Web Server which manage the events handling with both Model and View. Finally, the View is covered by the Client Application which displays data and information in a way that is possibile to interact with them due to a User Interface.\\

	\item \textbf{Proxy}:\\\newline
	On the Application side we keep a copy of the tokens which allow the user to correctly login. In this way it is not necessary to request every time the database server in order to know if a user is currently logged in or not. Therefore we can actually even double check if a user is really connected with a random control over time.\\

	\item \textbf{Singleton}:\\\newline
	The Application Server's module RequestController is a Singleton, as it is istatiated only once and handle all the possibile request by different users.\\

\end{itemize}

\section{Other design decisions}

We decided to display on the client side a map which displays the journey the user is willing to do. In order to achive this, we decided to use the Google Maps API.\\

For the Weather Forecast instead we decided to requests information to the OpenWeather API. In this way we can also display data about the forecast whenever the users' request them.\\

To keep stored the session of any current user, we decide to implement the login procedure based on a token-exhange and verification. Therefore is possibile to keep alive a session up to an estabilished time (for example 5 min) and refresh it whenever a correct HTTP GET is performed.\\

To ease the developement of a cross platform application, we decided to use Phonegap (https://phonegap.com/), which allows the creation of different kind of native applications starting from a WebApp. In that way it is possible to use it from iOS, Android and Windows Phone and from Desktop browsers

\chapter{Algorithm Design}

In this section we will explain the algorithms that concern the critical part of the implementation on the system.

\subsection*{Creation of a Journey/Event}

The algorithm used for the creation of a journey has to take into account every aspect of a user profile. It has to follow these steps:\\
\begin{enumerate}
	\item Consider the schedule of a chosen by user day
	\item Take information about the Weather Forecast
	\item Take the user's preferences about the means of transport
	\item Retrieve the information about the best path to take from Google Maps API
	\item Verify that the combination of created Event and Journey in the Schedule does not overlap with another currently existing Event or Journey
	\item Verify that there is always possibile to have an Event of type Break in the current Schedule
	\item If the previous control is satisfied we can save the update Schedule into the Database Server
	\item Else, the Application server notifies the user that something went wrong
\end{enumerate}

\subsection*{Token Creation}

This is an example of a piece of code which can be used to apply the algorithm.

\begin{lstlisting}
	/**
	* Generate a random string.
	*/
	public String nextString() {
		for (int idx = 0; idx < buf.length; ++idx)
			buf[idx] = symbols[random.nextInt(symbols.length)];
			return new String(buf);
	}

	public static final String special = "!%&/=#@";

	public static final String upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

	public static final String lower = upper.toLowerCase(Locale.ROOT);

	public static final String digits = "0123456789";

	public static final String alphanum = upper + lower + digits;

	private final Random random;

	private final char[] symbols;

	private final char[] buf;

	public RandomString(int length, Random random, String symbols) {
		if (length < 1) throw new IllegalArgumentException();
			if (symbols.length() < 2) throw new IllegalArgumentException();
			this.random = Objects.requireNonNull(random);
			this.symbols = symbols.toCharArray();
			this.buf = new char[length];
	}

	/**
	* Create an alphanumeric string generator.
	*/
	public RandomString(int length, Random random) {
		this(length, random, alphanum);
	}

	/**
	* Create an alphanumeric strings from a secure generator.
	*/
	public RandomString(int length) {
		this(length, new SecureRandom());
	}

	/**
	* Create session identifiers.
	*/
	public RandomString() {
		this(21);
	}
\end{lstlisting}

\subsection*{User Registration}

This is an example of a piece of code which can be used to apply the algorithm.

\begin{lstlisting}
	public void register(HashMap<String, String> newUser) {
		try {
			PreparedStatement prepared = connection
			.prepareStatement("insert into User (Surname, Name, Age, Email) values (?,?,?,?)");
			prepared.setString(1, newUser.get("Surname"));
			prepared.setString(2, newUser.get("Name"));
			prepared.setString(3, newUser.get("Age"));
			prepared.setString(4, newUser.get("Email"));
			prepared.executeUpdate();
		} catch (SQLException e) {
			e.printStackTrace();
		} finally {
		try {
			if (connection != null)
				connection.close();
			} catch (SQLException e) {
				e.printStackTrace();
			}
		}
	}
\end{lstlisting}

\subsection*{Payment}

In order to perform the purchase requested by the user, the system has to follow these steps:

\begin{enumerate}
	\item Consider the mean of transport found in the event
	\item Allow the user to choose the ticket or subscription referred to the mean of transport of his choice
	\item Consider the credit card data of the user
	\item Send the purchase information to third part services like PayPal
	\item If the purchase ends well, save the receipt of the ticket and add it to the stored ticket of the user in the Database Server
	\item Else, the system notifies the user that something went wrong with the transaction
\end{enumerate}

\chapter{User Interface Design}

\subsection*{UX Diagram}

The purpose of the UX diagram is to show the different screen provided by the user interface. Moreover it points out the interactions among the screens themselves and the presence of input form and required data in a specific screen.\\

The diagram provided below follow the User Interface requirements stated in the RASD. The Web and the Mobile application implement the same  functionalities and the same screen.

\begin{figure}[H]
	\centering
	\includegraphics[width=0.9\textwidth]{images/UXDiagram2}
	\caption{Component Interface of the Database Server}
\end{figure}

\chapter{Requirements Traceability}

In this section we create a bridge between the functional and not functional requirements defined before in the RASD with the sections in the DD.\\

\begin{tabular}{|c|p{0.7\textwidth}|}
	\hline
	\parbox[c][4ex]{20ex}{\textbf{DD Component}} & \textbf{Functional Requirements}\\
	\hline
	\parbox[c][14ex]{20ex} {Request Controller} & Register, Create Schedule, Data Management, Weather Forecast, Buy Ticket, Share Schedule, Update Schedule, Manage Break, Journey Infos\\[2ex]
	\hline
	\parbox[c][14ex]{14ex} {Data Handler}&Register, Create Schedule, Data Management, Buy Ticket, Share Schedule, Update Schedule, Manage Break, Journey Infos\\[2ex]
	\hline
	\parbox[c][14ex]{18ex} {Schedule Manager}&Create Schedule, Buy Ticket, Update Schedulet\\
	\hline
	\parbox[c][14ex]{18ex} {Payment Handler}&Buy Ticket\\
	\hline
	\parbox[c][14ex]{18ex} {External Request Manager}&Create Schedule, Weather Forecast, Update Schedule\\
	\hline
	\parbox[c][14ex]{18ex} {User Manager}& Login\\
	\hline
\end{tabular}
\newpage
\begin{tabular}{|c|p{0.7\textwidth}|}
	\hline
	\parbox[c][4ex]{20ex}{\textbf{DD Component}} & \textbf{Functional Requirements}\\
	\hline
	\parbox[c][14ex]{16ex} {Notification Manager} &Register, Create Schedule, Data Management, Weather Forecast, Buy Ticket, Share Schedule, Update Schedule, Manage Break\\[2ex]
	\hline
	\parbox[c][14ex]{16ex} {Application Controller}&Register, Create Schedule, Data Management, Weather Forecast, Buy Ticket, Share Schedule, Update Schedule, Manage Break, Journey Infos\\[2ex]
	\hline
	\parbox[c][14ex]{16ex} {UI Manager}&Register, Create Schedule, Data Management, Weather Forecast, Buy Ticket, Share Schedule, Update Schedule, Manage Break, Journey Infos\\[2ex]
	\hline
	\parbox[c][14ex]{16ex} {Notification Monitor}&Register, Create Schedule, Data Management, Buy Ticket, Share Schedule, Update Schedule, Manage Break\\
	\hline
\end{tabular}
\newpage
\begin{tabular}{|c|p{0.7\textwidth}|}
	\hline
	\parbox[c][6ex]{20ex}{\textbf{RASD Requirements}} & \textbf{DD Section}\\
	\hline
	\parbox[c][14ex]{16ex} {Security} & Highlevel components and their Interaction\\[2ex]
	\hline
	\parbox[c][14ex]{16ex} {Parallel Operation}& Client Server Architecture\\[2ex]
	\hline
	\parbox[c][14ex]{16ex} {Maintainability}& Selected Architectural styles and patterns\\[2ex]
	\hline
	\parbox[c][14ex]{16ex} {Portability}& Other design decisions\\
	\hline
\end{tabular}

\chapter{Implementation,Integration and Test Plan}

Once we defined the whole software and hardware architecture, the next step is the Implementation and Testing. During the testing phase we have to cover a certain amount of code:
\begin{itemize}
	\item \textbf{100\%} of the DBMS Server's components
	\item \textbf{80\%} for the Web \& Application Server's component
	\item \textbf{50\%} for the Client's component
\end{itemize}
We want to approach the Integration phase with a \textbf{bottom-up} paradigm, which starts with the developement of minor modules. Then we extend the modules integrating them each other.\\

Meanwhile we realize the presentation layer and data layer as they are separated each other, so can be developed in parallel. Therefore we implement on the server side:
\begin{enumerate}
	\item Data Handler
	\item User Manager and Security Authenticator
	\item Payment Handler and External Request Manager
	\item Schedule Manager
	\item Request Controller and Notification Manager
\end{enumerate}

Done that, we must create the Application Controller for the Client. Once completed, it is finally possible to integrate the single components together like shown in the following schemas:

\begin{figure}[H]
	\centering
	\includegraphics[width=1\textwidth,angle=-0]{images/impleServer1}
	\caption{Integration of the Request Controller with the User Handler}
\end{figure}

\begin{figure}[H]
	\centering
	\includegraphics[width=0.7\textwidth,angle=-0]{images/impleServer2}
	\caption{Integration of the Request Controller with the Data Handler}
\end{figure}

\begin{figure}[H]
	\centering
	\includegraphics[width=0.7\textwidth,angle=-0]{images/impleServer3}
	\caption{Integration of the Schedule Manager with Third Part Services}
\end{figure}

\begin{figure}[H]
	\centering
	\includegraphics[width=0.7\textwidth,angle=-0]{images/impleServer4}
	\caption{Integration of the Schedule Manager with the Request Controller}
\end{figure}

Once we integrate all these components, we can let them communicate in order to make the application work. Then, as in the scheme down here, we implement all the Client's modules.

\begin{figure}[H]
	\centering
	\includegraphics[width=0.7\textwidth,angle=-0]{images/implClient}
	\caption{Integration of the various components of the client}
\end{figure}

When all those implementations are done, it is effectively possibile to try and test the system as a whole.

\chapter{Effort Spent}

While working on the project, we always met to discuss main topics to provide more consistence to the project:\\

\begin{tabular}{|p{0.2\textwidth}|p{0.8\textwidth}|}
	\hline
	\parbox[c][6ex]{6ex}{\centering \textbf{Name}} & \textbf{Effort}
	\\
	\hline
	\parbox[c][8ex]{6ex}{\centering Lukasz Moskwa} & Group 30h and 5h alone\\
	\hline
	\parbox[c][8ex]{6ex}{\centering Marco Mussi} & Group 30h and 5h alone\\
	\hline
	\parbox[c][8ex]{6ex}{\centering Gianluigi Oliva} & Group 30h and 5h alone \\
	\hline

\end{tabular}

\chapter{References}

\begin{itemize}
	\item The orginal Travlendar application: \\
	\textbf{http://score-contest.org/2018/projects/travlendar.php}
	\item The revised document of the assignment:\\
	\textbf{https://goo.gl/9m1ojy}
	\item IEEE Std 830-1998 IEEE Recommended Practice for Software Requirements Specifications.
	\item IEEE Std 1016tm-2009 Standard for Information Tecnology-System Design-Software Design Descriptions.
	\item Phonegap: \\
	https://phonegap.com/
\end{itemize}

\end{document}

max_stars_repo_name: marcomussi/Travlandar

max_issues_repo_name: marcomussi/Travlandar

max_forks_repo_name: marcomussi/Travlandar


text:
%!TEX TS-program = lualatex
%!TEX encoding = UTF-8 Unicode

\documentclass[12pt]{exam}

%\printanswers

\usepackage{graphicx}
	\graphicspath{{/Users/goby/Pictures/teach/163/lab/}
	{img/}} % set of paths to search for images

\usepackage{geometry}
\geometry{letterpaper, left=1.5in, bottom=1in}
%\geometry{landscape}                % Activate for for rotated page geometry
\usepackage[parfill]{parskip}    % Activate to begin paragraphs with an empty line rather than an indent
\usepackage{amssymb, amsmath}
\usepackage{mathtools}
	\everymath{\displaystyle}

\usepackage[table]{xcolor}

\usepackage{fontspec}
\setmainfont[Ligatures={TeX}, BoldFont={* Bold}, ItalicFont={* Italic}, BoldItalicFont={* BoldItalic}, Numbers={OldStyle}]{Linux Libertine O}
\setsansfont[Scale=MatchLowercase,Ligatures=TeX]{Linux Biolinum O}
\setmonofont[Scale=MatchLowercase]{Inconsolatazi4}
\newfontfamily{\tablenumbers}[Numbers={Monospaced,Lining}]{Linux Libertine O}
\usepackage{microtype}

\usepackage{unicode-math}
\setmathfont[Scale=MatchLowercase]{TeX Gyre Termes Math}

\usepackage{amsbsy}
%\usepackage{bm}

% To define fonts for particular uses within a document. For example,
% This sets the Libertine font to use tabular number format for tables.
 %\newfontfamily{\tablenumbers}[Numbers={Monospaced}]{Linux Libertine O}
% \newfontfamily{\libertinedisplay}{Linux Libertine Display O}

\usepackage{multicol}
%\usepackage[normalem]{ulem}

\usepackage{longtable}
\usepackage{caption}
	\captionsetup{format=plain, justification=raggedright, singlelinecheck=off,labelsep=period,skip=3pt} % Removes colon following figure / table number.
%\usepackage{siunitx}
\usepackage{booktabs}
\usepackage{array}
\newcolumntype{L}[1]{>{\raggedright\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\newcolumntype{R}[1]{>{\raggedleft\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}

\usepackage{enumitem}
\setlist{leftmargin=*}
\setlist[1]{labelindent=\parindent}
\setlist[enumerate]{label=\textsc{\alph*}.}
\setlist[itemize]{label=\color{gray}\textbullet}
%\usepackage{hyperref}
%\usepackage{placeins} %PRovides \FloatBarrier to flush all floats before a certain point.
%\usepackage{hanging}

\usepackage[sc]{titlesec}

%% Commands for Exam class
\renewcommand{\solutiontitle}{\noindent}
\unframedsolutions
\SolutionEmphasis{\bfseries}

\renewcommand{\questionshook}{%
	\setlength{\leftmargin}{-\leftskip}%
}

%Change \half command from 1/2 to .5
\renewcommand*\half{.5}

\pagestyle{headandfoot}
\firstpageheader{\textsc{bi}\,163 Evolution and Ecology}{}{\ifprintanswers\textbf{KEY}\else Name: \enspace \makebox[2.5in]{\hrulefill}\fi}
\runningheader{}{}{\footnotesize{pg. \thepage}}
\footer{}{}{}
\runningheadrule

\newcommand*\AnswerBox[2]{%
    \parbox[t][#1]{0.92\textwidth}{%
    \begin{solution}#2\end{solution}}
%    \vspace*{\stretch{1}}
}

\newenvironment{AnswerPage}[1]
    {\begin{minipage}[t][#1]{0.92\textwidth}%
    \begin{solution}}
    {\end{solution}\end{minipage}
    \vspace*{\stretch{1}}}

\newlength{\basespace}
\setlength{\basespace}{5\baselineskip}

%% To hide and show points
\newcommand{\hidepoints}{%
	\pointsinmargin\pointformat{}
}

\newcommand{\showpoints}{%
	\nopointsinmargin\pointformat{(\thepoints)}
}

\newcommand{\bumppoints}[1]{%
	\addtocounter{numpoints}{#1}
}

\newcommand*\meanY{\overline{Y\kern1.67pt}\kern-1.67pt}
\newcommand*\meansubY{\overline{Y}}
%\newcommand*\meanY{\overline{Y}}
\newcommand*\ttest{\emph{t}-test}
\newcommand*\Popa{Population~\textsc{a}}
\newcommand*\Popb{Population~\textsc{b}}
\newcommand*\popa{population~\textsc{a}} %lower case
\newcommand*\popb{population~\textsc{b}} %lower case
\newcommand*\Corbicula{\textit{Corbicula}}
\newcommand*\AnswerBlank{\rule{0.75in}{0.4pt}\kern0.67pt.}
%
%\makeatletter
%\def\SetTotalwidth{\advance\linewidth by \@totalleftmargin
%\@totalleftmargin=0pt}
%\makeatother

\begin{document}

\subsection*{Hardy-Weinberg Practice Problems}

Problems 1, 2, and 7 adapted from Hartl and Clark, \textit{Principles of Population Genetics}, Third Edition. Other word problems by Dr. Jennifer Weber.

\subsubsection*{Review}

Remember that HW frequencies refer to a population level trait.

$p$ = the frequency of one allele (i.e., frequency of \emph{all} “A” alleles in a population), \\
$q$ = the frequency of another allele (i.e., frequency of \emph{all} “a” alleles in a population),\\
When there are only two alleles for a genotype, $p + q = 1$ (i.e., all of the alleles: $A + a = 1$).

$p^2 =$ the frequency of the homozygous individuals of one allele (i.e., $AA$), \\
$2pq =$ the frequency of the heterozygotes individuals (i.e., $Aa$), \\
$q^2 =$ the frequency of the homozygous individuals of another allele (i.e., $aa$).

With only two alleles for a genotype $p^2 +2pq + q^2 = 1$ (i.e., $AA + Aa + aa = 1$).

Individuals that are heterozygous are said to be “carriers” of a recessive trait, because they can pass it on without expressing that allele (because the dominant allele of the heterozygote is expressed instead).

\textsc{Hint:} Notice if you are given $p$ or $q$ versus when you are given $p^2$ or $q^2$!

\subsubsection*{Practice Problems}

\begin{questions}

\question
The allele frequencies in a population were estimated as $p = 0.87$ and $q = 0.13$,
for the wild type ($+$) and $Δ32$ allele, respectively. What will be the genotype
frequencies in the next generation for $+$/$+$, $+/Δ32$, and $Δ32/Δ32$?
($+$ is just an allele, like any other allele. You can use $A$ and $a$, if you want.)

\AnswerBox{2\baselineskip}{$+/+ = 0.757,$ \quad $+/Δ32 = 0.226,$ \quad $Δ32/Δ32 = 0.17.$}

\question
The $BanI$ site can either be present or absent in a chromosome of \textit{Drosophila melanogaster}.
Let $B$ represent the presence of $BanI$ with a frequency of $p = 0.48$ and let $b$
represent the absence of $BanI.$ Assuming Hardy-Weinberg, calculate the expected frequencies of the genotypes $BB,$ $Bb,$ and $bb$ in the next generation.

\AnswerBox{2\baselineskip}{$BB = 0.230,$ \quad $Bb = 0.500,$ \quad $bb = 0.270.$}

\question
In the $Ss$ blood group, three phenotypes corresponding to the genotypes $SS$, $Ss$
and $ss$ can be identified. Among 1000 British people the observed number of each
genotype for the $Ss$ blood groups were 99 $SS$, 418 $Ss$ and 483 $ss$.  Estimate
the allele frequencies of $S$ and $s$.  Do these deviate from Hardy-Weinberg equilibrium?

\AnswerBox{2\baselineskip}{$S = 0.308$ \quad $s = 0.692$; The population is not in equilibrium.}

\question
A deleterious, recessive allele is present in a population at a frequency of 0.06.
Assuming \textsc{hwe}, estimate the percentage of heterozygote “carriers” of the allele
in the population.

\AnswerBox{2\baselineskip}{Carriers: $2pq = 0.113$ or 11.3\% of the population.}

\question
In frogs, a recessive allele $g$ causes a debilitating disease that can decrease muscle strength.  Since the allele is recessive, it is only expressed when homozygous.  In a population of frogs, 5\% of the individuals in the population suffer from the disease.  Estimate the percentage of heterozygote “carriers” of the allele in the population.

\AnswerBox{2\baselineskip}{Carriers: $Gg = 0.347.$}

\question
In unicorns, geneticists have found that horn coloration is controlled by a gene with two alleles ($U$ and $u$). $UU$ individuals have purple horns; $Uu$ individuals have white horns and $uu$ individuals have rainbow colored horns.  If 70\% of unicorns have purple horns and 10\% of rainbow horns, what is the frequency of $U$ allele? (Pretend that unicorns are real. Pretend that geneticists that study unicorns are also real.)

\AnswerBox{4\baselineskip}{$U = 0.8.$; This population is not in equilibrium so you cannot take the square root of $0.70.$ To convince yourself, add together the square roots of 0.70 (\textit{UU}) and 0.10 (\textit{uu}).}

\question
 In one study of a heavily polluted area near Birmingham, England, Kettlewell (1956) observed a frequency of 87\% melanic \textit{Biston beularia}. Estimate the frequency of the dominant allele (the dark allele) leading to melanism in the population and the \emph{frequency of melanics} that are heterozygous.\textsc{Hint: dark moths can be $DD$ or $Dd$.}

\AnswerBox{2\baselineskip}{$D = 0.639$ \quad $Dd = 0.461$. Therefore, of the 87\% that are melanic, $0.461/0.87 = 0.53$ or 53\% are heterozygous.}

\end{questions}

\end{document}


text:
\documentclass[10pt,a4paper,twocolumn]{article}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{pgfplots}
\usepackage{algorithm,algorithmic}
\author{Alexandre \textsc{Barachant} -- alexandre.barachant@gmail.com}
\title{\textsc{Covariance toolbox documentation}}

\newcommand{\argmax}{\operatornamewithlimits{argmax}}
\newcommand{\argmin}{\operatornamewithlimits{argmin}}
\newcommand{\R}{\mathbb{R}}

\begin{document}
\maketitle
\begin{abstract}

\end{abstract}
\section{Introduction}

\end{document}


text:
\documentclass[12pt]{article}
\usepackage[noanswer]{exercise}
\usepackage[]{amsthm}
\usepackage[]{amsmath}
\usepackage[]{enumitem}
\usepackage[]{hyperref}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}

\theoremstyle{definition}
\newtheorem{definition}{Definition}

\let\set\mathbf

% I don't like how the "exercise" package normally lays things out.
% Feel free to copy this if you agree.
\renewcommand{\ExerciseHeader}{\noindent\textbf{\ExerciseName\ \ExerciseHeaderNB}\ \ExerciseHeaderTitle\ \ExerciseHeaderOrigin\smallskip}
\renewcommand{\ExerciseHeaderOrigin}{(\ExerciseOrigin)}
\renewcommand{\AnswerHeader}{\bigskip\noindent\textbf{Solution \ExerciseHeaderNB}\newline}

\title{Workshop Notes}
\author{Robert Dougherty-Bliss}
\date{27 January 2021}

\begin{document}

\maketitle

% Adding the * gets rid of the section numbering.
\section*{Logistics}%
\label{sec:logistics}

Nothing to say here.

\section*{New stuff}%
\label{sec:new_stuff}

This week you learned about about the real numbers. You already knew most of
the algebraic structure of the reals (addition, multiplication, inequalities,
etc.), but the real kicker is the \emph{completeness axiom}.

% There's a "\ " after \sup because \sup(0, 1) looks weird.
% Normally you would just do \sup S for a set S, with no "\ ".
% The "\ " adds a little bit of space.
Consider the set $(0, 1)$ of all reals between $0$ and $1$. Note that $x \leq
2$ for every $x \in (0, 1)$. That is, $2$ is an \emph{upper bound} for $(0,
1)$. There are many such upper bounds: $1 + 1/2$, and $1 + 1/3$, and $1
+ 1/999999999$, and so on. The completeness axiom tells us that there is a
\emph{least} one, i.e., an upper bound which we cannot ``improve'' by making it
smaller. We call this least upper bound the \emph{supremum} of $(0, 1)$, and
denote it $\sup\ (0, 1)$. Here, $\sup\ (0, 1) = 1$.

The axiom of completeness is silly for $(0, 1)$---obviously the least upper
bound exists in this case---but it is \emph{crucial} in cases where the least
upper bound is not obvious. I don't want to spoil Professor Coley's thunder, so
I'll just say that the completeness axiom is the most important property of the
reals.

The axiom is also a good philosophical example of \emph{infinity}. If there
were only finitely many upper bounds of $(0, 1)$, then we could go through the
list and pick the smallest. Since there are infinitely many we can't do this
``by hand,'' but the axiom says that we can do it abstractly. Trying to pick
the smallest element of an infinite set is a recurring problem throughout
analysis.

Now I'm going to open the floor to questions and discussion from everyone. If
discussion flows, perfect. Otherwise, I selected a few exercises.

\begin{Exercise}
    \begin{enumerate}[label=(\alph*)]
        \item What is $\sup \set{R}$?

        \item Can you construct a set $S$ with $\inf S \geq \sup S$? If yes,
            what are \emph{all} such sets? If no, prove that it is impossible.

        \item Can you construct a nonempty set, bounded from above, that does
            not contain its supremum?

        \item Can you construct a nonempty set of \emph{integers}, bounded from
            above, that does not contain its supremum?

        \item Can you construct a nonempty set bounded from above where the
            supremum is not obvious?
    \end{enumerate}
\end{Exercise}

\begin{Exercise}
    (Abbott, 1.4.8)

    The nested interval theorem says that $\bigcap_{k \geq 1} I_k$ is nonempty
    if $\{I_k\}$ is a sequence of nonempty, bounded, nested, closed intervals.
    Do we need all of those conditions? That is, what happens if the intervals
    are open? Or not nested? Or unbounded? The following questions explore some
    of these ideas.

    Give an example of each of the following, or argue that it is impossible.

    \begin{enumerate}[label=(\alph*)]
        \item \emph{Disjoint}, nonempty, bounded from above sets $A$ and $B$
            such that $\sup A = \sup B$, $\sup A \notin A$, and $\sup B \notin
            B$.

        \item A sequence of nested, \emph{open} intervals $I_1 \supseteq I_2
            \subseteq \cdots$ with $\bigcap_{k \geq 1} I_k$ having a nonzero
            but \emph{finite} number of elements.

        \item A sequence of nested, \emph{unbounded}, closed intervals $L_1
            \supseteq L_2 \supseteq \cdots$ with $\bigcap_{k \geq 1} L_k$
            empty.

        \item A sequence of closed, bounded intervals $J_1, J_2, \dots$ such
            that $\bigcap_{k = 1}^n J_k$ is nonempty for every positive integer
            $n$, yet $\bigcap_{k \geq 1} J_k$ is empty.
    \end{enumerate}
\end{Exercise}

\begin{Exercise}
    (Abbott, 1.3.4.) [I don't expect that we'll have time to get to this, so
    I'm not going to bother typing it up.]
\end{Exercise}

% Hidden secrets.

% I want everyone to have their own questions. If they don't, then I'm going to
% walk us through a few exercises.

% Describe a set without a supremum. The same for infimum.

% 1.3.2.
% 1.3.4. How does the supremum behave under unions?
% 1.4.8.

\end{document}


text:
\section{Chocolate Chip Cookies}
\label{chocolateChipCookies}
\setcounter{secnumdepth}{0}
Time: 1 day (15 minutes prep, overnight resting, 10 minutes baking)
Serves: About 30 cookies

\begin{multicols}{2}
\subsection*{Ingredients}
\begin{itemize}
    \item 8 ounces non-salted butter, at room temperature
    \item 2 eggs
    \item 5 ounces granulated white sugar
    \item 5.75 ounces dark brown sugar
    \item 1 teaspoon vanilla extract
    \item 11 ounces all purpose flour
    \item 1 scant teaspoon table salt
    \item 1 teaspoon baking soda
    \item 12 ounces semisweet chocolate chips
    \item 4 ounces nuts (optional, recommend walnuts or pecans)
\end{itemize}

\subsection*{Hardware}
\begin{itemize}
    \item Large mixing bowl
    \item parchment paper
    \item cookie sheet
    \item flexible spatular
    \item wire cooling rack
\end{itemize}
\clearpage

\subsection*{Instructions}
\begin{enumerate}
    \item Combine and mix 8 ounces butter, 2 eggs, 5 ounces white sugar, and 5.75 ounces dark brown sugar until smooth.
    \item Mix in 1 teaspoon vanilla extract.
    \item Add 11 ounces flour, 1 scant teaspoon salt, 1 teaspoon baking soda.
    \item Mix until well combined, but mix as little as possible.
    \item Add 12 ounces chocolate chips and 4 ounces nuts if desired. Cut into the dough with as little work as possible to prevent additional gluten formation.
    \item Cover with parchment paper and leave in the fridge overnight to cool down, rest, and allowing the fats to re-solidify.
    \item Preheat oven to 375F.
    \item Remove dough when about ready to bake.
    \item Grab chunks of dough, about 1 Tablespoon in size.
    \item Roll into a ball, then flatten slightly.
    \item Place disk on ungreased cookie sheet.
    \item Repeat as above, keeping cookies with about 1-2 inches between them (as they will spread).
    \item Once your cookie sheet is full, place in the 375F oven to bake.
    \item Bake for 9-10 minutes, until cookies are just barely crispy on the edge, but still a little raw looking in the middle.
    \item Remove cookie sheet from the oven and allow to sit for 2 minutes undisturbed. Cookies will bake slightly more at this time.
    \item Carefully remove cookies to a wire cooling rack and let cook for another 2-5 minutes.
    \item Consume with milk.
\end{enumerate}

\subsection*{Notes}
\begin{itemize}
    \item Based on the original (well, the original modern version) Nestle Toll House Chocolate Chip Cookie recipe: \url{https://cooking.nytimes.com/recipes/1019232-toll-house-chocolate-chip-cookies}.
    \begin{itemize}
        \item This recipe was licensed by Nestle from Ruth Wakefield.
        \item There is rumor that Ruth Wakefield's recipe used 14 ounces of chocolate, rather than 12. I can't comment on that, as I don't have any records of her recipe.
        \item Main differences are slightly different ingredient amounts (less flour, more brown sugar, less white sugar), change brown sugar to dark brown sugar, resting overnight, more instructions on how to form and bake the cookies, and the change from volumetric measurements to weighted measurements. While I know doing baking by weight is more European than American, and these are as American in origin as you can get, baking by volume allows for a more consistent baking experience.
    \end{itemize}
    \item There is what seems to be about a 15 second window that is the perfect time to pull these out before they are over cooked, but while they will still have a gooey middle after cooking on the sheet for 2 more minutes. Knowing exactly when to pull cookies comes with experience. Just try to keep a consistent size and cookie placement, and get to know your oven really well. Practice makes perfect, and even slightly overbaked or undercooked cookies are delicious.
    \item A note on chocolate. Nestle chocolate chips, while the "original", are frankly not that great. I recommend using the absolute best chocolate you can reasonably find and afford for these, as that takes the cookies to the next level. Ghirardelli are the most commonly found decent chocolate chips, and what my mom recommends. I've heard good things about Trader Joe's chips, though I've not tried them yet. Otherwise I've seen REALLY fancy chocolate, but did not want to spend that much on cookies.
    \item I changed ingredient amounts slightly from the original recipe to get a slightly chewier final cookie. the dark brown sugar's added molasses makes it chewier, as does using more brown than white sugar. The resting voernight allows the fats to solidify, so that cookies spread a little less while baking, which makes them less crispy overall.
    \item There is a Good Eats episode with a different cookie recipe, Alton Brown gets a little more into the ratios and chemistry for chewy versus non-chewy cookies. Recommend watching it if you can find it. I believe it was "Three Chips for SIsterm Marsha", season 3, episode 6.
    \item If you want a crispier cookie (you heretic), add white sugar, reduce brown sugar, and bake from room temperature.
    \item I grew up eating these cookies made by my mom. Until 2018 I thought they were some dark secret family recipe. Turns out she just used the Nestle Toll house recipe our whole life... I felt a little betrayed by that.
\end{itemize}
\end{multicols}
\clearpage


text:
\documentclass[10pt]{beamer}

\ifx\pdfoutput\undefined
% we are running LaTeX, not pdflatex
\usepackage{graphicx}
\else
% we are running pdflatex, so convert .eps files to .pdf
\usepackage{graphicx}
\usepackage{epstopdf}
\fi

%%%% comment out CJKUtf8 package if Chinese characters are not used.
\usepackage{CJKutf8}

\input{beihangbeamerstyle/beihangcolor}
\input{beihangbeamerstyle/beihangbeamerstyle}

\title{Beamer Style of 北京航空航天大学}
\author{Xiaoke Yang\\
Beihang University (\texttt{xiaokeyang@buaa.edu.cn})}
\date{What seminar/conference, Which location, Wed  1 Jun 11:25:45 CST 2016}

\begin{document}

%%%% comment out the CJK* environment if Chinese characters are not used.
\begin{CJK*}{UTF8}{gbsn}

%----------------------------------------------------------------------
% Title frame
\begin{frame}[plain]
\maketitle
\end{frame}

%----------------------------------------------------------------------
% Outline frame
% PLEASE RUN pdflatex TWICE
\begin{frame}
\frametitle{提纲Outline}
\tableofcontents
\end{frame}
%%=====================================================================
% Section I
\section{Motivation}
%----------------------------------------------------------------------
% Content frame
\begin{frame}
\frametitle{Motivation}
\framesubtitle{Why I made this beamer style}
\begin{block}{Demonstration of the use of items and blocks}
\begin{itemize}
\item No one has done it.
\item I need one.
\pause \item Share with others.
\end{itemize}
\end{block}
\pause
\begin{block}{Another block}
This block appears after a pause. Simply delete the \texttt{\textbackslash pause} command if this animation is not needed. Add the pause command whenever a pause is needed.
\end{block}
\end{frame}

%%=====================================================================
% Section II
\section{This is the second section: a two-column slide}
%----------------------------------------------------------------------
\begin{frame}
\frametitle{A Two-column Slide}
\begin{columns}
\begin{column}{0.5\textwidth}
\begin{block}{The first column}
This is the first column.
This is the first column.
This is the first column.
This is the first column.
This is the first column.
This is the first column.
This is the first column.
This is the first column.
This is the first column.
This is the first column.
This is the first column.
This is the first column.
This is the first column.
This is the first column.
\end{block}
\end{column}
\begin{column}{0.5\textwidth}
\begin{block}{The second column}
{\color{coreBlue}{This is the only ``Beihang colour'' I found. }} Other built-in colours can also be used, e.g. {\color{red}{red}}, {\color{orange}{orange}}, {\color{blue}{blue}}
\vspace{9.5em}
\end{block}
\end{column}
\end{columns}
\end{frame}

%%%% comment out the CJK* environment if Chinese characters are not used.
\end{CJK*}
\end{document}

max_stars_repo_name: teancake/latex-beamer-beihang

max_issues_repo_name: teancake/latex-beamer-beihang

max_forks_repo_name: teancake/latex-beamer-beihang