text:
\subsection{Methods}
This section decribes all the functions in the file ``ptwXY\_method.c''.

\subsubsection{ptwXY\_clip}
This function clips the y-values of \highlight{ptwXY} to be within the range \highlight{rangeMin} and \highlight{rangeMax}.
Points will be added to insure that the curve within the \highlight{rangeMin} and \highlight{rangeMax} is not altered.
\setargumentNameLengths{allocatedSize}
\CallingC{fnu\_status ptwXY\_clip(}{statusMessageReporting *smr,
    \addArgument{ptwXYPoints *ptwXY,}
    \addArgument{double rangeMin,}
    \addArgument{double rangeMax );}}
    \argumentBox{smr}{The \highlight{statusMessageReporting} instance to record errors.}
    \argumentBox{ptwXY}{A pointer to the \highlight{ptwXYPoints} object.}
    \argumentBox{rangeMin}{All y-values in \highlight{ptwXY} will be greater than or equal to this value.}
    \argumentBox{rangeMax}{All y-values in \highlight{ptwXY} will be less than or equal to this value.}

\subsubsection{ptwXY\_thicken}
This function thicken the points in \highlight{ptwXY} by adding points as determined by the input parameters.
\setargumentNameLengths{sectionSubdivideMax}
\CallingC{fnu\_status ptwXY\_thicken(}{statusMessageReporting *smr,
    \addArgument{ptwXYPoints *ptwXY,}
    \addArgument{int sectionSubdivideMax,}
    \addArgument{double dDomainMax,}
    \addArgument{double fDomainMax );}}
    \argumentBox{smr}{The \highlight{statusMessageReporting} instance to record errors.}
    \argumentBox{ptwXY}{A pointer to the \highlight{ptwXYPoints} object.}
    \argumentBox{sectionSubdivideMax}{The maximum number of points to add between two initial consecutive points.}
    \argumentBox{dDomainMax}{The desired maximum absolute x step between consecutive points.}
    \argumentBox{fDomainMax}{The desired maximum relative x step between consecutive points.}
This function adds points so that $x_{j+1} - x_j \le \highlight{dDoaminMax}$ and $x_{j+1} / x_j \le \highlight{fDomainMax}$ but will never add
more then \highlight{sectionSubdivideMax} points between any of the orginal points. If \highlight{sectionSubdivideMax} $<$ 1
or \highlight{dDomainMax} $<$ 0 or \highlight{fDomainMax} $<$ 1, the error \highlight{nfu\_badInput} is return.

\subsubsection{ptwXY\_thin}
This function returns a clone of \highlight{ptwXY} with its points thinned (i.e., removed) while maintaining interpolation
\highlight{accuracy} with \highlight{ptwXY}.
\setargumentNameLengths{accuracy}
\CallingC{ptwXPoints *ptwXY\_thin(}{statusMessageReporting *smr,
    \addArgument{ptwXYPoints *ptwXY,}
    \addArgument{double accuracy );}}
    \argumentBox{smr}{The \highlight{statusMessageReporting} instance to record errors.}
    \argumentBox{ptwXY}{A pointer to the \highlight{ptwXYPoints} object.}
    \argumentBox{accuracy}{The accuracy of the thinned \highlight{ptwXYPoints} object.}
    \vskip 0.05 in \noindent

\subsubsection{ptwXY\_thinDomain}
This function returns a clone of \highlight{ptwXYPoints} whose x-values are those of \highlight{ptwXY} but thinned so that
\begin{equation}
    x[i+1] - x[i] \ge 0.5 \times \rm{epsilon} \times (x[i+1] + x[i]) \ \ \ .
\end{equation}
\setargumentNameLengths{accuracy}
\CallingC{ptwXPoints *ptwXY\_thinDomain(}{statusMessageReporting *smr,
    \addArgument{ptwXYPoints *ptwXY,}
    \addArgument{double epsilon );}}
    \argumentBox{smr}{The \highlight{statusMessageReporting} instance to record errors.}
    \argumentBox{ptwXY}{A pointer to the \highlight{ptwXYPoints} object.}
    \argumentBox{epsilon}{The epsilon to thin the x-values to.}
    \vskip 0.05 in \noindent

\subsubsection{ptwXY\_trim}
This function removes all extra 0.'s at the beginning and end of \highlight{ptwXY}.
\CallingC{fnu\_status ptwXY\_trim(}{statusMessageReporting *smr,
    \addArgument{ptwXYPoints *ptwXY );}}
    \argumentBox{smr}{The \highlight{statusMessageReporting} instance to record errors.}
    \argumentBox{ptwXY}{A pointer to the \highlight{ptwXYPoints} object.}
    \vskip 0.05 in \noindent
If \highlight{ptwXYPoints} starts (ends) with more than two 0.'s then all intermediary are removed.

\subsubsection{ptwXY\_union}
This function creates a new \highlight{ptwXY} instance whose x-values are the union of \highlight{ptwXY1}'s and \highlight{ptwXY2}'s
x-values. The domains of \highlight{ptwXY1} and \highlight{ptwXY2} do not have to be mutual.
\setargumentNameLengths{unionOptions}
\CallingC{ptwXYPoints *ptwXY\_union(}{statusMessageReporting *smr,
    \addArgument{ptwXYPoints *ptwXY1,}
    \addArgument{ptwXYPoints *ptwXY2,}
    \addArgument{int unionOptions );}}
    \argumentBox{smr}{The \highlight{statusMessageReporting} instance to record errors.}
    \argumentBox{ptwXY1}{A pointer to a \highlight{ptwXYPoints} object.}
    \argumentBox{ptwXY2}{A pointer to a \highlight{ptwXYPoints} object.}
    \argumentBox{unionOptions}{Specifies options (see below).}
    \vskip 0.05 in \noindent
If an error occurs, NULL is returned. The default behavior of this function can be altered by setting bits
in the argument \highlight{unionOptions} . Currently, there are two bits, set via the C marcos
\highlight{ptwXY\_union\_fill} and \highlight{ptwXY\_union\_trim},
that alter \highlight{ptwXY\_union}'s behavior. The macro \highlight{ptwXY\_\-union\_\-fill} causes all y-values of the new \highlight{ptwXYPoints} object
to be filled via the y-values of \highlight{ptwXY1}; otherwise, the y-values are all zero.
Normally, the new \highlight{ptwXYPoints} object's x domain spans all x-values
in both \highlight{ptwXY1} and \highlight{ptwXY2}. The macro \highlight{ptwXY\_\-union\_\-trim} limits the x domain to the common x domain
of \highlight{ptwXY1} and \highlight{ptwXY2}.

The returned \highlight{ptwXYPoints} object will always contain no points in the \highlight{overflowPoints} region.

\subsubsection{ptwXY\_scaleOffsetXAndY}
This function scales and offset the x-values and y-values.
\CallingC{nfu\_status ptwXY\_scaleOffsetXAndY(}{statusMessageReporting *smr,
    \addArgument{ptwXYPoints *ptwXY1,}
    \addArgument{double domainScale,}
    \addArgument{double domainOffset,}
    \addArgument{double rangeScale,}
    \addArgument{double rangeOffset );}}
    \argumentBox{smr}{The \highlight{statusMessageReporting} instance to record errors.}
    \argumentBox{domainScale}{The scale for the x-values.}
    \argumentBox{domainOffset}{The offset for the x-values.}
    \argumentBox{rangeScale}{The scale for the y-values.}
    \argumentBox{rangeOffset}{The offset for the y-values.}


text:
\documentclass[a4paper,man,natbib]{apa6}
\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}

% Common Packages - Delete Unused Ones %
\usepackage{setspace}
\usepackage{amsmath}
% End Packages %

\title{Exercise Assignment 4}
\shorttitle{ES4}
\author{Brandon Hosley}
\date{2018 09 17}
\affiliation{Mike Davis}

%\abstract{}

