text:
\chapter{Methods}

In this section, I will review the methodology that was used in the two sections of this doctoral thesis. First, I will explain the components and structure of the research framework that was developed to organize and analyze efficiently the data of the Johns Hopkins Myositis Center longitudinal cohort study. Second, I will detail the most relevant statistical techniques that were used to perform the series of epidemiologic analysis of this clinical cohort. Finally, I will summarize the design of the Myositis muscle RNA sequencing studies, focusing on the bioinformatic analysis of the resulting sequencing data that was obtained. The detailed information about the methods of each of the individual studies that compose this doctoral thesis is included in \autoref{chap:appendix}.

\section{Longitudinal cohort study framework}

\subsection{The Johns Hopkins Myositis Center longitudinal cohort study}
In 2007 the Johns Hopkins Hospital founded a monographic center to treat and do research in patients with different types of myositis. It is a multidisciplinary unit combining the expertise of Rheumatologists, Neurologists, Pulmonologists, and Physical Therapy specialists. Over the years, more than two thousand patients suspected of having an inflammatory myositis have been evaluated and followed over time, becoming the largest longitudinal myositis cohort in the world.

\subsection{Database design}

In 2013, a research database was created to organize the information that was available for the patients of the myositis cohort. The first challenge was to collect all the information, that was originally spread over different files with data of variable quality, included inconsistencies, duplicated observations, was not normalized, and relied heavily on text descriptions.

To organize this heterogeneous collection of data, first, we had to choose what would be the main blocks of information that were relevant from a myositis research standpoint and how to organize them in a way that will be useful not just for a single project but for many studies to come.

It was decided that the minimum set of data that we needed included a unique identifier for each patient and epidemiological data, like the gender, date of birth, or the race. Moreover, it was necessary to include, among others: the general phenotype of the patients; the family history; the medications; the clinical features as they were longitudinally recorded; the results of the laboratory tests, \gls{mri}, muscle biopsy, pulmonary function tests, and chest \gls{ct}. Finally, we would need to include the information of each one of the autoantibodies, both the consensus interpretation and all the individual serologic results.

Also, we had to select the best technical solution to store the data according to the expected level of usage, limited time to maintain it, and availability of the software in the terminals of the different users. It was decided that using Microsoft Access fulfilled the required criteria for its initial intended usage (Figure \ref{fig:db_frontend}). It could be used concurrently by up to 20 users, both the front-end and the back-end could be easily maintained by a single researcher, and it had institutional support in all the user terminals. The database was designed so that only a limited number of people would have access to the back-end, but all the researchers in the protocol could view, query, and modify the data in the front-end. Over the years this framework stopped being compliant with the institutional Hopkins policies and the back-end was migrated to a Microsoft SQL Server, with ongoing plans for the front-end to be moved to a web framework.

A central database with un-duplicated information was shared by all the concurrent research projects, but each researcher was able to work in different subsets of patient and specific sets of variables by defining filters on each project's front-end. By having a central data repository, different projects would review and enter new data for themselves but, by doing so, they would be helping to curate the data for other concurrent and future projects, increasing the overall productivity of the group.

\begin{figure}
	\centering
	\includegraphics[width=1\linewidth]{db_frontend}
	\caption{Appearance of the front-end of the myositis database.}
	\label{fig:db_frontend}
\end{figure}

\subsection{Data mining}
Once the database was built, it was obvious that importing certain types of data could be automated. Originally, it was not feasible to access the back-end of the Hopkins electronic patient record system directly, but users had access to the front-end of the application to collect the data of those patients consented for the study. Also, there was no application programming interface to automate the data mining process. Thus, the only option, if we wanted to automate importing the thousands of registries, would be to do it through mouse and keyboard automation. A first crude data import was successful at automating the extraction of all the relevant clinical and laboratory data (e.g. creatine kinase, aldolase, AST, ALT, and autoantibody reports). This approach was further perfected through a script with modules to include each one of the sequences of key-strokes and mouse-clicks necessary to import each section of the data for every patient. Finally, contingency systems were put in place to reset and tag abnormal data imports when the system did not get the correct set of information.

A portion of the data required expert interpretation from researchers trained to evaluate medical jargon and familiarized with the type of disease. The front-end of the database was progressively modified to simplify these data-entry tasks and include quality control variables that could be used to detect errors during the process.

\subsection{Data wrangling}
Once the information was available in the database, a key part of any data analysis effort was to clean the raw data to adapt it to the specific analyses. It was key to automate these steps in order to be able to update the results if new data was added, be able to design the analysis at the same time that the data was being collected, and reuse the data cleaning steps to optimize productivity. Most analyses of clinical data were performed using Stata and thus, Stata scripts used the raw Access tables as the starting point of the process, which facilitated updating the data by replacing the raw tables. It was first necessary to integrate all the different tables in a single comprehensive dataset while allowing for enough flexibility so the process of integrating the tables was modular. A set of functions was built to merge each auxiliary table to the main one including the epidemiological features of the patients. Also, the variables were labeled and calculated fields were generated. Finally, a limited set of “working datasets” were built for the different families of analysis in order to avoid delays each time it was necessary to modify a piece of the code if the data to be used had not changed.

\subsection{Data analysis}
\subsubsection{Univariate analysis}
Univariate analysis is often the first step in an exploratory analysis. Hypothesis contrast using Fisher's exact test, Chi-squared, Student's T-tests, and Wilcoxon's rank-sum test is the bread and butter of any epidemiological study. However, performing these tests is often extremely labor-intensive due to the massive amount of comparisons that may be needed when multiple variables are being explored simultaneously. Also, generating publication-quality tables is often a source of productivity loss in research. For this reason, a Stata program called \textit{table\textunderscore compare} was built to simplify performing the hypothesis testing, deciding automatically when to perform Fisher's or Chi-square tests and manually to indicate if continuous variables should be considered normally-distributed or nonparametric tests should be applied. Moreover, this tool allows performing multivariate analysis, handles paired data, and can export the results ready for publication. This tool allowed us to speed up performing and updating the different analyses.

\subsubsection{Multilevel regression models}
A complication of observational longitudinal cohort studies, when performed in a clinical practice setting, is that each patient has a different number of observations (e.g. visits or laboratory determinations). In order to avoid bias, it is necessary to use techniques to take into account this uneven length of follow-up. A simplistic solution would be averaging the periods of observation and adjusting for the time of follow-up, but this would result in an unnecessary loss in statistical power. A valid alternative in this situation is to use a family of regression methods called multilevel regression models or random effects mixed models. These models include the fixed effects of conventional regression analysis but then allow for random components grouped in categories (e.g. each individual patient will have a different evolution of the \gls{ck} levels over time). Multilevel regression models allow for random intercepts (e.g. each patient having higher or lower overall \gls{ck}) and random slopes (e.g. each patient can have a faster or slower decrease in the \gls{ck} levels). Strictly speaking, the full model with random intercepts and random slopes is just necessary if it is significantly different from the model with random intercepts, and the model with random intercepts only if it is significantly different from the standard regression model. However, doing these model evaluations adds a layer of complexity that may be eliminated by using the most complex model with random slopes and random intercepts that will control for all possible variation caused by the heterogeneity of the patient population and the differential follow-up.

\subsubsection{Factor analysis of mixed data}
To model the phenotype of the patients we used factor analysis of mixed data. The phenotype is a latent variable, i.e., a variable that cannot be directly observed but has to be inferred through a mathematical model.

Factor analysis of mixed data is a principal component method dedicated to exploring data containing both continuous and categorical variables. The continuous variables are scaled to unit variance and the categorical variables are transformed into a disjunctive data table and then scaled using the specific scaling of multiple correspondence analysis. This ensures to balance the influence of both continuous and categorical variables in the analysis. It means that both variables are on an equal foot to determine the dimensions of variability. We used the package FactoMinerR v.2.1 to perform the factor analysis of mixed data and factoextra v. 1.0.6 to obtain the scree plots and the variable weight plots.

As input for the factor analysis of mixed data we selected a set of clinical, epidemiological, and laboratory parameters that were: 1) well documented in the literature to be associated with the phenotype of patients with myositis, 2) systematically collected in our cohort, and 3) well defined. Thus, we included:

\begin{enumerate}
	\item Epidemiologic variables: Gender, race, age at onset.

	\item Clinical variables: presence or absence during the course of the disease of muscle weakness, interstitial lung disease, arthritis, heliotrope or Gottron’s rash, calcinosis, Raynaud’s phenomenon, mechanic’s hands, dysphagia, and fevers.

	\item Laboratory values: Maximum \gls{ck}, presence of anti-Ro52 autoantibodies.
\end{enumerate}

Anti-Ro52 autoantibodies were included because they are associated with the severity of the disease and with specific clinical features in patients with myositis.\cite{PinalFernandez2017a,Vancsa2009,Marie2012,Bauhammer2016}

The detailed distribution of the muscle weakness, biopsy features, \gls{mri} patterns, or \gls{emg} findings were excluded from this analysis because they were not available for all patients, and restricting the sample size could bias the study.

\subsubsection{Model comparison}
Both the \gls{aic} and the \gls{bic} are estimators of out-of-sample prediction error and thereby the relative quality of statistical models for a given set of data.\cite{Akaike1974,Schwarz1978} Given a collection of models for the data, \gls{aic} and \gls{bic} estimate the quality of each model, relative to each of the other models. Thus, they provide a means for model selection.

The formula for \gls{aic} is:
\[AIC =  2-2\ln(\hat{L})\]

Whereas \gls{bic} is formally defined as:
\[BIC =  k\ln(n)-2\ln(\hat{L})\]

Where:
\begin{description}
	\item $\hat{L}$=the maximized value of the likelihood function of the model

	\item $n$=the number of observations

	\item $k$=the number of parameters estimated by the model
\end{description}

\gls{aic} and \gls{bic} are founded on information theory. When a statistical model is used to represent the process that generated the data, the representation will rarely be exact; so some information will be lost by using the model to represent the process. \gls{aic} and \gls{bic} estimate the relative amount of information lost by a given model: the less information a model loses, the higher the quality of that model.

In estimating the amount of information lost by a model, \gls{aic} and \gls{bic} deal with the trade-off between the goodness of fit of the model and the simplicity of the model. In other words, \gls{aic} and \gls{bic} deal with both the risk of overfitting and the risk of underfitting.

Given a set of candidate models for the data, the preferred model is the one with the minimum \gls{aic} or \gls{bic} value. Thus, \gls{aic} and \gls{bic} reward goodness of fit (as assessed by the likelihood function), but it also includes a penalty that is an increasing function of the number of estimated parameters. The penalty discourages overfitting, which is desired because increasing the number of parameters in the model almost always improves the goodness of the fit.

The main difference between \gls{aic} and \gls{bic} is that the penalty for the number of parameters is larger for \gls{bic}. Thus, if ‘k ‘is the number of parameters and ‘n’ is the number of observations, the penalty for \gls{aic} is $2k$, whereas for \gls{bic} is $\ln(n)k$.

Various authors have suggested guidelines to interpret the magnitude of the differences in \gls{aic} and \gls{bic} between two models ($\Delta$AIC and $\Delta$BIC respectively). Thus, Burnham and Anderson\cite{Burnham2004} suggested that models having $\Delta$AIC $\leq$ 2 have substantial support (evidence) to believe that are equivalent, those in which 4 $\leq$ $\Delta$AIC $\leq$ 7 have considerably less support, and models having $\Delta$AIC > 10 have essentially no support. Alternatively, Raftery\cite{Raftery1995} suggested that the evidence that two models are not equivalent would be weak with a $\Delta$BIC between 0-2, positive with $\Delta$BIC between 2-6, strong with $\Delta$BIC between 6-10, and very strong with $\Delta$BIC over 10. Based on this we selected a threshold of $\Delta$AIC and $\Delta$BIC of 10 to consider one model superior to others.

