text:
% Document Head
\documentclass[11pt, oneside]{book}
\usepackage{geometry}
\geometry{letterpaper}
\usepackage[parfill]{parskip}
\usepackage{graphicx}

% Essential Packages
\usepackage{ragged2e}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage[hyperref]{ntheorem}

% Theorem Style Customization
\setlength\theorempostskipamount{5ex}

\usepackage{hyperref}

% ntheorem Declarations
\theoremstyle{break}
\newtheorem{thm}{Theorem}[section]
\newtheorem{crly}{Corollary}[thm]
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{propo}{Proposition}[section]
\newtheorem{defn}{Definition}[section]
\newtheorem{eg}{Example}[section]
\newtheorem*{proof}{Proof}
\newtheorem*{remark}{Remark}

% Shortcuts
\newcommand{\bb}[1]{\mathbb{#1}}		% using bb instead of mathbb

% ntheorem listtheorem style
\makeatletter
	% Definition List Style
\def\thm@@thmline@name#1#2#3#4{%
        \@dottedtocline{-2}{0em}{2.3em}%
                   {\makebox[\widesttheorem][l]{\protect\numberline{#2}}#3}%
                   {#4}}
\@ifpackageloaded{hyperref}{
\def\thm@@thmline@name#1#2#3#4#5{%
    \ifx\\#5\\%
        \@dottedtocline{-2}{0em}{2.3em}%
            {\makebox[\widesttheorem][l]{\protect\numberline{#2}}#3}%
            {#4}
    \else
        \ifHy@linktocpage\relax\relax
            \@dottedtocline{-2}{0em}{2.3em}%
                {\makebox[\widesttheorem][l]{\protect\numberline{#2}}#3}%
                {\hyper@linkstart{link}{#5}{#4}\hyper@linkend}%
        \else
            \@dottedtocline{-2}{0em}{2.3em}%
                {\hyper@linkstart{link}{#5}%
                  {\makebox[\widesttheorem][l]{\protect\numberline{#2}}#3}\hyper@linkend}%
                    {#4}%
        \fi
    \fi}
}
\makeatother

\newlength\widesttheorem
\AtBeginDocument{
  \settowidth{\widesttheorem}{Proposition 1.1.1.1\quad}
}

% Main Body
\title{MATH239 Review for All Definitions and Theorems by Chapter and Section}
\author{Johnson Ng}

\begin{document}
\maketitle
\tableofcontents

\chapter*{List of Definitions}
\theoremlisttype{allname}
\listtheorems{defn}

\chapter*{List of Theorems}
\theoremlisttype{allname}
\listtheorems{lemma,thm,crly,propo}

\chapter{Combinatorial Analysis}

\section{Introduction}
\begin{defn}[Composition, Parts, Weights]
	A composition of $n \in \bb{N}$ is a sequence $(m_1, m_2, ..., m_k)$ where $\forall k \in \bb{Z}^+ \quad m_k \in \bb{Z}^+$ such that
	\begin{gather*}
		\sum_{i=1}^{k}m_i = n
	\end{gather*}
	The numbers $m_i$, for all $i\in\{1, 2, ..., k\}$, are called parts of the composition. We define the weight of a composition to be the sum of its parts.

\end{defn}

\begin{defn}[Binary Strings]
	(We shall write bin strs to represent binary strings in short) \\
	A bin str of length n is a sequence $a_1, a_2, ..., a_n$ where $\forall i \in \{1, 2, ..., n\} \quad a_i = 0$ or $a_i = 1$. We write the binary string as a concatenation, i.e. $a_1a_2a_3\hdots a_n$.
\end{defn}

\begin{remark}
	There are $2^n$ bin strs of length n.
\end{remark}

\section{Sums and Products}

\begin{defn}[Union \& Disjoint]
	Let A and B be sets. The union of A and B, denoted $A \cup B$, is defined as
	\begin{gather*}
		A \cup B := \{x : x \in A \lor x \in B\}
	\end{gather*}
	The two sets are said to be disjoint if their intersection is an empty set, i.e.
	\begin{gather*}
		A \cap B = \emptyset
	\end{gather*}
\end{defn}

\begin{remark}
	\begin{gather*}
		|A \cup B| = |A| + |B|
	\end{gather*}
\end{remark}

\begin{defn}[Cartesian Product]
	The Cartesian Product $A \times B$ of sets A and B is the set of ordered pairs $(a ,b)$ such that $a \in A$ and $b \in B$, i.e.
	\begin{gather*}
		A \times B := \{(a,b) : a \in A, b \in B \}
	\end{gather*}
	Thus
	\begin{gather*}
		|AB| = |A||B|
	\end{gather*}
\end{defn}

\begin{defn}[Cartesian Power]
	The Cartesian Power $A^k$ is defined as the ordered k-tuples of elements from A, i.e.
	\begin{gather*}
		A^k := \Bigr\{(a_1, a_2, ..., a_k): \forall i \in \{1, 2, ..., k\}, a_i \in A\Bigl\}
	\end{gather*}
\end{defn}

\begin{remark}
	When A is finite, $|A^k| = |A|^k$
\end{remark}

\section{Binomial Coefficients}

\begin{thm}
	$\forall n,k \in \bb{N}$, the number of k-element subsets of an n-element set is
	\begin{gather*}
		\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n(n-1)(n-2)\hdots(n-k+1)}{k!}
	\end{gather*}
\end{thm}

\begin{propo}[Binomial Identities]
	The following are some binomial identities:
	\begin{enumerate}
		\item $\binom{n}{k} = \binom{n}{n-k}$
		\item $(1-x)^n = \sum_{k=0}^{n}\binom{n}{k}x^k$
		\item $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
		\item $\binom{n+k}{n} = \sum_{i=0}^{k}\binom{n+i-1}{n-1}$
	\end{enumerate}
\end{propo}

\section{Generating Series}

\begin{defn}[Generating Series]
	Let $S$ be a set of configurations with a weight function $w$. The generating series for $S$ with respect to $w$ is defined by
	\begin{gather*}
		\Phi_S(x) = \sum_{\sigma \in S}x^{w(\sigma)}
	\end{gather*}
\end{defn}

\begin{thm}
	Let $\Phi_S(x)$ be a generating series for a finite set S with respect to weight function $w$. Then,
	\begin{enumerate}
		\item $\Phi_S(1) = |S|$;
		\item $\sum_{\sigma \in S}w(\sigma) = \Phi'_S(1)$; and
		\item the average weight of an element in S is $\frac{\Phi'_S(1)}{\Phi_S(1)}$.
	\end{enumerate}
\end{thm}

\section{Formal Power Series}

\begin{defn}[Formal Power Series]
	Let $(a_0, a_1, a_2, ...)$ be a sequence such that $\forall k \in \bb{N} \quad k \in \bb{Q}$.\\
	\begin{gather*}
		A(x) = \sum_{k=0}^{\infty}a_kx^k =  a_o + a_1x + a_2x^2 + \hdots
	\end{gather*}
	is called a formal power series. We say that $a_n$ is the coefficient of $x^n$ in $A(x)$ , and write
	\begin{gather*}
		[x^n]A(x) = a_n
	\end{gather*}
	A formal power series should be regarded as a way of encoding a sequence of numbers. Therefore, 2 formal power series are equal if and only if they share the same sequence of coefficients.
\end{defn}

\begin{defn}[Additional And Multiplication Rules of Formal Power Series]
	Let $A(x)$ and $B(x)$ be formal power series. \\
	(Addition)
	\begin{gather*}
		A(x) + B(x) = (a_0 + b_0) + (a_1 + b_1)x + (a_2 + b_2)x^2 + \hdots = \sum_{k = 0}^{\infty}(a_k + b_k)x^k
	\end{gather*}
	(Multiplication)
	\begin{align*}
		A(x)B(x) &= \Bigg(\sum_{i \geq 0}a_ix^i\Bigg)\Bigg(\sum_{j \geq 0}b_jx^j\Bigg) \\
				 &= \sum_{i \geq 0}\sum_{j \geq 0}a_ib_jx^{i+j} \\
				 &= \sum_{n \geq 0}\sum_{k = 0}^{n}a_kb_{n-k}x^n
	\end{align*}
\end{defn}

\begin{thm}
	Let $A(x) = a_0 + a_1x + a_2x^2 + \hdots, P(x) = p_0 + p_1x + p_2x^2 + \hdots$, and $Q(x) = 1 - q_1x - q_2x^2 - \hdots$ be formal power series. Then
	\begin{gather*}
		Q(x)A(x) = P(x) \\
		\iff \\
		a_n = p_n + q_1a_{n-1} + q_2a_{n-2} + \hdots + q_na_0
	\end{gather*}
\end{thm}

\begin{crly}
	Let $P(x)$ and $Q(x)$ be formal power series.
	\begin{gather*}
		Q(0) \neq 0 \implies \exists!A(x) \quad Q(x)A(x) = P(x)
	\end{gather*}
\end{crly}

\begin{defn}[Inverse of a Formal Power Series]
	We say that $B(x)$ is the inverse of $A(x)$ when
	\begin{gather*}
		A(x)B(x) = 1
	\end{gather*}
	and denote this by
	\begin{gather*}
		B(x) = A(x)^{-1} \quad \text{or} \quad B(x) = \frac{1}{A(x)}
	\end{gather*}
\end{defn}

\begin{remark}[Some important series]
	(Infinite Sum of a Geometric Series)
	\[
		1 + x + x^2 + \hdots = \sum_{i \geq 0}x^i = \frac{1}{1-x}
	\]
	(Sum of k terms in a Geometric Series)
	\[
		1 + x + x^2 + \hdots + x^k = \sum_{i=0}^{k} x^i = \frac{1 - x^{k+1}}{1 - x}
	\]

	(Negative Binomial Series)
	\[
		(1-x)^{-k} = \sum_{n \geq 0} \binom{n+k-1}{k-1}x^n
	\]
\end{remark}

\begin{thm}[Unique Existence of the Inverse of a Formal Power Series]
	A formal power series $P(x)$ has an inverse if and only if $P(0) \neq 0$. Moreover, the inverse if unique.
\end{thm}

\begin{defn}[Composition of Formal Power Series]
	The composition of formal power series $A(x) = a_0 + a_1x + a_2x^2 + \hdots$ and $B(x)$ is defined by
	\[
		A\Big(B(x)\Big) = a_0 + a_1B(x) + a_2B(x)^2 + \hdots = \sum_{i \geq 0} a_iB(x)^i
	\]
\end{defn}

\begin{thm}
	Let $A(x)$ and $B(x)$ be formal power series.
	\[
		B(0) = 0 \implies A\Big(B(x)\Big) \quad \text{is a formal power series}
	\]
\end{thm}

\section{Sum and Product Lemmas}

\begin{thm}[Sum Lemma]
	Let S be a set. Let $(A, B)$ be a partition of S such that A and B is a disjoint union of S. Then
	\[
		\Phi_S(x) = \Phi_A(x) + \Phi_B(x)
	\]
\end{thm}

\begin{remark}
	\[
		\Phi_S(x) = \Phi_A(x) + \Phi_B(x) - \Phi_{A \cap B}(x)
	\]
\end{remark}

\begin{thm}[Product Lemma]
	Let A and B be sets of configurations with weight functions $\alpha$ and $\beta$ respectively.
	\[
		\Big(\forall \sigma = (a, b) \in A \times B \quad w(\sigma) = \alpha(a) + \beta(b) \Big) \implies \Phi_{A \times B}(x) = \Phi_A(x) \Phi_B(x)
	\]
\end{thm}

\chapter{Compositions \& Strings}

\section{Compositions of an Integer}

\begin{defn}[Compositions of an Integer, Parts, and the Empty Composition]
	$\forall n,k \in \bb{N}$, a composition of n with k parts is an ordered list $(c_1, c_2, ..., c_k)$ where
	\[
		\forall i \in \{1, 2, ...,k\} \quad \sum_{i=1}^{k}c_i = n
	\]
	The $c_i$'s are called the parts of the composition.
	We define the composition of the number 0 as the empty composition, which is the only composition of length 0.
\end{defn}

\section{Subsets with Restrictions}

It is common to recast problems in order to allow us to invoke the Sum and Product Lemmas.

\section{Binary Strings}

\begin{defn}[Concatenation]
	Let A and B be bin strs. AB is said to be a concatenation where the bin str B is appended to the bin str A, i.e.
	\[
		AB := \{ab : a \in A, b \in B\}
	\]
	Similarly, we define
	\begin{align*}
		A^* &:= \{\epsilon\} \cup A \cup AA \cup AAA \cup \hdots\\
			&\,= \{\epsilon\} \cup A \cup A^2 \cup A^3 \cup \hdots
	\end{align*}
\end{defn}

\begin{defn}[Substring]
	For bin strs A and B, we say that B is a substring of A iff A = CBD where C and D are some bin str.
\end{defn}

\begin{defn}[Blocks]
	A block of a bin str is a maximal substring consisting of only 0's or 1's.
\end{defn}

\section{Unambiguous Expressions}

\begin{defn}[Ambiguity of an Expression]
	Let A and B be set of bin strs. Let AB is be the concatenation of A and B.\\
	AB is ambiguous
	\[
		\iff \exists(a_1, b_1), (a_2, b_2) \in A \times B \quad (a_1 \neq a_2 \land b_1 \neq b_2 \land a_1b_1 = a_2b_2)
	\]
	AB is unambiguous
	\[
		\iff \forall c \in AB \quad \exists! a \in A \land \exists! b \in B \quad c = ab
	\]
\end{defn}

\section{Some Decomposition Rules}
Some common decompositions rules: For a set S of all bin strs,
\begin{itemize}
	\item Decomposte a string after each 0 or 1. Each piece in the decomposition will be either 0 or 1, so this gives
	\[
		S = \{0, 1\}^*
	\]
	\item Decomposte a string after each occurrence of 0. Each piece in the decomposition will be of the form
	\[
		\{0, 10, 110, ...\} = \{1\}^* 0
	\]
	except possibly for the last piece that may consist of only 1's. Thus
	\[
		S = \Big(\{1\}^*0\Big)^*{1}^*
	\]
	\item Decompose a string after each block of 0's. Each piece in the decomposition, except possible the first and last piece, will consist of a block of 1's followed by a block of 0's. The first piece may consist of only block of 0's and the last piece, block of 1's. So
	\[
		S = \{0\}^*\Big(1\{1\}^*0\{0\}^*\Big)^*\{1\}^*
	\]
\end{itemize}

\section{Sum and Product Rules for Strings}

\begin{thm}
	Let A, and B be bin strs.
	\begin{enumerate}
		\item If AB is unambiguous, then
			\[
				\Phi_{AB}(x) = \Phi_{A}(x) \Phi_{B}(x)
			\]
		\item If $A^*$ is unambiguous, then
			\[
				\Phi_{A^*}(x) = \frac{1}{1-\Phi_{A}(x)}
			\]
	\end{enumerate}
\end{thm}

\section{Decomposition Using Blocks}

No definitions and theorems here, but examples of how to decompose a given binary string with its set of conditions.

\section{Recursive Decomposition of Binary Strings}

\begin{defn}[Recursive Definition]
	A recursive decomposition is a set that is decomposed in terms of itself. Let S be the set of all bin strs. We define S in the following way:
	\begin{enumerate}
		\item $\{\epsilon\} \in S$; and
		\item Any other elem of S consists of either 0 or 1, followed by an element of S.
	\end{enumerate}
	Such a definition is called a recursive definition. This leads the the recurive decomposition
	\[
		S = \{\epsilon\} \cup \{0, 1\}S
	\]
\end{defn}

\chapter{Resurrences, Binary Trees and Sorting}

\section{Coefficient of Rational Functions}

\begin{propo}[Partial Fractions]
	Let $a, b, c, k, x \in \bb{R}$
	\begin{center}
		\begin{tabular}{c | c}
			Factor in Denominator	&	Term in partial fraction decomposition \\
			\hline
			$ax + b$	 &	$\frac{A}{ax+b}$ \\
			$(ax+b)^k$	&	$\frac{A_1}{ax+b} + \frac{A_2}{(ax+b)^2} + \hdots + \frac{A_k}{(ax+b)^k}$\\
			$ax^2 + bx + c$	& $\frac{Ax+B}{ax^2 + bx + c}$\\
			$(ax^2 + bx + c)^k$	& $\frac{A_1x + B_1}{ax^2 + bx + c} + \frac{A_2x + B_2}{(ax^2 + bx + c)^2} + \hdots + \frac{A_kx + B_k}{(ax^2 + bx + c)^k}$
		\end{tabular}
	\end{center}
\end{propo}

\begin{lemma}
	\[
		f(x) \in \bb{P}_{\leq r} \implies \exists P(n) \in \bb{P}_{\leq r}(F) \quad [x^n]\frac{f(x)}{(1-\theta x)^r} = P(n) \theta^n
	\]
\end{lemma}

\begin{lemma}
	Suppose f and g are polynomials with $deg(f) < deg(g)$.
	\[
		\exists g_1, g_2 \in \bb{P}(F) \quad g_1 \perp g_2 \quad g(x) = g_1(x)g_2(x)
	\]
	\[
		\implies \exists f_1, f_2 \in \bb{P}(F) \quad \text{for } i = 1, 2 \quad deg(f_i) < deg(g_i) \text{ and } \frac{f(x)}{g(x)} = \frac{f_1(x)}{g_1(x)} + \frac{f_2(x)}{g_2(x)}
	\]
\end{lemma}

\begin{thm}
	Assumptions: $f, g \in \bb{P}(F) \quad deg(f) < deg(g)$. \\
	\begin{gather*}
		\forall i \in \bb{Z}_{\leq k}^+ \quad \exists \theta_i \in \bb{C} \quad \exists m_i \in \bb{Z}^+ \\
		g(x) = \prod_{i} (1 - \theta_i x)^{m_i} \\
		\implies \exists P_i \in \bb{P}(F) \quad deg(P_i) < m_i \\
		\text{and} \\
		[x^n]\frac{f(x)}{g(x)} = \sum_{i}P_i(n) \theta_i^n
	\end{gather*}
\end{thm}

\section{Solutions to Recurrence Equations}
\begin{thm}
	Let $C(x) = \sum_{n \geq 0} c_nx^n$ where the coefficients $c_n$ satisfy the recurrence $c_n + q_1c_{n-1} + \hdots + q_kc_{n-k} = 0, n \geq k$
	\begin{gather*}
		g(x) := 1 + q_1x + \hdots + q_kx^k \\
		\implies \exists f(x) \in \bb{P}(N) \quad deg(f) < k \\
		C(x) = \frac{f(x)}{g(x)}
	\end{gather*}
\end{thm}

\begin{thm}
	SPS $\langle c_n \rangle _{n \geq 0}$ satisfies the recurrence
	\[
		c_n + q_1c_{n-1} + \hdots + q_kc_{n-k} = 0
	\]
	so that the characteristic polynomial exists. If the characteristic polynomial of this recurrence has root $\beta_i$ with multiplicity $m_i$, for i = 1, ..., j, where j is the number of distinct roots, then the general solution for the recurrence is
	\[
		c_n = P_1(n)\beta_1^n + \hdots + P_j(n)\beta_j^n
	\]
	where $P_i(n)$ is a polynomial in n with degree less tahn $m_i$, and these polynomials are determined by the $c_i$'s.
\end{thm}

\section{Nonhomogenous Recurrence Equations}

\begin{thm}
	SPS that $a_0, a_1, ...$ is a solution to $b_n + q_1b_{n-1} + \hdots + q_kb_{n-k} = f(n)$ (any solution without checking the initial conditions). Then the general solution is given by
	\[
		b_n = a_n + c_n \quad n \geq 0
	\]
	where $c_n$ is given by Theorem 3.2.2, and the k constants $b_{1,1}, ..., b_{j,m_j}$ in $c_n$ can be chosen to fit the initial conditions for $b_n$.
\end{thm}

\begin{remark}[Some heuristics in solving non-homogeneous recurrences]
\mbox{}\\[-2ex]
	\begin{tabular}{c | c | c}
		If f(n) is					& 	First, try						&	Otherwise \\
		\hline
		constant 					& 	d 								& $d_1n + d_2$ \\
		$b_1n + b_2$	&	$d_1n + d_2$	&	$d_1n^2 + d_2n + d_3$ \\
		$\sum_{i=0}^{k}b_{k+1}n^{k+i}$ &	polynomial of degree k 	& polunomial of degree k + 1 \\
		$bs^n$				&	$ds^n$						& $dns^n$ \\
	\end{tabular}

	For all cases, if the otherwise case still does not work, try the variable n with a higher degree, or a polynomial of n with a higher degree.
\end{remark}

\textbf{Strategy to fight non-homogeneous recurrence}

\begin{enumerate}
	\item Find a general solution to the associated homogeneous recurrence.
	\item Find a single specific solution to the non-homogeneous recurrence.
	\item $a_n = \bigg(\text{general solution to homogeneous equation}\bigg) + c_n$
	\item Use initial conditions to solve for the remaining variables.
\end{enumerate}

\section{Binary Trees}

\begin{defn}[Binary Trees]
	A binary tree is either
	\begin{enumerate}
		\item an empty tree $\{\epsilon\}$
		\item a tree with a fixed root vertex such that each vertex has a left branch and a right branch (either of which may be empty)
	\end{enumerate}
\end{defn}

\begin{remark}
	Note that a binary tree with a right branch is not equal to a binary tree with a left branch, even if they have the same number of vertices.
\end{remark}

\begin{remark}[A decomposition of the binary tree]
	Let $\mathscr{T}$ be the set of all binary trees. We cab decompose $\mathscr{T}$ recursively as
	\[
		\mathscr{T} = \{\epsilon\} \cup \{\cdot\} \times \mathscr{T} \times \mathscr{T}
	\]
	And since this is an unambiguous decomposition, we have
	\[
		\Phi_{\mathscr{T}}(x) = 1 + x\Phi_{\mathscr{T}}(x)^2
	\]
	which if we let $T(x) = \Phi_{\mathscr{T}}(x)$ , it leads us to
	\[
		(2xT(x) - 1)^2 = 1 - 4x
	\]
\end{remark}

\section{The Binomial Series}

\begin{thm}[The Generalized Binomial Theorem]
	\begin{gather*}
		\forall a \in \bb{Q} \\
		(1 - x)^a = \sum_{k \geq 0} \binom{a}{k}x^k
	\end{gather*}
\end{thm}

\begin{remark}[Catalan Numbers]
	The number of binary trees with $n \geq 0$ vertices is
	\[
		\frac{1}{n + 1} \binom{2n}{n}
	\]
	which is called the Catalan Numbers.
\end{remark}

\chapter{Introduction to Graph Theory}

\section{Definitions}

\begin{defn}[Graph]
	A graph F iis a finite nonempty set, V(G), of objects called $\textbf{vertices}$, together with a set, E(G), of unordered pairs of distinct vertice. The elements of E(G) are called $\textbf{edges}$.
\end{defn}

\begin{defn}[Adjacency]
	2 vertices u and v are said to be adjacent if there is an edge connecting them. This edge is said to be $\textbf{incident}$ with vertices u and v, or that the edge $\textbf{joins}$ u and v.
\end{defn}

\begin{defn}[Neighbours]
	Vertices adjacent to a vertices u are called neighbours of u. The set of neighbours of u is denoted N(u).
\end{defn}

\begin{defn}[Planar]
	A graph which can be represented with no edges crossing is said to be planar.
\end{defn}

\begin{defn}[Directed graph or Digraph]
	A "graph" whose edges are non-distinct ordered pairs.
\end{defn}

\begin{defn}[Multigraph]
	A graph where multiple edges are allowed between 2 vertices.
\end{defn}

\section{Isomorphism}

\begin{defn}[Isomorphism]
	2 graphs $G_1$ and $G_2$ are isomorphic if
	\[
		\exists f:V(G_1) \mapsto V(G_2)
	\]
	that is a bijection, such that vertices f(u) and f(v) are adjacent in $G_2$ if and only if u and v are adjacent in $G_1$.
\end{defn}

\begin{defn}[Isomorphism Class]
	Collection of graphs that are isomorphic to G forms an isomorphism class of G.
\end{defn}

\begin{remark}
	In almost all cases, a graph shares its properties with graphs from the same isomorphism class. It is also feasible to think that there are infinitely many graphs in an isomorphism class. However, the number of isomorphism classes of graphs with a given finite set of vertices is finite itself.
\end{remark}

\begin{defn}[Automorphism and Identity Map]
	An automorphism of G is an isomorphism of G to itself. \\
	An identity map on V(G) is an isomorphism from the graph G to itself.
\end{defn}

\section{Degree}

\begin{defn}[Degree]
	The degree of a vertex v is the number of edges that are incident with v.
\end{defn}

\begin{thm}[Handshake Lemma]
	For any graph G,
	\[
		\sum_{v \in V(G)} deg(v) = 2 | E(G) |
	\]
\end{thm}

\begin{crly}
	The number of vertices of odd degree in a graph is even.
\end{crly}

\begin{crly}
	The average degree of a verex in a graph G is
	\[
		\frac{2| E(G) |}{V(G)}
	\]
\end{crly}

\begin{defn}[k-regular Graph]
	A graph in which every vertex has degree k, for some fixed k, is called a k-regular graph.
\end{defn}

\begin{defn}[Complete Graph]
	A complete graph is one in which all pairs of distinct vertices are adjacent to each other. The complete graph with p vertices is denoted $K_p$.
\end{defn}

\section{Bipartite Graph}

\begin{defn}[Bipartite Graph]
	A bipartite graph is a graph in which its vertices are partitioned into 2 sets, A and B. G is said to have a bipartition (A, B), such that each edge in G joins a vertex in A to a vertex in B.
\end{defn}

\begin{remark}
	A $\textbf{complete bipartite graph}, K_{m, n}$ has all vertices in A adjacent to all vertices in B with $|A| = m$ and $|B| = n$.
\end{remark}

\begin{defn}[n-cube]
	For $n \geq 0$, the n-cube is the graph whose vertices are the $\{0, 1\}$-strings of length n, and 2 strings are adjacent to each other if and only if they differ by exactly one position (or one byte).
\end{defn}

\section{How to Specify A Graph}
Not covered by MATH239

\section{Paths and Cycles}

\begin{defn}[Subgraph]
	A subgraph S of a graph G is a graph such that $V(S) \subseteq V(G) \text{ and } E(S) \subseteq E(G)$. If $V(S) = V(G)$ then S is a spanning subgraph of G. If S is a subgraph of G but $S \neq G$ , then S is a proper subgraph of G.
\end{defn}

\begin{defn}[Walk]
	A walk in a graph G from $v_0$ to $v_n, n /geq 0$, is an alternating sequence of vertices and edges of G
	\[
		v_0, \{v_0, v_1\}, v_1, \{v_1, v_2\}, v_2, ..., v_{n-1}, \{v_{n-1}, v_n\}, v_n
	\]
	which begins with $v_0$ and ends with $v_n$ and $\{v_i, v_j\}$ denotes the edges incident to the vertices contained in the set notation. Such a walk is called a $v_0, v_n \text{-} walk$. The length of a walk is the number of the edges in the walk. \\
	If $v_0 = v_n$, then the walk is called a closed walk.
\end{defn}

\begin{defn}[Path]
	A path is a walk where all its vertices are distinct.
\end{defn}

\begin{thm}
	If there is a walk from vertex x to vertex y in G, then there is a path from x to y in G.
\end{thm}

\begin{crly}
	Let $x, y, z \in V(G)$ where G is a graph. If there is a path from x to y in G and a path from y to z in G, then there is a path from x to z in G.
\end{crly}

\begin{defn}[Cycle]
	A cycle in a graph G is a subgraph with n distinct vertices $v_0, v_1, ..., v_{n-1}, \text{ for } n \geq 0$, and n distinct edges $\{v_0, v_1\}, \{v_1, v_2\}, ..., \{v_{n-2}, v_{n-1}\}, \{v_{n-1}, v_0\}$. Equivalently, a cycle is a connected graph that is 2-regular. A cycle with n edges is called an n-cycle, or a cycle of length n.
\end{defn}

\begin{remark}[Comparison of Path and Cycles]
	\mbox{}\\[-2ex]
	\begin{tabular}{l | l}
		Paths											&			Cycles \\
		\hline
		\multicolumn{2}{c}{Similarities} \\
		\hline
		\multicolumn{2}{l}{$\bullet$ The two drawings may look similar} \\
		\multicolumn{2}{l}{$\bullet$ Both go through the same vertex once (save the initial which can be equal to the final one)} \\
		\hline
		\multicolumn{2}{c}{Differences} \\
		\hline
		$\bullet$ Described as a sequence of vertices 	&	$\bullet$ A cycle is a graph \\
		$\bullet$ Has more information (i.e. direction) &	$\bullet$ Has no particular direction \\
		$\bullet$ Has a specific starting vertex		&	$\bullet$ Any vertex can be a starting vertex \\
		$\bullet$ Can have length 0 (for closed paths)	&	$\bullet$ Must have at least 3 vertices \\

	\end{tabular}
\end{remark}

\begin{thm}
	SPS G is a graph. If $\forall v \in V(G), deg(v) = 2 \implies$ G contains a cycle.
\end{thm}

\begin{defn}[Hamilton Cycle]
	A spanning cycle in a graph is known as a Hamilton Cycle.
\end{defn}

\section{Equivalence Relations}

Only thing to note here is that a walk is an equivalence relation, i.e. it satisfies the properties:
\begin{enumerate}
	\item Reflexivity
	\item Symmetry
	\item Trasitivity
\end{enumerate}

\section{Connectedness}

\begin{defn}[Connected]
	A graph G is connected if $\forall x, y \in V(G)$ there is a path from x to y.
\end{defn}

\begin{thm}
	Let G be a graph and let $v \in V(G)$. If $\forall w \in V(G)$ there is a path from v to w in G, then G is connected.
\end{thm}

\begin{defn}[Component]
	A component of G is a subgraph C of GF such that\
	\begin{enumerate}
		\item C is connected; and
		\item No subgraph of G that properly contains C is connected.
	\end{enumerate}
\end{defn}

\begin{remark}
	\begin{enumerate}
		\item The two conditions may sometimes be stated as "a component of G is a subgraph which is maximal, subject to being connected."
		\item If a graph has more than one component, the graph is said to be disconnected.
	\end{enumerate}
\end{remark}

\begin{defn}[Edge Cut]
	Let G be a graph and $X \subseteq V(G)$. The edges of G with one end in X and one end in $X^c$ form an edge cut of G.
\end{defn}

\begin{thm}
	A graph G is disconnected if and only if there exists a non-empty proper subgraph of G such that the cut induced by X on G is empty.
\end{thm}

\begin{defn}[Equivalence Class]
	Let G be a graph. The equivalence class under the graph connected by a related path are called connected components (or components) of G.
\end{defn}

\section{Eulerian Circuits}

\begin{defn}[Eulerian Circuit]
	An Eulerian circuit of a graph G is a closed walk that contains every edge of G exactly once.
\end{defn}

\begin{defn}[Eulerian Trail]
	An Eulerian Trail on a graph G is a walk that contains every edge of G exactly once.
\end{defn}

\begin{thm}
	Let G be a connected graph. Then G has an Eulerian citcuit iff every vertex has even degree.
\end{thm}

\begin{remark}[Strategy for finding an Eulerian Circuit]
	\begin{enumerate}
		\item First, try to find a large cycle and use that as the "base" of where the circuit will revolve around.
		\item Trace from any vertex on the cycle in any direction.
		\item Whenever you meet a vertex that is incident with an edge not on the cycle, go to the vertex on the other end.
		\item You can try to work from step 1 and apply the same strategy, or simply trace an Eulerian circuit on that subgraph.
		\item When you come back to the vertex on the "base" cycle, continue to iterate through step 3 to 5.
		\item Perform the operation until you complete the "base" cycle. This will give you an Eulerian circuit (on a connected graph).
	\end{enumerate}
\end{remark}

\section{Bridges}

\begin{defn}[Bridge]
	An edge e of G is called a bridge if G-e has more components than G.
\end{defn}

\begin{remark}
	This definition implies that if G is connected, then G-e is disconnected.
\end{remark}

\begin{lemma}
	Let G be a connected graph. For some $x, y \in V(G)$, if $e=\{x, y\}$ is a bridge, then G-e has precisely 2 components; Furthermore, x and y are in different components.
\end{lemma}

\begin{thm}
	An edge e is a bridge of a graph G iff it is not connected in any cycle of G.
\end{thm}

\begin{crly}
	If there are 2 distinct paths from vertex u to vertex v in G, then G contains a cycle.
\end{crly}

\section{Certifying Properties}
$\textbf{Certifying connectedness:}$
\begin{itemize}
	\item G is connected if:
	\begin{itemize}
		\item $\forall x,y \in V(G)$, there exists a path in G that connects x and y
	\end{itemize}
	\item G is not connected if:
	\begin{itemize}
		\item A cut can be producted; SPS sets A and B, where $A, B \subseteq V(G) \quad A \cap B = \emptyset \quad \nexists e = \{x, y\} \in E(G)$ where $x \in A \text{ and } y \in B$
	\end{itemize}
\end{itemize}

$\textbf{Certifying whether an edge e is a bridge in a connected graph G:}$

\begin{itemize}
	\item e is a bridge if:
	\begin{itemize}
		\item A cut can be induced from A to B for G-e, where if $e=\{u, v\}$ where for $A, B \in V(G) \quad A \cap B = \emptyset \quad u \in A \land v \in B$
	\end{itemize}
	\item e is not a bridge if:
	\begin{itemize}
		\item A cycle that contains e can be found; or
		\item Showing that G-e is connected (usually tedious)
	\end{itemize}
\end{itemize}

\chapter{Trees}

\section{Trees}

\begin{defn}[Tree]
	A tree is a connected graph with no cycles.
\end{defn}

\begin{lemma}
	There is a unique path between every pair of vertices u and v in a tree T.
\end{lemma}

\begin{lemma}
	Every edge of a tree is a bridge.
\end{lemma}

\begin{defn}[Forest]
	A graph with no cycles, not necessarily connected, is a forest.
\end{defn}

\begin{defn}[Leaf]
	A vertex of degree 1 on a tree is called a leaf.
\end{defn}

\begin{propo}
	\begin{enumerate}
		\item Every subgraph of a tree is forest.
		\item If a tree T has at least 2 vertices, then T has at least 2 leaves.
		\item If a tree T has a leaf v, then T-v is also a tree.
		\item If T is a tree, then $|E(T)| = |V(T)| - 1$.
	\end{enumerate}
\end{propo}

\begin{propo}
	If G is a tree, TFAE:
	\begin{enumerate}
		\item G is connected
		\item G has no cycles
		\item $|E(G)| = |V(G)| - 1$
	\end{enumerate}
\end{propo}

\section{Spanning Trees}

\begin{defn}[Spanning Trees]
	A spanning subgraph that is also a tree is called a spanning tree.
\end{defn}

\begin{thm}
	A graph G is connected iff G has a spanning tree.
\end{thm}

\begin{thm}
	If T is a spanning tree of G and e is an edge not in T, then T + e contains exactly one cycle C. Moreover, if e' is any edge on C, then T + e - e' is also a spanning tree of G.
\end{thm}

\begin{thm}
	If T is a spanning tree of G and e is an edge in T, then T - e has 2 components. Moreover, if e' is in the cut induced by one of the components, then T - e + e' is also a spanning tree of G.
\end{thm}

\section{Characterizing Bipartite Graphs}

\begin{defn}[Odd cycle]
	An odd cycle is a cycle with an odd number of vertices.
\end{defn}

\begin{lemma}
	An odd cycle is not bipartite.
\end{lemma}

\begin{thm}
	A graph is bipartite iff it has no odd cycles.
\end{thm}

\section{Minimum Spanning Tree (MST)}

\begin{defn}[Minimal Spanning Tree]
	If each edge of a graph G has a certain weight function, then an MST is a spanning tree that has the smallest weight.
\end{defn}

$\textbf{Prim's Algorithm}$ \\
Let x be an arbitrary vertex in a connected graph G, and let T be the tree that consists only of x. \\
while(T is not a spanning tree of G) \{
	\begin{enumerate}
		\item Compare all edge cuts induced by V(T)
		\item Let e = uv be an edge cut with the smallest weight in the cut, where $u \in V(T) \land v \notin V(T)$
		\item Add v to V(T) and add e to E(T)
	\end{enumerate}
\}

\begin{thm}
	Prim's algorithm always produces an MST for G.
\end{thm}

\chapter{Planar Graphs}

\section{Planarity}

\begin{defn}[Planar, Planar Embedding / Planar Map]
	A graph G is planer if it has a drawing in the plane so that its edges intersect only at their ends, and so that no 2 vertices coincide. The actual drawing is called a plannar embedding of G, or a planar map.
\end{defn}

\begin{defn}[Faces]
	A planar embedding partitions the plane in to connected regions called faces. One of those regions, called the outer face, is unbounded.
\end{defn}

\begin{defn}[Boundary of a face, Adjacent Faecs, Boundary Walk]
	Consider a planar embedding of a connected graph G. The subgraph formed by the vertices and edges of a face is called the boundary of the face. We say that 2 faces are adjacent if they are incident with a common edge. As on moves around the perimeter of a face f, we may describe this as a closed walk, called the boundary walk of the face f.
\end{defn}

\begin{defn}[Degree of a face]
	Consider a planer embedding of a connected graph G with an arbitrary face f in G. We denote $w_f \equiv$ number of edges in the boundary walk of f, or the degree of the face f.
\end{defn}

\begin{thm}[colloquially the Faceshaking Lemma]
	If we have a planar embedding of a connected graph G with s faces $f_1, f_2, ..., f_s$, then
	\[
		\sum_{i=1}^{s}deg(f_i) = 2| E(G) |
	\]
\end{thm}

\begin{crly}
	If the connected graph G has a planar embedding with f faces, the average degree of a face in the embedding is
	\[
		\frac{2|E(G)|}{f}
	\]
\end{crly}

\section{Euler's Formula}

\begin{thm}[Euler's Formula]
	Let G be a connected graph with p vertices and q edges. If G has a planar embedding with f faces then
	\[
		p - q + f = 2
	\]
\end{thm}

\section{Stereographic Projection}

\begin{thm}
	A graph is planar iff it can be drawn on the surface of a sphere.
\end{thm}

\section{Plantonic Solids}

\begin{propo}
	There are only 5 platonic solids:
	\begin{enumerate}
		\item Tetrahedron
		\item Cube
		\item Octahedron
		\item Dodecahedron
		\item Icosahedron
	\end{enumerate}
\end{propo}

\begin{lemma}
	Let G be a planar embedding with p vertices, q edges and f faces, in which each vertex has degree $d \geq 3$ and each face has degree $d^* \geq 3$. Then $(d, d^*)$ is one of the five pairs
	\[
		\{(3, 3), (3, 4), (4, 3), (3, 5), (5, 3)\}
	\]
\end{lemma}

\begin{lemma}
	If G is platonic with p vertices, q edges and f faces, where each vertex has degreee d and each face has degree $d^*$, then
	\[
		q = \frac{2dd^*}{2d + 2d^* -dd^*}
	\]
	where $p=\frac{2q}{d}$ and $f = \frac{2q}{d^*}$
\end{lemma}

\begin{thm}
	There are exactly 5 platonic graphs.
\end{thm}

\section{Nonplanar graphs}

\begin{lemma}
	If G is connected and not a tree, then in a planar embedding G, the boundary of each face contains a cycle.
\end{lemma}

\begin{lemma}
	Let G be a planar embedding with p vertices and q edges. IF each face of G has degree at least $d^*$, then $(d^* - 2)q \leq d^*(p-2)$
\end{lemma}

\begin{thm}
	In a connected planar graph with $p \geq 3$ vertices and q edges, we have
	\[
		q \leq 3p - 6
	\]
	In a connected planar graph that is bipartite with similar traits,
	\[
		q \leq 2p - 4
	\]
\end{thm}

\begin{crly}
	$K_5$ is nonplanar.
\end{crly}

\begin{crly}
	A planar graph has a vertex of degree at most 5.
\end{crly}

\begin{lemma}
	$K_{3, 3}$ is nonplanar.
\end{lemma}

\section{Kuratowski's Theorem}

\begin{defn}[Edge Subdivision]
	Edge subdivision of a graph is obtained by replacing any number of edges in the graph by paths of length 1 or more, with new interval vertices.
\end{defn}

\begin{thm}[Kurotowski's Theorem]
	A graph is nonplanar iff it has a subgraph that is a edge subdivision of $K_5$ or $K_{3, 3}$.
\end{thm}

\section{Colouring and Planar Graphs}

\begin{defn}[Colouring]
	A k-colouring of a graph G is a function from V(G) to a set of size k (whose elements are called colours), so that adjacent vertices always have different colours. A graph with a k-colouring is called a k-colourable graph.
\end{defn}

\begin{thm}
	A graph is 2-colourable iff it is bipartite.
\end{thm}

\begin{thm}
	$K_n$ is n-colourable, and not k-colourable for any k < n.
\end{thm}

\begin{thm}
	Every planar graph is 6-colourable.
\end{thm}

\begin{defn}[Edge Contraction]
	Let G be a graph and let e = {x, y} be an edge of G. The graph G-e obatined from G by contracting the edge e is the graph with vertex set $V(G) - \{x, y\} \cup \{z\}$, where z is a new vertex, and edge set
	\[
		\Bigr\{\{u, v\} \in E(G) : \{u, v\}\cap\{x, y\}=\emptyset\Bigl\}\cup\Bigr\{\{u, z\}:u\notin\{x,y\},\{u, w\}\in E(G) \text{ for some } w\in\{x, y\}\Bigl\}
	\]
\end{defn}

\begin{thm}
	Every planar graph is 5-colourable.
\end{thm}

\begin{thm}
	Every planar graph is 4-colourable.
\end{thm}

\section{Dual Planar Graphs}

\begin{defn}[Dual]
	Given a connected planar embedding G, the dual $G^*$ is a planar embedding constructed as follows:\\
	\begin{enumerate}
		\item $G^*$ has one vertex in each face of G
		\item 2 vertices of $G^*$ are joined by an edge if the corresponding faces are adjacent
		\item The edge is drawn across the common boundary in G.
	\end{enumerate}
\end{defn}

\chapter{Matchings}

\section{Matching}

\begin{defn}[Matching]
	A matching in a graph G is a set of M edges of G such taht no 2 edges in M have a common end.
\end{defn}

\begin{defn}[Saturation]
	We say that a vertex v of G is saturated by M, or that M saturates v, if v is incident with an edge in M.
\end{defn}

\begin{defn}[Maximum Matching]
	The maximum matching of G is the largest matching in G.
\end{defn}

\begin{defn}[Perfect Matching]
	A maximum matching where the size of the matching is $\frac{p}{2}$ where p is the number of vertieces in the graph.
\end{defn}

\begin{remark}
	Not every graph has a perfect matching, especially when p is odd.
\end{remark}

\begin{defn}[Alternating Path]
	We say that a path $v_0v_1v_2\hdots v_n$is an alternating path with respect to a matching M if one of the following is true:
	\begin{itemize}
		\item $\{v_i, v_{i+1}\} \in M$ if i is even AND $\{v_i, v_{i+1}\} \notin M$ if i is odd.
		\item $\{v_i, v_{i+1}\} \in M$ if i is odd AND $\{v_i, v_{i+1}\} \notin M$ if i is even.
	\end{itemize}
\end{defn}

\begin{defn}[Augmenting Path]
	An augmenting path with respect to a matching M is an alternating path joining 2 distinct vertices neither of which is saturated by M.
\end{defn}

\begin{lemma}
	If M has an augmenting path, it is not a maximum matching.
\end{lemma}

\section{Covers}

\begin{defn}[Cover]
	A cover of a graph G is a set C of vertices such taht every edge of G has at least one end in C.
\end{defn}

\begin{lemma}
	If M is a matching of G and C is a cover of G, then $|M| \leq |C|$.
\end{lemma}

\begin{lemma}
	If M is a matching and C is a coevr and $|M| = |C|$, then M is a maximum matching and C is a minimum cover.
\end{lemma}

\section{König's Theorem}

\begin{thm}[König's Theorem]
	In a bipartite graph the maximum size of a matching is the minimum size of a cover.
\end{thm}

$\textbf{König's Algorithm}$ \\
const G = graph\\
let $M = \emptyset \quad$ // not necessarily empty\\
let A, B = bipartition of G\\
declare X, Y, pr()\\
while($|M| \neq |Y| \cup |A - X|$) \{
\begin{align*}
	\text{ let } &X = \{ u \in A : \text{ u is unsaturated by M } \}, \\
					   &Y = \emptyset, \\
					   &pr(v) = \text{ undefined } \forall v \in V(G);
\end{align*}

	$\quad$ for each $v \in B - Y$ with an edge uv where $u \in X$ \{\\
		$\text{ }\quad \quad$Y.push(v); \\
		$\text{ }\quad \quad$ set pr(v) = u;\\
		$ $\\
		$\text{ }\quad \quad$ if v is saturated \{\\
			$\text{ }\quad \quad \quad$ trace back (v, pr(v), pr(pr(v)), ...); \\
			$\text{ }\quad \quad \quad$ swap the augmenting path to get larger M;\\
			$\text{ }\quad \quad \quad$ continue while;\\
		$\text{ }\quad \quad$\}\\
	$\text{ }\quad$\}\\

	$\quad$ for each $v \in A - X$ with an edge uv where $u \in Y$ \{\\
		$\text{ }\quad \quad$X.push(v); \\
		$\text{ }\quad \quad$ set pr(v) = u; \\
	$\text{ }\quad$\}\\
\}\\
$ $\\
return M and $C = Y \cup (A - X)$

\section{Applications of König's Theorem}

\begin{defn}[Neighbour Set]
	Let G be a graph. Let $D \subseteq V(G)$. The neighbor set is
	\[
		N(D) := \{v \in V(G) : \exists u \in D, uv \in E(G)\}
	\]
\end{defn}

\begin{thm}[Hall's Theorem]
	A bipartite graph G with bipartition (A, B) has a matching saturating every vertex in A
	\[
		\iff \forall D \subseteq A \quad |N(D)| \geq |D|
	\]
\end{thm}
\end{document}

ext: tex


text:
\section{Symmetric-Key Encryption}\label{s:symmetric-key-encryption}
The simplest form of encryption, is the use of a symmetric key scheme. Such a scheme utilizes a secret key which is used to perform the mathematical operations of both encrypting and decrypting of a message.
The communicating parties must share the same key in order to communicate securely.
Symmetric-key algorithms are algorithms that use the same key for both encryption of the plaintext and decryption of the ciphertext.
The keys represent a shared secret between two or more parties that can be used to maintain a private information channel.
The requirement that both parties have access to the secret key is one of the main drawbacks of symmetric key encryption, in comparison to public-key encryption schemes that we expand in section \ref{s:public-key-encryption}.

More formally, given a plaintext $P$ and a secret key $K$, a ciphertext $C$ is produced such that:
\begin{equation}
  \label{eq:symmetric-key-encryption}
  \begin{aligned}
    C = Enc(P, K)\\
    P = Dec(C, K) = Dec(Enc(P, K), K)
  \end{aligned}
  \end{equation}
Where $Enc$ and $Dec$ are the \textit{Encryption} and \textit{Decryption} algorithms respectively.

max_stars_repo_name: jimouris/master-thesis

max_issues_repo_name: jimouris/master-thesis

max_forks_repo_name: jimouris/master-thesis


text:
\documentclass[letter,11pt,oneside]{article}

%%% (occur "\\(\\\\[a-z]*section\\|appendix\\|input\\|\\<include\\>\\)")

%%\documentclass[11pt,twocolumn]{article}
%%\usepackage[inline]{asymptote}   %% Inline asymptote diagrams
%%\usepackage{wglatex}             %% Use this one and kill others.
\usepackage{color}               %% colored letters {\color{red}{{text}}
\usepackage{fancyhdr}            %% headers/footers
%%\usepackage{fancyvrb}            %% headers/footers
\usepackage{datetime}            %% pick up tex date time
\usepackage{lastpage}            %% support page of ...lastpage
\usepackage{times}               %% native times roman fonts
\usepackage{textcomp}            %% trademark
\usepackage{amssymb,amsmath}     %% greek alphabet
\usepackage{parskip}             %% blank lines between paragraphs, no indent
\usepackage{shortvrb}            %% short verb use for tables
\usepackage{lscape}              %% landscape for tables.
\usepackage{longtable}           %% permit tables to span pages wg-longtable
\usepackage{url}                 %% Make URLs uniform and links in PDFs
\usepackage{enumerate}           %% Allow letters/decorations for enumerations
\usepackage{endnotes}            %% Enhance footnotes/endnotes
\usepackage{listings}            %% Make URLs uniform and links in PDFs
\pdfadjustspacing=1                %% force LaTeX-like character spacing
\usepackage{geometry}            %% allow margins to be relaxed
%%\usepackage{wrapfig}             %% permit wrapping figures.
%%\usepackage{subfigure}              %% images side by side.
\geometry{margin=1in}            %% Allow narrower margins etc.
\usepackage[T1]{fontenc}         %% Better Verbatim Font.
\renewcommand*\ttdefault{txtt}   %%
%%\usepackage{natbib}   %% bibitems

%% include background image (wg-document-page-background)

\usepackage{graphicx}            %% Include pictures into a document
%% (wg-texdoc-inserttikz)

\def\documentisdraft{NOTDRAFT}

%% (wg-texdoc-isdraft)
%% (wg-texdoc-insert-fancy-headers)

%%\usepackage[bookmarks]{hyperref} %% Make huperlinks within a PDF
%%\usepackage{makeidx}             %% Make an index uncomment following line
%%\makeindex                       %%.. yeah this one, too. index{key} in text
%%

\definecolor{verbcolor}{rgb}{0.6,0,0}
\definecolor{darkgreen}{rgb}{0,0.4,0}
\newcommand\debate[1]{\textcolor{darkgreen}{DEBATE: #1} \marginpar{\textcolor{red}{DEBATE} }}
\newcommand{\ltodo}[2]{\marginpar{\textcolor{red}{ACTION: #1}\endnote{#2}}}
\renewcommand{\thefigure}{\thesection-\arabic{figure}}
\newcommand{\menu}{\ensuremath{\;\rightarrow\;}}
%%(wg-add-inline-images)  %% add inline images to the mix

%%Begin User Definitions: Hint: ~/.latex.defs and  latex.defs
%%End User Definitions:
%%(wg-texdoc-adjust-paper-width)
%% (wg-texdoc-insert-hypersetup)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%% (wg-latex-pretty-title-page)
%% (wg-texdoc-titleblock)

\setcounter{section}{0}
\pagenumbering{arabic}

\ifx\documentisdraft\drafttest
\linenumbers    %%%%%%%%%%%%% DRAFT
\fi

\section{Useful Things}

ADS account.
\url{http://adsabs.harvard.edu/cgi-bin/nph-manage_account?man_cmd=new}

\appendix
\renewcommand \thesection{Appendix \Alph{section}}

\section{Installing}

Download ISIS
Save main zip file, unpack
run the setup script
download the isis library zip file to main directory
unpack the zip file.

\section{Libraries}

These libraries model main spectral types and vary key parameters
like metallicity, effective temperature, surface gravity. They
consider photospheres with balanced Local Thermodynamical Equilibrium
conditions. Other issues like binarity, proxcimity to hot stars,
extinction etc are not in the models.

-Pickles \cite{1998PASP..110..863P} 1998 131 observed flux calibrated stellar spectra
-Kurucz 1993 models and  Kurucz and Castelli ATLAS-9 and ATLAS-12 models
-- 1993 model
-- ATLAS-9
-- ATLAS-12
- MILES library
- Others (RAVE/SDSS/APOGEE I) etc.

%% use a bibitem approach to the references publications etc.
%% (wg-bibitem)

%%\clearpage
%%\addcontentsline{toc}{section}{References}
%%\renewcommand*{\refname}{My Bibliography and References}
%%\bibliographystyle{plain}	% bibliographystyle{apalike} and \usepackage{natbib}
%%\bibliography{MasterBib}	% expects file "MasterBib.bib"

%%\clearpage
%%\addcontentsline{toc}{section}{Index}
%%\printindex %% www.cs.usask.ca/resources/tutorials/latex/notes/toc-index.pdf

%%\begin{thebibliography}{80}
%%\usepackage{natbib}   %% bibitems
%%\end{thebibliography}

% /home/wayne/clones/isis/doc/GettingStarted.tex

%% (wg-texdoc-endnotes)
\end{document}
http://www.stsci.edu/hst/observatory/crds/pickles_atlas.html

Discussion about short comings of AAVSO database.
http://www.spectro-aras.com/forum/viewtopic.php?f=8&t=2264


text:
\documentclass[10pt,letterpaper]{article}
\input{settings}

\usepackage{soul}
\newcommand{\DIFadd}[1]{\textbf{#1}}
\newcommand{\DIFdel}[1]{\st{#1}}

\begin{document}
\vspace*{0.2in}

\begin{flushleft}
{\Large
\textbf\newline{Twelve Quick Tips for Software Design}
}
\newline
\\
{Greg Wilson}\textsuperscript{1{\ddag}}
\\
\bigskip
\textbf{1} Third Bit\\
{\ddag} Corresponding author, gvwilson@third-bit.com.
\end{flushleft}

\section*{Introduction}

Most people can lift one kilogram,
but would struggle to lift one hundred,
and could not lift a thousand without planning and support.
Similarly,
\DIFadd{many researchers who} can write a few lines of Python, R, or MATLAB to create a plot
struggle to create \DIFadd{programs that are} a few hundred lines long,
and \DIFadd{don't} know where to start
\DIFadd{designing an application made up of dozens or hundreds of files} or packages.

The core challenge is that
\emph{programming in the large} is qualitatively different from \emph{programming in the small}.
as the number of pieces in a program grows,
the number of possible interactions between those pieces grows much more quickly
because $N$ components can be paired in $N^2$ ways.
Programmers who don't manage this complexity
\DIFadd{invariably produce} software that behaves in unexpected (usually unfortunate) ways
and cannot be modified without heroic effort.

\DIFadd{This paper presents} a dozen tips that can help data scientists design large programs.
These tips are taken from published sources \DIFadd{like \cite{Kernighan1999,Budgen2020}},
the author's personal experience,
and discussions over thirty-five years with the creators of widely-used libraries and applications.
\DIFadd{They aren't always appropriate---for example,
short scripts written for exploratory data analysis
don't need to worry about unit testing---but
if you find yourself sketching data structures on the whiteboard,
thinking about how different configuration options interact,
or wondering how you're going to support old releases while working on the new one,
these tips may help.}

\begin{itemize}
  \itemsep0em
  \item[] Tip 1: design after the fact.
  \item[] Tip 2: design for people's cognitive capacity.
  \item[] Tip 3: design in coherent levels.
  \item[] Tip 4: design for evolution.
  \item[] Tip 5: group related information together.
  \item[] Tip 6: use common patterns.
  \item[] Tip 7: design for delivery.
  \item[] Tip 8: design for testability.
  \item[] Tip 9: design as if code was data.
  \item[] Tip 10: design graphically.
  \item[] Tip 11: design with everyone in mind.
  \item[] Tip 12: design for contribution.
\end{itemize}

\subsection*{Acknowledgments}

The author is grateful to Sam Albers,
Rebecca Barter,
John Blischak,
Neil Brown,
Matthias Bussonnier,
Daniel Chen,
Ildi Czeller,
Bradford Dykes,
Damien Irving,
\DIFadd{Peter Lin},
\DIFadd{Varun Lodaya},
Mandip Mistry,
\DIFadd{Shruti Muralidhar},
Julia Silge,
\DIFadd{Morgan Taschuk},
and Donny Winston
for \DIFadd{their feedback}.

\section*{Tip 1: design after the fact.}

When we are doing research,
we often don't know what the code should do tomorrow
until we've seen today's results.
It's therefore often pointless to invest as much in up-front planning for our software
as we would in drawing up blueprints for a building.
But this isn't a license to create a tangled mess:
we can and should make it \emph{\DIFadd{look}} as though we \DIFadd{had a plan}
so that the next person who has to read our code will be able to understand it \cite{Parnas1986}.

\emph{Refactoring} is the process of reorganizing or rewriting code
without changing its externally-visible behavior.
\cite{Fowler2018} describes common refactorings,
such as ``extract function''
(i.e., move some code out of the function \DIFadd{it is} in
and put it in a new function so that it can be called separately)
and ``combine parameters into object''
(which we we will revisit in Tip~5).
Just as the tidying steps in a data pipeline
either convert messy data to a tidy layout or move the data from one tidy layout to another \cite{Wickham2017},
most refactoring operations move code toward or between well-defined patterns \cite{Kerievsky2004}.

\begin{mdframed}
  \noindent
  Many designers explain the design of their software
  by recapitulating its history \cite{Brown2011,Brown2012}.
  This is sometimes called \emph{challenge and response}:
  the only way to understand why something works the way it does
  is to understand the problems that existed at the time it was written
  and the tools that were available then.
  Neither programming languages nor existing graphical notations (Tip~10)
  are particularly good at capturing this,
  and while many tools have been written for tracking and managing requirements,
  none have worked well enough that the average programmer would voluntarily adopt them.
\end{mdframed}

\section*{Tip 2: design for people's cognitive capacity.}

Just as computers have hard drives and RAM,
human brains have long-term and short-term memory \cite{Hermans2021}.
We only have conscious access to short-term memory,
and it is much smaller than most people realize:
early estimates were that the average person could hold
$7{\pm}2$ items in short-term memory at once \cite{Miller1956},
and more recent estimates put its capacity closer to $4{\pm}1$.

\DIFadd{This limitation leads to the} second tip for software design:
to ensure that the number of \DIFadd{things} someone has to remember at any time
in order to understand the code
\DIFdel{they're looking at} fits in short-term memory.
For example,
if a function takes 37 parameters
then the odds are slim
that someone will remember them all and put them in the right order
without a lot of trial and error.
Breaking the function into pieces,
each of which takes only a handful parameters,
\DIFadd{reduces} the \emph{cognitive load}.
Similarly,
defining default values for \DIFdel{most or all of the} parameters
\DIFadd{(e.g., ``black'' as a default font color)}
allows people not to worry about them most of the time.

A complementary approach is to create families of functions
that all take similar inputs and outputs
and then combine them using \emph{pipes}.
The pipe operator is one of Unix's key contributions to computing \cite{Kernighan2019},
and the idea has been adopted by many other programming systems,
including the ``tidyverse'' family of packages in R \cite{Wickham2017}.
Where a mathematician would write $f(g(h(x)))$,
a programmer using pipes would write $h(x) | g | f$
so that the functions' names appear in the order in which they are applied.
As a result,
the reader only has to hold one piece of information in their head at a time,
which frees up more space for worrying about other things.

\section*{Tip 3: design in coherent levels.}

Another tip for designing functions is that
each function should be short, shallow, and single-purpose,
i.e.,
it should implement a single mental operation
so that it only takes up a single slot in short-term memory.
The easiest way to check if this tip is being followed
is to read the function aloud
and ask whether all the steps are at the same conceptual level.
For example,
if I read this Python function aloud:

\begin{lstlisting}
 def main():
     config = buildConfiguration(sys.argv)
     state = initializeState(config)
!\colorbox{gray!30}{~~~~~while config.currentTime < config.haltTime:}!
         updateState(config, state)
     report(config, state)
\end{lstlisting}

\noindent
the highlighted comparison of the current time to the halting time in the \texttt{while} loop
feels like it's at a lower level of detail than the function calls.
I would probably replace the comparison with a function called something like \texttt{stillEvolving}:

\begin{lstlisting}
 def main():
     config = buildConfiguration(sys.argv)
     state = initializeState(config)
!\colorbox{gray!30}{~~~~~while stillEvolving(config, state):}!
         updateState(config, state)
     report(config, state)
\end{lstlisting}

\noindent
This rewrite saves the reader
from having to jump between two different levels of detail
while they're trying to figure out what this function does.

\begin{mdframed}
  \noindent
  While the final design should be levelled,
  the process used to create it almost certainly won't be.
  Studies of expert designers have found that
  they constantly drill down from high-level ideas to concrete implications
  to find out whether their plan will work or not \cite{Schon1984}.
  \DIFdel{To the best of the author's knowledge,
  no currently-available software design tools or methodologies do a better job of capturing these ``why not'' insights
  than blog posts or lengthy comments in code.}
\end{mdframed}

\section*{Tip 4: design for evolution.}

Replacing a low-level test with a function as shown above also makes future evolution easier.
If we decide that the simulation should run until a specified time
\emph{or} until its state has stabilized,
we can make that change in the \texttt{stillEvolving} function
without modifying anything else.

Hiding details like this is another general rule of software design.
Software changes over time because our problems change,
our environments change,
and because our skills improve.
A good design makes independent evolution of parts easier:
basically,
a fix \emph{here} shouldn't require changes \emph{there}.
More realistically,
a change in one place should only require a small number of changes
in a few predictable places.

Software designers achieve this \DIFadd{in two ways.}
\emph{Information hiding} means
putting the data \DIFdel{that} each part of a program needs \DIFdel{to do its job} in one place,
and only accessing \DIFadd{that data} through a small set of functions.
Doing this \DIFdel{makes no difference to the computer---by the time it runs the program,
it's all just a bunch of instructions---but
people need to understand the program ,
not execute it.}
\DIFadd{reduces cognitive load
by allowing people to focus on one part of the program at a time.}
\DIFadd{\emph{Loose coupling} means making those parts independent of one another so that}
they can be combined in many different ways
\DIFdel{because none of them depends on the internals of any of the others.}
\DIFadd{Again,
one of the reasons the Unix command line and R's tidyverse have been so successful
is how easily their elements can be rearranged to do different things}.

Programmers usually implement these principles
by separating \emph{interface} from \emph{implementation}.
The interface specifies what a piece of software can do;
its implementation is how it achieves that,
and no other piece of software should be tied to its implementation details.
The goal is to enable the construction of software components
that can be mixed and matched in the way that USB interfaces allow pieces of hardware to be combined.
Many of the more advanced features of programming languages exist to support or enforce this,
such as being able to derive classes from one another in object-oriented languages like Python,
or creating generic functions that do the same logical thing in different ways for different types of data in languages like R and Julia.

\emph{Design by contract} is one way to enforce this idea \cite{Meyer1994}.
Any function \DIFdel{or method} can be characterized by
the \emph{pre-conditions} that must be true of its inputs in order for it to run
and the \emph{post-conditions} that it guarantees will be true of its output.
For example,
a function \DIFadd{might require} that its input \DIFdel{must} be an array of numbers in sorted order,
and its post-condition might be that \DIFdel{the value it returns is one of those elements.}
\DIFadd{it returns the median of those numbers.
If the input isn't an array, doesn't contain numbers, or isn't sorted,
the function may not work;
if the input satisfies all three conditions,
the output is guaranteed to be the median.
}

If design by contract is followed,
then a \DIFadd{new version of} this function can \DIFadd{only} \emph{weaken} the pre-conditions,
i.e.,
place \DIFadd{\emph{fewer} restrictions on what it accepts.}
This rule ensures that the new function will be able to handle
everything that the old one could:
if the new version placed extra restrictions,
such as requiring all the numbers in the input to be positive as well as sorted,
then the new version might reject some inputs that the original version would accept.

\DIFadd{Similarly,
a new version of the function can only \emph{strengthen} the post-conditions,
i.e., make \emph{more}} guarantees about its outputs
so that the values the new version produces are a subset of the values the old version could produce.
For example,
if the old version of the function returned positive numbers,
the new version could guarantee to return positive numbers in the range zero to one,
but could \DIFadd{\emph{not} return negative numbers as well as positive ones.}
This rule ensures that anything using the old function's output
will still be able to handle everything the new one produces.
\DIFdel{Continuing with the previous example,
a new function's pre-conditions could be that it takes any array of numbers,
not just one that is sorted,
and that it produces the largest element in the array.}

\section*{Tip 5: group related information together.}

If several things are closely related or frequently occur together,
our brains combine them into a ``chunk''
that only takes up one slot in short-term memory \cite{Thalmann2019}.
We can aid this by combining related values into data structures.
For example,
instead of storing the X, Y, and Z coordinates of points separately like this:

\begin{lstlisting}
def enclose(x0, y0, z0, x1, y1, z1, nearness):
    ...
\end{lstlisting}

\noindent
we can store each point's coordinates in \DIFdel{a structure} \DIFadd{an object}
and write our code like this:

\begin{lstlisting}
def enclose(p0, p1, nearness):
    ...
\end{lstlisting}

\noindent
This allows us to thing about each point as one ``thing''.
Where we need the individual coordinates,
we can refer to them as \texttt{p0.X}, \texttt{p0.Y}, and so on.

Grouping related information together also aids code evolution (Tip~4).
If, for example, we decide to use radial coordinates instead of Cartesian coordinates,
we can change how points are represented without changing most of the functions that pass them around.

\section*{Tip 6: use common patterns.}

Some chunks appear so often that we call them ``patterns'' and give them names.
\DIFdel{For example,
parasitism and symbiosis take many forms,
and it's impossible to draw a precise boundary between them,
but they are powerful ideas that help us make sense of the world.}
Good programmers use \emph{design patterns} to structure their code,
both to reduce the amount of thinking they have to do
and because these patterns have proven to be useful in the past.
Learning patterns helps make someone a better programmer,
i.e.,
there is causation, not just correlation \cite{Tichy2010}.
Conforming to widely-understood patterns also makes code more comprehensible,
just as dividing this paper into sections and a bibliography
that are consistent with what you've read before
makes it easier to read.

\begin{mdframed}
  \noindent
  \DIFadd{Patterns don't have to be precisely defined in order to be useful.
  A classic example is concept of a porch \cite{Brand1995}:
  two people might disagree over whether a specific structure is one or not,
  but the idea is still useful.}
\end{mdframed}

Patterns can be found at all scales of programming.
For example,
introductory programming courses often show a pattern for finding the ``most valuable''
\DIFdel{variables} \DIFadd{elements of a collection, such as the minimum or maximum} \cite{Byckling2005},
\DIFadd{while ``filter the rows, group them by category, and calculate a summary for each group''
is a common pattern in introductory data analysis.
In more advanced courses students may be introduced to object-oriented design patterns
for traversing complex data structures
or using one set of objects to hide the details of how another set of objects work
\cite{Gamma1994,Freeman2020}}.

But design patterns can be a mixed blessing.
First,
our brains try so hard to match inputs to patterns that they will sometimes misclassify things.
For example,
it once took me the better part of an hour to spot the error in this code:

\begin{lstlisting}
 for (i=0; i<a.width; i++) {
     for (j=0; i<a.height; j++) {
         a[i][j] = cos(abs(a[i][j]) - lemaitre(b_norm, a[j][i]))
     }
 }
\end{lstlisting}

The problem is in the second line,
which mistakenly uses the variable \texttt{i} where it should use the variable \texttt{j}.
I couldn't find the mistake because
the code was so close to what it should have been that my brain ``corrected'' what my eyes were seeing,
and because I assumed that since the third line was the most complicated,
the error had to be there.

\begin{mdframed}
  In the same way that you shouldn't write a math problem with a function \texttt{x} of variable \texttt{g},
  you should use the same naming conventions as your peers
  to make your code easier to read.
  It doesn't matter what these are,
  any more than it matters whether you spell ``color'' the correct way or the British way;
  what matters is the predictability that comes from consistency.
\end{mdframed}

This example illustrates a corollary to Tip~2:
we should write programs that maximize the ratio of unique code to boilerplate.
In most modern languages,
the five lines shown above can be written as:

\begin{lstlisting}
a = cos(abs(a) - lemaitre(b_norm, a.transpose()))
\end{lstlisting}

\noindent
This version is probably as efficient as the first,
but it is much easier to read and therefore much less likely to mislead.

\section*{Tip 7: design for delivery.}

Developer operations (DevOps) has become a buzzword in the last few years.
Like ``data science'' or ``computational thinking'',
the term is popular because people can use it to mean whatever they want,
but the core idea is a good one:
\DIFdel{automate} \DIFadd{managing} compilation, packaging, distribution, deployment, and monitoring
\DIFdel{by writing software that operates on or monitors other software}
\DIFadd{to make them faster and more reliable}
\cite{Kim2016,Forsgren2018}.
Automating these tasks pays off many times over,
but only if you design things so that they can be automated.
\cite{Taschuk2017} lays out some rules for doing this,
and a few others include:

\begin{enumerate}

\item
  Use the same tools to build packages as everyone else who uses your language,
  e.g., \texttt{pip} for Python or \texttt{devtools} for R.

\item
  Organize your source files in the way your build system expects
  so that those tools can do their job.

\item
  Use a logging library rather than \texttt{print} commands
  to report what your program is doing and any errors it has encountered.
  Logging libraries allow you to enable and disable certain categories of messages selectively.
  This is very useful during development,
  but even more so in production,
  since it lets whoever is using your software turn reporting on
  without having to rebuild anything.

\end{enumerate}

\section*{Tip 8: design for testability.}

Research software is notoriously difficult to test \cite{Hook2009,Kanewala2014},
in part because its developers often don't know precisely what output the code is supposed to produce.
(As a frustrated chemist once said to the author,
``If I knew what the right answer was, I'd have published it already.'')
It \emph{is} possible to test the ``other 90\%'' of a typical data science application---the parts that
parse input files,
clean up messy data,
and so on,
but only if those parts are designed with testing in mind.

\emph{Legacy code} is software that we're afraid to try to modify
because it's hard to understand and things will break unexpectedly.
A comprehensive set of tests makes us less afraid \cite{Feathers2004},
but we can only create those tests if we design the software in testable pieces.
We can check how well we've done this by asking:

\begin{itemize}
\item
  How easy is it to create a \emph{fixture}
  (i.e., the input that a test runs on)?
\item
  How easy is it to invoke just the behavior we want?
\item
  How easy is it to check the result?
\item
  How easy is it to figure out what ``right'' is?
\item
  How easy is it to delete the feature?
\end{itemize}

For example,
suppose that our program uses species data stored in a large database
\DIFadd{that takes several seconds to query.
In order to make our program easier to test,
we can create a second version of the lookup function
that returns hard-coded values for
the two or three species used in testing.}
\DIFadd{When the program is running in production,
it uses the original function;
when we are testing,
we swap out that function and use the testing version instead.}
This trick only works if \emph{all} requests for species information
\DIFadd{are made via that function,
but doing this} ensures that if we want to change how information is looked up in future
we \DIFdel{are} \DIFadd{can be} certain that we'll only have to modify one small piece of code.

\section*{Tip 9: design as if code was data.}

The insight on which all modern computing is based is that
code is just another kind of data.
Programs are just text files,
\DIFdel{and once a program is loaded into memory it is just another data structure:
instead of interpreting its bytes as characters or pixels,
we interpret them as instructions,
but they're still just bytes.}
\DIFadd{which means we can process it like any other piece of text.}
Examples of this include:

\begin{itemize}
\item
  style-checking tools that check that the layout, variable names, and other properties
  conform to coding standards;
\item
  documentation tools that extract specially-formatted comments
  and create cross-referenced manual pages; and
\item
  indexing and navigation tools that enable us to jump directly to
  the definition of a function or variable.
\end{itemize}

\DIFdel{It is the second insight---the fact that a function in memory}
\DIFadd{Similarly, once a program is loaded into memory it} is just another
\DIFdel{kind of data---that has the most impact on design.
Just a few of the ways it shows up are} \DIFadd{data structure:
instead of interpreting its bytes as characters or pixels,
we interpret them as instructions,
but they're still just bytes.
This fact impacts design in many ways:}

\begin{itemize}
\item
  Passing functions as arguments to other functions
  so that common operations only have to be written once.
\item
  Storing functions in data structures
  so that new operations can be added to a program
  without changing any of the pre-existing code.
\item
  Loading modules based on configuration parameters
  (as in the earlier example of getting species information).
\end{itemize}

For example,
if we want to count the number of positive values in an array,
we can write:

\begin{lstlisting}
def count_positive(array):
    number = 0
    for value in array:
        if value >= 0:
            number = number + 1
    return number
\end{lstlisting}

If we want to count the number that are negative,
we could write a \texttt{count\_negative} function that differed by only one character
(replacing the \texttt{>} with \texttt{<}).
Alternatively,
we could write a generic function like this:

\begin{lstlisting}
def count_interesting(array, test):
    number = 0
    for value in array:
        if test(value):
            number = number + 1
    return number
\end{lstlisting}

\noindent
then put each test in a function like this:

\begin{lstlisting}
def is_positive(value):
    return value >= 0
\end{lstlisting}

\noindent
and then write something like:

\begin{lstlisting}
count_interesting(pressures, is_positive)
\end{lstlisting}

Many features in modern languages,
such as lazy evaluation in R or decorators in Python,
leverage this insight,
and taking advantage of it can make code much smaller
and easier to understand---but only if you remember that
what is powerful in the hands of experts is spooky action-at-a-distance for novices.

\begin{mdframed}
  The best balance between abstraction and detail
  depends on how much people already know.
  For a novice,
  too many low-level details obscure the meaning,
  while too much abstraction makes it impossible to figure out what's actually going on
  (Figure~\ref{comprehension}).
  As that person gains experience
  they become better able to synthesize meaning from detail
  and translate generalities into specifics,
  but their optimum balance also shifts.
  Software that is easiest for them to understand may not be optimal for someone else.
\end{mdframed}

\begin{figure}
  \centering
  \includegraphics{comprehension.pdf}
  \caption{Comprehension curves for novices and experts}
  \label{comprehension}
\end{figure}

\section*{Tip 10: design graphically.}

Many formal graphical notations for software have been designed over the years.
The most famous is the Unified Modeling Language (UML),
but in practice it is taught more often than it is used,
and when it \emph{is} used,
it is usually not in the ways its creators intended \cite{Petre2013}.

However,
many programmers do sketch when they're designing,
and these sketches do help them design.
These sketches are usually not meant as blueprints:
instead,
they help people \emph{externalize cognition},
i.e.,
get their thoughts out where they can see them \cite{Cherubini2007,Petre2016}.
Among the drawings that working programmers often find helpful are:

\begin{itemize}
\item
  flowcharts, which are unfairly maligned \cite{Scanlan1989}
  (Figure~\ref{flowchart});
\item
  entity-relationship diagrams showing how database tables relate to one another
  (Figure~\ref{er-diagram});
\item
  concept maps showing how the designer thinks about the overall problem
  (Figure~\ref{concept-map}); and
\item
  many others,
  such as dataflow diagrams,
  system architecture diagrams showing the major components of an application,
  and use case maps that show how activity flows through an architecture \cite{Reekie2006}.
\end{itemize}

\begin{figure}
  \centering
  \includegraphics[scale=0.6]{flowchart.pdf}
  \caption{Flowchart}
  \label{flowchart}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[scale=0.6]{er-diagram.pdf}
  \caption{Entity-relationship diagram}
  \label{er-diagram}
\end{figure}

\begin{figure}
  \centering
  \includegraphics[scale=0.6]{concept-map.pdf}
  \caption{Concept map}
  \label{concept-map}
\end{figure}

\section*{Tip 11: design with everyone \DIFdel{in mind}.}

If the last few years have taught us anything about software,
it's that fairness, privacy, and security cannot be sprinkled on after the fact.
For example,
if a program is initially designed in a way that allows every user to see everyone else's data,
adding privacy controls later will be expensive and almost certainly buggy.
Programmers call this the \emph{Principle of Least Privilege}:
every component in the system should require as few permissions as possible
for as short as possible.

But there is much more to safety-conscious design than just data protection.
For example,
if an application requires users to change their password every few weeks,
\emph{security fatigue} will soon set in
and people will choose less and less secure passwords \cite{Smalls2021}.
Similarly,
programs should not email files to people:
doing that trains them to open attachments,
which is a common channel for attacks.
And \DIFdel{every application should} \DIFadd{in many jurisdictions application must} allow people to erase data,
which means its data structures and database tables have to be designed to allow for actual erasure,
not just ``mark as inactive''.

Accessibility also can't be sprinkled onto software after the fact.
Close your eyes and try to navigate your institution's website.
Now imagine having to do that all day, every day.
Imagine trying to use a computer when your hands are crippled by arthritis.
Better yet, don't imagine it:
have one of your teammates tape some popsicle sticks to your fingers so you can't bend them
and see what it's like to reply to an email.

Making software accessible doesn't just help people with obvious disabilities:
the population is aging,
and everything you do to help people who are deaf also helps people
who are gradually losing their hearing \cite{Johnson2017}.
\cite{UKHO} is a good short guide for accessible design:
each poster in this series lays out a few simple do's and don'ts that will help make your software accessible
to people who are neurodivergent,
use screen readers,
are dyslexic,
have physical or motor challenges,
or are hard of hearing.

\section*{Tip 12: design for contribution.}

Study after study has shown that diversity improves outcomes in fields from business to healthcare
because many perspectives make for fewer errors \cite{Gompers2018,Gomez2019}.
Good design makes it easier for people who aren't already immersed in your project
to figure out where and how they can contribute to it \cite{Sholler2019},
but just as good programmers consider things like packaging and deployment in their designs,
so too do they think about the factors that influence contribution:

\begin{itemize}

\item
  Software licensing is a design issue,
  since a program can't use libraries whose licenses are incompatible with its own.
  Many designers therefore prefer permissive licenses like the MIT License
  to maximize the number of people who will be able to take advantage of their work.

\item
  Applications that support plug-ins---i.e.,
  that allow people to write small modules that the main program can load and use---are
  often easier for newcomers to contribute to.
  Similarly,
  libraries with strong and consistent conventions for passing data
  (like Unix command-line tools or R's tidyverse functions)
  enable people to start with small contributions.

\end{itemize}

\DIFadd{Designing with contribution in mind is also essential to designing inclusively.
Many well-meaning attempts at inclusive design fall short
because the designers don't involve the people they intend to help in the process.
Nobody can simultaneously be an expert on programming,
a research domain,
and the needs of multiple overlapping diversities.
Asking for help early on maximizes your chance to get things right;
designing in ways that make contribution easy maximizes your chances
that people who know more than you will share their insights.}

\section*{\DIFdel{Conclusion}}

\DIFdel{Figure~REMOVED is a De Rosa SK Pininfarina bicycle.
It is not a work of art,
but it \emph{was} carefully designed,
and as a result it can be analyzed and appreciated esthetically.
Tips like the ones in this paper
may one day help us create data analyses that also deserve to be called ``beautiful''.}

\bibliography{12-design}

\end{document}


text:
\section{Programming and Advanced LaTeX}
% What does it mean to program in LaTeX

\subsection{Basic Macros}
\input{sections/programming/Basic_macros}

\subsection{Common Programming Features in LaTeX}
\input{sections/programming/Common_features}

\subsection{Advanced Features} \label{section:programming/advancedFeatures}
\input{sections/programming/Advanced_features}

\subsection{Synthesising \LaTeX{} From Other Languages}
\input{sections/programming/Other_languages}

\subsection{Calling External Programs}
\input{sections/programming/Common_features}

\subsection{Programming Tikz Pictures}
\input{sections/programming/Tikz}

\subsection{Writing Packages}
\input{sections/programming/Packages}

\subsection{Writing Classes}
\input{sections/programming/Classes}

\subsection{Breaking \LaTeX}
\input{sections/programming/Breaking}


text:
\addtocontents{toc}{\protect\pagebreak}
\chapter{Library of transformations}
\label{chapter:library_of_transformations}

The previous chapter introduced a framework to reason about composable model transformations formally. This framework does allow one to create models from scratch by iteratively adding different elements. Although the previous chapter did introduce the needed definitions and theorems to explain this framework, it did not discuss how to apply the framework in practice. In order to apply the framework, the framework needs two essential ingredients. First of all, the framework needs a set of proven model transformations that can be used to build models iteratively. Finally, these proven model transformations must be applied within the framework to create some larger model.

In this chapter, a set of small model transformations between GROOVE and Ecore is introduced. These model transformations can be used within the framework as `building blocks', which are used to create larger models. The goal of this chapter is to show possible model transformations that can be applied with the framework from the previous chapter, in order to validate the framework using an application of these transformations. Therefore, the set of model transformations presented in this chapter will be non-exhaustive. It will only include transformations that are necessary for the application, as well as some transformations that show the potential of the framework.

This chapter is split into two parts. Within the first part, a set of model transformations between type models and type graphs is introduced. This set is used within the second part, where a set of model transformations between instance models and instance graphs is introduced. However, before any of these sets is discussed, some definitions used throughout this chapter are introduced.

\input{tex/05_library_of_transformations/01_definitions.tex}
\input{tex/05_library_of_transformations/02_type_level_transformations.tex}
\input{tex/05_library_of_transformations/03_instance_level_transformations.tex}


text:
\section{Related Work}
\label{relatedwork}

This chapter will present different ideas and projects which have
served as motivation and inspiration not only for the \textit{Drift} language
but for the entire \textit{Drift} project.

First two talks by Rich Hickey will be presented and the relevant
aspects will be extracted. The first talk discusses the necessity
and design of a ``Language of the System'', especially in the
context of highly distributed systems and the second talk
introduces the concepts of \textit{place oriented programming}
and \textit{value oriented programming} with an emphasis on
the importance of immutable data in programming language design.

Then, as a representative of the \textit{functional programming}
approach, \textit{Cuneiform}, a functional scientific workflow language
and \textit{HiWay}, its distributed execution engine
will be introduced. Both of which are being developed here at the
Humboldt University of Berlin at the department of bioinformatics (WBI)
and have served as a major source of inspiration and opposing
concepts.

After that, core concepts of UNIX-like operating system design
and more importantly of the UNIX shell \textit{bash} as one representative
of a typicall UNIX shell are being introduced. Especially a
mapping between the language constructs of the \textit{bash} shell
and core concepts of functional programming languages will be
presented.

Furthermore a new distributed data base project will be introduced
which tries to combine the functional programming concepts of
immutable data and value orientation with the distributed data base
context of data accretion, distributed logging, time series data
and streaming.

Then the source code version control system \textit{git} will
be introduced because it shows how a seemingly stateful system
on the user facing side can be implemented on top of an immutable,
append only file system of objects addressed by hashes of hashes.

At last a talk by Bret Victor will be summarized in which he presents
his idea of \textit{immediate feedback} in the context of programming
and tooling for programming. In this talk he showcases multiple
prototypes which show how to interactively visualize code and how
this could be used to aid the process of developing software.
The most relevant feature presented will be a \textit{time bar}
which allows to interactively go back and forth through past
states of the code and the actively running program.

max_stars_repo_name: flange/drift-dev

max_issues_repo_name: flange/drift-dev

max_forks_repo_name: flange/drift-dev


text:
\chapter{Randomized Strategies}

\section{Mastermind Satisfiability Problem}

Mastermind Satisfiability Problem is NP-Complete.

[know nothing about this]

max_stars_repo_name: bijaykoirala/mastermind-strategy

max_issues_repo_name: bijaykoirala/mastermind-strategy

max_forks_repo_name: bijaykoirala/mastermind-strategy


text:
% $Id$ %
\chapter{The Main Menu}
\section{\label{ref:main_menu}Introducing the Main Menu}
\screenshot{main_menu/images/ss-main-menu}{The main menu}{}
The \setting{Main Menu} is the screen from which all of the Rockbox functions
can be accessed. This is the first screen you will see when starting Rockbox.
To return to the \setting{Main Menu},
  \nopt{ONDIO_PAD}{press the \ActionStdMenu{} button.}%
  \opt{ONDIO_PAD}{hold the \ButtonMenu{} button.}%

All settings are stored on the unit. However, Rockbox does not access
the \disk{} solely for the purpose of saving settings. Instead, Rockbox will
save settings when it accesses the \disk{} the next time, for example when
refilling the music buffer or navigating through the \setting{File Browser}.
Changes to settings may therefore not be saved unless the \dap{} is shut down
safely (see \reference{ref:Safeshutdown}).

\section{Navigating the Main Menu}
  \begin{btnmap}
    \ActionStdNext
        &
    \opt{HAVEREMOTEKEYMAP}{\ActionRCStdNext
        &}
    Select the next option in the menu.\newline
    Inside a setting, increase the value or choose next option.
        \\
    %
    \ActionStdPrev
        &
    \opt{HAVEREMOTEKEYMAP}{\ActionRCStdPrev
        &}
    Select the previous option in the menu.\newline
    Inside a setting,decrease the value or choose previous option.
        \\
    %
    \ActionStdOk
        &
    \opt{HAVEREMOTEKEYMAP}{\ActionRCStdOk
        &}
    Select option.
        \\
    %
    \ActionStdCancel
        &
    \opt{HAVEREMOTEKEYMAP}{\ActionRCStdCancel
        &}
    Exit menu or setting, or move to parent menu.
        \\
  \end{btnmap}

\section {Recent Bookmarks}
\screenshot{main_menu/images/ss-list-bookmarks}%
{The list bookmarks screen}{}
If the \setting{Save a list of recently created bookmarks} option is enabled
then you can view a list of several recent bookmarks here and select one to
jump straight to that track.\\*

 \note{Bookmarking only works when tracks are launched from the file browser,
        and does not currently work for tracks launched via the
        database. In addition, they do not currently work with dynamic
        playlists.\\*}

  \begin{btnmap}
    \ActionStdNext
    \opt{HAVEREMOTEKEYMAP}{& \ActionRCStdNext}
    & Select the next bookmark.\\
    %
    \ActionStdPrev
    \opt{HAVEREMOTEKEYMAP}{& \ActionRCStdPrev}
    & Select the previous bookmark.\\
    %
    \ActionStdOk
    \opt{HAVEREMOTEKEYMAP}{& \ActionRCStdOk}
    & Resume from the selected bookmark.\\
    %
    \ActionStdCancel
    \opt{HAVEREMOTEKEYMAP}{& \ActionRCStdCancel}
    & Exit Recent Bookmark menu.\\
    %
    \nopt{GIGABEAT_S_PAD}{\ActionBmDelete
    \opt{HAVEREMOTEKEYMAP}{& \ActionRCBmDelete}
    & Delete the currently selected bookmark.\\}
    %
    \ActionStdContext
    \opt{HAVEREMOTEKEYMAP}{& \ActionRCStdContext}
    & Enter the context menu for the selected bookmark.\\
  \end{btnmap}

There are two options in the context menu:\\*

  \setting{Resume} will commence playback of the currently selected bookmark entry.

  \setting{Delete} will remove the currently selected bookmark entry from the list.\\*

This entry is not shown in the \setting{Main Menu} when the option is off
(the default setting).  See \reference{ref:Bookmarkconfigactual}
for more details on configuring bookmarking in Rockbox.

\section{Files}
Browse the files on your \dap{} (see \reference{ref:file_browser}).

\section{Database}
Browse by the meta-data in your audio files (see \reference{ref:database}).

\section{Now Playing/Resume Playback}
Go to the \setting{While Playing Screen} and resume if music playback is
stopped or paused and there is something to resume (see \reference{ref:WPS}).

\section{Settings}

The \setting{Settings} menu allows you to set or adjust many parameters that
affect the way your \dap{} works. There are many submenus for different
parameter areas. Every time you are setting a value of a parameter, and that
value is selected from a list of some predefined available values, you can press
\ActionStdContext, and the selection cursor will jump to the default value for
the parameter. You can then confirm or cancel the value. This is useful if you
have changed the value of the parameter from the default to some other value and
would like to restore the default value.

\subsection{Sound Settings}
The \setting{Sound Settings} menu offers a selection of sound properties you may
change to customise your listening experience. The details of this menu are covered
in \reference{ref:configure_rockbox_sound}.

\subsection{Playback Settings}
The \setting{Playback Settings} menu allows you to configure settings related
to audio playback. The details of this menu are covered
in \reference{ref:configure_rockbox_playback}.

\subsection{General Settings}
The \setting{General Settings} menu allows you to customise the way Rockbox looks
and the way it plays music. The details of this menu are covered in
\reference{ref:configure_rockbox_general}.

\subsection{Theme Settings}
The \setting{Theme Settings} menu contains options that control the visual
appearance of Rockbox. The details of this menu are covered in
\reference{ref:configure_rockbox_themes}.

\opt{recording}{
\subsection{Recording Settings}
The \setting{Recording Settings} menu allows you to configure settings related
to recording. The details of this menu are covered in detail in
\reference{ref:Recordingsettings}.
}

\subsection{Manage Settings}
The \setting{Manage Settings} option allows the saving and re-loading of user
configuration settings, browsing the hard drive for alternate firmwares, and finally
resetting your \dap{} back to initial configuration.
%
The details of this menu are covered in
\reference{ref:manage_settings}.

\opt{recording}{\input{main_menu/recording_screen.tex}}

\opt{radio}{\input{main_menu/fmradio.tex}}

\section{\label{ref:playlistoptions}Playlists}
  This menu allows you to work with playlists. Playlists can be created in
  three ways. Playing a file in a directory causes all the files in it
  to be placed in a playlist. Playlists can be created manually by
  either using the  \setting{Context Menu} (see \reference{ref:Contextmenu}) or using
  the \setting{Playlist} menu. Both automatically and manually created
  playlists can be edited using this menu.

\begin{description}
\item[Create Playlist:]
  Rockbox will create a playlist with all tracks in the current directory
and all sub-directories. The playlist will be created one directory level ``up''
from where you currently are.

\item[View Current Playlist:]
  Displays the contents of the playlist currently stored in memory.

\item[Save Current Playlist:]
  Saves the current dynamic playlist, excluding queued tracks, to the
specified file. If no path is provided then playlist is saved to the current
directory.

\item[View Catalogue:]
  Provides a simple interface to maintain
  several playlists (see \reference{ref:working_with_playlists}).
\end{description}

\section{Plugins}
  With this option you can load and run various plugins that have been
written for Rockbox. There are a wide variety of these supplied with
Rockbox, including several games, some impressive demos and a number of
utilities. A detailed description of the different plugins is to be found in
\reference{ref:plugins}.

\section{\label{ref:Info}System}
\opt{player}{Use the MINUS and PLUS keys to step through several
pages of information.}

\begin{description}
\item[Rockbox Info:]
  Displays some basic system information. This is, from top to bottom,
  the amount of memory Rockbox has available for storing music (the buffer).
  The battery status.
\opt{multivolume}{%
  Memory size and amount of free space on the two data volumes, this info is
  given separately for internal memory (\emph{Int}) and for a plugged in
  memory card
  \opt{ondio}{(\emph{MMC})}
  \opt{sansa,e200v2,fuze,fuzev2,clipplus,clipzip}{(\emph{MSD})}.
}%
\nopt{multivolume}{Hard disk size and the amount of free space on the disk.}

\item[Credits:]
  Display the list of contributors.

\item[Running Time:]
  Shows the runtime of your \dap{} in hours, minutes and seconds.
  \begin{description}
    \item[Running Time:]
        This item shows the cumulative overall runtime of your \dap{} since you
        either disconnected it from charging (in Rockbox) or manually
        reset this item. A manual reset is done through pressing any button,
        followed by pressing \ActionStdOk{}.
    \item[Top Time:]
        This item shows the cumulative overall runtime of your \dap{} since you
        last manually reset this item. A manual reset is done through pressing
        any button, followed by pressing \ActionStdOk{}.
  \end{description}

\item[Debug (Keep Out!):]
  This sub menu is intended to be used \emph{only} by Rockbox developers.
  It shows hardware, disk, battery status and other technical information.
  \warn{It is not recommended that users access this menu unless instructed to
  do so in the course of fixing a problem with Rockbox. If you think you have
  messed up your settings by use of this menu please try to reset \emph{all}
  settings before asking for help.}
\end{description}

\opt{player}{
  \section{Shutdown}
  This menu option saves the Rockbox configuration and turns off the hard
  drive before shutting down the machine. For maximum safety this procedure
  is recommended when turning off the \dap. (There is a very small risk
  of hard disk corruption otherwise.) See \reference{ref:Safeshutdown}
  for more details.
}

\opt{quickscreen}
{
\section{\label{ref:QuickScreen}Quick Screen}
  Although the \setting{Quick Screen} is accessible from nearly everywhere,
  not just the \setting{Main Menu}, it is worth mentioning here.  It allows
  rapid access to your four favourite settings.  The default settings are
  \setting{Shuffle} (\reference{ref:PlaybackSettings}),
  \setting{Repeat} (\reference{ref:PlaybackSettings}) and the
  \setting{Show Files} (\reference{ref:ShowFiles}) options, but almost all
  configurable options in Rockbox can be placed on this screen.  To change the
  options, navigate through the menus to the setting you want to add and press
  \ActionStdContext.  In the menu which appears you will be given options
  to place the setting on the \setting{Quick Screen}.

  Press \ActionStdQuickScreen{} to access it and \ActionQuickScreenExit{} to exit.
  The direction buttons will modify the individual setting values as indicated
  by the arrow icons. Please note that the settings at opposite sides of the
   screen cycle through the available options in opposite directions.
   Therefore if you select the same setting at e.g. the top and bottom of the
   quickscreen, then pressing up and down will cycle through this setting in
   opposite directions.
}

\section{\label{ref:MainMenuShortcuts}Shortcuts}

This menu item is a container for user defined shortcuts to files, folders or
settings. With a shortcut,
\begin{itemize}
  \item A file can be ``run'' (i.e. a music file played, plugin started or
        a \fname{.cfg} loaded)
  \item The file browser can be opened with the cursor positioned at
        a specified file or folder
  \item A file's or folder's ``Current Playlist'' context menu item can
        be displayed
  \item A setting can be configured (any which can be added to the
        \setting{Quick Screen})
  \item A debug menu item can be displayed (useful for developers mostly)
\opt{rtc}{
  \item The current time can be spoken
}
  \item The sleep timer can be configured
  \item The \dap{} can be turned off
\end{itemize}

\note{Shortcuts into the database are not possible}

Shortcuts are loaded from the file \fname{/.rockbox/shortcuts.txt} which lists
each item to be displayed. Each shortcut looks like the following:

\begin{example}
    [shortcut]
    type: <shortcut type>
    data: <what the shortcut actually links to>
    name: <what the shortcut should be displayed as>
    icon: <number of the theme icon to use (see \wikilink{CustomIcons})>
    talkclip: <filename of a talk clip to speak when voice menus are enabled>
\end{example}

Only ``type'' and ``data'' are required (except if type is ``separator'' in which case
``data'' is also not required).

Available types are:
\begin{description}
\item[file] \config{data} is the name of the file to ``run''
\item[browse] \config{data} is the file or the folder to open the file browser at
\item[playlist menu] \config{data} is the file or the folder to open the
  ``Current Playlist'' context menu item on
\item[setting] \config{data} is the config name of the setting you want to change
  (see \reference{ref:config_file_options} for the list of the possible settings)
\item[debug] \config{data} is the name of the debug menu item to display
\item[separator] \config{data} is ignored; \config{name} can be used to display text,
  or left blank to make the list more accessible with visual gaps
\item[time] \config{data} needs to be \opt{rtc}{either ``talk'' to talk the time, or }``sleep X''
  where X is the number of minutes to run the sleep timer for (0 to disable). \config{name}
  is required for this shortcut type.
\item[shutdown] \config{data} is ignored; \config{name} can be used to display text
\end{description}

If the name/icon items are not specified, a sensible default will be used.

\note{For the ``browse'' type, if you want the file browser to start \emph{inside}
a folder, make sure the data has the trailing slash (i.e \fname{/Music/} instead of
\fname {/Music}). Without the trailing slash, it will cause the file browser to open
with \fname{/Music} selected instead.}

The file \fname{shortcuts.txt} can be edited with any text editor. Most items can
also be added to it through their context menu item ``Add to shortcuts''.
A reboot is needed for manual changes to \fname{shortcuts.txt} to be applied.

Shortcuts can be manually removed by selecting the one you wish to remove and pressing
\ActionStdContext{}.

max_stars_repo_name: Rockbox-Chinese-Community/Rockbox-RCC

max_issues_repo_name: Rockbox-Chinese-Community/Rockbox-RCC

max_forks_repo_name: Rockbox-Chinese-Community/Rockbox-RCC


text:
\section{conclusion}

Part of conclusion

max_stars_repo_name: zijuexiansheng/latex-examples

max_issues_repo_name: zijuexiansheng/latex-examples

max_forks_repo_name: zijuexiansheng/latex-examples


text:
Mover Transport (MVT) Package information is read from the file that is specified by ``MVT6'' as the file type.  Only one MVT Package can be specified for a GWT model.

The MVT Package is used to route solute mass according to flows from the GWF Water Mover (MVR) Package.  This MVT Package must be activated by the user if the MVR Package was active for the GWF Model.  Flows from the GWF MVR Package must be available to the GWT model either through activation of a GWF-GWT Exchange or through specification of ``GWFMOVER'' in the PACKAGEDATA block of the GWT FMI Package.

\vspace{5mm}
\subsubsection{Structure of Blocks}
\lstinputlisting[style=blockdefinition]{./mf6ivar/tex/gwt-mvt-options.dat}

\vspace{5mm}
\subsubsection{Explanation of Variables}
\begin{description}
\input{./mf6ivar/tex/gwt-mvt-desc.tex}
\end{description}

\vspace{5mm}
\subsubsection{Example Input File}
\lstinputlisting[style=inputfile]{./mf6ivar/examples/gwt-mvt-example.dat}