\begin{document}
	\maketitle
	\singlespacing
	\subsection{3.4 c)}
	\textbf{Convert $[1011]_{2}$ from binary to decimal, assuming unsigned binary.} \\
	$1011_{2} = 11_{10}$
	\subsection{3.4 e)}
	\textbf{Convert $[11111]_{2}$ from binary to decimal, assuming unsigned binary.} \\
	$11111_{2} = 31_{10}$
	\subsection{3.13 a)}
	\textbf{Write the polynomial representation of $29.458_{10}$} \\
	$(2)10^{1}+(9)10^{0}+(4)10^{-1}+(5)10^{-2}+(8)10^{-2}$
	\subsection{3.13 c)}
	\textbf{What is the decimal value of $1011.100101_{2}$} \\
	$1011.100101_{2} = 11.65625_{10}$
	\subsection{3.16 a)}
	\textbf{Convert $[51]_{10}$ to binary using nine-bit two's compliment.} \\
	$51_{10} = 0 0011 0011_{2}$
	\subsection{3.16 e)}
	\textbf{Convert $[-256]_{10}$ to binary using nine-bit two's compliment.} \\
	$-256_{10} = 1 0000 0000_{2}$
	\subsection{3.20 c)}
	\textbf{Perform a binary addition, assuming nine-bit two's compliment. Show the effect on the status bits:} \\
	1 0001 1011 \\
	\noindent\underline{ADD 1 0101 0100} \\
	0 0110 1111 \\
	N = 1 \\
	Z = 0 \\
	V = 1 \\
	C = 1
	\newpage
	\subsection{3.20 e)}
	\textbf{Perform a binary addition, assuming nine-bit two's compliment. Show the effect on the status bits:} \\
	0 0011 0100 \\
	\noindent\underline{ADD 0 1101 0010} \\
	1 0000 0110 \\
	N = 0 \\
	Z = 0 \\
	V = 1 \\
	C = 0
	\subsection{3.21 c)}
	\textbf{With two's complement binary representation what is the range of numbers in binary and decimal notation for: a four-bit cell} \\
	A four bit cell has: \\
	$range_{2} = 1000$ to $0111$ \\
	$range_{10} = -8$ to $7$
	\subsection{3.21 d)}
	\textbf{With two's complement binary representation what is the range of numbers in binary and decimal notation for: a five-bit cell} \\
	A five-bit cell has: \\
	$range_{2} = 1 0000$ to $0 1111$ \\
	$range_{10} = -16$ to $15$

	\newpage
	\nocite{warford10}
	\bibliography{ComputerArchitecture} %link to relevant .bib file
	\bibliographystyle{apacite}

\end{document}

ext: tex

max_stars_repo_name: bhosley/Schoolwork

max_issues_repo_name: bhosley/Schoolwork

max_forks_repo_name: bhosley/Schoolwork


text:
\chapter{Horizontal explicit virtical implicit}
\label{chap:hevi}
{\bf \Large
\begin{tabular}{ccc}
\hline
  Corresponding author & : & Seiya Nishizawa\\
\hline
\end{tabular}
}

\section{Equations}

\begin{align}
  \frac{\partial G^{\frac{1}{2}}\rho}{\partial t}
  &= -\frac{\partial J_{33}G^{\frac{1}{2}}\rho w}{\partial \xi} + G^{\frac{1}{2}}S_\rho, \\
  \frac{\partial G^{\frac{1}{2}}\rho w}{\partial t}
  &= -\frac{\partial J_{33}G^{\frac{1}{2}}p}{\partial \xi} -G^{\frac{1}{2}}\rho g + G^{\frac{1}{2}}S_{\rho w}, \\
  \frac{\partial G^{\frac{1}{2}}\rho\theta}{\partial t}
  &= -\frac{\partial J_{33}G^{\frac{1}{2}}\rho w\theta}{\partial \xi} + G^{\frac{1}{2}}S_{\rho\theta}, \\
  p &= P_{00}\left(\frac{R\rho\theta}{P_{00}}\right)^{c_p/c_v},
\end{align}
where
\begin{align}
  G^{\frac{1}{2}}S_\rho
  &= - G^{\frac{1}{2}}\frac{\partial \rho u}{\partial x}
     - G^{\frac{1}{2}}\frac{\partial \rho v}{\partial y} \nonumber\\
  &= - \frac{\partial G^{\frac{1}{2}}\rho u}{\partial x^*}
     - \frac{\partial G^{\frac{1}{2}}\rho v}{\partial y^*}
     - \frac{\partial J_{13}G^{\frac{1}{2}}\rho u + J_{23}G^{\frac{1}{2}}\rho v}{\partial \xi}, \\
  G^{\frac{1}{2}}S_{\rho w}
  &= - G^{\frac{1}{2}}\frac{\partial u\rho w}{\partial x}
     - G^{\frac{1}{2}}\frac{\partial v\rho w}{\partial y}
     - G^{\frac{1}{2}}\frac{\partial w\rho w}{\partial z} \nonumber\\
  &= - \frac{\partial G^{\frac{1}{2}}u\rho w}{\partial x^*}
     - \frac{\partial G^{\frac{1}{2}}v\rho w}{\partial y^*}
     - \frac{\partial}{\partial \xi}(J_{13}G^{\frac{1}{2}}u\rho w + J_{23}G^{\frac{1}{2}}v\rho w + J_{33}G^{\frac{1}{2}}w\rho w), \\
  G^{\frac{1}{2}}S_{\rho\theta}
  &= - G^{\frac{1}{2}}\frac{\partial u\rho\theta}{\partial x}
     - G^{\frac{1}{2}}\frac{\partial v\rho\theta}{\partial y} \nonumber\\
  &= - \frac{\partial G^{\frac{1}{2}}u\rho\theta}{\partial x^*}
     - \frac{\partial G^{\frac{1}{2}}v\rho\theta}{\partial y^*}
     - \frac{\partial J_{13}G^{\frac{1}{2}}u\rho\theta+J_{23}G^{\frac{1}{2}}v\rho\theta}{\partial \xi}.
\end{align}

\section{Descritization}

For the temporal discritization, backward temporal integrations are employed for the terms related to acoustic wave in vertical direction.
\begin{align}
  \frac{\rho^{n+1}-\rho^n}{\Delta t}
  &= -G^{-\frac{1}{2}}\frac{\partial}{\partial \xi}\{J_{33}G^{\frac{1}{2}}(\rho w)^{n+1}\} + S_\rho^n, \\
  \frac{(\rho w)^{n+1}-(\rho w)^n}{\Delta t}
  &= -G^{-\frac{1}{2}}\frac{\partial}{\partial \xi}(J_{33}G^{\frac{1}{2}}p^{n+1}) -g\rho^{n+1} + S_{\rho w}^n, \\
  \frac{p^{n+1} - p^n}{\Delta t}
  &\sim \frac{c_p^n}{c_v^n} \frac{p^n}{(\rho\theta)^n}\frac{\partial \rho\theta}{\partial t}, \\
  \frac{\partial \rho\theta}{\partial t}
  &= -G^{-\frac{1}{2}}\frac{\partial}{\partial \xi}\{J_{33}G^{\frac{1}{2}}\theta^n (\rho w)^{n+1}\} + S_{\rho\theta}^n.
\end{align}
Note that the pressure equation is linealized.

Eliminating $p^{n+1}, (\rho\theta)^{n+1}$, and $\rho^{n+1}$, the Helmholtz equation for $(\rho w)^{n+1}$ is obtained:
\begin{align}
  &
  (\rho w)^{n+1}
  - \frac{\Delta t^2 g}{G^{\frac{1}{2}}}\frac{\partial}{\partial \xi} \{J_{33}G^{\frac{1}{2}}(\rho w)^{n+1}\}
  - \frac{\Delta t^2}{G^{\frac{1}{2}}}\frac{\partial}{\partial \xi}\left(J_{33}\frac{c_p^n p^n}{c_v^n (\rho\theta)^n}\frac{\partial J_{33}G^{\frac{1}{2}}\theta^n (\rho w)^{n+1}}{\partial \xi}\right) \nonumber\\
  &= (\rho w)^n
  - \frac{\Delta t}{G^{\frac{1}{2}}}\frac{\partial}{\partial \xi}\left\{J_{33}G^{\frac{1}{2}}p^n\left(1+\frac{\Delta t c_p^n S_{\rho\theta}^n}{c_v^n (\rho\theta)^n}\right)\right\}
  - \Delta t g (\rho^n + \Delta t S_\rho^n)
  + \Delta t S_{\rho w}^n.
\end{align}

Vertical differencials are discritized as follows:
\begin{align}
&
  (\rho w)_{k+1/2}^{n+1}
  -\frac{\Delta t^2 g}{(\Delta z_{k+1} + \Delta z_k) G^{\frac{1}{2}}_{k+1/2}}
  \left\{J_{33}G^{\frac{1}{2}}(\rho w)^{n+1}_{k+3/2}
        -J_{33}G^{\frac{1}{2}}(\rho w)^{n+1}_{k-1/2}\right\}
    \nonumber\\ &
  - \frac{\Delta t^2}{\Delta z_{k+1/2} G^{\frac{1}{2}}_{k+1/2}}
  \left\{
    \left(J_{33}\frac{c_pp}{c_v\rho\theta}\right)_{k+1}\frac{
    J_{33}G^{\frac{1}{2}}(\rho w)_{k+3/2}\hat{\theta}_{k+3/2}-J_{33}G^{\frac{1}{2}}(\rho w)_{k+1/2}\hat{\theta}_{k+1/2}}{\Delta z_{k+1}} \right.\nonumber\\&\:\:\:\:\:\:\:\:\:\:\:\:\:\:\left.
    -\left(J_{33}\frac{c_pp}{c_v\rho\theta}\right)_k\frac{
    J_{33}G^{\frac{1}{2}}(\rho w)_{k+1/2}\hat{\theta}_{k+1/2}-J_{33}G^{\frac{1}{2}}(\rho w)_{k-1/2}\hat{\theta}_{k-1/2}}{\Delta z_k}\right\} \nonumber\\
  &=
  (\rho w)_{k+1/2}^n \nonumber\\&
  -\frac{\Delta t}{\Delta z_{k+1/2} G^{\frac{1}{2}}_{k+1/2}} \left\{
    J_{33}G^{\frac{1}{2}} p_{k+1}\left(1+\frac{\Delta tc_pS_{\rho\theta}}{c_v\rho\theta}\right)_{k+1}
  - J_{33}G^{\frac{1}{2}} p_k   \left(1+\frac{\Delta tc_pS_{\rho\theta}}{c_v\rho\theta}\right)_k \right\}\nonumber\\ &
  -\frac{\Delta t g}{2} \left\{ (\rho+\Delta t S_\rho)_{k+1}+(\rho+\Delta t S_\rho)_k\right\} + \Delta t S_{\rho w},
\end{align}
where
\begin{equation}
  \hat{\theta}_{k+1/2} = \frac{1}{12}\left(-\theta_{k+2}+7\theta_{k+1}+7\theta_k-\theta_{k-1}\right).
\end{equation}

Finally we obtained
\begin{align}
  &-\frac{1}{G^{\frac{1}{2}}_{k+1/2}}\left\{
    \frac{\hat{\theta}_{k+3/2}}{\Delta z_{k+1/2}}A_{k+1} + B_{k+1/2}
  \right\} (\rho w)_{k+3/2}^{n+1} \\
  &+ \left\{ 1 + \frac{\hat{\theta}_{k+1/2}}{\Delta z_{k+1/2} G^{\frac{1}{2}}_{k+1/2}}(A_{k+1} + A_k)  \right\} (\rho w)_{k+1/2}^{n+1} \\
  &- \frac{1}{G^{\frac{1}{2}}_{k+1/2}}\left\{
  \frac{\hat{\theta}_{k-1/2}}{\Delta z_{k+1/2}}A_k - B_{k+1/2}
  \right\} (\rho w)_{k-1/2}^{n+1} \\
  &= C_{k+1/2},
\end{align}
where
\begin{align}
  A_k &= \frac{\Delta t^2 J_{33}G^{\frac{1}{2}} }{\Delta z_k}\left(J_{33}\frac{c_pp}{c_v\rho\theta}\right)_k, \\
  B_{k+1/2} &= \frac{\Delta t^2 g J_{33}G^{\frac{1}{2}}}{\Delta z_{k+1}+\Delta z_k}, \\
  C_{k+1/2} &=
  (\rho w)_{k+1/2}^n \nonumber \\&
  -\Delta t\frac{
  J_{33}G^{\frac{1}{2}}p_{k+1}\left(1+\Delta t\frac{c_pS_{\rho\theta}}{c_v\rho\theta}\right)_{k+1}
  - J_{33}G^{\frac{1}{2}} p_k\left(1+\Delta t\frac{c_pS_{\rho\theta}}{c_v\rho\theta}\right)_k}{\Delta z_{k+1/2} G^{\frac{1}{2}}_{k+1/2}} \nonumber\\ &
  -\Delta t g \frac{(\rho+\Delta t S_\rho)_{k+1}+(\rho+\Delta t S_\rho)_k}{2} + \Delta t S_{\rho w}.
\end{align}


text:
\begin{appendices}
  \chapter{Complete Match Transcript}
  \chapter{2004 Gaming Journal Excerpts}
  \chapter{Coding Journal Excerpts}
  \chapter{Web Resources}
\end{appendices}
\clearpage

max_stars_repo_name: tphummel/tetris-latex

max_issues_repo_name: tphummel/tetris-latex

max_forks_repo_name: tphummel/tetris-latex


text:
\section{Introduction and Motivation}
\label{sec:intro}
Everyday, millions of people access online communities and social networks, producing
a huge amount of data. This data, if properly analyzed, can be exploited in many different ways.
In particular, in this work we focus on Twitter, a social network where the main
content produced by users are tweets. Tweets are short texts, up to 280 characters,
that are usually written by people to share with their followers something they think to be
relevant. Tweets can contain, for instance, funny jokes, special personal events or facts
and opinions about current news. The latter are particularly important,
because they reflect a part of the public opinion on recent events.
Therefore, they can be exploited, for example,
by politicians to gain consensus or by social networks or other online platforms to
recommend contents about the most trending topics to better engage their users.
Another example is that by observing which concepts are frequently mentioned together, we could
identify the spread of some fake news. Also, trending topics
may be a good indicator of how a TV series has been welcomed by the public, and
film companies can regulate their investments accordingly.

The purpose of this work is to identify which topics become popular many times
over time.
% The purpose of this work is to identify
% an effective method to identify consistent topics.

We define a topic as a set of terms, that can be words, hashtags
or another person's username.
One could think that a trending
topic is a topic that appears many times in the tweets of dataset, as in a typical
market-basket scenario, where we have many baskets, in this case represented by
tweets, each of which contains a small set of items, in this case represented by terms,
and we are asked to identify the most frequent combinations of items appearing together
in many baskets.
However, in the context of Twitter, tweets have also associated a timestamp,
that corresponds to the date and time the tweet has been posted.

Considering this, topics may be appear many times in some intervals of time,
when they are trending, while being less frequent in others.
Our objective is to identify popular consistent topics in time, i.e.\ topics that
are frequent in many periods of time.
In the next sections we will define more formally the problem
and show a way to approach it. This procedure will then be evaluated and results will
be analyzed.


text:
\documentclass[a4paper, 11pt, english]{article}
\author{Thomas Cuvillier}
\usepackage{amsmath, amssymb, enumerate, hyperref}
\usepackage[style=alphabetic]{biblatex}
\usepackage[a4paper]{geometry}
\usepackage[all]{xy}
\usepackage{listings}

\bibliography{researchproposal}{}
%\newtheorem{thm}{Theorem}
%\newtheorem*{lem}{Lemma}
%\newtheorem*{clm}{Claim}
%\newtheorem*{conj}{Conjecture}
%\newtheorem*{cor}{Corollary}
%\newtheorem*{prop}{Proposition}
%\newtheorem*{defn}{Definition}
%\newtheorem*{rem}{Remark}
\title{Millr}

\newcommand{\field}{\mathsf{f}}
\newcommand{\getter}{get}
\newcommand{\setter}{set}
\newcommand{\getField}{\mathsf{getField}}
\newcommand{\setField}{\mathsf{putField}}
\newcommand{\method}{method}
\newcommand{\methodBis}{method'}
\newcommand{\arr}{\mathsf{arr}}
\newcommand{\new}{\mathsf{new}}
\newcommand{\inherits}{\triangleleft}
\newcommand{\obj}{\mathsf{Object}}
\newcommand{\ArrayWrapper}{\mathsf{ArrayWrapper}}
%\newcommand{\object}{\mathsf{Object}}
\begin{document}

\maketitle

\section{Motivations}

Speak about mokapot. Goal
\begin{itemize}
\item to make every operations on object a method Call
\item All classes created at compile time.
\item Allow creations of standin (all methods overridable)
\item Hide the use of standin instead of original objects.
\end{itemize}

\section{Millr in the ideal world}

\subsection{Field access}

\textit{
Transforming direct field access thanks to getter and setter.
Talk about the difference between hiding and and overriding, and what it implies for the names of the method.}

Millr replaces every instruction in the bytecode that access or changes the state of an object with an appropriate method call. This transformation happens as follows. For each field $\field$ of a class, two methods are created $\getter$ and $\setter$, corresponding to getter and setter respectively. Each $\getField$ - $\setField$in the bytecode instruction is replaced with an appropriate method call.
\begin{tabular}{ll}
$x.f$ & $\rightarrowtail x.\getter_\field()$. \\
$x. f = e$ & $ \rightarrowtail x.\setter_\field( e)$
\end{tabular}

Due to the semantics of java, one must be particularly careful in picking up name for the getter-setter methods. Indeed, if a class $A$ inherits another class $B$, and $A$ contains a field $\field$ with same name as another one in $\field'$ in $B$, then $\field$ will \enquote{hide} $\field'$. On the other hand, if $A$ has a method $\method$ with same name as a method $\methodBis$ from $B$ (and this method is visible from $A$), then $\method$ will override $\methodBis$. However, the semantics of overriding and hiding are different.

For instance, let us consider classes A and B as follows.
\begin{lstlisting}
class A{
   Object field = new Object();
   Object getField(){
 	return field;
 }
}
\end{lstlisting}
and
\begin{lstlisting}
class B extends A{
	Object field = new Object();
	Object getField(){
		return field;
	}
}
\end{lstlisting}
Then the output of the following code:
\begin{lstlisting}
A a = new B();
return a.field.equals(a.getField());
\end{lstlisting}
is false. Indeed, a is perceived of type A, and then the field that will be accessed will be the one of A. On the other hand, the method getField in A will be overriden, and hence getField() with return the field from B.
Therefore, we in order for the semantic to work, we need to consider two injective functions:
\begin{itemize}
\item $\mathsf{nameGetter}$ : (NameOfClass * NameOfField) $\rightarrow$ String.
\item $\mathsf{nameSetter}$ : (NameOfClass * NameOfField) $\rightarrow$ String
\end{itemize}
whose duty are self-explanatory.

\subsection{Array access}

We transform each array with an ArrayWrapper. An ArrayWrapper is a class that contains an array state, and access to this array is done through getters and setters methods, as specified in the following code. Creation of an array can be done thanks to reflection, with as arguments the dimension of the array, as well as the class. A naive ArrayWrapper class could be like this.

\begin{lstlisting}

class ArrayWrapper<T>{

	public ArrayWrapper(Class<? extends T> class, int args){
		 array = reflect.
	}

	T[] array;

	public T get(int i){
		return array[i];
	}

	public void set(int i, T o){
		array[i] = o;
	}

}
\end{lstlisting}

However, we have to take account two constraints:
\begin{enumerate}
\item Multi-dimensional arrays.
\item The ability to return the internal array, with "original types".
\end{enumerate}

These two constraints forces us to abandon generic types. Indeed, an array of type $[[Object$, would now become of type $ArrayWrapper<ArrayWrapper<Object>>$, hence obtaining an internal array of type $[ArrayWrapper<Object>$, whereas we would like to interface with an internal array of type $[[Object$.

Therefore, we need to remove to remove generics, and have more sophisticated getter and setters to take care of possible ArrayWrapper types. We need two abilities:
\begin{enumerate}
\item to transform an array into an arrayWrapper.
\item That this transformation respects reference equality.
\end{enumerate}

\begin{lstlisting}

class ArrayWrapper{

	private static Map<Object[], ArrayWrapper> fromArrayToWrapper
	 = new ConcurrentHashMap<>();

	public ArrayWrapper(Class<? extends T> class, int args){
		 array = reflect.
		 map.put(array, this);
	}

	private ArrayWrapper(Object[] array){
		this.array = array;
		map.put(array, this);
	}

	Object[] array;

	private static fromArrayToWrapper(Object[] array){
		if (map.contains(array)){
			return map.get(array);
		}
		else{
			ArrayWrapper wrapper = new ArrayWrapper(array);
			return wrapper:
		}
	}

	public Object get(int i){
		if (array[i]) == null{
			return null;
		}
		if array[i].getClass().isArray(){
			return fromArrayToWrapper(array[i));
		}
		else{
			return array[i];
		}

	}

	public void set(int i, Object o){
		if (o instanceof ArrayWrapper){
			array[i]=o.array;
		}
		else{
			array[i] = o;
		}
	}

}
\end{lstlisting}

Some problems arise with the above class, the first being that "this" is leaked in the constructor. The second is that storing everything in a static map prevents garbage collection, leading to a memory leak.

The first problem is solved by making the constructors private, and calling static factory methods instead. Those factory methods will first construct the object, and then place it in the Map. The second is solved by using a Map with weak references.

The fromArrayToWrapper map is now defined as of type:
\begin{lstlisting}
 WeakHashMap<Object[], WeakReference<ObjectArrayWrapper>>
\end{lstlisting}

and the factory method is designed like this:
\begin{lstlisting}
    public final static ObjectArrayWrapper
     getObjectArrayWrapper(int[] dims, Class componentType) {
        ArrayWrapper wrap = new ArrayWrapper(dims, componentType);
        MAP.put(wrap.array, new WeakReference<>(wrap));
        return wrap;
    }
\end{lstlisting}

The transformation simply consists in replacing each creation of an array, or access through the appropriate method, followed by casting in the case of the get method. In the following, $\arr$ is an array of type $T[]$.

\begin{tabular}{ll}
$ S \arr = \new{} T[n] $ & $\rightsquigarrow ArrayWrapper \; \arr = \;ArrawWrapper.getNewArrayWrapper(T, n)$ \\
$\arr[i] $ & $\rightsquigarrow (T) arr.get(i)$\\
$\arr[i] = a$ & $arr.set(i, a)$; \\
\end{tabular}

 Furthermore, as one can see, the ArrayWrapper does not remember the class of the original array: types are erased.  This leads us to make particular care for casting. We must hence create a particular method for cast, so that it results in equivalent behaviour at runtime. We do that in two steps. First, we add a $asArray$ to the $ArrayWrapper$ class that returns the original array.

 \begin{lstlisting}
public Object[] asArray(){
	return internal ;
 }
 \end{lstlisting}
 We then create this static method.
 \begin{lstlisting}
 public void cast(Object o, Class t){
 	if (o  instanceof ArrayWrapper){
 		 (t) ((ArrayWrapper) o).asArray();
 		 return;
 	}
 	(t) o;
 }
 \end{lstlisting}

 Also, we replace the type of every field that are arrays to ArrayWrapper.

 \begin{tabular}{ll}
 $f : t $ & $ $.
 \end{tabular}
$ \rightsquigarrow
  \begin{cases}f : \ArrayWrapper \text{ if } t \inherits \obj \\
   f : t \text{ otherwise} \end{cases}$
\subsection{Synchronization}
\textit{
Transformation of the synchronized(o){ } into call to two methods
lock(o) and unlock(o).}

Each object present in the JVM has an internal lock, that can be access either by calling synchonized methods, or with the instruction $\mathsf{synchronized}$. The $\mathsf{synchronized}\{ ... \} $ translates into bytecode by two instructions $\mathsf{monitorenter}$ and $\mathsf{monitorexit}$. We want to replace these instructions with methods call that will respectively acquire and release the internal lock of the object.

\newcommand{\getLock}{$\mathsf{getLock}$}
\newcommand{\releaseLock}{$\mathsf{releaseLock}$}
\newcommand{\latchTread}{$\mathsf{latchThread}$}
\newcommand{\doneLatch}{$\mathsf{doneLatch}$}
Therefore, for each class we add two methods \getLock{} and \releaseLock. It is important that \getLock{} returns quickly while keeping the lock of the object held. \getLock{} will start a thread \latchTread that will acquire the lock of the object, while \releaseLock will end the thread. To each class we add a field \doneLatch{} of type CountDownLatch. A CountDownLatch initilized with 1 \enquote{serves as a simple on/off latch, or gate: all threads invoking await wait at the gate until it is opened by a thread invoking countDown().} \ref{javaspec}

 The class \latchTread{} is defined as follows.

\begin{lstlisting}
public class LatchThread extends Thread{
  hasSyncMethods o;
  CountDownLatch signal;
  public LatchThread(hasSyncMethods o,
          CountDownLatch signal){
    this.o = o;
    this.signal = signal;
  }
  public void run(){
    o.getLock(signal);
  }
}
\end{lstlisting}
The method for the \getLock{} is as follows.
\begin{lstlisting}
public void startLock(){
  try{
    CountDownLatch latch =
        new CountDownLatch(1);
    Thread latchTread =
       new latchTread(this, latch);
    latchTread.run();
    latch.await();
  }
  catch(InterruptedException ex){
    throw new RuntimeException(ex);
  }
}
\end{lstlisting}

\begin{lstlisting}
public void releaseLock(){
  this.doneLatch.countDown();
}
\end{lstlisting}

 The code for the \getLock{} is as follows.

\begin{lstlisting}
public synchronized void
 getLock(CountDownLatch latch){
  try{
    latch.countDown();
    this.doneLatch = new CountDownLatch(1);
    this.doneLatch.await();
  }
  catch(InterruptedException ex){
    throw new RuntimeException(ex);
  }
}
\end{lstlisting}

\subsection{Introspection modifications}

In the case where mokapot is used to create a remote object,
\begin{lstlisting}
$A object = communicator.runRemotely(-> new A());
\end{lstlisting}
mokapot will, in most cases, not return an object of type $A$, but of a different type castable to $A$. Meaning that, in this case $object.getClass().equals(A.class)$ will evaluate to false, which is an unexpected behaviour. Millr fixes this issue by replacing the $getClass()$ method. Mokapot possesses an internal public static method that allows it to detect if an object acts as a proxy for an object of another class, and produces the original class.
Therefore, every $getClass()$ method is replaced into a static call to this method.

\begin{tabular}
$o.getClass() $ & $\rightsquigarrow mokapot.getClass(o)$
\end{tabular}

\subsection{Visibility modifications}

In order for mokapot to put a non-copiable object remotely, it needs to create locally a standin, that will redirect local calls to the remote object. If the original object was of class $A$, mokapot will create a local object of class $A'$ extends $A$. This one will need to overrides every methods that the original object has. In particular, this includes method that may not visible from $A$, because they belong in classes that $A$ overrides and have private / package-private visibilities.

-Remove final modifiers.\\
-Package-private -> protected\\
-Private -> protected with cases analysis.

\subsection{Lambdas removal}
->RetroLambda transformation.

\section{Making millr works with non-milled dependencies}

\subsection{Field access}
If a Class A extends some class that is non milled getters are created for the fields inherited by the class. Local analysis is carried to know if the objects in the program subclass A and call to getters / setter can be used.

\subsection{Array}
Arrays pose problems because of type modification.
1) Mechanisms to cope with classes / interface inheritances.
2) Mechanisms to cope with method calls to methods belonging outside the milled programs.
3)Discussion about generics.

\subsection{Visibility and possible overriding issues}
-> Detection at millr time.

\printbibliography

  \end{document}

max_stars_repo_name: danghica/mokapot

max_issues_repo_name: danghica/mokapot

max_forks_repo_name: danghica/mokapot


text:
\section{Model Functions}

This module is intended to be used an approximation to a flexing body attached to the spacecraft. Examples include solar arrays, antennas, and other appended bodies that would exhibit flexing behavior. Below is a list of functions that this model performs:

\begin{itemize}
	\item Compute it's contributions to the mass properties of the spacecraft
	\item Provides matrix contributions for the back substitution method
	\item Compute it's derivatives for $\theta$ and $\dot{\theta}$
	\item Adds energy and momentum contributions to the spacecraft
\end{itemize}

\section{Model Assumptions and Limitations}
Below is a summary of the assumptions/limitations:

\begin{itemize}
	\item Is a first-order approximation to a flexing body
	\item Is developed in such a way that does not require constraints to be met
	\item The hinged rigid body must have a diagonal inertia tensor with respect the $\mathcal{S}_i$ frame as seen in Figure~\ref{fig:FlexFigure}
	\item Only linear spring and damping terms
	\item Will only approximate one flexing mode at a time
	\item Cannot simulate multiple interconnected panels
	\item The hinged rigid body will always stay attached to the hub (the hinge does not have torque limits)
	\item The hinge does not have travel limits, therefore if the spring is not stiff enough it will unrealistically travel through bounds such as running into the spacecraft hub
	\item The EOMs are nonlinear equations of motion, therefore there can be inaccuracies (and divergence) that result from integration. Having a time step of $<= 0.10\ \text{sec}$ is recommended, but this also depends on the natural frequency of the system
	\item When trying to match the frequency of a physical appended body, note that the natural frequency of the coupled system will be different than the appending body flexing by itself
\end{itemize}


text:
\lab{Exceptions and File I/O}{Exceptions and File I/O}
\label{lab:Exceptions}
\objective{
In Python, an \emph{exception} is an error detected during execution.
Exceptions are important for regulating program usage and for correctly reporting problems to the programmer and end user.
Understanding exceptions allows us to safely read data from and export data to external files, and being able to read from and write to files is important to analyzing data and communicating results.
In this lab we present exception syntax and file interaction protocols.
}

\section*{Exceptions} % =======================================================

Every programming language has a formal way of indicating and handling errors.
In Python, we raise and handle \emph{exceptions}.
Some of the more common exceptions are listed below, along with the kinds of problems that they typically indicate.
%
\begin{table}[H]
\centering
\begin{tabular}{r|l}
    Exception & Indication \\ \hline
    \li{AttributeError} & An attribute reference or assignment failed.\\
    % \li{ImportError} & An \li{import} statement failed.\\
    \li{IndexError} & A sequence subscript was out of range.\\
    \li{NameError} & A local or global name was not found.\\
    \li{SyntaxError} & The parser encountered a syntax error.\\
    \li{TypeError} & An operation or function was applied to an object of \\ &inappropriate type.\\
    \li{ValueError} & An operation or function received an argument that had \\ & the right type but an inappropriate value.\\
    % \li{ZeroDivisionError} & The second argument of a division or modulo operation \\ & was zero.
\end{tabular}
\end{table}
%
\begin{lstlisting}
>>> print(x)
<<Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'x' is not defined>>

>>> [1, 2, 3].fly()
<<Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'list' object has no attribute 'fly'>>
\end{lstlisting}

See \url{https://docs.python.org/2/library/exceptions.html} for the complete list of Python's built-in exception classes.

\subsection*{Raising Exceptions} % --------------------------------------------

Many exceptions, like the ones demonstrated above, are due to coding mistakes and typos.
Exceptions can also be used intentionally to indicate a problem to the user or programmer.
To create an exception, use the keyword \li{raise}, followed by the name of the exception class.
As soon as an exception is raised, the program stops running unless the exception is handled properly.

Exception objects can be initialized with any number of arguments.
These arguments are stored as a tuple attribute called \li{args}, which serves as the string representation of the object.
We typically provide a single string detailing the reasons for the error.

\begin{lstlisting}
# Raise a generic exception, without an error message.
>>> if 7 is not 7.0:
...     raise Exception
...
<<Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
Exception>>

# Now raise a more specific exception, with an error message included.
>>> for x in range(10):
...     if x > 5:
...         raise ValueError("'x' should not exceed 5.")
...     print(x),
...
0 1 2 3 4 5
<<Traceback (most recent call last):
  File "<stdin>", line 3, in <module>
ValueError: 'x' should not exceed 5.>>
\end{lstlisting}

\begin{problem} % Raising Exceptions during magic trick.
Consider the following arithmetic ``magic'' trick.
\begin{enumerate}
    \item Choose a 3-digit number where the first and last digits differ by 2 or more (for example, $123$).
    \label{magic-trick-step-1}
    \item Reverse this number by reading it backwards ($321$).
    \item Calculate the positive difference of these numbers ($321 - 123 = 198$).
    \item Add the reverse of the result to itself ($198 + 891 = 1089$).
\end{enumerate}
The result of the last step will \emph{always} be $1089$, regardless of the original number chosen in step \ref{magic-trick-step-1} (can you explain why?).

The following function prompts the user for input at each step of the magic trick, but does not check that the user's inputs are correct.
\newpage
\begin{lstlisting}
def arithmagic():
    step_1 = raw_input("Enter a 3-digit number where the first and last "
                                           "digits differ by 2 or more: ")
    step_2 = raw_input("Enter the reverse of the first number, obtained "
                                              "by reading it backwards: ")
    step_3 = raw_input("Enter the positive difference of these numbers: ")
    step_4 = raw_input("Enter the reverse of the previous result: ")
    print str(step_3) + " + " + str(step_4) + " = 1089 (ta-da!)"
\end{lstlisting}

Modify \li{arithmagic()} so that it verifies the user's input at each step.
Raise a \li{ValueError} with an informative error message if any of the following occur:
\begin{enumerate}
\item The first number (\li{step_1}) is not a 3-digit number.
\item The first number's first and last digits differ by less than $2$.
\item The second number (\li{step_2}) is not the reverse of the first number.
\item The third number (\li{step_3}) is not the positive difference of the first two numbers.
\item The fourth number (\li{step_4}) is not the reverse of the third number.
\end{enumerate}
%
(Hint: \li{raw_input()} always returns a string, so each variable is a string initially. Use \li{int()} to cast the variables as integers when necessary. The built-in function \li{abs()} may also be useful.)

\end{problem}

\subsection*{Handling Exceptions} % -------------------------------------------

To prevent an exception from halting the program, it must be handled by
placing the problematic lines of code in a \li{try} block.
An \li{except} block then follows.

\begin{lstlisting}
# The 'try' block should hold any lines of code that might raise an exception.
>>> try:
...     raise Exception("for no reason")
...     print "No exception raised"
... # The 'except' block is executed when an exception is raised.
... except Exception as e:
...     print "Exception raised", e
...
<<Exception raised for no reason>>
>>> # The program then continues on.
\end{lstlisting}

In this example, the name \li{e} represents the exception within the except block.
Printing \li{e} displays its error message.

\begin{comment}
We could also raise the exception again with the syntax \li{raise e} or just \li{raise}.

\begin{lstlisting}
>>> try:
...     raise Exception("for no reason")
... except Exception as e:
...     print "Exception raised", e
...     e.args = ("BECAUSE MATH!!",)        # Assign 'e' a new error message.
...     raise e                             # Raise the exception again.
...
Exception raised for no reason
<<Traceback (most recent call last):
  File "<stdin>", line 6, in <module>
Exception: BECAUSE MATH!!>>
\end{lstlisting}
\end{comment}

\newpage

The try-except control flow can be expanded with two other blocks.
The flow proceeds as follows:

\begin{enumerate}
\item The \li{try} block is executed until an exception is raised, if at all.

\item An \li{except} statement specifying the same kind of exception that was raised in the try block ``catches'' the exception, and the block is then executed.
There may be multiple except blocks following a single try block (similiar to having several \li{elif} statements following a single \li{if} statement), and a single except statement may specify multiple kinds of exceptions to catch.

\item The optional \li{else} block is executed if an exception was \emph{not} raised in the try block.
Thus either an except block or the else block is executed, but not both.

\item Lastly, the optional \li{finally} block is always executed if it is included.
\end{enumerate}

% Note that a try block must always be followed by at least one except or finally block.

\begin{lstlisting}
>>> try:
...     raise ValueError("The house is on fire!")
... # Check for multiple kinds of exceptions using parentheses.
... except (ValueError, TypeError) as e:
...     house_on_fire = True
... else:                           # Skipped due to the exception.
...     house_on_fire = False
... finally:
...     print "The house is on fire:", house_on_fire
...
<<The house is on fire: True>>

>>> try:
...     house_on_fire = False
... except Exception as e:
...     house_on_fire = True
... else:                           # Executed because there was no exception.
...     print "The house is probably okay."
... finally:
...     print "The house is on fire:", house_on_fire
...
<<The house is probably okay.
The house is on fire: False>>
\end{lstlisting}

The code in the \li{finally} block is \emph{always} executed, even if a \li{return} statement or an uncaught exception occurs in any block following the try statement.

\begin{lstlisting}
>>> try:
...     raise ValueError("The house is on fire!")
... finally:                        # Executes before the error is reported.
...     print "The house may be on fire."
...
<<The house may be on fire.
Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
ValueError: The house is on fire!>>
\end{lstlisting}

See \url{https://docs.python.org/2/tutorial/errors.html} for more examples.

\begin{problem} % Problem: Catch a KeyboardInterrupt to stop a random walk.
A \emph{random walk} is a path created by a series of random steps.
% Random walks are used in many applications, including molecular movement, image segmentation, and (somewhat disturbingly) stock market prices.
The following function simulates a random walk where at every step, we either step forward (adding $1$ to the total) or backward (adding $-1$).

\begin{lstlisting}
from random import choice

def random_walk(max_iters=1e12):
    walk = 0
    direction = [1, -1]
    for i in xrange(int(max_iters)):
        walk += choice(direction)
    return walk
\end{lstlisting}

A \li{KeyboardInterrupt} is a special exception that can be triggered at any time by entering \li{ctrl c} (on most systems) in the keyboard.
% A \li{KeyboardInterrupt} is usually used to manually escape faulty code that runs forever, but it can also be used to intentionally truncate a process.
Modify \li{random_walk()} so that if the user raises a \li{KeyboardInterrupt}, the function handles the exception and prints ``Process interrupted at iteration $i$''.
If no \li{KeyboardInterrupt} is raised, print ``Process completed''.
In both cases, return \li{walk} as before.
\end{problem}

\begin{info} % Exception Hierarchy
The built-in Python exceptions are organized into a class hierarchy.
This can lead to some confusing behavior.

\begin{lstlisting}
>>> try:
...     raise ValueError("This is a ValueError!")
... except StandardError as e:
...     print(e)
...
<<This is a ValueError!>>                       # The exception was caught.

>>> try:
...     raise StandardError("This is a StandardError!")
... except ValueError as e:
...     print(e)
...
<<Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
StandardError: This is a StandardError!>>     # The exception wasn't caught!
\end{lstlisting}

It turns out that the \li{ValueError} class inherits from the \li{StandardError} class.
Thus a \li{ValueError} \emph{is} a \li{StandardError}, so the first except statement was able to catch the exception, but a \li{StandardError} is \emph{not} a \li{ValueError}, so the second except statement could not catch the exception.

The complete exception class hierarchy is documented at \url{https://docs.python.org/2/library/exceptions.html#exception-hierarchy}.
\end{info}

\begin{comment}
\begin{warn} % Don't use except by itself; specify an exception class.
An \li{except} statement by itself catches \emph{any} exception raised in the corresponding try block, but this approach can mistakenly mask unexpected errors.
Consider the following function, which intends to avoid dividing by zero.

\begin{lstlisting}
>>> def divider(x, y):
...     try:
...         return x / float(yy)
...     except:
...         print("y must not equal zero!")
...
>>> divider(2, 3)
<<y must not equal zero!>>
\end{lstlisting}

Because \li{y} is misspelled as \li{yy}, a \li{NameError} is always raised in the try block.
Always specify the kinds of exceptions you expect to encounter.

\begin{lstlisting}
>>> def divider(x, y):
...     try:
...         return x / float(yy)
...     except ZeroDivisionError:
...         print("y must not equal zero!")
...
>>> divider(2, 3)
<<Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in divider
NameError: global name 'yy' is not defined>>    # Now we can see the mistake.
\end{lstlisting}
\end{warn}
\end{comment}

\section*{File Input and Output} % ============================================

Python has a useful \li{file} object that acts as an interface to all kinds of different file streams.
The built-in function \li{open()} creates a file object.
It accepts the name of the file to open and an editing mode.
The mode determines the kind of access to use when opening the file.
There are three common options:
%
\begin{description}
\item \li{'r'}: \textbf{read}.
This is the default mode.
The file must already exist.
\item \li{'w'}: \textbf{write}.
This mode creates the file if it doesn't already exist and \textcolor{red}{\textbf{overwrites everything}} in the file if it does already exist. %(wake up and pay attention to this)
\item \li{'a'}: \textbf{append}.
New data is written to the end of the file.
This mode also creates a new file if it doesn't already exist.
\end{description}

\begin{lstlisting}
>>> myfile = open("in.txt", 'r')        # Open 'in.txt' with read-only access.
>>> print(myfile.read())                # Print the contents of the file.
Hello World!                            # (it's a really small file.)
>>> myfile.close()                      # Close the file connection.
\end{lstlisting}

\subsection*{The With Statement} % --------------------------------------------

An \li{IOError} indicates that some input or output operation has failed.
If a file cannot be opened for any reason, an \li{IOError} is raised and the file object is not initialized.
A simple \li{try}-\li{finally} control flow can ensure that a file stream is closed safely.

The \li{with} statement provides an alternative method for safely opening and closing files.
Use \li{with open(<filename>, <mode>) as <alias>:} to create an indented block in which the file is open and available under the specified alias.
At the end of the block, the file is automatically closed.
This is the preferred file-reading method when a file only needs to be accessed briefly.
The more flexible \li{try}-\li{finally} approach is typically better for working with several file streams at once.

\begin{lstlisting}
>>> myfile = open("in.txt", 'r')        # Open 'in.txt' with read-only access.
>>> try:
...     contents = myfile.readlines()   # Read in the content by line.
... finally:
...     myfile.close()                  # Explicitly close the file.

# Equivalently, use a 'with' statement to take care of errors.
>>> with open("in.txt", 'r') as myfile: # Open 'in.txt' with read-only access.
...    contents = myfile.readlines()    # Read in the content by line.
...                                     # The file is closed automatically.
\end{lstlisting}

In both cases, if the file \texttt{in.txt} does not exist in the current directory, an \li{IOError} will be raised.
However, errors in the \li{try} or \li{with} blocks will not prevent the file from being safely closed.

\newpage

\subsection*{Reading and Writing} % -------------------------------------------

Open file objects have an implicit \emph{cursor} that determines the location in the file to read from or write to.
After the entire file has been read once, either the file must be closed and reopened, or the cursor must be reset to the beginning of the file with \li{seek(0)} before it can be read again.

Some of more important file object attributes and methods are listed below.

\begin{table}[H]
\begin{tabular}{r|l}
Attribute & \multicolumn{1}{c}{Description} \\
\hline
\li{closed} & \li{True} if the object is closed.\\
\li{mode} & The access mode used to open the file object.\\
\li{name} & The name of the file.\\ \\
Method & \multicolumn{1}{c}{Description}\\
\hline
\li{close()} & Close the connection to the file.\\%Flush any delayed writes
% \li{flush()} & Flush the internal I/O buffer.\\
% \li{<<next()>>} & Read the next value.\\
\li{read()} & Read a given number of bytes; with no input, read the entire file.\\
\li{readline()} & Read a line of the file, including the newline character at the end.\\
\li{readlines()} & Call \li{readline()} repeatedly and return a list of the resulting lines.\\
\li{seek()} & Move the cursor to a new position.\\
\li{tell()} & Report the current position of the cursor.\\
\li{write()} & Write a single string to the file (spaces are \emph{not} added).\\
\li{writelines()} & Write a list of strings to the file (newline characters are \emph{not} added).\\
\end{tabular}
\end{table}

Only strings can be written to files; to write a non-string type, first cast it as a string with \li{str()}.
Be mindful of spaces and newlines to separate the data.

\begin{lstlisting}
>>> with open("out.txt", 'w') as outfile:   # Open 'out.txt' for writing.
...     for i in xrange(10):
...         outfile.write(str(i**2)+' ')    # Write some strings (and spaces).
...
>>> outfile.closed                          # The file is closed automatically.
True
\end{lstlisting}

Executing this code replaces whatever used to be in \texttt{out.txt} (whether or not it existed previously) with the following:

\begin{lstlisting}
0 1 4 9 16 25 36 49 64 81
\end{lstlisting}

\begin{problem} % ContentFilter.__init__().
Define a class called \li{ContentFilter}.
Implement the constructor so that it accepts the name of a file to be read.
%
\begin{enumerate}
\item If the filename argument is not a string, raise a \li{TypeError}.

(Hint: The built-in functions \li{type()} and \li{isinstance()} may be useful.)

\item Read the file and store its name and contents as attributes
(store the contents as a single string).
Securely close the file stream.
\end{enumerate}
\end{problem}

\section*{String Formatting} % ================================================

Python's \li{str} type class has several useful methods for parsing and formatting strings.
They are particularly useful for processing data from a source file and for preparing data to be written to an external file.

\begin{table}[H]
\begin{tabular}{r|l}
Method & \multicolumn{1}{c}{Returns} \\ \hline
\li{count()} & The number of times a given substring occurs within the string.\\
\li{find()} & The lowest index where a given substring is found.\\
\li{isalpha()} & \li{True} if all characters in the string are alphabetic (a, b, c, \ldots).\\
\li{isdigit()} & \li{True} if all characters in the string are digits (0, 1, 2, \ldots).\\
\li{isspace()} & \li{True} if all characters in the string are whitespace (\li{" "}, \li{'\\t'}, \li{'\\n'}).\\
% \li{capitalize()} & A copy of the string with only its first character capitalized. \\
\li{join()} & The concatenation of the strings in a given iterable with a\\&specified separator between entries.\\
\li{lower()} & A copy of the string converted to lowercase. \\
\li{upper()} & A copy of the string converted to uppercase. \\
\li{replace()} & A copy of the string with occurrences of a given substring\\&replaced by a different specified substring.\\
\li{split()} & A list of segments of the string, using a given character or string \\
 & as a delimiter.\\
\li{strip()} & A copy of the string with leading and trailing whitespace removed. \\
\end{tabular}
\end{table}

The \li{join()} method translates a list of strings into a single string by concatenating the entries of the list and placing the principal string between the entries.
Conversely, \li{split()} translates the principal string into a list of substrings, with the separation determined by the a single input.

\begin{lstlisting}
# str.join() puts the string between the entries of a list.
>>> words = ["state", "of", "the", "art"]
>>> "-".join(words)
<<'state-of-the-art'>>

>>> " o_O ".join(words)
<<'state o_O of o_O the o_O art'>>

# str.split() creates a list out of a string, given a delimiter.
>>> "One fish\nTwo fish\nRed fish\nBlue fish\n".split('\n')
<<['One fish', 'Two fish', 'Red fish', 'Blue fish', '']>>

# If no delimiter is provided, the string is split by its whitespace characters.
>>> "One fish\nTwo fish\nRed fish\nBlue fish\n".split()
<<['One', 'fish', 'Two', 'fish', 'Red', 'fish', 'Blue', 'fish']>>
\end{lstlisting}

Can you tell the difference between the following routines?

\begin{lstlisting}
>>> with open("in.txt", 'r') as myfile:
...     contents = myfile.readlines()
...
>>> with open("in.txt", 'r') as myfile:
...     contents = myfile.read().split('\n')
\end{lstlisting}

\begin{problem} % ContentFilter methods.
Add the following methods to the \li{ContentFilter} class for writing the contents of the original file to new files.
Each method should accept a the name of a file to write to and a keyword argument \li{mode} that specifies the file access mode, defaulting to \li{'w'}.
If \li{mode} is not either \li{'w'} or \li{'a'}, raise a \li{ValueError} with an informative message.

\begin{enumerate}
\item \li{uniform()}: write the data to the outfile with uniform case. Include an additional keyword argument \li{case} that defaults to \li{"upper"}.

If \li{case="upper"}, write the data in upper case.
If \li{case="lower"}, write the data in lower case.
If \li{case} is not one of these two values, raise a \li{ValueError}.

\item \li{reverse()}: write the data to the outfile in reverse order. Include an additional keyword argument \li{unit} that defaults to \li{"line"}.

If \li{unit="word"}, reverse the ordering of the words in each line, but write the lines in the same order as the original file.
If \li{unit="word"}, reverse the ordering of the lines, but do not change the ordering of the words on each individual line.
If \li{unit} is not one of these two values, raise a \li{ValueError}.

\item \li{transpose()}: write a ``transposed'' version of the data to the outfile.
That is, write the first word of each line of the data to the first line of the new file, the second word of each line of the data to the second line of the new file, and so on.
\end{enumerate}

Also implement the \li{__str__()} magic method so that printing a \li{ContentFilter} object yields the following output:
\begin{lstlisting}
<<Source file:              <filename>
Total characters:         <The total number of characters in the file>
Alphabetic characters:    <The number of letters>
Numerical characters:     <The number of digits>
Whitespace characters:    <The number of spaces, tabs, and newlines>
Number of lines:          <The number of lines>>>
\end{lstlisting}

\begin{comment}
Examples:

\begin{lstlisting}
# example.txt
a b c
d e f
\end{lstlisting}

\begin{lstlisting}
>>> cf = ContentFilter("example.txt")

>>> cf.uniform("uniform.txt", mode='w', case="upper")
>>> cf.uniform("uniform.txt", mode='a', case="lower")

>>> cf.reverse("reverse.txt", mode='w', unit="word")
>>> cf.reverse("reverse.txt", mode='a', unit="line")

>>> cf.transpose("transpose.txt", mode='w')
\end{lstlisting}

\begin{lstlisting}
# uniform.txt
A B C
D E F
a b c
d e f
\end{lstlisting}

\begin{lstlisting}
# reverse.txt
c b a
f e d
d e f
a b c
\end{lstlisting}

\begin{lstlisting}
a d
b e
c f
\end{lstlisting}
\end{comment}

\end{problem}

\newpage

\section*{Additional Material} % ==============================================

\subsection*{Custom Exception Classes} % --------------------------------------

Custom exceptions can be defined by writing a class that inherits from some existing exception class.
The generic \li{Exception} class is typically the parent class of choice.

\begin{lstlisting}
>>> class TooHardError(Exception):
...     pass
...
>>> raise TooHardError("This lab is impossible!")
<<Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
__main__.TooHardError: This lab is impossible!>>
\end{lstlisting}

This may seem like a trivial extension of the \li{Exception} class, but it is useful to do because the interpreter never automatically raises a \li{TooHardError}.
Any \li{TooHardError} must have originated from a hand-written \li{raise} command, making it easier to identify the exact source of the problem.

\subsection*{Assertions} % ----------------------------------------------------

An \li{AssertionError} is a special exception that is used primarily for software testing.
The \li{assert} statement is a shortcut for testing the truthfulness of an expression and raising an \li{AssertionError}.

\begin{lstlisting}
>>> assert <expression>, <message>

# Equivalently...
>>> if not <expression>:
...     raise AssertionError(<message>)
...
\end{lstlisting}

\begin{comment} % This is only a feature in Python 3 (TODO).
\subsection*{Chaining Exceptions} % -------------------------------------------
\begin{lstlisting}
>>> try:
>>>     raise ValueError("First Exception")
>>> except ValueError as e:
>>>     raise TypeError("Second Exception") from e
\end{lstlisting}
This syntax makes it possible to see where an error originated from and to ``pass it up'' to the next process.
\end{comment}

\begin{comment}
\subsection*{Buffering} % -----------------------------------------------------
The {open()} function also accepts a third argument that specifies buffering size.
% TODO: Details about file.flush(), the buffer argument for open(), and reading large files.
\end{comment}

\subsection*{The CSV Module} % ------------------------------------------------

The CSV format (comma separated value) is a common file format for spreadsheets and grid-like data.
The \li{csv} module in the standard library contains functions that work in conjunction with the built-in \li{file} object to read from or write to CSV files.
See \url{https://docs.python.org/2/library/csv.html} for details.

\newpage

\subsection*{More String Formatting} % ----------------------------------------

Concatenating string values with non-string values is often cumbersome and tedious.
Consider the problem of printing a simple date:

\begin{lstlisting}
>>> day, month, year = 14, "March", 2015
>>> print("Is today " + str(day) + str(month) + ", " + str(year) + "?")
Is today 14 March, 2015?
\end{lstlisting}

The \li{str} class's \li{<<format()>>} method makes it easier to insert non-string values into the middle of a string.
Write the desired output in its entirety, replacing non-string values with curly braces \li{\{\}}.
Then use the \li{<<format()>>} method, entering each replaced value in order.

\begin{lstlisting}
>>> print("Is today {} {}, {}?".<<format>>(day, month, year))
Is today 14 March, 2015?
\end{lstlisting}

This method is extremely flexible and provides many convenient ways to format string output nicely.
Suppose, for example, that we would like to visualize the progress that a program is making through a loop.
The following code prints out a simple status bar.

\begin{lstlisting}
>>> from sys import stdout

>>> iters = int(1e7)
>>> chunk = iters // 20
>>> for i in xrange(iters):
...     print("\r[{:<20}] i = {}".<<format>>('='*((i//chunk)+1), i)),
...     stdout.flush()
...
\end{lstlisting}

Here the string \li{"\\r[\{:<20\}]"} used in conjunction with the \li{<<format()>>} method tells the cursor to go back to the beginning of the line, print an opening bracket, then print the first argument of \li{<<format()>>} left-aligned with at least $20$ total spaces before printing the closing bracket.
The comma after the print command suppresses the automatic newline character, keeping the output of each individual print statement on the same line.
Finally, \li{sys.stdout.flush()} flushes the internal buffer so that the status bar is printed in real time.

Of course, printing at each iteration dramatically slows down the progression through the loop.
How does the following code solve that problem?

\begin{lstlisting}
>>> for i in xrange(iters):
...     if not i % chunk:
...         print "\r[{:<20}] i = {}".<<format>>('='*((i//chunk)+1), i),
...         stdout.flush()
...
\end{lstlisting}

See \url{https://docs.python.org/2/library/string.html\#format-string-syntax} for more examples and specific syntax for using \li{str.<<format()>>}.

max_stars_repo_name: jaredawebb/Labs

max_issues_repo_name: jaredawebb/Labs

max_forks_repo_name: jaredawebb/Labs


text:
\newpage
\section{Introduction}
\label{intro}

Main memory sizes have grown significantly to the degree that
they can hold big chunks of data main-memory resident, often all the data of modern database instances.
This has lead to an increased attention towards main-memory tailored techniques.
Even though data can be accessed fast in main-memory, e.g., with scans over dense arrays, still
proper indexing provides significant benefits for range or point queries.

Past research has shown that main-memory tailored indexing techniques can significantly outperform
standard techniques such as binary search over a dense sorted array \cite{cbbtrees,art}.

\begin{figure}[t]
\center
\includegraphics[width=0.85\columnwidth]{graphs/motivation.pdf}%
%\vspace{-1.5em}
\caption{The need for transitive indexing: A different design is best for different stages of a workload.}
%\vspace{-2.5em}
\label{F:Motivation}
\end{figure}

\textbf{The Problem: Read-write Intensive Workloads.}
In this paper, we address the need of modern applications to handle workloads which require both efficient read and efficient update
support in the same system.
There is an increasing attention to this problem at various levels, e.g.,
in terms of database architectures with efforts such as SAP HANA \cite{Hana} and Hyper \cite{hyper} or also at the indexing level
with efforts such as ART main-memory indexing \cite{art}.
A problem with traditional  static indexing approaches is that one has to know exactly which data should be indexed
and then also have the time and resources to go through a very expensive indexing phase.
As applications become more and more real-time and with ad-hoc querying demands, such static approaches
become a bottleneck to having a quick access to new data.
A number of adaptive indexing approaches have been proposed lately to address exactly this problem of static indexing \cite{IKM:CIDR07,hail}.
With adaptive indexing, indexes are built and refined incrementally during query processing
by treating each query as an advice of how data should be stored.
However, we show that although existing adaptive indexing techniques
do provide significant improvement for ad-hoc workloads, minimizing or even eliminating initialization costs,
they are not resilient in the same way that non-adaptive indexing is for read-write intensive workloads.

\textbf{Motivating Example.}
Figure \ref{F:Motivation} demonstrates this problem: it depicts the relative time needed ($y$-axis)
to answer the first X queries ($x$-axis) in a long sequence of random range
queries and updates over a single column of $10^8$ tuples (10 updates arrive every 10 read queries).
Each graph is normalized (independently) over its static indexing costs.
In this case, for static indexing we use the state-of-the-art in memory index ART \cite{art}
while for adaptive indexing we use the state-of-the-art stochastic cracking index \cite{StochasticCracking}.
Figure \ref{F:Motivation} shows that while early in the query sequence adaptive indexing
significantly outperforms static indexing,
as the sequence evolves,
adaptive indexing loses its advantage over static indexing, i.e.,  it is not resilient.
The first query for adaptive indexing is more than 10 times faster than static indexing;
Full indexing needs to fully index the column, while adaptive indexing performs only small index refinement actions with every query.
However, as more queries and updates arrive, adaptive indexing eventually becomes more than 10 times slower than static indexing.

Ideally, we would like to maintain the performance of adaptive indexing early in the query sequence
and the performance of static indexing later on.

\textbf{Contributions: Transitive Indexing.}
Our contributions are as follows.
\begin{itemize}

\item We propose a new main-memory indexing research area, termed
\emph{transitive indexing}.
The idea is that a data structure representing an index does not have a static shape.
Instead, its shape morphs over time as the workload evolves.

\item
We present Trimmer, a transitive indexing approach which
initially requires no preparation or initialization steps.
Data is simply appended in the form of vectors with no order forced
both inside each vector and across vectors.
As the workload evolves, Trimmer starts forcing order and structure.
Each vector is independently indexed and refined, while data starts flowing from vector to vector.
Gradually, the vectors start morphing into a Trie structure optimized for main-memory.
Only the hot part of the data morphs and everything happens during query processing
without any need for any administration or control.

\item
We show that Trimmer  maintains all the good properties of
both existing adaptive indexing approaches and those of non-adaptive approaches,
i.e., it is lightweight, it continuously adapts by incrementally refining indexes
and it requires zero workload knowledge and preparation costs.
At the same time it is resilient, i.e., it maintains its performance advantages
unfettered even under long strings of queries and continuous data updates;
it is geared towards continuous on-the-fly data exploration under massive updates.

\end{itemize}

We experimentally demonstrate the advantages of Trimmer
over existing static indexing and adaptive indexing techniques.
We use both synthetic benchmarks as well as real world data and queries.
For example, in experiments with a 4 Terabyte instance of
data and queries from the Sloan Digital Sky Survey/SkyServer
from the astronomy domain,
we show that Trimmer can handle a combined workload of $15*10^4$ queries and $5*10^8$ updates in roughly 1 minute, while
state-of-the-art adaptive indexing needed more than 16 hours and state-of-the-art non adaptive indexing needs ??.

%\textbf{Paper Organization.}
%The rest of the paper is organized as follows.
%Section \ref{sec:related} discusses background and related work.
%Then, Section \ref{sec:problem} presents in detail the resilience problem of
%existing adaptive indexing techniques and their inability to cope with the requirements
%of continuous exploration.
%Section \ref{sec:cracke} presents a series of possible patches in existing adaptive indexing
%that deal with the problem only to a certain degree
%and then it introduces CTree for full resilient and adaptive exploration.
%In Section \ref{sec:experiments}, we present a detailed experimental analysis, demonstrating the effectiveness
%and the advantages of CTree both on synthetic and on real workloads.
%Finally, Section \ref{sec:conclusion} discusses future work and concludes the paper.

%As we enter the era of data deluge one of the main emerging patterns is the need for
%data exploration techniques \cite{SurajitSigmod2012Keynote}.
%Data arrives continuously while businesses and sciences need to continuously pose
%queries in an adaptive and interactive mode \cite{NoDBcidr,Blinkmit,ResearcherGuide,Sciborg}.
%A characteristic property in such environments is that there is little idle time and workload knowledge.
%
%\textbf{Physical Design.}
%Good performance in database systems largely relies on proper \emph{tuning} and \emph{physical design}.
%Typically, all tuning choices happen up-front, assuming sufficient workload knowledge
%and idle time. Workload knowledge is necessary in order to determine the appropriate
%tuning actions, while idle time is required in order to perform those actions.
%Modern database systems rely on auto-tuning tools to carry out these steps, e.g.,
%\cite{CN:VLDB:97,FST88,H76,SHU:VLDB:2004,DB2DesignAdvisor}.
%

%\textbf{Dynamic Environments.}
%However, in dynamic environments, workload knowledge and idle time are scarce resources.
%For example, in scientific databases new data arrive on a daily or even hourly basis,
%while query patterns follow an exploratory path as the scientists try to interpret the data
%and understand the patterns observed; there is no time and knowledge
%to analyze and prepare a different physical design hour-by-hour or even day-by-day.
%
%Traditional indexing via tuning presents three fundamental weaknesses in such cases:
%(a) the workload may have changed by the time we finish tuning;
%(b) there may be no time to finish tuning properly;
%and (c) there is no indexing support during tuning.
%
%\textbf{Adaptive Indexing.}
%Recently, a new approach to the physical design problem was proposed,
%namely \emph{database cracking} \cite{IKM:CIDR07}. %\cite{CrackingThesis}.
%Cracking introduces the notion of continuous, incremental, partial and on-demand adaptive indexing.
%Thereby, indexes are incrementally built and refined during query processing.
%Data is physically reorganized in a continuous manner, aiming to
%match the workload, by treating each query as an advice of how data should be stored.
%
%
%\textbf{The Problem. Non-Resilient Exploration.}
%At a first glance it would seem that existing adaptive indexing approaches can cover the need
%towards adaptive exploration in the era of data deluge.
%However, in this paper we show that
%existing adaptive indexing techniques such as database cracking, adaptive merging and their variations
%do not cope with these new challenges. The fundamental weaknesses we identify are the inability to
%support long strings of exploratory queries interleaved with  updates.
%Figure \ref{F:Motivation} demonstrates this problem: it depicts the relative time needed ($y$-axis)
%to answer the first X queries ($x$-axis) in a long sequence of random select
%queries and updates over a single column of $10^8$ tuples.
%Each graph is normalized (independently) over its full indexing costs.
%Figure \ref{F:Motivation} shows that as the sequence evolves in the read only case,
%adaptive indexing (cracking) loses its advantage over a traditional full indexing approach, i.e.,  it is not resilient.
%The first query for cracking is more than 10 times faster than full indexing;
%Full indexing needs to fully index the column, while cracking performs only small index refinement actions with every query.
%However, as more queries arrive, cracking eventually becomes 2 times slower than full indexing.
%The performance degradation is significantly worse when continuous updates interleave with read queries
%(10 updates arrive every 10 read queries).
%In order to cope with the data deluge,
%we would like to keep both the lightweight and the adaptive behavior of cracking for the early queries,
%while still maintaining this behavior in the long run even during continuous updates.
%
%
%\textbf{The Solution. Comb: Resilient Adaptive Indexing.}
%In this paper, we propose a new adaptive indexing approach, termed
%\emph{ Comb (Cracking Over Malleable Buckets)}.
%Comb maintains all the good properties of existing
%approaches, i.e., it is lightweight, it continuously adapts by incrementally refining indexes
%and it requires zero workload knowledge and preparation costs.
%At the same time it is resilient, i.e, it maintains its performance advantages
%unfettered even under long strings of queries and continuous data updates;
%it is geared towards on-the-fly data exploration.
%
%Comb is designed for main memory column-stores; it breaks a single column into multiple disjoint pieces
%and each piece is indexed, accessed and updated independently, while data flows from piece to piece in an adaptive way
%when the index needs to be balanced.
%We present Comb in detail and we experimentally demonstrate its advantages
%over existing indexing and adaptive indexing techniques.
%We use both synthetic benchmarks as well as real world data and queries.
%For example, in experiments with a 4 Terabyte instance of
%data and queries from the Sloan Digital Sky Survey/SkyServer
%from the astronomy domain,
%we show that Comb can handle a combined workload of $15*10^4$ queries and $5*10^8$ insertions in roughly 1 minute, while
%state-of-the-art adaptive indexing needed more than 16 hours.
%
%\textbf{Paper Organization.}
%The rest of the paper is organized as follows.
%Section \ref{sec:related} discusses background and related work.
%Then, Section \ref{sec:problem} presents in detail the resilience problem of
%existing adaptive indexing techniques and their inability to cope with the requirements
%of continuous exploration.
%Section \ref{sec:cracke} presents a series of possible patches in existing adaptive indexing
%that deal with the problem only to a certain degree
%and then it introduces Comb for full resilient and adaptive exploration.
%In Section \ref{sec:experiments}, we present a detailed experimental analysis, demonstrating the effectiveness
%and the advantages of Comb both on synthetic and on real workloads.
%Finally, Section \ref{sec:conclusion} discusses future work and concludes the paper.
%

max_stars_repo_name: felix-halim/indexing-benchmark

max_issues_repo_name: felix-halim/indexing-benchmark

max_forks_repo_name: felix-halim/c-tree


text:
 \documentclass [12pt]{article}

\usepackage {amsmath}
\usepackage {amsthm}
\usepackage {amssymb}
\usepackage {graphicx}
\usepackage {float}
\usepackage {multirow}
\usepackage {xcolor}
\usepackage {algorithmic}
\usepackage [ruled,vlined,commentsnumbered,titlenotnumbered]{algorithm2e} \usepackage {array}
\usepackage {booktabs}
\usepackage {url}
\usepackage {parskip}
\usepackage [margin=1in]{geometry}
\usepackage [T1]{fontenc}
\usepackage {cmbright}
\usepackage [many]{tcolorbox}
\usepackage [colorlinks = true,
            linkcolor = blue,
            urlcolor  = blue,
            citecolor = blue,
            anchorcolor = blue]{hyperref}
\usepackage {enumitem}
\usepackage {xparse}
\usepackage {verbatim}
\usepackage{listings}
\usepackage{xcolor}
\lstset { %
    language=C++,
    backgroundcolor=\color{black!5}, % set backgroundcolor
    basicstyle=\footnotesize,% basic font setting
}
\newtheorem{theorem}{Theorem}
\newtheorem{remark}{Remark}

\DeclareTColorBox {Solution}{}{breakable, title={Solution}} \DeclareTColorBox {Solution*}{}{breakable, title={Solution (provided)}} \DeclareTColorBox {Instruction}{}{boxrule=0pt, boxsep=0pt, left=0.5em, right=0.5em, top=0.5em, bottom=0.5em, arc=0pt, toprule=1pt, bottomrule=1pt} \DeclareDocumentCommand {\Expecting }{+m}{\textbf {[We are expecting:} #1\textbf {]}} \DeclareDocumentCommand {\Points }{m}{\textbf {(#1 pt.)}}

\begin {document}

{\LARGE \textbf {COMP 285 (NC A\&T, Spr `22)}\hfill \textbf {Lecture 5} }
\vspace {1em}
\begin {Instruction}

Adapted From Virginia Williams' lecture notes. Additional credits: J. Su, W. Yang, Gregory Valiant, Mary Wootters, Aviad Rubinstein, Sami Alsheikh.
\end {Instruction}

\begin{centering}
\section*{Introduce to Recurrences and Master Theorem}
\end{centering}

\section{Introduction to Recurrences}

Recall that divide and conquer algorithms divide up a problem into a number of subproblems that are the smaller instances of the same problem, solve those problems recursively, and combine the solutions to the subproblems into a solution for the original problem. When a subproblem size is small enough, the subproblem is solved in a straightforward manner. In the past lectures we have seen two examples of divide and conquer algorithms: \texttt{MergeSort} and \texttt{Karatsuba}’s algorithm for integer multiplication.

The running time of divide and conquer algorithms can be naturally expressed in terms of the running time of smaller inputs. Today we will show two techniques for solving these recurrences. The first is called the master method to solve these recurrences. This method can only be used when the size of all the subproblems is the same (as was the case in the examples).

\section{Recurrences}
Stated more technically, a divide and conquer algorithm takes an input of size $n$ and does some operations all running in $O(f (n))$ time for some $f$ and runs itself recursively on $k \geq 1$ instances of size $n_1, n_2, \dots n_k$ , where $n_i < n$ for all $i$. To talk about what the runtime of such an algorithm is, we can write a runtime \textbf{recurrence}. Recurrences are functions defined in terms of themselves with smaller arguments, as well as one or more base cases. We can
define a recurrence more formally as follows:

Let $T(n)$ be the worst-case runtime on instances of size $n$. If we have $k$ recursive calls on a given step (of sizes $n_i$) and each step takes time $O(f (n))$, then we can write the runtime as $T(n) \leq c \cdot f (n) + \sum_{i=1}^k T(n_i)$ for some constant $c$, where our base case is $T(c') \leq O(1)$.

Now let’s try finding recurrences for some of the divide and conquer algorithms we have seen.

\subsection{Integer Multiplcation}
Recall the integer multiplication problem, where we are given two $n$-digit integers $x$ and $y$ and output the product of the two numbers. The long multiplication/grade school algorithm runs in $O(n^2)$ time. In lecture 1 we saw two divide and conquer algorithms for solving this problem.
In both of them, we divided each of $x$ and $y$ into two $(n/2)$-digit numbers in the following
way: $x = 10^{\frac{n}{2}} a + b$ and $y = 10^{\frac{n}{2}} c + d$. Then we compute $xy = ac\cdot 10^n + 10^{\frac{n}{2}} (ad + bc) + bd$.

In the first algorithm, which we call \texttt{Mult1}, we simply computed the four products $ac, ad, bc, bd$. Karatsuba found that since we only need the sum of $ad$ and $bc$, we can save one multiplication operation by noting that $ad + bc = (a + b)(c + d) - ac - bd$.

\begin{algorithm}
\caption{Mult1(x,y)}\label{alg:mult1}
\begin{algorithmic}
\STATE Split $x$ and $y$ into $x = 10^{\frac{n}{2}} a + b$ and $y = 10^{\frac{n}{2}} c + d$
\STATE $z_1 = \text{Mult1}(a, c)$
\STATE $z_2 = \text{Mult1}(a, d)$
\STATE $z_3 = \text{Mult1}(b, c)$
\STATE $z_4 = \text{Mult1}(b, d)$
\STATE return $z_1\cdot 10^n + 10^{\frac{n}{2}} (z_2 + z_3) + z_4$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Karatsuba(x,y)}\label{alg:karatsuba}
\begin{algorithmic}
\STATE Split $x$ and $y$ into $x = 10^{\frac{n}{2}} a + b$ and $y = 10^{\frac{n}{2}} c + d$
\STATE $z_1 = \text{Karatsuba}(a, c)$
\STATE $z_2 = \text{Karatsuba}(a, d)$
\STATE $z_3 = \text{Karatsuba}(a+c, c+d)$
\STATE $z_4 = z_3 - z_1 - z_2$
\STATE return $z_1\cdot 10^n + z_4 \cdot 10^{\frac{n}{2}} + z_2$
\end{algorithmic}
\end{algorithm}

We now express the running time of these two algorithms using recurrences. Adding two $n$ digit integers is an $O(n)$ operation, since for each position we add at most three digits: the $i$th digit from each number and possibly a carry from the additions due to the $(i-1)$th digits.

Let $T_1(n)$ and $T_2(n)$ denote the worst-case runtime of Mult1 and Karatsuba, respectively, on inputs of size $n$. Then, the runtime of Mult1 can be written as the recurrence

$$
T_1(n) = 4T_1\left(\frac{n}{2}\right) + O(n)
$$
and Karatsuba's runtime can be written as the recurrence
$$
T_2(n) = 3T_2\left(\frac{n}{2} \right) + O(n)
$$

Note that the constant ``hidden'' in the $O(n)$ term in $T_2$ may be greater than in $T_1$, but for asymptotic analysis of the running time, these constants are not important.

\subsection{MergeSort}
Consider the basic steps for algorithm MergeSort($A$), where $|A| = n$.

\begin{enumerate}
    \item If $|A| = 1$, return $A$.
    \item Split $A$ into $A_1, A_2$ of size $\frac{n}{2}$.
    \item Run MergeSort($A$) and MergeSort($A_2$).
    \item Merge($A_1, A_2$)
\end{enumerate}

Steps 2 and 4 each take time $O(n)$. In step 3, we are splitting the work up into two subproblems of size $\frac{n}{2}$. Therefore, we get the following recurrence:
$$
T(n) = 2T\left(\frac{n}{2} \right) + O(n)
$$

In the previous lecture, we saw that the running time of MergeSort is O(n\ log n). In this lecture we will show how to derive this using the master method.

\section{The Master Method}

We now introduce a general method, called the \textit{master method}, for solving recurrences where all the subproblems are of the same size. We assume that the input to the master method is a recurrence of the form

$$
T(n) = a \cdot T \left( \frac{n}{b} \right) + O(n^d)
$$

In this recurrence, there are three constants:

\begin{itemize}
    \item $a$ is the number of subproblems that we create from one problem, and must be an integer greater than or equal to $1$.
    \item $b$ is the factor by which the input size shrinks (it must hold that $b > 1$).
    \item $d$ is the exponent of $n$ in the time it takes to generate the subproblems and combine their solutions.
\end{itemize}

There is another constant ``hidden'' in the big-O notation. We will introduce it in the proof and see that it does not affect the result.

In addition, we need to specify the ``base case'' of the recurrence, that is, the runtime when the input gets small enough. For a sufficiently small $n$ (say, when $n = 1$), the worst-case runtime of the algorithm is constant, namely, $T(n) = O(1)$.

We now state the \textit{master theorem}, which is used to solve the recurrences.

\begin{theorem}[Master Theorem]
Let $T(n) = a \cdot T\left(\frac{n}{b}\right) + O(n^d)$ be a recurrence where $a, b > 1$, Then,

\begin{align*}
T(n) &= \begin{cases}
    O(n^d \log n) & \text{if } a = b^d \\
    O(n^d) & \text{if } a < b^d \\
    O(n^{\log_b a}) & \text{if } a > b^d
\end{cases}
\end{align*}
\end{theorem}

\begin{remark}
In some cases, the recurrence may involve subproblems of size $\lceil \frac{n}{b} \rceil, \lfloor \frac{n}{b} \rfloor$ or $nb + 1$. The master theorem holds for these cases as well. However, we do not prove that here.
\end{remark}

Before we turn to the proof of the master theorem, we show how it can be used to solve the recurrences we saw earlier.

\begin{itemize}
    \item Mult1: $T(n) = 4T(\frac{n}{2})+ O(n)$. The parameters are $a = 4, b = 2, d = 1$, so $a > b^d$, hence $T(n) = O(n^{log_2(4)}) = O(n^2)$.
    \item Karatsuba: $T(n) = 3T(\frac{n}{2})+ O(n)$. The parameters are $a = 3, b = 2, d = 1$, so $a > b^d$, hence $T(n) = O(n^{log_2(3)}) = O(n^{1.59})$.
    \item MergeSort: $T(n) = 2T(\frac{n}{2})+ O(n)$. The parameters are $a = 2, b = 2, d = 1$, so $a = b^d$, hence $T(n) = O(n\ log n)$.
    \item Another example: $T(n) = 2T(\frac{n}{2})+ O(n^2)$. The parameters are $a = 2, b = 2, d = 2$, so $a < b^d$, hence $T(n) = O(n^2)$.
\end{itemize}
We see that for integer multiplication, Karatsuba is the clear winner!

\textit{Proof of the Master Theorem} Let $T(n) = a\cdot T(\frac{n}{b})+ O(n^d)$ be the recurrence we solve using the master theorem. For simplicity, we assume that $T(1) = 1$ and that $n$ is a power of $b$. From the definition of big-O, we know that there is a constant $c > 0$ such that for sufficiently large $n$, $T(n) \leq a\cdot T(\frac{n}{b})+ c\cdot n^d$. The proof of the master theorem will use the recursion tree in a similar way to our analysis of the running time of MergeSort.

\begin{figure}[h!]
\centering
\includegraphics[scale=0.75]{master_theorem_proof.png}
\end{figure}

The recursion tree drawn above has $log_b n + 1$ level. We analyze the amount of work done at each level, and then sum over all levels in order to get the total running time. Consider level $j$. At level $j$, there are $a^j$ subproblems. Each of these subproblems is of size $\frac{n}{b^j}$, and will take time at most $c\left(\frac{n}{b^j}\right)^d$ to solve (this only considers the work done at level $j$ and does not include the time it takes to solve the subsubproblems). We conclude that the total work done at level $j$ is at most $a^j \cdot c\left(\frac{n}{b^j}\right)^d= cn^d\left(\frac{a}{b^d}\right)^j$.

Writing the running time this way shows us where the terms $a$ and $b^d$
come from: $a$ is the branching factor and measures how the number of subproblems grows at each level, and $b^d$ is the shrinkage in the work needed (per subproblem).

Summing over all levels, we get that the total running time is at most $cn^d\Sigma_{j=0}^{\log_b n}\left(\frac{a}{b^d}\right)^j$. We now consider each of the three cases.

\begin{enumerate}
    \item $a = b^d$. In this case, the amount of work done at each level is the same: $cn^d$. Since there are $\log_b n+1$ levels, the total running time is at most $(\log_b n+1)cn^d = O(n^d\ log n)$.
    \item $a < b^d$. In this case, $\frac{a}{b^d} < 1$, hence, $\Sigma^{\log_b n}_{j=0} \left(\frac{a}{b^d}\right)^j \leq \Sigma^{\infty}{j=0} \left(\frac{a}{b^d}\right)^j = \frac{1}{1-\frac{a}{b^d}}= \frac{b^d}{b^d-a}$. Hence, the total running time is $cn^d \cdot \frac{b^d}{b^d-a} = O(n^d)$.

    Intuitively, in this case the shrinkage in the work needed per subproblem is more significant, so the work done in the highest level ``dominates'' the other factors in the running time.
    \item $a > b^d$. In this case, $\Sigma^{\log_b n}_{j=0} \left(\frac{a}{b^d}\right)^j = \frac{\left(\frac{a}{b^d}\right)^{\log_bn+1}-1}{\frac{a}{b^d} -1}$. Since $a, b, c, d$ are constants, we get that the total work done is $O\left(n^d\cdot(\frac{a}{b^d})^{\log_b n}\right) = O\left(n^d\cdot \frac{a^{\log_b n}}{b^{d \log_b n}}\right) = O\left(n^d \cdot \frac{n^{\log_b a }}{n^d}\right)=O\left(n^{\log_b a}\right)$.

    Intuitively, here the branching factor is more significant, so the total work done at each level increases, and the leaves of the tree ``dominate''.
\end{enumerate}

We conclude with a more general version of the master theorem.

\begin{theorem}[Master Theorem - more general version]
Let $T(n) = a \cdot T(\frac{n}{n}) + f(n)$ be a recurrence where $a \geq 1, b > 1$. Then,
    \begin{itemize}
        \item If $f(n) = O(n^{\log_n(a) - \epsilon})$ for some constant $\epsilon > 0, T(n) = \Theta(n^{\log_b (a)})$.
        \item If $f(n) = \Theta(n^{\log_b(a)})$, $T(n) = \Theta(n^{\log_b (a)} \log n)$.
        \item If $f(n) = \Omega(n^{\log_n(a) + \epsilon})$ for some constant $\epsilon > 0$ and if $af(n/b) \leq cf(n)$ for some $c < 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$.
    \end{itemize}
\end{theorem}
\end{document}

max_stars_repo_name: facebookEIR/algorithms-course

max_issues_repo_name: facebookEIR/algorithms-course

max_forks_repo_name: facebookEIR/algorithms-course


text:
\section{Brokerinfo access Class List}
Here are the classes, structs, unions and interfaces with brief descriptions:\begin{CompactList}
\item\contentsline{section}{\hyperlink{classBrokerInfo}{Broker\-Info} (Parses .Broker\-Info file containing job submission parameters )}{\pageref{classBrokerInfo}}{}
\item\contentsline{section}{\hyperlink{classBrokerInfoEx}{Broker\-Info\-Ex} }{\pageref{classBrokerInfoEx}}{}
\end{CompactList}

max_stars_repo_name: italiangrid/wms

max_issues_repo_name: italiangrid/wms

max_forks_repo_name: italiangrid/wms


text:
\section{Introduction}
\label{sec:introduction}

Peer-to-peer (p2p) systems have become more and more popular in several network applications and services. Due to their self-organizing paradigm, p2p systems avoid a single-point-of-failure and have been proven to be cost-effective, robust and scalable. However, in modern miscellaneous peer-to-peer networks, combining desktop computers and mobile devices, the homogeneous roles of peers clash with the heterogeneous capabilities of their hosts. Weaker hosts that are responsible for important tasks, such as providing popular files, may reduce the overall service quality. Therefore, advanced p2p systems try to allocate heavier load to stronger peers.

Identifying and indexing peers by their capabilities is an ongoing research. Recently, we have proposed PacketSkip, a Skip Graph based, ordered indexing structure, that provides multidimensional range queries for multi-featured peer capacities. Skip Graphs provide a non-hierarchical, distributed data structure where data is arranged in a sorted sequence, access times are logarithmic on average and the graph is robust against node failure. The PacketSkip service inherits and extends these features. PacketSkip can be added as an additional layer to any DHT-based p2p overlay. Although its storage demands are already low, storage and update traffic scalability was still of concern for high-dimensional data. Also, the index uses the overlay's lookup mechanism which adds the networks lookup complexity as a factor to its communication durations.

In this paper, we propose several efficiency optimizations for PacketSkip which help to reduce storage and traffic costs while also boosting performance:

\begin{enumerate}
  \item protocol change: additional features are added to index elements on the receiving node instead of the sending peer
  \item protocol change: additional features are only stored in an index element if they are lexicographically higher
  \item protocol change: a multidimensional search must focus on the feature which is lexicographically lowest
  \item message delivery optimization: adding a node$\rightarrow$host mapping as a communication cache to each node
\end{enumerate}

PacketSkip has been introduced in detail in Funke \cite{packetskip09} and Disterh{\"o}ft et al. \cite{packetskip10}.
%A concise recap follows in Section~\ref{subsec:packetskip}.
From now on we will refer to these previous protocol revisions as (protocol) v0.9 and v1.0, respectively.
The now introduced changes to the protocol, which are discussed in Section~\ref{sec:solution}, will be referred to as v1.1 and v1.2.

The remainder of this paper is organized as follows: first, we briefly discuss related works (Section~\ref{sec:related}). We then give a short introduction to Skip Graphs and recapitulate the protocol versions 0.9 and 1.0 by which PacketSkip was originally defined (Section~\ref{sec:protocol}). Next, we discuss the issues on which we want to elaborate our solutions (Section~\ref{sec:solution}) and present the outcome of our thorough evaluation (Section~\ref{sec:evaluation}). Finally, our conclusion and further suggestions for improvements are discussed in Section~\ref{sec:conclusion}.

max_stars_repo_name: andifunke/packetskip

max_issues_repo_name: andifunke/packetskip

max_forks_repo_name: andifunke/packetskip


text:
\documentclass[a4paper]{report}
%Gummi|063|=)
\title{\textbf{RnD Meeting 1} \\
		Minutes for October 30, 2014}

\author{B-IT Master Studies Autonomous Systems\\
		University of Applied Sciences Bonn-Rhein-Sieg\\
		}
\date{}
\begin{document}

\maketitle

\section{Present}
\begin{itemize}
	\item Deebul Nair
	\item Prof. Dr. Paul G. Pl{\"o}ger
\end{itemize}
\section{Discussed}
\begin{itemize}
	\item Deebul Presented his RnD Proposal for winter semester 2014. Proposal was regarding application of Recommender System in Robotics. PhD Thesis of Pyry Matikainen was briefly discussed about similar application. Also University of Frieburgs application of the system in Robot Learning was discussed.
	\item Professor commented not to use the specific case of Recommender Systems. But to Generalize the idea of Recommender System (i.e. to completely understand the science behind the Recommender systems) and view the problem as a general Machine learning problem. Such that the Recommender System becomes 1 of the application of the generalized Machine learning.
	\item Based on this scientific knowledge behind Recommender System Deebul will Program a solution  for Robotics application and evaluate the results.

\end{itemize}

\section{Approved Activities}
\begin{itemize}
	\item Extending the Robot Learning experiment(From Univ Frieburg) for youBot and applying in Robocup as a use case to the RnD.
	\item Continue exploration for new areas in robotics application where the Recommender systems can be applied.
	\item Prof. Dr. Paul G. Pl{\"o}ger has agreed to be the advisor of Nair Deebul.
\end{itemize}

\section{Next Meeting}
To be decided.
\end{document}

max_stars_repo_name: deebuls/RecommenderSystemInRobotics

max_issues_repo_name: deebuls/RecommenderSystemInRobotics

max_forks_repo_name: deebuls/RecommenderSystemInRobotics


text:
\documentclass[11pt]{exam}

\usepackage{listings}
\usepackage{lipsum}
\usepackage{graphicx}
\usepackage{color}
\usepackage{multirow}

\lstdefinestyle{latexsty}{
	language={[LaTeX]TeX},
    basicstyle=\small\ttfamily,
    breaklines=true,
    breakindent=0pt,
    numbers=left, stepnumber=1, numbersep=5pt,
    commentstyle=\color{red},
    showstringspaces=false,
    keywordstyle=\color{blue}\bfseries,
    morekeywords={align,begin},
    tabsize=2,
    frame=single,
}

\pagestyle{headandfoot}
\runningheader{\LaTeX: An Introduction (Part 1)}{Exercise 3}{10th February 2014}
\runningheadrule
\runningfooter{}{\thepage}{}
\runningfootrule

\title{Exercise 3 - Lists and Tables in \LaTeX}
\author{UGC `\LaTeX: An Introduction (Part 1)' Training Course}
\date{February 10th 2014}

\begin{document}
\maketitle

\fbox{\parbox{0.9\textwidth}{In this exercise, we will practice making lists and tables. You can do it in a separate document, or continue adding content to the document you used in the last exercise.}}

\vspace{0.2in}

\section{Lists}

\begin{questions}

\question
Add a simple list that looks like the one below to your document.

\begin{itemize}
	\item A list item
	\item Another list item
	\item Yet another list item
\end{itemize}

\question
Can you change the list you just made so that the items are numbered? How?

\question
Try creating a description list like the one below. Again, the text you use doesn't particularly matter.

\vspace{0.1in}
\begin{minipage}[ht!]{0.4\textwidth}
\begin{description}
	\item[First Paragraph] Some text about something, I'm not sure what
	\item[Second Paragraph] Some more text about something else that is different?
	\item[Third Paragraph] This isn't the same as the previous items
\end{description}
\end{minipage}

\question
Create a nested list. Can you nest lists of different type within each other?

\end{questions}

\section{Tables}

\begin{questions}

\question Make a simple table like the one below:

\begin{center}
\begin{tabular}{l | l | l}
    a & b & c \\
    d & e & f \\
    g & h & i \\
    j & k & l \\
\end{tabular}
\end{center}

\question Add a header row to your table so it looks like this:

\begin{center}
\begin{tabular}{l | l | l}
	1 & 2 & 3 \\
	\hline
    a & b & c \\
    d & e & f \\
    g & h & i \\
    j & k & l \\
\end{tabular}
\end{center}

\question
Create a table like the one below where the text in one of the columns is too large to fit on the page without wrapping:

\begin{center}
    \begin{tabular}{ | r | l | l | p{6cm} |}
    \hline
   	Number & Player & Position & Summary \\ \hline
	1 & Chris Weale & Goalkeeper & Experienced goalkeeper who moved to the Greenhous Meadow in July 2012 after three seasons at Championship club Leicester City. \\ \hline
	2 & Jermaine Grandison & Defender & The powerful defender, equally comfortable at right back or centre half, joined the club from Coventry City, initially on loan in January 2011, impressing enough to be offered a permanent deal.\\ \hline
	7 & Mark Wright & Midfielder & The Wolverhampton-born winger has emerged as a consistent goalscorer since joining Shrewsbury, registering double figures from out wide in each of his first two seasons at the Greenhous Meadow.\\ \hline
    \end{tabular}
\end{center}

\question
Create a table with a heading cell that spans multiple columns as below:

\begin{center}
\begin{tabular}{ |l|l| }
  \hline
  \multicolumn{2}{|c|}{Team sheet} \\
  \hline
  GK & Chris Weale \\
  DF & Jermaine Grandison \\
  DF & Joe Jacobson \\
  DF & Connor Goldson \\
  DF & Cameron Gayle \\
  MF & Mark Wright \\
  MF & Paul Parry \\
  MF & Aaron Wildig \\
  MF & Matt Richards \\
  ST & Marvin Morgan \\
  ST & Ryan Doble \\
  \hline
\end{tabular}
\end{center}
\clearpage

\question
Create a complex table like the one below where some cells stretch over multiple columns and some stretch over multiple rows. (\emph{Hint - remember the \texttt{multirow} package})
\begin{center}
\begin{tabular}{ |l|l|l| }
\hline
\multicolumn{3}{ |c| }{Team sheet} \\
\hline
Goalkeeper & GK & Chris Weale \\ \hline
\multirow{4}{*}{Defenders} & LB & Jermaine Grandison \\
 & DC & Joe Jacobson \\
 & DC & Connor Goldson \\
 & RB & Cameron Gayle \\ \hline
\multirow{3}{*}{Midfielders} & MC & Mark Wright \\
 & MC & Paul Parry \\
 & MC & Aaron Wildig \\ \hline
Forward & FW & Matt Richards \\ \hline
\multirow{2}{*}{Strikers} & ST & Marvin Morgan \\
 & ST & Ryan Doble \\
\hline
\end{tabular}
\end{center}

\end{questions}

\end{document}