\subsubsection{Graphical analysis of longitudinal data}
A key part of any scientific study is to represent the results visually in a way that is easy and quick to understand even for non-experts. To do so in an efficient manner, functions were build to make the most common graphical analysis, including individual and aggregated patient evolution plots and Kaplan-Meier curves. A useful graphical method to represent the evolution of nonlinear parameters longitudinally is the \gls{lowess}. \gls{lowess} fits simple models to localized segments of the data to build up a function that describes the deterministic part of the variation in the data, point by point.
The advantage of \gls{lowess} over other methods (e.g. quadratic regression) is that it does not need to specify a function to fit the model to the data, making it simple and flexible for complex graphical representations. Alternatively, it requires a dense cloud of observations to be stable and it can be easily biased by outliers if the local density of data is low. Also, \gls{lowess} does not return a simple mathematical function and, thus, is complicated to use for predictive purposes. Finally, \gls{lowess} is relatively computationally intensive, but with the range of observations that we used (in the thousands), this was a negligible issue.

\subsubsection{Survival analysis}
Many clinical questions in our dataset were related to the rate of development of the clinical manifestations from the onset of the disease. Also, death is, in all severe systemic diseases, an important prognostic predictor to analyze. Both the timing to develop a clinical manifestation and the time to death were appropriate questions to analyze using COX regression and Kaplan-Meier curves.

\subsubsection{Standardized cancer and mortality rates}
A recurrent question in cohort studies of patients with myositis is if certain groups of patients have higher cancer or mortality rates. Internal comparisons can be helpful by defining if some groups have higher or lower mortality rates than others or than the rest of the individuals in the cohort. However, the most relevant comparison is often with the general population through indirect standardization. A limitation of these types of comparisons is that they require well-annotated epidemiological data. In the US, both survival and cancer data can be acquired through the Centers for Disease and Control Prevention. Specifically, mortality data can be obtained from the United States Cancer Statistics (UCSC) registry (\url{www.cdc.gov/cancer/uscs/}) while the survival data can be acquired from the Compressed Mortality File (\url{wonder.cdc.gov/wonder/help/cmf.html}).

\section{Myositis muscle RNA sequencing studies}
Obtaining insight into the pathogenesis of the disease is the first basic step to understand the variability in the clinical manifestations, tailor specific treatments for the disease, and estimate how many disease categories there are. In order to do so, Next Generation Sequencing techniques are extremely powerful since they allow us to get great volumes of data on the transcriptional changes of the affected tissues. For this section of the study, we used RNA sequencing from myositis muscle biopsies to understand the mechanisms of muscle damage in these autoimmune diseases. Moreover, for certain studies, we also used RNA sequencing data from differentiated human skeletal muscle cells and injured mouse muscle.

\subsection{Cultured human skeletal muscle cells}
Human skeletal muscle myoblasts (Lonza) were cultured according to the manufacturer’s protocol. When 80\% confluent, the cultures were induced to differentiate into myotubes by replacing the growth medium with differentiation medium (DMEM, 2\% horse serum, and L-glutamine).  Two plates of cells were collected for RNA extraction at 7 separate time points: immediately before differentiation and then daily for 6 days.

\subsection{Mouse Muscle Injury}
Muscle injury and regeneration were induced in mice using cardiotoxin. Briefly, 6 week-old C57BL/6 mice were unilaterally injured by intramuscular injection of 0.1 mL of 10 uM CTX into the tibialis anterior muscle. Injured tibialis anterior muscles were harvested at days 3 (n=2), 5 (n=2), 7 (n=2), 10 (n=4), 14 (n=4), and 28 (n=3) post-injury. Contralateral (uninjured) tibialis anterior muscles were also collected (n=9). Muscle tissue was snap-frozen and stored at -80 degrees Celsius.

\subsection{Human muscle biopsy processing}
Open muscle biopsies were placed in an aluminum foil envelope. 2-methylbutane (isopentane) was pre-chilled using liquid nitrogen and the aluminum foil envelopes were submerged in the isopentane for 15 seconds. After this, the samples were placed in cryovials at -80º for long-term storage. Samples collected at other institutions were shipped in dry ice to the NIH Muscle Disease Unit.

\subsection{RNA extraction}
The first step to perform RNA sequencing is to get the RNA from the samples of interest. To do so we had first to homogenize the muscle tissue using ceramic beads and then separate the RNA from the rest of the components of the cell using the TRIzol protocol. Briefly, muscle biopsies were homogenized in TRIzol using 1.4 mm ceramic bead low-binding tubes, and the RNA was extracted using the regular TRIzol protocol. Concentration and quality of the resulting RNA were assessed using standard NanoDrop and TapeStation protocols, respectively.

\subsection{RNA library preparation}
Libraries were prepared using the NeoPrepTM system according to the TruSeqM Stranded mRNA Library Prep protocol (Illumina) and sequenced using the Illumina HiSeq 2500 or 3000. This methodology had the advantage of being mostly automated, decreasing possible human errors in this step.

\subsection{RNA sequencing analysis}
\subsubsection{Demultiplexing}
Since modern DNA sequencers have a huge sequencing capacity, several samples can be run in each lane of a flow cell. Thus, the first step after we have sequenced the RNAseq library will be to separate all the different experiments in individual folders based on their characteristic index. This was performed using bcl2fastq v.2.17.1 parallelizing it to speed up the process. The output of this step is a file in .fastq format consisting of repeating blocks of 4 lines containing the annotation, sequence, comments, and quality of each one of the reads of the experiment.

\subsubsection{Sequence cleanup}
After the sequences of each sample are demultiplexed it is convenient to clean up the data to eliminate sequences with low quality and remove adapter contamination that may bias the results. This was performed using trimmomatic v.0.36.

\subsubsection{Alignment}
Once the sequences were cleaned each read had to be aligned to the reference genome in order to be able to identify what genes are expressed and how much. A technical complication for this step in RNAseq libraries is that mature RNA has been already spliced and thus, sequences containing sections of two or more exons will not be aligned to any region of the reference DNA since it includes the intronic regions. To overcome this limitation, specific RNA aligners have been developed that work by splitting reads that cannot be aligned confidently and trying to align each fragment of the split separately. This will be repeated recursively until the whole read could be aligned or it was concluded that there was no good match in the reference genome.  Limited studies have compared the multiple available tools to perform RNA alignment, concluding that STAR offers slightly better accuracy compared to other options.\cite{Baruzzo2017} Thus, to perform the alignment we used STAR v.2.5 using the hg19 (GRCh37) or the mm10 (GRCm38) reference genomes.

\subsubsection{Gene expression quantitation}
In RNA sequencing libraries the number of reads of each gene is proportional to the level of expression of that gene in the sample of origin. However, the number of reads will be influenced by the length of the gene and the total number of reads of the library. Thus, to quantify the levels of expression of each gene the resulting number of reads has to be normalized to the total number of reads of the library and the length of each gene. Two basic statistics are used to measure the level of expression of RNAseq experiments depending on how the normalization is performed, \gls{fpkm}, and \gls{tpm}. \glspl{fpkm} are calculated by dividing the read counts of each gene by the total number of read counts of the library and the result is divided by the length of the gene in kilobases. Alternatively, the \gls{tpm} is calculated by dividing first by the length of the gene and later on by the total number of reads of the library. The advantage of \gls{tpm} over \gls{fpkm} would be that the total number of \glspl{tpm} per library will be constant and this will allow us to compare the levels of expression of different genes across different samples. Alternatively, \gls{fpkm} is more popular and is valid for comparing the same gene across different samples, which is one of the most common comparisons to make.

RNAseq libraries can be single-end or pair-end depending on the number of RNA reads that are obtained from each strand of RNA (one in single-end and two at each side in pair-end). In single-end experiments, \gls{fpkm} can be also named RPKM or reads per kilobase million. However, for paired-end experiments the term read is not correct because each pair of reads identifies a fragment, and for this reason, is preferable to use the term \gls{fpkm} that will be correct both for single and pair-end experiments.

There are multiple libraries that allow quantitation of the level of expression of each gene and most of them result in similar results provided that the same gene coordinates are used. In our case, we used Stringtie v.1.3.3, which is a tool contained in the “new Tuxedo package”.\cite{Pertea2016}

\subsubsection{Quality control}
A key part of any Next Generation Sequencing pipeline is to confirm that the quality of the reads is adequate for the purposes of the analysis and there are no sequencing artifacts. This can be performed right after the sequencing, the demultiplexing, the alignment, or after the gene quantification steps. Given that examining the output of the quality control for hundreds of samples can be tedious and time-consuming, in our experience it was more efficient to perform the quality control at the end of the pipeline to capture any failures that the process could have produced. In case of problems with the sample, further steps of quality control after each one of the steps can help to identify the error. For doing the quality control we used fastqc v.0.11.2.

\subsubsection{Differential expression}
The main results of an RNAseq analysis are the expression levels of each one of the ~20,000 genes in a biological sample. However, the relevant questions usually require comparing the differences between conditions. The process of comparing the levels of expression among biologically relevant groups is called differential expression. This is, arguably, one of the most critical steps in the RNAseq pipeline given the multiple models that can be used to do the comparisons and the variety of tools available for the task. Some of these tools use the Poisson distribution, others the negative binomial or the beta-binomial while there are some that use Bayesian non-parametric models. Thus, both edgeR and DESeq2 use a variation of the Fisher exact test adopted for the negative binomial distribution returning exact p-values computed from the derived probabilities. CuffDiff uses the test statistics $T=\dfrac{E[\log(y)]}{Var[\log(y)]}$, where y is the ratio of the normalized counts between two conditions, and this ratio approximately follows a normal distribution. Hence a t-test is used to calculate the p-value for the differential expression. Finally, limma uses a moderated t-statistic to compute p-values in which both the standard error and the degrees of freedom are modified. All of these tools used the Benjamini and Hochberg approach for multiple hypothesis correction.\cite{Benjamini1995}

The results of these tools vary considerably and there is yet no gold standard on which is the best to do these types of analyses. However, there are studies comparing them showing that DESeq may have a slight advantage in terms of detection accuracy.\cite{Seyednasrollah2015} Moreover, our own benchmark tests showed that CuffDiff had a very poor correspondence with previous gene expression data in our field, while both EdgeR, DESeq, and limma had similar and good results. In conclusion, we decided to use the DESeq2 v.1.20 algorithm for differential expression.\cite{Love2014}

DESeq2 performs an internal normalization where the geometric mean is calculated for each gene across all samples. The counts for a gene in each sample are then divided by this mean. The median of these ratios in a sample is the size factor for that sample. This procedure corrects for library size and RNA composition bias, which can arise, for example, when only a small number of genes are very highly expressed in one experiment condition but not in the other.

Additionally, DESeq2 automatically detects count outliers using the Cooks' distance and removes these genes from the analysis. DESeq2 v.1.20 also performs independent filtering which maximizes the number of genes which will have a Benjamini and Hochberg-adjusted p–value\cite{Benjamini1995} less than a critical value set by default to 0.1. Removing these genes with low counts improves the detection power by making the multiple testing adjustment of the p-values less severe. To speed up the computations we prefiltered genes with a total count across conditions below 10. Since these genes would have been excluded from the analysis afterward anyways, this did not influence the calculations at all.

DESeq2 uses shrinkage estimation for dispersions and fold changes. A dispersion value is estimated for each gene through a model fit procedure. Using these estimations, the package fits a negative binomial generalized linear model for each gene and uses the Wald test for significance testing. The Wald test p-values from the subset of genes that pass the independent filtering step are adjusted for multiple testing using the procedure of Benjamini and Hochberg.\cite{Benjamini1995}

To ensure the stability of the central tendency and dispersion values of each biological group between different sections of the study, the normalization process included the totality of the samples even if that specific comparison did not include some of those samples.

We assigned equal weights to each autoantibody subgroups within \gls{dm} and  \gls{imnm} to avoid giving more importance to differentially expressed transcriptomic features of autoantibody subgroups with a higher number of biopsies at this stage of the analysis.

\subsubsection{Pathway analysis}
Once we have identified the list of genes explaining the differences between two or more conditions it is often necessary to find what are the pathways that are activated or suppressed. Doing so has the main difficulty of being based on manual annotations of the pathways. Thus, if the annotation is poor, incomplete, or contains wrong data our pathway analysis will be biased. There are several tools to perform pathway analysis, most of them basing their results on the Fisher’s exact test, the hypergeometric distribution, or a chi-square analysis of the 2x2 contingency tables comparing the number of genes observed in our dataset with the genes present in each pathway. DAVID and MetaCore have similar approaches to the problem by doing a simple frequentist assessment of genes present in the case dataset vs. genes observed in each pathway. Alternatively, IPA Pathway analysis also performs this basic analysis but it also provides information about the activation or suppression of the pathway. Another option is to use \gls{gsea}. This approach has the advantages of not needing an arbitrary threshold to define a list of “significant” genes and that it uses the actual significance of the associations of the genes with the trait being analyzed. However, it is limited to a single pathway comparison at a time and, thus, it is less suitable for pathway discovery purposes.

\subsubsection{RNAseq-based classification}
RNAseq is an extremely powerful technique that quantifies simultaneously the expression of more than twenty thousand genes. This has the potential to be used predictively to classify complex diseases based on its pathogenesis. Multiple algorithms can be used for this task, from simplistic approaches using logistic regression and simple classification trees to bagging or boosting strategies (like the random forest or AdaBoost respectively). Moreover, neural networks and other algorithms like the support vector machines can also be useful for this task. However, given that there are no good studies assessing when to use each algorithm based on the characteristics of the data, we took an agnostic approach to this problem by testing all these mathematical tools in the same training datasets and testing their accuracy in those samples that were not used for training purposes.

In short, the sample was split into a training set containing 2/3 of the observations and a test set containing the remaining 1/3. The training set was used to build the classificatory models and the testing set to evaluate the accuracy of the model. The classifiers that we tested were the linear support vector machine (SVM), the radial basis function SVM, random forest, nearest neighbor, Gaussian process, decision tree, multi-layer perceptron neural network, adaptative boosting (AdaBoost), gaussian naïve Bayes and quadratic discriminant analysis. Models were built in 2/3 random resamples of the data and tested in the remaining 1/3. The accuracy of classifying correctly each one of the myositis subsets was determined based on the mean and 95\% CI of one thousand resampling cycles.

We decided to use all the genes that were significantly different (with a cutoff q-value <0.05) in each group compared to the rest using all the samples. An alternative would have been to include the differentially expressed genes contained in the training set of each cycle. However, this approach was excessively computationally expensive. Nonetheless, to demonstrate the equivalency of these approaches, we modified our pipeline to train 100 cross-validation cycles using only the differentially expressed genes resulting from each training set and the performance of the models was equivalent using both methods.

\subsubsection{Ranking genes in classificatory models}
Oftentimes it is interesting to rank the most important features for the classification model. This can be done, independently of the algorithm, using recursive feature elimination.\cite{Guyon2002} This technique iteratively constructs new models removing the features with low weights and thus, estimating the importance of each feature for the prediction task.


text:
\documentclass[landscape, 8pt, a4paper, oneside, twocolumn]{extarticle}
%\documentclass[]{article}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\usepackage{minted}
\usepackage{amsmath}
\usepackage{pdfpages}
\usepackage[compact]{titlesec}
\usepackage{fancyhdr}
\usepackage{lastpage}
\setlength{\columnseprule}{0.4pt}

%\title{Process Coding! Re:Debug Team's Team Note}
%\author{Lee Dong Kwan (cyberflower)}
%\date{\today}

\pagestyle{fancy}
\lhead{Korea Univ - Process Coding! Re:Debug, author: Lee Dong Kwan, Kim Sang Rae, Park Min Soo}
\rhead{Page \thepage  \ of \pageref{LastPage} }
\fancyfoot{}

\begin{document}{
\large
%\maketitle
\tableofcontents
}
\pagebreak

\section{Segment Tree}
\subsection{Lazy propagation}
\begin{minted}{cpp}
ll seg[4*SZ];
ll lazy[4*SZ];
void upd_lazy(int idx, int l, int r){
  seg[idx]+=(ll)(r-l+1)*lazy[idx];
  if(l!=r){
    lazy[2*idx]+=lazy[idx];
    lazy[2*idx+1]+=lazy[idx];
  }
  lazy[idx]=0LL;
}
void seg_update(int idx, int l, int r, int fl, int fr, ll plus){
  upd_lazy(idx,l,r);
  if(r<fl || fr<l) return;
  if(fl<=l && r<=fr){
    seg[idx]+=(ll)(r-l+1)*plus;
    if(l!=r){
      lazy[2*idx]+=plus;
      lazy[2*idx+1]+=plus;
    }
    return;
  }
  seg_update(2*idx,l,(l+r)/2,fl,fr,plus);
  seg_update(2*idx+1,(l+r)/2+1,r,fl,fr,plus);
  seg[idx]=seg[2*idx]+seg[2*idx+1];
}
ll seg_find(int idx, int l, int r, int fl, int fr){
  upd_lazy(idx,l,r);
  if(r<fl || fr<l) return 0LL;
  if(fl<=l && r<=fr) return seg[idx];
  return seg_find(2*idx,l,(l+r)/2,fl,fr)+seg_find(2*idx+1,(l+r)/2+1,r,fl,fr);
}
\end{minted}

\subsection{Persistent Segment Tree}
\begin{itemize}
    \item this code is find the number of point inside rectangle
    \item rectangle represent as lx,rx,by,ty
\end{itemize}
\begin{minted}{cpp}
vector<int> graph[SZ];
int head[SZ];
struct Node{
  ll val; int l, r;
  Node():val(0),l(l),r(r){}
  Node(int l, int r, ll val):l(l),r(r),val(val){}
};
vector<Node> pst(2);
void update(int idx, int il, int ir, int g, ll x){
  if(g<il || ir<g) return;
  if(il==ir) return;
  int m=(il+ir)/2;
  if(g<=m){
    int lx=pst[idx].l;
    pst.pb(Node(pst[lx].l,pst[lx].r,pst[lx].val+x));
    pst[idx].l=pst.size()-1;
    update(pst[idx].l,il,m,g,x);
  }
  else{
    int rx=pst[idx].r;
    pst.pb(Node(pst[rx].l,pst[rx].r,pst[rx].val+x));
    pst[idx].r=pst.size()-1;
    update(pst[idx].r,m+1,ir,g,x);
  }
}
ll query(int idx, int il, int ir, int fl, int fr){
  if(ir<fl || fr<il) return 0;
  if(fl<=il && ir<=fr) return pst[idx].val;
  ll res=0;
  res+=query(pst[idx].l,il,(il+ir)/2,fl,fr);
  res+=query(pst[idx].r,(il+ir)/2+1,ir,fl,fr);
  return res;
}
int main(void){
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  int t; cin>>t;
  while(t--){
    memset(head,0,sizeof(head));
    for(int i=0;i<SZ;i++) graph[i].clear();
    pst.clear();
    pst.resize(2);
    int n,m; cin>>n>>m;
    for(int i=0;i<n;i++){
      int x,y; cin>>x>>y;
      x++; y++;
      graph[x].pb(y);
    }
    for(int i=1;i<SZ;i++){
      if(!head[i]){
        pst.pb(Node(pst[head[i-1]].l,pst[head[i-1]].r,pst[head[i-1]].val));
        head[i]=pst.size()-1;
      }
      for(int y:graph[i]){
        pst[head[i]].val+=1;
        update(head[i],1,SZ-1,y,1);
      }
    }
    ll res=0;
    for(int i=0;i<m;i++){
      int lx,rx,by,ty; cin>>lx>>rx>>by>>ty;
      lx++, rx++, by++, ty++;
      res+=(query(head[rx],1,SZ-1,by,ty)-query(head[lx-1],1,SZ-1,by,ty));
    }
    cout<<res<<'\n';
  }
  return 0;
}
\end{minted}

\subsection{Heavy Light Decomposition(HLD)}
\begin{minted}{cpp}
vector<vector<pii>> v,grp;
int dep[N],par[N],sz[N],lca[N][20],edge[N][2];
pii id[N];
struct segtree{
  int root[N],siz[N],t[N*2],l[N*2],r[N*2],now=0;
  int construct(vector<pii> &a,int s,int e){
    int x=now++;
    if(s==e) t[x]=a[s].ss;
    else{
      int mid=(s+e)/2;
      l[x]=construct(a,s,mid);
      r[x]=construct(a,mid+1,e);
      t[x]=max(t[l[x]],t[r[x]]);
    }
    return x;
  }
  void construct(vector<pii> &a, int k){
    root[k]=construct(a,0,a.size()-1);
    siz[k]=a.size();
  }
  void update(int s,int e,int x,int p,int vv){
    if(s==e) t[x]=vv;
    else{
      int mid=(s+e)/2;
      if(p<=mid) update(s,mid,l[x],p,vv);
      else update(mid+1,e,r[x],p,vv);
      t[x]=max(t[l[x]],t[r[x]]);
    }
  }
  void update(int k,int p,int vv){
    update(0,siz[k]-1,root[k],p,vv);
  }
  int query(int s,int e,int x,int left, int right){
    if(left>e||s>right) return 0;
    if(left<=s&&e<=right) return t[x];
    int mid=(s+e)/2;
    return max(query(s,mid,l[x],left,right),query(mid+1,e,r[x],left,right));
  }
  int query(int k,int left,int right) {
    return query(0,siz[k]-1,root[k],left,right);
  }
}t;
int dfs0(int x, int parent, int hei){
  dep[x]=hei;
  par[x]=parent;
  sz[x]=1;
  for(auto i:v[x]){
    if(i.ff!=parent) sz[x]+=dfs0(i.ff,x,hei+1);
  }
  return sz[x];
}
void dfs(int x, int wei, vector<pii> &a){
  a.emplace_back(x,wei);
  int heavy=0,mx=0;
  for(auto i:v[x]) {if(i.ff!=par[x]&&mx<sz[i.ff]) mx=sz[i.ff],heavy=i.ff;}
  for(auto i:v[x]){
    if(i.ff!=par[x]){
      if(i.ff==heavy) dfs(i.ff,i.ss,a);
      else{
        grp.emplace_back();
        dfs(i.ff,i.ss,grp[grp.size()-1]);
      }
    }
  }
}
int LCA(int x,int y){
  if(dep[x]>dep[y]) return LCA(y,x);
  for(int i=19,d=dep[y]-dep[x];i>=0;i--) if(d&(1<<i)) y=lca[y][i];
  for(int i=19;i>=0;i--) if(lca[x][i]!=lca[y][i]) x=lca[x][i],y=lca[y][i];
  return x==y?x:par[x];
}
int down(int x,int p){
  if(id[x].ff==id[p].ff){
    return t.query(id[x].ff, id[p].ss+1, id[x].ss);
  }
  else{
    return max(t.query(id[x].ff,0,id[x].ss),down(par[grp[id[x].ff][0].ff],p));
  }
}
int query(int x,int y){
  int l=LCA(x,y);
  return max(down(x,l),down(y,l));
}
int main(){
  int n;
  scanf("%d",&n);
  v.resize(n+1);
  for(int i=1;i<n;i++){
    int x,y,d;
    scanf("%d %d %d",&x,&y,&d);
    v[x].push_back({y,d});
    v[y].push_back({x,d});
    edge[i][0]=x;
    edge[i][1]=y;
  }
  grp.reserve(N);
  dfs0(1,1,1);
  grp.emplace_back();
  dfs(1,0,grp[0]);
  for(int i=0;i<grp.size();i++)
    for(int j=0;j<grp[i].size();j++) id[grp[i][j].ff]={i,j};
  for(int i=1;i<=n;i++) lca[i][0]=par[i];
  for(int j=1;j<20;j++)
    for(int i=1;i<=n;i++) lca[i][j]=lca[lca[i][j-1]][j-1];
  for(int i=0;i<grp.size();i++) t.construct(grp[i],i);
  int q;scanf("%d",&q);
  while(q--){
    int qt,x,y;
    scanf("%d %d %d",&qt,&x,&y);
    if(qt==1){
      int X=edge[x][0],Y=edge[x][1];
      pii Z=dep[X]<dep[Y]?id[Y]:id[X];
      t.update(Z.ff,Z.ss,y);
    }
    else printf("%d\n",query(x,y));
  }
}
\end{minted}

\section{Graph Theory}
\subsection{2-SAT, SCC}
\begin{minted}{cpp}
const int SZ = 2*10005;
int num[SZ];
int low[SZ];
int scc[SZ];    // scc group
vector<int> graph[SZ];
stack<int> s;
int p,q,n,m;
void dfs(int x){
  s.push(x);
  num[x]=++p;
  low[x]=p;
  for(int nxt : graph[x]){
    if(num[nxt]==0){
      dfs(nxt);
      low[x]=min(low[x],low[nxt]);
    }
    else if(scc[nxt]==0) low[x]=min(low[x],num[nxt]);
  }
  if(num[x]==low[x]){
    q++;
    while(!s.empty()){
      int t = s.top(); s.pop();
      scc[t]=q;
      if(t==x) break;
    }
  }
}
int sat(){
  for(int i=1;i<=n;i++){
    if(scc[i]==scc[i+n]) return false;
  }
  return true;
}
int main(void){
  cin>>n>>m;
  for(int i=0;i<m;i++){
    int x,y; cin>>x>>y;
    graph[x>0?x+n:-x].push_back(y<0?-y+n:y);
    graph[y>0?y+n:-y].push_back(x<0?-x+n:x);
  }
  for(int i=1;i<=2*n;i++){
    if(num[i]!=0) continue;
    dfs(i);
  }
  if(sat()){
    cout<<1<<'\n';
    for(int i=1;i<=n;i++) cout<<scc[i]<scc[n+i])<<'\n';//tracking true/false
  }
  else cout<<0;
  return 0;
}
\end{minted}

\subsection{BCC, Seperating Vertex/Edge}
\begin{minted}{cpp}
vector<int> graph[SZ], sep_v;
vector<pii> sep_e;
int dfn[SZ], low[SZ];
int piv;
void dfs(int x, int p){
	dfn[x] = low[x] = ++piv;
    int ch=0; bool flg=false;
	for(int w:graph[x]){
		if(w == p) continue;
		if(!dfn[w]){
            ch++;
			dfs(w, x);
			low[x] = min(low[x], low[w]);
            if(dfn[x]<=low[w]){
                flg=true;
                if(dfn[x]<low[w]) sep_e.pb({min(x,w),max(x,w)});
            }
		}
		else if(dfn[x]>dfn[w]) low[x] = min(low[x], dfn[w]);  // back edge
	}
    if(!p && ch>=2) sep_v.pb(x);
    if(p && flg) sep_v.pb(x);
}
\end{minted}

\subsection{LCA}
\begin{minted}{cpp}
vector<int> graph[SZ]; //tree
int lv[SZ]; //equal
int par[MXH][SZ]; //dp for parent
int vst[SZ]; //equal
int n; // number of nodes
void dfs(int x, int parent, int level){
  vst[x]=1;
  par[0][x]=parent;
  lv[x]=level;
  for(int nxt: graph[x]){
    if(vst[nxt]==1) continue;
    dfs(nxt,x,level+1);
  }
}
void memo(){
  for(int i=1;i<MXH;i++){
    for(int j=1;j<=n;j++){
      par[i][j]=par[i-1][par[i-1][j]];
    }
  }
}
int level_up(int x, int d){ // d is a number for lv up!
  for(int i=MXH-1;i>=0;i--){
    if(d&(1<<i)) x=par[i][x];
  }
  return x;
}
int query(int x, int y){
  x=level_up(x,max(0,lv[x]-lv[y]));
  y=level_up(y,max(0,lv[y]-lv[x]));
  if(x==y) return x;
  for(int i=MXH-1;i>=0;i--){
    if(par[i][x]!=par[i][y]){
      x=par[i][x];
      y=par[i][y];
    }
  }
  x=par[0][x];
  return x;
}
\end{minted}

\subsection{Johnson's Algorithm}
\begin{itemize}
    \item $ O(V ^ {2} lg V + VE) $ instead of Floyd Warshall
    \item 1. add new vertex q connected by zero path to any one vertex
    \item 2. use Bellman-Ford from q (fill $ dist(q,x) $ and check negative cycle)
    \item 3. reweight $ edge(u,v) $ to $ edge(u,v) + dist(q,u) - dist(q,v) $
    \item 4. there're no negative edge, do dijkstra from all vertex(fill $ final(x,y) $)
    \item 5. real distance from u to v is $ dist(q,v) - dist(q,u) + final(u,v) $
\end{itemize}

\section{Flows, Matching}

\subsection{Hungarian Method}
\begin{minted}{cpp}
int hungarian(vector<vector<int> > &mat){
  int n=mat.size(),m=mat[0].size();
  vector<int> u(n+1),v(m+1),p(m+1),way(m+1),minv(m+1),used(m+1);
  for(int i=1;i<=n;i++){
    int j0=0; p[0]=i;
    for(int j=0;j<=m;j++) minv[j]=INF, used[j]=0;
    while(1){
      used[j0]=1;
      int i0=p[j0],delta=INF,j1;
      for(int j=1;j<=m;j++){
        if(used[j]==0){
          int cur=mat[i0-1][j-1]-u[i0]-v[j];
          if(cur<minv[j]) minv[j]=cur,way[j]=j0;
          if(minv[j]<delta) delta=minv[j],j1=j;
        }
      }
      for(int j=0;j<=m;j++){
        if(used[j]) u[p[j]]+=delta, v[j]-=delta;
        else minv[j]-=delta;
      }
      j0=j1;
      if(p[j0]==0) break;
    }
    while(1){
      int j1=way[j0];
      p[j0]=p[j1]; j0=j1;
      if(!j0) break;
    }
  }
  return -v[0];
}
\end{minted}

\subsection{Flow Common}
\begin{minted}{cpp}
struct Edge{
  int to,rev,cap,cost;
  Edge(int to, int rev, int cap, int cost):
  to(to),rev(rev),cap(cap),cost(cost){
  }
};
void push_edge(int a, int b, int capa, int cst){
  graph[a].pb(Edge(b,graph[b].size(),capa,cst));
  graph[b].pb(Edge(a,graph[a].size()-1,0,-cst));
}
\end{minted}

\subsection{Dinic}
\begin{minted}{cpp}
struct Dinic{
  int n,m,src,dst;
  vector<vector<edge>> graph;
  vector<int> crt;
  vector<int> lv;
  Dinic(int n, int m, int src, int dst):n(n),m(m),src(src),dst(dst){
    graph.resize(n+m+5);
    crt.resize(n+m+5);
    lv.resize(n+m+5);
  }
  bool bfs(){
    for(int i=0;i<=n+m+1;i++) lv[i]=0;
    queue<int> q;
    q.push(src); lv[src]=1;
    while(!q.empty()){
      int f=q.front(); q.pop();
      for(auto nxt:graph[f]){
        if(lv[nxt.to] || nxt.cap<=0) continue;
        q.push(nxt.to); lv[nxt.to]=lv[f]+1;
      }
    }
    return lv[dst]!=0;
  }
  int dfs(int x, int mnc){
    if(x==dst) return mnc;
    for(int &i=crt[x];i<(int)graph[x].size();i++){
      auto &e=graph[x][i];
      if(lv[x]>=lv[e.to] || e.cap<=0) continue;
      int f=dfs(e.to,min(mnc,e.cap));
      if(f>0){
        e.cap-=f;
        graph[e.to][e.rev].cap+=f;
        return f;
      }
    }
    return 0;
  }
  int flow(){
    int ans=0;
    while(bfs()){
      for(int i=0;i<=n+m+1;i++) crt[i]=0;
      int f;
      while((f=dfs(src,INF)) > 0) {
        ans+=f;
      }
    }
    return ans;
  }
};
\end{minted}

\subsection{MCMF}
\begin{minted}{cpp}
struct MCMF{
  vector<vector<Edge>> graph;
  vector<pii> par;
  int n,src,snk;
  MCMF(int n, int src, int snk):n(n),src(src),snk(snk){
    graph.resize(n+5);
    par.resize(n+5);
  }
  bool SPFA(){
    vector<int> inq,dst;
    inq.resize(n+5,0);
    dst.resize(n+5,INF);
    queue<int> q;
    q.push(src); inq[src]=1; dst[src]=0;
    while(!q.empty()){
      int h=q.front(); q.pop();
      inq[h]=0;
      for(int i=0;i<(int)graph[h].size();i++){
        auto e=graph[h][i];
        if(e.cap<=0) continue;
        if(dst[h]<INF && dst[e.to]>dst[h]+e.cost){
          dst[e.to]=dst[h]+e.cost; par[e.to]={h,i};
          if(inq[e.to]==0){
            q.push(e.to);
            inq[e.to]=1;
          }
        }
      }
    }
    return dst[snk]!=INF;
  }
  pii flow(){
    int work=0,money=0;
    while(SPFA()){
      int c=0, f=INF;
      for(int i=snk;i!=src;i=par[i].ff){
        auto &e=graph[par[i].ff][par[i].ss];
        f=min(f,e.cap);
        c+=e.cost;
      }
      work+=f;
      money+=f*c;
      for(int i=snk;i!=src;i=par[i].ff){
        auto &e=graph[par[i].ff][par[i].ss];
        e.cap-=f;
        graph[e.to][e.rev].cap+=f;
      }
    }
    return {work,money};
  }
};
\end{minted}

\section{Geometry}
\subsection{Geometry}
\begin{minted}{cpp}
struct Point{
  ll x,y;
  bool operator < (const Point &p) const{
    return y==p.y?x<p.x:y<p.y;
  }
};
struct Geometry{
  ll dis(Point a,Point b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
  }
  ll ccw(Point p1,Point p2,Point p3){
    ll c=(p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
    return c?(c>0?1:-1):0;
  }
  bool intersect(Point a,Point b,Point c,Point d){
    ll ab=ccw(a,b,c)*ccw(a,b,d);
    ll cd=ccw(c,d,a)*ccw(c,d,b);
    if(!ab&&!cd){
      if(b<a) swap(a,b);
      if(d<c) swap(c,d);
      return !(b<c||d<a);
    }
    return ab<=0&&cd<=0;
  }
  bool inside(Point p,Point *q,int n){
    int sum=0;
    for(int i=0;i<n;i++){
      int j=(i+1)%n;
      if(intersect(p,p,q[i],q[j])) return true;
      if((q[i].y>p.y)!=(q[j].y>p.y)){
        ll l=(p.x-q[i].x)*(q[j].y-q[i].y);
        ll r=(p.y-q[i].y)*(q[j].x-q[i].x);
        if(q[i].y>q[j].y) swap(l,r);
        if(l<r) sum++;
      }
    }
    return sum%2>0;
  }
  void convexhull(Point *q,int n,Point *h,int &m){
    for(int i=0;i<n;i++) if(q[i]<q[0]) swap(q[i],q[0]);
    sort(q+1,q+n,[&](Point &p1,Point &p2) {
      ll c=ccw(q[0],p1,p2);
      return c?c>0:p1<p2;
    });
    m=0;
    for(int i=0;i<n;i++){
      while(m>=2&&ccw(h[m-2],h[m-1],q[i])<=0) m--;
      h[m++]=q[i];
    }
  }
  ll diameter(Point *q,int n){
    int l=0,r=0;
    while(r<n&&q[r]<q[(r+1)%n]) r++;
    ll mx=dis(q[l],q[r]);
    while(r){
      int dl=(l+1)%n,dr=(r+1)%n;
      if((q[dl].y-q[l].y)*(q[r].x-q[dr].x)<(q[r].y-q[dr].y)*(q[dl].x-q[l].x)) l=dl;
      else r=dr;
      mx=max(mx,dis(q[l],q[r]));
    }
    return mx;
  }
  ll closest(Point *q,int n){
    sort(q,q+n,[&](Point &p1,Point &p2){
      return p1.x<p2.x;
    });
    set<Point> s={q[0],q[1]};
    ll ans=dis(q[0],q[1]);
    int cur=0;
    for(int i=2;i<n;i++){
      while(cur<i){
        if((q[i].x-q[cur].x)*(q[i].x-q[cur].x)>ans) s.erase(q[cur++]);
        else break;
      }
      ll rt=(ll)sqrt((double)ans)+1;
      auto low=s.lower_bound({-INF,q[i].y-rt});
      auto up=s.lower_bound({INF,q[i].y+rt});
      for(auto it=low;it!=up;it++) ans=min(ans,dis(*it,q[i]));
      s.insert(q[i]);
    }
    return ans;
  }
};
\end{minted}

\subsection{Get Area}
\begin{minted}{cpp}
struct Event{
  ll x,y1,y2;
  int b;
};
int n;
ll seg[4*SZ],num[4*SZ];
vector<ll> vi;
vector<Event> evt;
int getidx(int x){
  return lower_bound(vi.begin(),vi.end(),x)-vi.begin();
}i
void update(int idx,int l,int r,int st,int en,int x){
  if(en<l||r<st) return;
  if(st<=l&&r<=en) num[idx]+=x;
  else{
    update(2*idx,l,(l+r)/2,st,en,x);
    update(2*idx+1,(l+r)/2+1,r,st,en,x);
  }
  if(num[idx]) seg[idx]=vi[r+1]-vi[l];
  else seg[idx]=seg[2*idx]+seg[2*idx+1];
}
ll getarea(){
  sort(evt.begin(),evt.end(),[&](Event &e1,Event &e2){
    return e1.x<e2.x;
  });
  sort(vi.begin(),vi.end());
  vi.resize(unique(vi.begin(),vi.end())-vi.begin());
  ll ans=0,last=evt[0].x;
  for(auto e:evt){
    ans+=(e.x-last)*seg[1];
    last=e.x;
    update(1,0,vi.size()-1,getidx(e.y1),getidx(e.y2)-1,e.b);
  }
  return ans;
}
\end{minted}

\subsection{Smallest Enclosing Sphere}
\begin{minted}{cpp}
#include<bits/stdc++.h>
using namespace std;
double dist(double x,double y,double z){
  return x*x+y*y+z*z;
}
double ses(vector<double> x,vector<double> y,vector<double> z){
  int n=x.size();
  double nx=0,ny=0,nz=0;
  for(int i=0;i<n;i++) nx+=x[i],ny+=y[i],nz+=z[i];
  nx/=n;ny/=n;nz/=n;
  double maxv,tmp,R=0.1;
  int maxi;
  for(int i=0;i<10000;i++){
    maxv=-1;maxi=-1;
    for(int j=0;j<n;j++){
        if(maxv<(tmp=dist(x[j]-nx,y[j]-ny,z[j]-nz))) {
            maxv=tmp; maxi=j;
        }
    }
    nx+=(x[maxi]-nx)*R; ny+=(y[maxi]-ny)*R; nz+=(z[maxi]-nz)*R;
    R*=(1-0.002);
  }
  return sqrt(maxv);
}
\end{minted}

\subsection{Polygon Area, Pick's theorem}
\begin{minted}{cpp}
ll gcd(ll x,ll y){
  return y?gcd(y,x%y):x;
}
ll area2(vector<pair<ll,ll>>&A){
  ll ats = 0;
  for(int i=2; i<A.size(); i++){
    ats+=(A[i].ff-A[0].ff)*(A[i-1].ss-A[0].ss);
    ats-=(A[i].ss-A[0].ss)*(A[i-1].ff-A[0].ff);
  }
  return abs(ats);
}
ll boundary(vector<pair<ll,ll>>&A){
  ll ats=A.size();
  for(int i=0;i<A.size();i++){
    ll tmp=(i+1==A.size()?0:i+1);
    ats+=abs(gcd(A[i].ff-A[tmp].ff,A[i].ss-A[tmp].ss))-1;
  }
  return ats;
}
ll inside(vector<pair<ll,ll>>&A){ //S=I+B/2-1 -> 2*I=2*S+2-B
  return (area2(A)-boundary(A)+2)/2;
}
\end{minted}

\section{DP optimization}

\subsection{Divide and Conquer DP optimization}
\begin{itemize}
    \item $O( k n ^ {2} ) \to O( k n lg(n) )$
    \item Con 1) $ DP[t][i]=min_{k<i}(DP[t-1][k]+C[k][i]) or DP[i]=min_{k<i} B[k]+C[k][i] $
    \item Con 2) A[t][i]=k that determine C[t][i] then $ A[t][i] \leq A[t][i+1] $ (hard to find)
    \item Con 2') $ C[a][c]+C[b][d] \leq C[a][d]+C[b][c] $ ($ a \leq b \leq c \leq d $)
\end{itemize}
\begin{minted}{cpp}
int DP[MAXK][MAXN],C[MAXN][MAXN];
void dc_opt(int t,int s,int e,int l,int r){ // solve DP[t][s~e] on l<=k<=r
    if(s>e) return;
    int mid=(s+e)/2;
    DP[t][mid]=INF;
    int v,w;
    for(int k=l;k<=min(r,m-1);k++){
      if(DP[t][mid]>(v=DP[t-1][k]+C[k][mid])) DP[t][mid]=v,w=k;
    }
    dc_opt(t,s,mid-1,l,w);
    dc_opt(t,mid+1,e,w,r);
}
\end{minted}

\subsection{Knuth DP optimization}
\begin{itemize}
    \item $O( n ^ {3} ) \to O( n ^ { 2 } )$
    \item Con 1) $ DP[i][j]=min_{i<k<j}(DP[i][k]+DP[k][j])+C[i][j] $
    \item Con 2) $ C[a][c]+C[b][d]\leq C[a][d]+C[b][c] (a\leq b \leq c \leq d) $
    \item Con 3) $ C[b][c] \leq C[a][d] (a \leq b \leq c \leq d) $
    \item KN[i][j]=k that determining DP[i][j], then $ KN[i][j-1] \leq KN[i][j] \leq KN[i+1][j] $
\end{itemize}
\begin{minted}{cpp}
for(int i=0;i<N;i++) {DP/KN[i][i+1] set}
for(int d=2;d<=N;d++)for(int i=0;i+d<=N;i++){
  int j=i+d;
  DP[i][j]=INF;
  for(int k=KN[i][j-1];k<=KN[i+1][j];k++){
    int tmp=DP[i][j] with k
    if(DP[i][j]>tmp) DP[i][j]=tmp, KN[i][j]=k;
  }
}
\end{minted}

\subsection{Convex Hull Trick}
\begin{itemize}
    \item $O ( N Q ) \to O( (N + Q ) lg ( N ) )$
\end{itemize}
\begin{minted}{cpp}
struct line{  // y = a*x + b
  long long a,b;
};
struct cht{ // DP[i]=min(A[i]*B[j]+C[j])+D[i], B[i] is decreasing
  int s=0,e=0;
  int idx[1111111];
  line deq[1111111];
  double cross(int a,int b){
    return 1.0*(deq[a].b-deq[b].b)/(deq[b].a-deq[a].a);
  }
  void insert(line v,int lidx){
    deq[e]=v; idx[e]=lidx;
    while(s+1<e&&cross(e-2,e-1)>cross(e-1,e)){
        deq[e-1]=deq[e],idx[e-1]=idx[e],e--;
    }
    e++;
  }
  pair<ll,ll> query(long long x){  // query has increasing x
    while(s+1<e&&deq[s+1].b-deq[s].b>=x*(deq[s].a-deq[s+1].a)) s++;
    return pair<ll,ll>(deq[s].a*x+deq[s].b,idx[s]);
  }
  pair<ll,ll> query2(long long x){ // normal query
    int l=0,r=e-1;
    while(l!=r){
      int m=(l+r)/2;
      if(cross(m,m+1)<=x) l=m+1;
      else r=m;
    }
    return pair<ll,ll>(deq[l].a*x+deq[l].b,idx[l]);
  }
  void clear(){s=e=0;}
};
int main(){
  cht CHT;
  CHT.clear();
  line ins; //set base line
  CHT.insert(ins,0);
  for(int i=1;i<=n;i++){
    dp[i]=CHT.query2(A[i]).first+D[i];
    ins.a=B[i];
    ins.b=C[i];
    CHT.insert(ins,i);
  }
  printf("%lld",dp[n]);
}
\end{minted}

\section{Math}

\subsection{Grundy Number}
\begin{minted}{cpp}
int grundy_number(state x) {// has no cycle in game, A's goal=B's goal
  if(gr[x]!=-1) return gr[x];
  if(x is end_state) return gr[x]=0;
  priority_queue<int,vector<int>,greater<int>> pq;
  for(y=next state of x){
    pq.push_back(grundy_number(y));
  }
  int P=0;
  while(!pq.empty()){
    if(pq.top()>P+1) return gr[x]=P;
    P=pq.top(); pq.pop();
  }
}//first person wins when bitwise of grundy_numbers of gameboards is not 0
\end{minted}

\subsection{Matrix}
\begin{minted}{cpp}
struct Mat {
  vector<vector<double> > data;
  Mat(int n) { data.resize(n, vector<double>(n,0)); }
  double* operator[] (int idx) {
    return &data[idx][0];
  }
  void swapRow(int i, int j) {
    if(i==j) return;
    for(int k=0;k<data.size();k++)
      swap(data[i][k], data[j][k]);
  }
  void setIdentity() {
    for(int i=0;i<data.size();i++)
    for(int j=0;j<data.size();j++)
      if(i==j) data[i][j]=1;
      else data[i][j]=0;
  }
};
Mat mult(Mat a, Mat b, int sz){
  Mat c(sz);
  for(int i=0;i<sz;i++)for(int j=0;j<sz;j++){
    c[i][j]=0;
    for(int k=0;k<sz;k++) c[i][j]+=a[i][k]*b[k][j];
  }
  return c;
}
pair<pair<bool, double> , Mat> inv(Mat aa,int sz){
  Mat a(sz),b(sz);
  double K=1;
  for(int i=0;i<sz;i++)for(int j=0;j<sz;j++) a[i][j]=aa[i][j];
  b.setIdentity();
  for(int k=0;k<sz;k++) {
    int t=k-1;
    while(t+1<sz && !a[++t][k]);
    if(t==sz-1 && !a[t][k]) {return {{false,0},a}; }
    a.swapRow(k,t), b.swapRow(k,t);
    if(k!=t) K=-K;
    double d=a[k][k];
    for(int j=0;j<sz;j++) a[k][j]/=d, b[k][j]/=d, K*=d;
    for(int i=0;i<sz;i++){
      if(i!=k) {
        double m=a[i][k];
        for(int j=0;j<sz;j++) {
          if(j>=k) a[i][j]-=a[k][j]*m;
          b[i][j]-=b[k][j]*m;
        }
      }
    }
  }
  return {{true,K},b};
}
\end{minted}

\subsection{Karatsuba}
\begin{minted}{cpp}
vi multi(vi& A, vi& B){
  int s1 = A.size(), s2 = B.size(); vi res;
  res.resize(s1 + s2 - 1, 0);
  for (int i = 0; i < s1; i++)
    for (int j = 0; j < s2; j++) res[i + j] += A[i] * B[j];
  return res;
}
void add(vi& vec1, vi& vec2, int k){
  int s = max(vec2.size() + k, vec1.size());
  vec1.resize(s, 0);  vec2.resize(s, 0);
  for (int i = 0; i < s - k; i++) vec1[i + k] += vec2[i];
}
void sub(vi& vec1, vi& vec2){
  int s = max(vec1.size(),vec2.size());
  vec1.resize(s, 0); vec2.resize(s, 0);
  for (int i = 0; i < s; i++) vec1[i] -= vec2[i];
}
vi Karatsuba(vi& A, vi& B){
  if (A.size() < 50){vi res; res = multi(A,B); return res;}
  int half = A.size() / 2;
  if (A.empty() || B.empty()) return vi();
  vi a1 = vi(A.begin(), A.begin() + half);
  vi a0 = vi(A.begin() + half, A.end());
  vi b1 = vi(B.begin(), B.begin() + min(half, B.size()));
  vi b0 = vi(B.begin() + min(half, B.size()), B.end());
  vi z0, z1, z2;
  z0 = Karatsuba(a0, b0); z2 = Karatsuba(a1, b1);
  add(a0, a1, 0);add(b0, b1, 0);
  z1 = Karatsuba(a0, b0);
  sub(z1, z0);sub(z1, z2);
  vi res;
  add(res, z2, 0); add(res, z1, half); add(res, z0, half + half);
  return res;
}
\end{minted}

\subsection{Extended GCD}
\begin{minted}{cpp}
pair<int,pii> exgcd(int r1, int r2){ // gcd s t
  if(r1==0||r2==0) return {-1,{0,0}};
  if(r1>r2) {
    pair<int,pii> Ans=exgcd(r2,r1);
    return {Ans.ff,{Ans.ss.ss,Ans.ss.ff}};
  }
  int r, q, s, s1=1, s2=0, t, t1=0, t2=1, tmp = r1;
  while(r2) {
    q = r1/r2; r = r1%r2;
    s = s1 - q*s2; t = t1 - q*t2;
    r1 = r2; r2 = r;
    s1 = s2; s2 = s;
    t1 = t2; t2 = t;
  }
  return {r1,{s1,t1}};
}
pair<bool, pii> crt(pii a, pii b){// a.ff mod a.ss b.ff mod b.ss
  int g=exgcd(a.ss,b.ss).ff;
  int l=a.ss/g*b.ss;
  if((a.ff-b.ff)%g!=0) return {false,{0,0}};
  int p=exgcd(a.ss,b.ss).ss.ff;
  p=((long long)p*(b.ff-a.ff))%l;
  p=(((long long)p*a.ss)+a.ff)%l;
  return {true,{p,l}};
}
\end{minted}

\subsection{FFT}
\begin{minted}{cpp}
typedef complex<long double> cp;
int RB(int v, int bits) {
  int r = 0;
  for (int i = 0; i < bits; i++) {
    r <<= 1;
    r += (v & 1);
    v >>= 1;
  }
  return r;
}
vector<cp> fft(vector<cp> poly, int bits, bool is_inverse) {
  const double PI = atan(1.0) * 4;
  double whole = -PI;
  if (is_inverse) whole = -whole;
  int n = (1<<bits);
  for (int i = 0; i < n; i++) {
     int r = RB(i, bits);
    if (i < r) swap(poly[i], poly[r]);
  }
  for (int step = 1; step < n; step += step) {
    for (int s = 0; s < n; s += 2*step) {
      for (int i = 0; i < step; i++) {
        double rad = whole * i / step;
        cp t(cos(rad), sin(rad));
        cp a = poly[s + i] + t * poly[s + i + step];
        cp b = poly[s + i] - t * poly[s + i + step];
        poly[s+i] = a;
        poly[s+i+step] = b;
      }
   }
  }
  if (is_inverse) {
    for (int i = 0; i < n; i++) {
      poly[i] /= n;
    }
  }
  return poly;
}
\end{minted}

\subsection{Chinese Remainder Theorem}
\begin{minted}{cpp}
pair<int,pii> exgcd(int r1, int r2){ // gcd s t
  if(r1==0||r2==0) return {-1,{0,0}};
  if(r1>r2) {
    pair<int,pii> Ans=exgcd(r2,r1);
    return {Ans.ff,{Ans.ss.ss,Ans.ss.ff}};
  }
  int r, q, s, s1=1, s2=0, t, t1=0, t2=1, tmp = r1;
  while(r2) {
    q = r1/r2; r = r1%r2;
    s = s1 - q*s2; t = t1 - q*t2;
    r1 = r2; r2 = r;
    s1 = s2; s2 = s;
    t1 = t2; t2 = t;
  }
  return {r1,{s1,t1}};
}
pair<bool, pii> crt(pii a, pii b){// a.ff mod a.ss b.ff mod b.ss
  int g=exgcd(a.ss,b.ss).ff;
  int l=a.ss/g*b.ss;
  if((a.ff-b.ff)%g!=0) return {false,{0,0}};
  int p=exgcd(a.ss,b.ss).ss.ff;
  p=((long long)p*(b.ff-a.ff))%l;
  p=(((long long)p*a.ss)+a.ff)%l;
  return {true,{p,l}};
}
\end{minted}

\subsection{Factorize}
\begin{minted}{cpp}
bool wit(ull a,ull n,ull s){
  a%=n;
  if(a<=1) return true;
  ull d=n>>s, x=pow(a,d,n); //define pow
  if(x==1||x==n-1) return true;
  while(s-- > 1){
    x=mulmod(x,x,n); //define mulmod
    if(x==1) return false;
    if(x==n-1) return true;
  }
  return false;
}
bool millerRabin(ull n){
  if(n==2) return true;
  if(n<2||n%2==0) return false;
  ull d=n>>1,s=1;
  for(;(d&1)==0;s++) d>>=1;
#define Tk(a) wit(a##ull , n, s)
  if(n<4759123141LL) return Tk(2)&&Tk(7)&&Tk(61);
  else return Tk(2)&&Tk(325)&&Tk(9375)&&Tk(28178)&&Tk(450775)&&Tk(9780504)&&Tk(1795265022);
}
ll rho(ll n){
  uniform_int_distribution<ll> dis(1,n-1);
  ll x=dis(rd2),c=dis(rd2),g=1,y=x;//random
  while(g==1){
    x=(mulmod(x,x,n)+c)%n;
    y=(mulmod(y,y,n)+c)%n;
    y=(mulmod(y,y,n)+c)%n;
    g=gcd(abs(x-y),n); // define gcd
  }
  return g;
}
void factorize(ll n, vector<ll>& v){
  if(n==1) return;
  if(n%2==0) v.pb(2),factorize(n/2,v);
  else if(millerRabin(n)) v.pb(n);
  else{
    ll f=rho(n);factorize(f,v);factorize(n/f,v);
  }
}
\end{minted}

\subsection{Algebra}
\begin{itemize}
    \item 1000th Prime : 7919
    \item 5000th Prime : 48611
    \item 10000th Prime : 104729
    \item $ 998244353 = 119 \times 2 ^ {23} + 1 $ ( Primitive root : 3 )
    \item primitive root of $ A  \times 2 ^ {C} +1 $ is $ x ^ { 2 ^ {C - 1} } = -1 $
    \item prime test on $ n : n - 1 = 2 ^ {s} \times d $
    \item $ a ^ {d} \ne 1 $ and $ a ^ { d2 ^ {t} } \ne -1 $ then n is not prime
    \item n is int range $ \to a=2,7,61 , n \leq 3.4e17 \to a=2,3,5,7,11,13,17 $
\end{itemize}

\section{String Matching}
\subsection{KMP}
\begin{minted}{cpp}
string s,p;
int pi[SZ];
vector<int> ans;
void getPi(string p){
  int m=p.size(),j=0;
  for(int i=1;i<m;i++){
    while(j>0&&p[i]!=p[j]) j=pi[j-1];
    if(p[i]==p[j]) pi[i]=++j;
  }
}
void kmp(string s,string p){
  getPi(p);
  int n=s.size(),m=p.size(),j=0;
  for(int i=0;i<n;i++){
    while(j>0&&s[i]!=p[j]) j=pi[j-1];
    if(s[i]==p[j]){
      j++;
      if(j==m){
        ans.push_back(i-m+1);
        j=pi[j-1];
      }
    }
  }
}
\end{minted}

\subsection{Aho-corasick}
\begin{minted}{cpp}
struct Ahocorasick{
  int tot;
  int trie[SZ][27],output[SZ],fail[SZ];
  Ahocorasick():tot(0){
    memset(trie,0,sizeof(trie));
    memset(output,0,sizeof(output));
    memset(fail,0,sizeof(fail));
  }
  void update(string &s){
    int p=0;
    for(auto c:s){
      if(!trie[p][c-'a']) trie[p][c-'a']=++tot;
      p=trie[p][c-'a'];
    }
    output[p]=1;
  }
  void bfs(){
    queue<int> Q;
    for(int c=0;c<26;c++)
      if(trie[0][c]) Q.push(trie[0][c]);
    while(!Q.empty()){
      int t,x=Q.front(); Q.pop();
      for(int i=0;i<26;i++){
        if(t=trie[x][i]){
          int p=fail[x];
          while(p&&!trie[p][i]) p=fail[p];
          p=trie[p][i];
          fail[t]=p;
          if(output[p]) output[t]=1;
          Q.push(t);
        }
      }
    }
  }
  bool find(string &s){
    int p=0;
    for(auto c:s){
      while(p&&!trie[p][c-'a']) p=fail[p];
      p=trie[p][c-'a'];
      if(output[p]) return true;
    }
    return false;
  }
};
\end{minted}

\subsection{Manacher's Algorithm}
\begin{minted}{cpp}
int n,p[SZ]; // Be careful to double the length.
void manacher(string t) {
  string s="#";
  for(int i=0;i<t.size();i++) s+=t[i],s+="#";
  n=s.size();
  int r=0,k=0;
  for(int i=0;i<n;i++) {
    if(i<=r) p[i]=min(r-i,p[2*k-i]);
    while(i-p[i]-1>=0&&i+p[i]+1<n&&s[i-p[i]-1]==s[i+p[i]+1]) p[i]++;
    if(r<i+p[i]) r=i+p[i],k=i;
  }
}
\end{minted}

\subsection{Z algorithm}
\begin{minted}{cpp}
int n,p[SZ];
void z_algorithm(string s) {
   n=s.size(),p[0]=n-1;
   int l=-1,r=-1;
   for(int i=1;i<n;i++) {
      if(i<=r) p[i]=min(r-i,p[i-l]);
      else p[i]=-1;
      while(i+p[i]+1<n&&s[i+p[i]+1]==s[p[i]+1]) p[i]++;
      if(r<i+p[i]) r=i+p[i],l=i;
   }
}
\end{minted}

\subsection{Suffix Array slow ver}
\begin{minted}{cpp}
vector<int> suffix(string &s){
  int n=s.size();
  vector<int>sa(n),x(n+1);
  for(int i=0;i<n;i++) sa[i]=i,x[i]=s[i];
  x[n]=-1;
  for(int t=1;t<n;t<<=1){
    auto cmp=[&](int i, int j){
      return x[i]==x[j]?x[i+t]<x[j+t]:x[i]<x[j];
    };
    sort(sa.begin(),sa.end(),cmp);
    vector<int> tmp(n+1);
    tmp[sa[0]]=0; tmp[n]=-1;
    for(int i=1;i<n;i++) tmp[sa[i]]=tmp[sa[i-1]]+cmp(sa[i-1],sa[i]);
    x=tmp;
  }
  return sa;
}
\end{minted}

\subsection{Suffix Array fast ver}
\begin{minted}{cpp}
vector<int> suffix(string &s) {
  int n=s.size(),m=max(257,n+1);
  vector<int> sa(n),x(n+1),y(n+1);
  for(int i=0;i<n;i++) sa[i]=i, x[i]=s[i];
  for(int t=1;t<n;t<<=1) {
    vector<int> cnt(m);
    for(int i=0;i<n;i++) cnt[x[min(i+t,n)]]++;
    for(int i=1;i<m;i++) cnt[i]+=cnt[i-1];
    for(int i=n-1;i>=0;i--) y[--cnt[x[min(i+t,n)]]]=i;
    cnt.clear(); cnt.resize(m);
    for(int i=0;i<n;i++) cnt[x[i]]++;
    for(int i=1;i<m;i++) cnt[i]+=cnt[i-1];
    for(int i=n-1;i>=0;i--) sa[--cnt[x[y[i]]]]=y[i];
    auto cmp=[&](int i,int j){
      return x[i]==x[j]?x[i+t]<x[j+t]:x[i]<x[j];
    };
    vector<int> tmp(n+1);
    tmp[sa[0]]=1;
    for(int i=1;i<n;i++) tmp[sa[i]]=tmp[sa[i-1]]+cmp(sa[i-1],sa[i]);
    x=tmp;
  }
  return sa;
}
\end{minted}

\subsection{Longest Common Prefix}
\begin{minted}{cpp}
vector<int> prefix(string s,vector<int> sa){
   int k=0,n=s.size();
    vector<int> lcp(n),rank(n);
    for(int i=0;i<n;i++) rank[sa[i]]=i;
    for(int i=0;i<n;i++){
       if(!rank[i]) continue;
       while(s[i+k]==s[sa[rank[i]-1]+k]) k++;
      lcp[rank[i]]=k?k--:0;
   }
   return lcp;
}
\end{minted}

\section{E.T.C}

\subsection{Parellel Binary Search}
\begin{minted}{cpp}
int n,m,q,lo[N],hi[N],an[N],sz[N],rsz[N],g[N];
pii qry[N];
pair<int,pii> edge[N];
vector<vector<int>> V;
int find(int x){
  return x==an[x]?x:an[x]=find(an[x]);
}
void merge(int x, int y) {
  x=find(x),y=find(y);
  if(x==y)return;
  an[x]=y;sz[y]+=sz[x];
}
int main(){
  scanf("%d %d",&n,&m);
  for(int i=1;i<=m;i++){
    scanf("%d %d %d",&edge[i].ss.ff,&edge[i].ss.ss,&edge[i].ff);
  }
  sort(edge+1,edge+m+1); // sort
  scanf("%d",&q);
  for(int i=0;i<q;i++){ // lo[i]<=ans<hi[i] offline query
    scanf("%d %d",&qry[i].ff,&qry[i].ss);
    lo[i]=1;hi[i]=m+1;
  }
  bool f=true;
  while(f) {// until there're change
    f=false;
    for(int i=1;i<=n;i++) an[i]=i,sz[i]=1;
    V.clear(); V.resize(m+2);
    for(int i=0;i<q;i++){
      if(lo[i]<hi[i]) V[(lo[i]+hi[i])/2].push_back(i);
    }
    for(int i=1;i<=m;i++){
      merge(edge[i].ss.ff,edge[i].ss.ss);
      while(V[i].size()){
        f=true;
        int idx=V[i].back();
        V[i].pop_back();
        if(find(qry[idx].ff)==find(qry[idx].ss)){
          hi[idx]=i;
          g[idx]=edge[i].ff;
          rsz[idx]=sz[find(qry[idx].ff)];
        }
        else lo[idx]=i+1;
      }
    }
  }
  for(int i=0;i<q;i++){
    if (lo[i]==m+1) puts("-1");
    else printf("%d %d\n", g[i], rsz[i]);
  }
}
\end{minted}

\subsection{Fast Input/Output}
\begin{minted}{cpp}
struct FastIo{
   char buf[SZ];
   int p;
   FastIo():p(0){}
   inline char readChar(){
      if(p==SZ){
         fread(buf,1,SZ,stdin);
         p=0;
      }
      return buf[p++];
   }
   inline int readInt(){
      int a=0;
      char c;
      bool minu = false;
      while((c=readChar())!='\n' && c!=' '){
         if(c!='-'){
            a *= 10;
            a += (c&0b1111);
         }
         else if(c=='-') minu=true;
      }
      while(buf[p]==' ' || buf[p]=='\n'){
         p++;
      }
      if(minu) return -a;
      return a;
   }
};
\end{minted}

\subsection{Random}
\begin{minted}{cpp}
random_device rd1;
seed_seq sseq = {rd1(), rd1(), rd1(), rd1()};
mt19937 rd2(sseq);
uniform_int_distribution<int> gen(1, 6); // [1, 6] gen(rd2)
uniform_real_distribution<double> genr(0.0, 1.0); // [0, 1) genr(rd2)
\end{minted}

\end{document}

ext: tex


text:
%-------------------------
% Resume in Latex
% Author : Benjamin Giles
% License : MIT
%------------------------

\documentclass[11pt]{article}

\input{glyphtounicode}
\usepackage{latexsym}
\usepackage[empty]{fullpage}
\usepackage{titlesec}
\usepackage{marvosym}
\usepackage[usenames,dvipsnames]{color}
\usepackage{verbatim}
\usepackage{enumitem}
\usepackage[hidelinks]{hyperref}
\usepackage{fancyhdr}
\usepackage[english]{babel}
\usepackage{tabularx}

\pagestyle{fancy}
\fancyhf{} % clear all header and footer fields
\fancyfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}

% Adjust margins
\addtolength{\oddsidemargin}{-0.5in}
\addtolength{\evensidemargin}{-0.5in}
\addtolength{\textwidth}{1in}
\addtolength{\topmargin}{-.5in}
\addtolength{\textheight}{1.0in}

\urlstyle{rm}

\raggedbottom
\raggedright
\setlength{\tabcolsep}{0in}

% Sections formatting
\titleformat{\section}{
  \vspace{-4pt}\scshape\raggedright\large
}{}{0em}{}[\color{black}\titlerule \vspace{-5pt}]

\pdfgentounicode=1

%-------------------------
% Custom commands
\newcommand{\resumeItem}[2]{
  \item\small{
    \textbf{#1}{: #2 \vspace{-2pt}}
  }
}

\newcommand{\resumeSubheading}[4]{
  \vspace{-1pt}\item
    \begin{tabular*}{0.97\textwidth}[t]{l@{\extracolsep{\fill}}r}
      \textbf{#1} & #2 \\
      \textit{\small#3} & \textit{\small #4} \\
    \end{tabular*}\vspace{-5pt}
}

\newcommand{\resumeSubSubheading}[2]{
    \begin{tabular*}{0.97\textwidth}{l@{\extracolsep{\fill}}r}
      \textit{\small#1} & \textit{\small #2} \\
    \end{tabular*}\vspace{-5pt}
}

\newcommand{\resumeSubItem}[2]{\resumeItem{#1}{#2}\vspace{-4pt}}

\renewcommand{\labelitemii}{$\circ$}

\newcommand{\resumeSubHeadingListStart}{\begin{itemize}[leftmargin=*]\vspace{5pt}}
\newcommand{\resumeSubHeadingListEnd}{\end{itemize}}
\newcommand{\resumeItemListStart}{\begin{itemize}}
\newcommand{\resumeItemListEnd}{\end{itemize}\vspace{-5pt}}
%-------------------------------------------
%%%%%%  CV STARTS HERE  %%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%----------HEADING-----------------
\begin{tabular*}{\textwidth}{l@{\extracolsep{\fill}}r}
  \textbf{\Large Benjamin Giles} & Email : \href{mailto:btgiles@gmail.com}{btgiles@gmail.com} \\
  \href{https://github.com/benkant}{https://github.com/benkant} & Mobile : +61-400-732-837 \\
  \href{https://www.linkedin.com/in/rbp-0xdeadbeef/}{https://www.linkedin.com/in/rbp-0xdeadbeef/}
\end{tabular*}

%
%--------PROGRAMMING SKILLS------------
\section{Analysis and Development Experience}
  \resumeSubHeadingListStart
    \resumeSubItem{Languages}{Python, JavaScript, SQL, C99, C++11, ASM (x86), Java, MATLAB, Lua, Perl, Bash, PowerShell, .NET.}
    \resumeSubItem{Tools}{gcc/ld/gdb, make, nasm, coreutils, git, vim, ESRI SDK's, Visual Studio, JetBrains, IDA Pro, x64gdb, WireShark, Linux, IIS/Windows Server}
    \resumeSubItem{Programming practice}{version control, DevOps, UML, ER-diagrams, CI/CD, pair programming, code review}
    \resumeSubItem{Leadership}{Mentoring, tasking, reporting, course delivery, hiring, management, agile processes}
    \resumeSubItem{Applications}{Linux system and network programming, geographic information systems, algorithm development, data analysis, database development}
  \resumeSubHeadingListEnd

%-----------EXPERIENCE-----------------
\section{Recent Experience}
  \resumeSubHeadingListStart
    \resumeSubheading
      {Australian Defence Force Academy}{Canberra, Australia}
      {Master of Cyber Security (Advanced Tradecraft)}{Feb 2020 - current (indefinite leave)}
        \resumeItemListStart
          \resumeItem
            {Core Coursework}{Reverse engineering / Information Security and Assurance / Wireless, Mobile, and Internet of Things Security / Digital Forensics}
          \resumeItem
            {Auxiliary Coursework}{Engineering Mathematics}
          \resumeItemListEnd

    \resumeSubheading
      {FEISAR Pte Ltd}{Singapore}
      {Senior Analysis Programmer}{June 2014 - December 2019}
      \resumeItemListStart
        \vspace{5pt}
          {Delivered software consulting and development services to oil \& gas and fintech sectors. \\}
            \resumeItem{Pin Payments}
              {Developed a machine learning model in MATLAB to predict customer risk during onboarding to reduce fraud loss.}

            \resumeItem{Player, with GIS-Pax Pty Ltd}
              {Implemented features in the de facto standard data analysis tool for oil \& gas exploration geoscientists. Used on Windows Workstations at supermajors (ExxonMobil, BP, Royal Dutch Shell, Chevron, Total, Conoco Phillips) and the majority of mid-sized firms (Hess, Repsol, Petronas, Equinor, Petrobras). Written with ESRI SDK's for .Net and Python.}

            \resumeItem{Player QwikVol, with GIS-Pax Pty Ltd}
              {Designed, implemented and formally tested for stability several numerical algorithms, including a Markov Chain Monte Carlo simulation to produce probability distributions of expected oil, gas and condensate in prospects. The result of this is the primary information for a \$100m exploration drilling decision. Designed for portability, it runs on x64 workstations and Apple A-Series ARM CPU's. Technologies used: C, MATLAB, C\#, Mathematica, Math.NET Numerics.}

            \resumeItem{PlayHouse, with GIS-Pax Pty Ltd}
              {Lead engineering on a team that developed a geospatial data pipeline that consumed data produced by geoscientists to feed visualisation and decision support systems. These were consumed by oil \& gas exploration economists and senior exploration management. Implemented in Python, C, C\#, JavaScript, React, Bash scripts, PowerShell, and integrated with ArcGIS Server / API for JavaScript.}

            \resumeItem{Consulting, with GIS-Pax Pty Ltd}
              {Conducted technical pre-sales and onsite deployments worldwide, and in the cloud (GCP, Azure and AWS).}

            \resumeItem{Professional development in Mathematics and Machine Learning}
              {Multivariable Calculus, Linear Algebra, Differential Equations, Vector Calculus, Numerical Methods, Number Theory, Probability, Statistics, Supervised Learning, Unsupervised Learning.}
      \resumeItemListEnd

    \resumeSubheading
      {Pin Payments}{Melbourne, Australia}
      {Engineer Manager}{May 2012 - May 2014}
      \resumeItemListStart
        \resumeItem{Core Payment Systems}
          {Lead software design, architecture, development and infrastructure for international payments, foreign exchange, fraud detection and credit card processing. Written in Ruby, SQL, Bash, Mathematica.}
        \resumeItem{Financial system integrations}
          {Managed relationships and technical requirements with upstream financial providers.}
        \resumeItem{Leadership}
          {Hired and managed five technical staff, and several contractors, defining software development processes and best practices.}
        \resumeItem{Acqusition prospect analysis}
          {Performed technical and economic due diligence of acquisitions.}
        \resumeItem{Dev/test/prod/analysis environment}
          {Owned DevSecOps automation in AWS, including HA production and high security internal analytics systems.}
        \resumeItem{Data ETL for analytics}
          {Setup, schema design and management of Amazon Redshift for use by Tableau users in operations and management.}
      \resumeItemListEnd
  \resumeSubHeadingListEnd

\section{Further Experience}
  \resumeSubHeadingListStart
    \resumeSubheading
        {ActiveEight}{Australia}
        {Freelance Programmer}{Feb 2003 - May 2012}
        \resumeItemListStart
          \resumeItem{Department of Defence, Nova Systems}
            {Geospatial analysis tools, written in C, C++, Python, and Java.}
          \resumeItem{iiNet}
            {IP telecommunications management systems, written in Perl and DB/2 on Debian.}
          \resumeItem{Spoon Media}
            {Statistical analysis tools for a reproductive medicine startup, written in Drupal.}
        \resumeItemListEnd

    \resumeSubheading
      {ESRI Australia}{Canberra, Australia}
      {Geographic Information Systems Programmer}{May 2000 - Jan 2003}
        \resumeItemListStart
          \resumeItem{Consulting at Department of Defence}
            {Developed spatial data transformation pipeline.}
          \resumeItem{ActewAGL}
            {Developed tool to translate Autodesk CAD models into a spatial database.}
          \resumeItem{Software Development}
            {Designed, developed, and tested workstation \& server-based GIS products for using Sun, SGI, DEC, Microsoft, and GNU C/C++ compilers with ESRI's SDK's.}
          \resumeItem{Geospatial analysis}
            {Performed ad hoc geospatial data analysis in Perl.}
          \resumeItem{Consulting}
            {Provided technical support for federal government ArcGIS programmers and analysts using ESRI and Microsoft SDKs.}
          \resumeItem{Training Delivery}
            {Delivered ESRI certification track training courses.}
        \resumeItemListEnd

    \resumeSubheading
      {Eclipse Group}{Melbourne, Australia}
      {System Programmer}{Dec 1997 - Apr 2000}
        \resumeItemListStart
        \resumeItem{Deloitte Touche Tohmatsu stake in Eclipse Group Pty Ltd}
          {Oversaw hiring of 20 technical staff and provisioning of Linux servers, Cisco network infrastructure, and Mac workstations for the expansion to Melbourne. This team ultimately became what is known today as Deloitte Digital.}
        \resumeItem{Multimedia software development}
          {Designed, developed, and tested desktop real-time 2D/3D multimedia software and libraries for macOS and Windows in Java, C++, and OpenGL.}
        \resumeItem{Web development}
          {Apache CGI script development on Linux servers using Perl, C, and shell scripts. JavaScript in support of front-end developers.}
        \resumeItemListEnd
    \resumeSubHeadingListEnd

    %-----------PROJECTS-----------------
\section{Other noteworthy projects}
  \resumeSubHeadingListStart
    \resumeSubItem{Royal Australian Navy}
      {Large volume data processing system deployed on vessels using NetCDF data from other Defence agencies. Pipeline written in Java- embedded system written in Qt/C++}
    \resumeSubItem{OpenAI}
      {Contribution of MATLAB client for OpenAI's gym used to measure the performance of deep reinforcement learning agents.}
    \resumeSubItem{RMIT \& Defence Science and Technology Group}
      {Researched mobile ad hoc network protocol performance using simulations sampling from large multi-nation wargame datasets.}
    \resumeSubItem{Victorian Government}
      {Developed fire models and visualisation used by emergency personel and operations staff.}
    \resumeSubItem{Diploma of Screenwriting - Film and Television Institute}
      {Wrote a number of spec scripts, and directed music videos including writing custom VFX software \href{https://github.com/benkant/FXPlug-cloner}{https://github.com/benkant/FXPlug-cloner}.}
    \resumeSubItem{Spoon Media}
      {Developed a WYSIWYG website builder written entirely in the browser. Backend development in Drupal, front-end in JavaScript.}
  \resumeSubHeadingListEnd

%-----------EDUCATION-----------------
\section{Education}
  \resumeSubHeadingListStart
    \resumeSubheading
      {Australian Defence Force Academy @ UNSW Canberra}{Canberra, Australia}
      {Master of Cyber Security (Advanced Tradecraft)}{Feb. 2020 -- current (indefinite leave)}
    \resumeSubheading
      {Royal Melbourne Institute of Technology}{Melbourne, Australia}
      {Master of Computing in Distributed Systems (Awarded with Distinction);  GPA: 3.9/4}{Mar. 2011 -- Dec. 2014}
  \resumeSubHeadingListEnd

%-------------------------------------------
\end{document}

max_stars_repo_name: benkant/resume

max_issues_repo_name: benkant/resume

max_forks_repo_name: benkant/resume


text:
%\begingroup
%\let\cleardoublepage\clearpage

% English abstract
\cleardoublepage
\chapter*{Abstract}
\markboth{Abstract}{Abstract}
\addcontentsline{toc}{chapter}{Abstract (English/Français/Deutsch)} % adds an entry to the table of contents
% put your text here
\lipsum[1-2]

% German abstract
\begin{otherlanguage}{german}
\cleardoublepage
\chapter*{Zusammenfassung}
\markboth{Zusammenfassung}{Zusammenfassung}
% put your text here
\lipsum[1-2]
\end{otherlanguage}

% French abstract
\begin{otherlanguage}{french}
\cleardoublepage
\chapter*{Résumé}
\markboth{Résumé}{Résumé}
% put your text here
\lipsum[1-2]
\end{otherlanguage}

%\endgroup
%\vfill


text:
% ******************************* Thesis Appendix B ********************************

\chapter{TRECVID MED 2015 Results}

\ifpdf
\graphicspath{{Appendix3/Figs/Raster/}{Appendix3/Figs/PDF/}{Appendix3/Figs/}}
\else
\graphicspath{{Appendix3/Figs/Vector/}{Appendix3/Figs/}}
\fi
In TRECVID MED 2015, beside using audio and visual features with Fisher vector encoding, we also use deep learning features extracted from a pre-trained model. The features from the output of the final layer are also employed to zero shot event detection. Our results demonstrated the benefit of using deep learning features, especially in the case of less training examples.

\section{Improvements over MED'14 System}

\textbf{DCNN features}.\label{dcnnfeatures} We use the popular DeepCaffe \cite{jia2014caffe} framework to extract image features. We used the pre-trained deep model provided by Zhou et al. \cite{zhou2014learning}. This model was trained on an image collection of 1,183 categories including 205 scene categories from the Places Database and 978 object categories from the ImageNet 2012. We selected the neuron activations from the last three layers for the feature representation. The third and second-to-last layer has 4,096 dimensions, while the last layer has 1,183 dimensions. We denote these features as FC6, FC7, and FULL in our experiments.

\textbf{Zero-shot event detection.} In order to calculate the similarity between an video and an event, we adopt a concept expansion strategy as in \cite{chen2014event}. The outline of our method is illustrated in Fig. \ref{c5_figure_2} and it consists of four steps: concept detection, event representation, concept-event similarity and instance-event similarity (as described in detail in Section \ref{instance_event_similarity}).

\section{Contribution of New Components}
We evaluated the contribution of new components on the KINDREDTEST14 dataset. All results are reported in terms of Mean Average Precision (MAP). Here we only report the over all performance, which is averaged from all events. In figure \ref{fig_feat_perf}, we show the performance of each feature, including low level features for comparison.

\textbf{DCNN Features}. In terms of single feature performance, FC7 feature has the best performance, even better than dense trajectories feature. It can be seen that feature of the last layer (FULL) does not perform well. It is due to the lost of information after applying max pooling from the previous layer.

\textbf{Zero-shot Event Detection}. Performance of our EK0 run is around 6\% MAP, which is slightly better than the audio MFCC run. Moreover, this run is complementary to low level and deep learning features. Combining with all low level and deep learning features, we obtained around 8\% relative improvement, as shown in the last column of Fig. \ref{fig_feat_perf}.

\begin{figure}
	\centering
	\includegraphics[width=1\textwidth]{feat_perf.png}
	\caption{Performance of each feature and the fused runs.}
	\label{fig_feat_perf}
\end{figure}

\section{Submitted Systems}

After evaluating the improvements on the KINDREDTEST dataset, we chose to submit the run that combining all available features for EK10 and EK100 settings. We also submit our EK0 system to the full evaluation.

\section{Result and Conclusion}

Results of our MED system on the full evaluation set is shown in Fig. \ref{result_team}. Performance is reported in terms of MAP. Comparing with other systems, we are ranked 6th out of 7 teams in the EK10 evaluation full and 6th out of 16 in the sub evaluation.

We have learnt that top performance systems have incorporated a couple of semantic concept detectors including audio and visual concepts, which can be more helpful when number of training videos are limited. This is the reason for lower performance of our EK10 system.

On the other hand, our system performed better in EK100 the setting. For example, we got a better performance than the top team in this setting. This indicate that our low level features work well when the number of training videos is abundant. We also observed that our year-to-year improvement on EK10 is 72.5 \%, while this number is only 25.9\% for the EK100. This observation confirms the contributions of high level and deep learning features in case of event detection with few examplars.

\begin{figure}
	\centering
	\includegraphics[width=1\textwidth]{result_team.png}
	\caption{Comparison of our performance with top systems in terms of MAP.}
	\label{result_team}
\end{figure}

max_stars_repo_name: DengPingFan/phd-thesis-template

max_issues_repo_name: DengPingFan/phd-thesis-template

max_forks_repo_name: DengPingFan/phd-thesis-template


text:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% UMB-CS114-2015F: Introduction to Programming in Java
% Copyright 2015 Pejman Ghorbanzade <pejman@ghorbanzade.com>
% Creative Commons Attribution-ShareAlike 4.0 International License
% More info: https://github.com/ghorbanzade/UMB-CS114-2015F
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def \topDirectory {.}
\def \texDirectory {\topDirectory/src/main/tex}

\documentclass[12pt,letterpaper,twoside]{article}
\usepackage{\texDirectory/template/style/directives}
\usepackage{\texDirectory/template/style/assignment}
\input{\texDirectory/template/config}

\usepackage{amsmath}

\begin{document}

\doc{title}{Assignment 2}
\doc{date-pub}{Oct 05, 2015 at 5:30 PM}
\doc{date-due}{Oct 19, 2015 at 5:30 PM}
\doc{points}{8}

\prepare{header}

\section*{Question 1}

Given coordinates of a point and a sphere in tridimensional space, a point can either be inside, outside or on the sphere.

Write a program \texttt{PointAndSphere.java} that takes respectively coordinates of a point and center of a sphere as command line arguments and prompts user for radius of the sphere.
Your program would then determine the location of the point with respect to the sphere.
Following is an example of an accepted output format.

\begin{terminal}
$ java PointAndSphere 1 1 1 0 0 0
Radius of the sphere: 1.7
The point is outside the sphere.
$ java PointAndSphere 1 1 1 0 0 0
Radius of the sphere 1.8
The point is inside the sphere.
\end{terminal}

\section*{Question 2}

Using Leibniz Formula, the number $\pi$ can be approximated using the series given in Equation \ref{eq1}.

\begin{equation}
\pi = 4 \left( 1 - \frac{1}{3} + \frac{1}{5} + \cdots + \frac{(-1)^{i+1}}{2i-1} \right)
\label{eq1}
\end{equation}

Write a program \texttt{PiProximator.java} that prompts user for a number $i$ and approximates the number $\pi$ using the first $i$ sentences of Equation \ref{eq1}.
Your program should also print the approximation error compared to the \texttt{Math.PI} value.
Following is the expected output of a sample run of your program.

\newpage

\begin{terminal}
$ javac PiProximator.java
$ java PiProximator
Number of Sentences: 100
Approximate Value: 3.131593
Approximation Error: 0.010000
\end{terminal}

\section*{Question 3}

Write a program \texttt{PrimePrinter.java} that prompts user for a number $x$ and prints all prime numbers less than or equal to the number $x$.
Your program should function as shown in the example given below.

\begin{terminal}
$ javac PrimePrinter.java
$ java PrimePrinter
Enter Upper Limit: 29
2 3 5 7 11 13 17 19 23 29
\end{terminal}

\section*{Question 4}

Write a program \texttt{MatrixFiller.java} that prompts user for a number $x$ between 1 to 9 and generates an $x \times x$ matrix with random elements from 1 to $x^2$.
Following is an expected sample run of your program.

\begin{terminal}
$ javac MatrixFiller.java
$ java MatrixFiller
Size of Matrix: 5
 05 21 07 25 11
 17 02 17 01 07
 25 14 14 08 07
 02 05 01 14 02
 02 14 14 13 07
\end{terminal}

\newpage

\section*{Question 5}

Write a program \texttt{Pyramid.java} that prompts user for a number between 1 to 10 and displays a pyramid of the given format.

\begin{terminal}
$ javac Pyramid.java
$ java Pyramid
Number of Rows: 5
                   1
               1   2   1
           1   2   4   2   1
       1   2   4   8   4   2   1
   1   2   4   8  16   8   4   2   1
\end{terminal}

\prepare{footer}

\end{document}