text:
\documentclass[12pt]{article}

\usepackage[margin=1.2in]{geometry}
\usepackage{hyperref}
\usepackage{datetime}
\usepackage[auth-sc,affil-sl]{authblk}
\usepackage{color}
\usepackage{placeins}
\usepackage{enumerate}
\definecolor{black}{rgb}{0,0,0}
\definecolor{blue}{rgb}{0,0,0.7}
\newcommand{\inblue}[1]{\color{blue}\textbf{#1} \color{black}}
\definecolor{green}{rgb}{0.133,0.545,0.133}
\newcommand{\ingreen}[1]{\color{green}\textbf{#1} \color{black}}
\definecolor{yellow}{rgb}{1,0.549,0}
\newcommand{\inyellow}[1]{\color{yellow}\textbf{#1} \color{black}}
\definecolor{red}{rgb}{1,0.133,0.133}
\newcommand{\inred}[1]{\color{red}\textbf{#1} \color{black}}
\definecolor{purple}{rgb}{0.58,0,0.827}
\newcommand{\inpurple}[1]{\color{purple}\textbf{#1} \color{black}}
\definecolor{brown}{rgb}{0.55,0.27,0.07}
\newcommand{\inbrown}[1]{\color{brown}\textbf{#1} \color{black}}

\newcommand{\coursewebpage}{\href{https://github.com/kapelner/QC_Math_341_Spring_2019}{course homepage}}

\newcommand{\qu}[1]{``#1''}

\title{MATH 341 Spring 2019 (3 credits) \\ Course Syllabus}

\author[]{Adam Kapelner, Ph.D.}

\affil[]{Queens College, City University of New York}
\settimeformat{ampmtime}
\date{\small document last updated \today ~\currenttime }

\begin{document}
\maketitle

\begin{table}[htp]
\centering
\begin{tabular}{rl}
Instructor & Professor Adam Kapelner \\
%Office & 604 Kiely Hall \\
Contact & \url{kapelner@qc.cuny.edu} \\
Lecture Time / Loc & Tues and Thurs 9:15 - 10:30AM / Kiely 283 \\
My Office Hours / Loc & Tues and Thurs 12:50-1:30PM  / Kiely 283 \\
TA Office Hours / Loc & Thurs 1:45-2:45PM  / Kiely 5th fl lounge\\
Course Homepage & \href{https://github.com/kapelner/QC_Math_341_Spring_2019}{https://github.com/kapelner/QC\_Math\_341\_Spring\_2019} \\
\end{tabular}
\end{table}

\section*{Course Overview}

MATH 341. Bayesian Modeling. 3 hr.; 3 cr. Prereq.: MATH 241. A review of frequentist methods followed by a survey of statistical modeling using the Bayesian framework: prior distribution design, including Jeffrey’s priors; likelihood models; posterior probabilities; hypothesis tests; Bayesian linear regression; Gibbs sampling; Metropolis-Hastings (basic Bayesian computing).  Emphasis on real-world applications, including those in finance and applied probability. The goal is to be fluent enough to understand how industry uses Bayesian modeling and computation by the end of the course.

Statistics has historically been taught from the frequentist perspective. Recently, the Bayesian perspective has become popular (1) due to their models' performance on previously intractable problems and the recent availability of inexpensive computational power and (2) it solves many philosophical quandaries in the Frequentist perspective. Further, many scientific journals have stopped accepting p-values and confidence intervals in favor of Bayesian inference and testing. It is imperative to teach this perspective; students will see these models in industry and this mode of thinking is becoming mainstream in science at large. \pagebreak

This course covers (and is not limited to) the following topics:

\begin{itemize}
\itemsep -0.0em
\item Data modeling with parametric families
\item Bayes Rule as it applies to parameters
\item prior distribution design
\item Jeffrey's priors
\item likelihood models and maximum likelihood estimators
\item posterior probabilities
\item Bayesian inference: credibility intervals
\item Bayesian inference: p-values for hypothesis tests
\item mixture priors
\item mixture models
\item Newton-Raphson and Expectation-Maximization Algorithms
\item basic computing for Bayesian models including Gibbs sampling and Metropolis-Hastings Sampling
\end{itemize}

\noindent The only prerequisite is Math 241 or equivalent. You should be familiar with the following:

\begin{itemize}
\itemsep -0.0em
\item Basic Set Theory
\item Counting Methods | permutations and combinations
\item Basic Probability Theory | axioms, conditional probability, in/dependence
\item Modeling with Discrete Random Variables: Bernoulli, Hypergeometric, Binomial, Pois-
son, Geometric, Negative Binomial, Uniform Discrete and others
\item Expectation and Variance
\item Modeling with Continuous Random Variables: Exponential, Uniform and Normal
\item Frequentist Confidence Intervals and Hypothesis Testing for one-sample proportions
\end{itemize}

\noindent We will review the above \textit{throughout the semester} when needed and we will do so rapidly. \\

\textbf{This is not your typical mathematics course.} This course develops ideas and concepts for helping to make decisions based on randomness and we will do lots of modeling of real-world situations. The course does not dwell on theory nor details of computation but will make use of computation especially using the \texttt{R} statistical language.

\section*{The 650.3 section}

You are the students taking this course as part of a masters degree in mathematics. Thus, there will be extra homework for you and you will be graded on a separate curve.

\section*{Course Materials}

\paragraph{Textbook:} Introduction to Bayesian Statistics by William M. Bolstad First Edition. It can be purchased used on \href{http://www.amazon.com/gp/offer-listing/0471270202/ref=sr_1_2_twi_1_har_olp?ie=UTF8&qid=1433515305&sr=8-2&keywords=introduction+to+bayesian+statistics+bolstad}{Amazon}. This is \textit{recommended}. ton get a way to get ``another take'' on the material. However, most of the material in the class comes from the lecture notes.  %We will also be using Bayesian Methods in Finance by by Svetlozar T. Rachev, John S. J. Hsu, Biliana S. Bagasheva  and Frank J. Fabozzi (First Edition) which can be bought on \href{http://www.amazon.com/gp/product/0471920835/ref=ox_sc_sfl_title_1?ie=UTF8&psc=1&smid=A1Q1B6W57NND6W}{Amazon}.

\paragraph{Popular Book:} We will also be reading the non-fiction novel \qu{The Theory that Would not Die: How Bayes' Rule Cracked the Enigma Code, Hunted Down Russian Submarines, and Emerged Triumphant from Two Centuries of Controversy} by Sharon Bertsch McGrayne which can also be purchased on \href{http://www.amazon.com/Theory-That-Would-Not-Die/dp/0300188226/ref=sr_1_1?ie=UTF8&qid=1454261896&sr=8-1&keywords=The+Theory+that+Would+not+Die}{Amazon}. This is \textit{required} --- you will have homework questions directly from this book.

\paragraph{Computer Software:} We will also be using \texttt{R} which is a free, open source statistical programming language and console. You can download it from: \url{http://cran.mirrors.hoobly.com/}. I do not expect you to do \textit{any} programming. I will be giving you \texttt{R} code to run and expect you to interpret the results based on concepts explained during the course.

\paragraph{Calculator:} You can use a TI-84, 85, 89 or any calculator which you wish. I strongly suggest you use \href{http://www.wolframalpha.com/}{Wolfram Alpha} and its smartphone app.

\section*{Announcements}

Announcements will be made via email. I am known to send a couple emails per week on important issues. Thus, I will need the email address that you reliably check. The default is whatever is in CUNYfirst which many of you do not check. (See Homework \#0 for more information).

\section*{Lectures}

I have a no computer / tablet / phone policy during lectures. Only pen / pencil and paper. There are 28 scheduled meetings. Of these, 23 will be lectures, 2 will be midterm exams which are in class and 2 will be review periods (the meeting before the exams). The exam schedule is given on page~\pageref{subsec:exam_schedule}.

\subsection*{Lecture Upload}

As many previous students have noted, my handwritten notes are useful to me and not to many others. Thus, I will be rewarding students for taking notes, scanning them in and sending them to me. You will be rewarded in two ways: (1) if you do this for more than 10 lectures, you will be given the automatic 5 points (see grading policy on page \pageref{sec:grading}) for your classroom participation grade and (2) you have the option for me to say your name publicly on the \coursewebpage. Make sure you follow these instructions:

\begin{itemize}
\item You have \emph{one week only} from the time of the lecture to email me lecture notes.
\item There must be \emph{one} file and it must be in PDF format only.
\item The file must be $<$2MB. No exceptions.
\end{itemize}

\section*{Homework}

There will be 9-11 homework assignments. Homeworks will be assigned and placed on the \coursewebpage~ and will usually be due a week later in class. Homework will be \textbf{graded} out of 100 with extra credit getting scores possibly $> 100$. I will be doing the grading and will grade an \textit{arbitrary subset of the assignment} which is determined after the homework is handed in. Homework must be printed, neat and stapled (\textbf{it cannot be emailed to me}). Homework can be given to me in class or delivered under my office door (KY 604).

Graded homework will be returned in class. Regrades are handled during office hours or right after class is over. Scores for homeworks are finalized one week after the graded copies are handed back. Thereafter there will be no changes and no re-grading. Do not delay checking your graded homeworks. I am not perfect and I do make mistakes. It is your obligation to find our mistakes and report them.

You are encouraged to seek help from me if you have questions. After class and office hours are good times. \ingreen{You are highly recommended to work with each other and help each other.} \inred{You must, however, submit your own solutions, \textit{with your own write-up} and in \textit{your own words}. There can be no collaboration on the actual \textit{writing}. Failure to comply will result in severe penalties.} The university honor code is something I take seriously and I send people to the Dean every semester for violations.

\subsection*{Philosophy of Homework}

Homework is the \textit{most} important part of this course.\footnote{In one student's \href{http://www.ratemyprofessors.com/ShowRatings.jsp?tid=1951051}{observation}, I give a \qu{mind-blowing homework} every week.} Success in Statistics and Mathematics courses comes from experience in working with and thinking about the concepts. It's kind of like weightlifting; you have to lift weights to build muscles. My job as an instructor is to provide assistance through your \href{http://en.wikipedia.org/wiki/Zone_of_proximal_development}{zone of proximal development}. With me, you can grow more than you can alone. To this effect, homework problems are color coded \ingreen{green} for easy, \inyellow{yellow} for harder, \inred{red} for challenging and \inpurple{purple} for extra credit. You need to know how to do all the greens by yourself. If you've been to class and took notes, they are a joke. Yellows and reds: feel free to work with others. Only do extra credits if you have already finished the assignment. The \qu{[Optional]} problems are for extra practice --- highly recommended for exam study.

\subsection*{Time Spent on Homework }

This is a three credit course. Thus, the amount of work outside of the 2.5hr in-class time per week is 6-9 hours. I will aim for 6hr of homework per week on average. However, doing the homework well is your sole responsibility since I will make sure that by doing the homework you will study and understand the concepts in the lectures and you won't have all that much to do when the exams roll around.

\subsection*{Late Homework}

Late homework will be penalized 10 points per business day (Monday--Friday save holidays) for a maximum of five days. \textit{Do not ask for extensions}; just hand in the homework late. After five days, \textbf{you can hand it in whenever you want} until May 15 at noon. As far as I know, this is one of the most lenient and flexible homework policies in college. I realize things come up. Do not abuse this policy; you will fall far, far behind.

\subsection*{Homework \LaTeX~Bonus Points}

Part of good mathematics is its beautiful presentation. Thus, \ingreen{there will be a 1--10 point bonus} added to your homework grade  for typing up your homework using the \LaTeX ~typesetting system based on the elegance of your presentation. The bonus is arbitrarily determined by me.

I recommend using \href{http://overleaf.com}{overleaf} to write up your homeworks (make sure you upload both the hw\#.tex and the preamble.tex file). This has the advantage of (a) not having to install anything on your computer and not having to maintain your \LaTeX ~installation (b) allowing easy collaboration with others (c) alway having a backup of your work since it's always on the cloud. If you insist to have \LaTeX ~running on your computer, you can download it for Windows \href{http://www.miktex.org/download}{here} and for MAC \href{http://www.tug.org/mactex/}{here}. For editing and producing PDF's, I recommend \TeX works which can be downloaded \href{http://www.tug.org/texworks/#Getting_TeXworks}{here}. Please use the \LaTeX ~code provided on the \coursewebpage ~for each homework assignment.

If you are handing in homework this way, read the comments in the code; there are two lines to comment out and you should replace my name with yours and write your section. The easiest way to use overleaf is to copy the raw text from hwxx.tex and preamble.tex into two new overleaf tex files with the same name. If you are asked to make drawings, you can take a picture of your handwritten drawing and insert them as figures or leave space using the \qu{$\backslash$vspace} command and draw them in after printing or attach them stapled.

Since this is extra credit, do not ask me for help in setting up your computer with \LaTeX~ in class or in office hours. Also, \textbf{never share your \LaTeX~code with other students} --- it is cheating and if you are found I will take it seriously.

\subsection*{Homework Extra Credit}

There will be many extra credit questions sprinkled throughout the homeworks. They will be worth a variable number of points arbitrarily assigned based on my perceived difficulty of the exercise. Homework scores in the 140's are not unheard of. They are a good boost to your grade; I once had a student go from a B to and A- based on these bonuses.
%
%\subsection*{Homework Redo Policy}
%
%There is no homework redo policy for Math 341. Hand in what you have, late if need be.

\subsection*{Homework \#0}

For your first homework, you must:

\begin{enumerate}[(1)]
\item email me at \href{kapelner@qc.cuny.edu}{kapelner@qc.cuny.edu} from the email address you wish to be contacted at for this course (most commonly this is a gmail address),
\item in the email, you must say \qu{My name is $<$Your Full Name as appears in the registrar$>$ and I have read and understand all the material in the course syllabus}
\end{enumerate}

\noindent \inred{This constitutes a contract --- you are agreeing to this syllabus.} \\

This assignment is due Friday, Feb 1, 5PM and will receive a grade of 0 or 100 with the usual 10 point penalty for lateness.

\section*{Examinations}

Examinations are solely based on homeworks (which are rooted in the lectures)! If you can do all the green and yellow problems on the homeworks, the exams should not present any challenge. I will \textit{never} give you exam problems on concepts which you have not seen at home on one of the weekly homework assignments. There will be three exams and the schedule is below.

\subsection*{Exam Schedule}\label{subsec:exam_schedule}

\begin{itemize}
\itemsep -0.0em
\item Midterm examination I will be Tues, March 5 in class with the first review session on the Thurs prior
\item Midterm examination II will be Thurs, April 11 in class with a review on the Tues prior
\item The final examination will be .... in KY283 with a review on the prior Tues, May 14.
\end{itemize}

\subsection*{Exam Materials}

I allow you to bring any calculator you wish but it cannot be your phone. The only other items allowed are pencil and eraser. I do not recommend using pen but it is allowed

I also allow \qu{cheat sheets} on examinations. For both midterms, you are allowed to bring one 8.5'' $\times$ 11'' sheet of paper (front and back). \inred{Two sheets single sided are not allowed.} On this paper you can write anything you would like which you believe will help you on the exam. For the final, you are allowed to bring three 8.5'' $\times$ 11'' sheet of paper (front and back). \inred{Six sheets single sided are not allowed.} I will be handing back the cheat sheets so you can reuse your midterm cheat sheets for the final if you wish.

%
%\subsection*{Cheating on Exams}
%
%If I catch you cheating, you can either take a zero on the exam, or you can roll the dice before the University Honor Council who may choose to suspend you.

\subsection*{Missing Exams}

There are no make-up exams. If you miss the exam, you get a zero. If you are sick, I need documentation of your visit to a hospital or doctor. Expect me to call the doctor or hospital to verify the legitimacy of your note. %If you need to leave the country for an emergency, I will expect proper documentation as well.

\subsection*{Special Services}

If you are a student who takes exams at the special services center, I need to see your blue slip one week before the exam to make proper arrangements with the center.

\section*{Class Participation (and attendance)}

I will be taking attendance selectively throughout the semester. Attendance counts towards the class participation portion of your grade in equal part with how often you ask and answer questions during the lecture.

\section*{Grading and Grading Policy}\label{sec:grading}

Your course grade will be calculated based on the percentages as follows:

\begin{table}[h]
\centering
\begin{tabular}{l|l}
Homework & 20\% \\
Class participation & 5\% \\
Midterm Examination I & 20\%\\
Midterm Examination II & 20\%\\
Final Examination & 35\%
\end{tabular}
\end{table}
\FloatBarrier

The semester is split into three periods :

\begin{enumerate}
\item From the beginning until midterm I. Midterm I covers material during this time..
\item From midterm I to midterm II. Midterm II covers material in this period only.
\item From midterm II until the final. The final is cumulative and covers all course material.
\end{enumerate}

Each of the periods is assessed evenly. Thus, each period must count the same towards your grade. Since there is 75\% of the grade allotted to exams, there is 25\% allotted to each period. Thus, the final is upweighted towards the material covered in the third period. In summary, the final will have 5/35 points $\approx$ 14\% for the first period's material, 5/35 points $\approx$ 14\% for the second period's material and 25/35 points $\approx$ 71\% for the last period's material. A good strategy for the final is to just study the material after Midterm II and minimal studying for the previous material.

\subsection*{The Grade Distribution}

As this is a small and advanced class, the class curve will be quite generous. If you do your homework and demonstrate understanding on the exams, you should expect to be rewarded with an A or a B. $\leq$C's are for those who \qu{dropped out} somewhere mid-semester or who cannot demonstrate basic understanding.

\subsection*{Checking your grade and class standing}

You can always check your grades in real-time using the \href{http://gradesly.com}{grading site}. You will enter in your QC ID number (or email) and the password I will provide to you after homework 0.

\section*{Auditing}

Auditors are welcome in both sections. They are encouraged to do all homework assignments. I will even grade them. Note that the university does not allow auditors to take examinations.

\end{document}


text:
\documentclass[conference]{IEEEtran}
% packages
\usepackage{xspace}
\usepackage{hyperref}
\usepackage{todonotes}
\usepackage{tikz}
\usepackage[utf8]{inputenc}

\def\CC{{C\nolinebreak[4]\hspace{-.05em}\raisebox{.4ex}{\tiny\bf ++}}}
\def\ea{\,et\,al.\ }

\begin{document}

% paper title
\title{At Least Two Solutions}

% author names and affiliations
% use a multiple column layout for up to three different
% affiliations
\author{
\IEEEauthorblockN{Norbert Manthey}
\IEEEauthorblockA{nmanthey@conp-solutions.com\\Dresden, Germany}
}

\maketitle

\def\coprocessor{\textsc{Coprocessor}\xspace}
\def\ALT{\textsc{AtLeastTwo}\xspace}

% the abstract is optional
\begin{abstract}
This document describes the \ALT tool, as well as the benchmarks that have been submitted to the SAT competition 2021.
The tool takes a CNF and encodes a new CNF which is satisfiable only if the initial CNF has at least two satisfying solutions. The difference of the two solutions can be restricted to input variables only, to support formulas that have been encoded with auxiliary variables.
The generated formulas are expected to reduce the effectiveness of symmetry breaking, as well as reduce the number of autarkies in formulas.
\end{abstract}

\section{Introduction}

When encoding problems, one might ask whether given problem has more than one solution.
This property is for example useful when generating logic puzzles to know whether a generated puzzle has multiple solutions.
A related property is to encode that a formula has exactly one solution.
Similarly, the encoding could be extended to ask for at least two satisfying assignments, or at most $k$ satisfying assignments.
However, the result formula would grow quadratically with $k$.
The current tool only supports asking for at least two solutions.
Other extensions would be to encode that at least a given number of $K$ assignments need to be different.
In this case, the currently used \emph{at-least-$k$} constraint -- a clause -- would have to be replaced by a properly encoded cardinality constraint.

The generated formulas are expected to reduce the effectiveness of symmetry breaking, because for a symmetry in the output formula, there would need to by a symmetry in the input formula that works for pairs of solutions.
Similarly, for an autarky in the input formula would have to be extended to the clauses that require the assignment of variables being different.
This results at least in larger autarkies.

\section{Encoding At Least Two Solutions}

The input for the \ALT tool is an uncompressed CNF file with the formulas $F$.
This formula has $n$ variables, and $m$ clauses, where we assume all variables $n$ to be present.
As in CNF, variables are represented as integers, we will use math rules to describe transformations.
The resulting formula is basically encoded by the following steps:
(1) duplicate $F$ into a formula $G$, but add the offset $n$ to all variables to obtain fresh variables,
(2) encode the equivalence for all variable pairs in $F$ and $G$, respecting the offset, and
(3) enforce that are least one equivalence from (2) is falsified.
The three steps will be explained in more details next.

\subsection{Duplicate Input Formula}

As a first step, we duplicate all clauses in $F$.
During this step, for all clauses $C_i$, we add the offset $n$ to the variable representation of all literals $l_i$ when creating the new clauses.

\[G := \bigwedge_{C_i \in F} \bigvee_{l_i \in C_i} l_i + n \]

\subsection{Encode Solution Equality}

To encode whether two variable assignments are equivalent, we need to introduce a new variable for each existing variable in $F$, or at least for the range of selected variables whose satisfying assignment should be different.
Let $e$ be the number of variables from $1$ to $e$ which should have at least one different assignment.
As the default case, the number of variables to consider is the number of variables in the input, i.e. $e = n$.

\[E := \bigwedge_{i=1}^{e} a_i \leftrightarrow (f_i \leftrightarrow g_i), \]

\noindent
where $a_i$ are variables that do not occur in $F$ nor in $G$.
Note, the variables $f_i$ and $g_i$ again have the offset of $n$ again, i.e. $g_i = f_i +n$.

\subsection{Force Inequality of Solutions}

When combining all formulas above, we obtain a formula that encodes the same formulas twice, and a sub-formula that indicates whether the assignments for both formulas are equal:

\[R' = F \land G \land E. \]

\noindent
A model for this formula can assign the same truth value for all variable pairs in $F$ and $G$.
To make sure, the models are different, we need to ensure that at least one pair of variables is not equal, by encoding an at-least-one constraint for the new auxiliary variables:

\[R = F \land G \land E \land \bigvee_{i=1}^{e} \neg a_i.  \]

\noindent
Formula $R$ is the resulting formula that will be generated by the tool.

\subsection{Properties of the Generated Formula}

First, we discuss the relationship between the satisfiability of the input formula $F$ and the produced formula $R$.
When the input formula $F$ is unsatisfiable, the resulting formula $R$ is also unsatisfiable.

Next, when $F$ has exactly one model, the truth values of this model can be assigned to satisfy $F$.
Formula $G$ will can only be satisfied with the same set of assignments.
Consequently, all variables $a_i$ will be assigned to $\top$.
In this case, the last sub-formula of $R$ will be falsified.

In the final case, multiple model $I$ and $J$ exist to satisfy $F$.
Then, $I$ can satisfy $F$, and $J$ can satisfy $G$ by respecting the offset $n$.
As $I$ and $J$ are different, at least one variable $a_i$ will be assigned to $\bot$, resulting in a satisfying assignment for $R$.
Note, such a satisfying assignment to $R$ contains the two models $I$ and $J$ that satisfy the input formula $F$.

Given a formula $F$ with $n$ variables and $m$ clauses, as well as targetting $e$ variables with $e \leq n$ for the in-equality results in a formula $R$ with $2n + e$ variables.
Furthermore, $R$ has $2m + 4e$ clauses, because an equality of three variables can be encoded with $4$ clauses.

\section{The Submitted Benchmark}

The submitted benchmark formulas have been generated by using formulas from previous SAT competition benchmarks.
\newpage

\noindent
The initial set of formulas to select the submitted formulas from is the robust benchmark for tuning SAT solvers from~\cite{SATgauss}.

\section{Availability}

The source of the tool is publicly available under the MIT license at \url{https://github.com/conp-solutions/cnfmiter}.

\bibliographystyle{IEEEtranS}
\bibliography{local}

\end{document}

ext: tex

max_stars_repo_name: conp-solutions/cnfmiter

max_issues_repo_name: conp-solutions/cnfmiter

max_forks_repo_name: conp-solutions/cnfmiter


text:
\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{commath}
\usepackage{mathtools}

% For multipage align*
\allowdisplaybreaks

\title{AVL maths}
\author{}
\date{}

\begin{document}
\maketitle

\section{Rotation}

For left rotation, where $X$ and $Y$ are the balance of nodes, and $a$, $b$, and
$c$ are the heights of subnodes.

\begin{verbatim}
  X
 / \
a   Y
   / \
  b   c
\end{verbatim}

\begin{verbatim}
    Y'
   / \
  X'  c
 / \
a   b
\end{verbatim}

\begin{align*}
    X &= \max(b,c) + 1 - a\\
    Y &= c - b\\
    \\
    X' &= b - a\\
    Y' &= c - (\max(a,b) + 1)\\
    \\
    X &= \max(b,c) + 1 - a\\
    -a &= X - \max(b,c) - 1\\
    -a &= X + \min(-b,-c) - 1\\
    b - a &= X + \min(0,b-c) - 1\\
    b - a &= X + \min(0,-Y) - 1\\
    X' &= X - \max(0,Y) - 1\\
    \\
    Y' &= c - \max(a,b) - 1\\
    Y' - b &= c - b - \max(a,b) - 1\\
    Y' - b &= Y - \max(a,b) - 1\\
    Y' - b &= Y + \min(-a,-b) - 1\\
    Y' &= Y + \min(b-a,0) - 1\\
    Y' &= Y + \min(X',0) - 1
\end{align*}

For right rotation we simply get

\begin{align*}
    X &= X' + \max(0,Y) + 1\\
    Y &= Y' - \min(X',0) + 1
\end{align*}

\end{document}


text:
\chapter{Conclusion}\label{chap:conclusion}
\par In conclusion, we successfully built a symmetric encryption protocol and a key exchange protocol using the Rubik's Cube. The steps we took demonstrated the general strategy of constructing encryption schemes: we first need to find a problem that is computationally hard, and we must analyze the problem and understand it well. We have shown the central role that a formal definition of security plays in the cryptography world. You must know what you are trying to achieve to deduce if you succeed or not. While we are not recommending commercial usage of this encryption system, we believe that it does provide a secure environment for two parties to communicate without leaking any visible information, given that the attacker possesses limited computational power such as one laptop.
\par Future work on this topic includes testing the Rubik's Cube encryption under even stronger definitions. Recall that in the security game described in Chapter~\ref{chap:security}, Alice can interact with the protocol only once before she guesses the encrypted message. But in the real world, once parties construct a secure channel, they will likely communicate multiple times. Thus under a stronger definition of security, we allow Alice to make multiple requests and observe the results to catch potentially leaked information. Then if she notices any vulnerabilities in the trial queries, she can generate two corresponding messages to crack the protocol. For the key exchange protocol, we can expand this to an $n-$party key exchange protocol, rather than the two-party protocol we designed.


text:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{\label{sec:gotchas}Upgrading from the 7.6 series to the 7.8 series of HTCondor}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\index{upgrading!items to be aware of}
While upgrading from the 7.6 series of HTCondor to the 7.8 series will bring many
new features and improvements introduced in the 7.7 series of HTCondor, it will
also introduce changes that administrators of sites running from an older
HTCondor version should be aware of when planning an upgrade.  Here is a list of
items that administrators should be aware of.

\begin{itemize}

\item In the grid universe, the Amazon grid-type is gone and has been replaced
	with the EC2 grid-type.  Also, support for grid-type gt4 (Web Services
	GRAM) has been removed.

\item Default job submit options related to file transfers have changed.
Across all platforms, defaults are now
\begin{verbatim}
  should_transfer_files = IF_NEEDED
  when_to_transfer_output = ON_EXIT
\end{verbatim}
See section~\ref{sec:file-transfer-if-when} for details.

\item  On Linux and Mac OS, common utility code is now contained in a set of
shared libraries. In the Linux native packages, most of these libraries
are placed under \File{/usr/lib[64]/condor} and the RUNPATH attribute is set in
the binaries to search there for them.
In the tarball packages, these libraries are placed under \File{lib} and
\File{lib/condor}, and the RUNPATH attribute is set in the binaries to search
for them under the relative paths \File{../lib} and \File{../lib/condor}.
This means that if you move or copy an HTCondor binary from a tarball
package to a different location, you must do one of the following:
\begin{itemize}
	\item Move or copy the corresponding \File{lib/} directory with it, or
  \item Make a symlink in the new location pointing back to the original \File{lib/}
  directory, or
  \item Set environment variable \Env{LD\_LIBRARY\_PATH} to point to the original \File{lib/} and \File{lib/condor/}
  directories
\end{itemize}
One of the new shared libraries, \File{libcondor\_utils\_7\_8\_0}, has no \File{.so}
versioning. Instead, the HTCondor version is included in the library name.
This means that an HTCondor binary must always be matched with the
\File{libcondor\_utils} library from the same HTCondor release.

\item  The \Condor{hdfs} service is no longer included within the HTCondor
	release.  Instead, the HTCondor + HDFS integration previously bundled with
	version 7.6 is available in version 7.8 as a \Term{Contribution Module}.
	Contribution Modules are optional packages that add functionality to
	HTCondor, but are provided and maintained outside of the core code base.  See
	the HTCondor Wiki at
	\URL{https://condor-wiki.cs.wisc.edu/index.cgi/wiki?p=ContribModules}.

\item Previous to version 7.8, by default the \Condor{master} would restart any
	individual daemon under its control if it notices that the file
	modification time of the binary for that daemon has changed.  Now the
	\Condor{master} will only monitor the file modification time of the
	\Condor{master} binary itself.  See section~\ref{sec:Pool-Upgrade}.  Also,
	see \MacroNI{MASTER\_NEW\_BINARY\_RESTART} on
	page~\pageref{param:MasterNewBinaryRestart}.

\item In DAGMan, if you have a PRE and a POST script on a node, the default now
	is that the POST script is run even if the PRE script failed.   This change
	could impact unaware workflows such that POST scripts might erroneously
	report the node as succeeded. You can get the old behavior by setting
	\MacroNI{DAGMAN\_ALWAYS\_RUN\_POST} to False.  In addition, you can no
	longer directly submit a rescue DAG file with \Condor{submit\_dag} unless
	\MacroNI{DAGMAN\_WRITE\_PARTIAL\_RESCUE} is set to False (not normally
	recommended).  See section~\ref{sec:DAGMan}.

\item The \MacroNI{KILL} expression cannot be used to grant more time to a job
	than offered by \Macro{MachineMaxVacateTime}. In HTCondor v7.8 and above, it
	is anticipated that most sites will simply use a default value of False for
	\MacroNI{KILL} and set \MacroNI{MachineMaxVacateTime} to control how long
	to wait.  See page~\pageref{param:MachineMaxVacateTime} for more
	information.

\end{itemize}

max_stars_repo_name: neurodebian/htcondor

max_issues_repo_name: neurodebian/htcondor

max_forks_repo_name: neurodebian/htcondor


text:
%!TEX root = ./ERL Industrial Robots.tex

%--------------------------------------------------------------------
%--------------------------------------------------------------------
%--------------------------------------------------------------------
\section{Robots and Teams}
\label{sec:RobotsTeams}
The purpose of this section is twofold:
\begin{enumerate}
\item It specifies information about various robot features that can be derived from the environment and the targeted tasks. These features are to be considered at least as desirable, if not required for a proper solution of the task. Nevertheless, we will try to leave the design space for solutions as large as possible and to avoid premature and unjustified constraints.
\item The robot features specified here should be supplied in detail for any robot participating in the competition. This is necessary in order to allow better assessment of competition and benchmark results later on.
\end{enumerate}

The description of the robot should be included in the team description paper.

\subsection{General Specifications and Constraints on Robots and Teams}
\label{ssec:RobotSpecification}

%-----------
\begin{robotSpec}[System]
A competing team may use a single robot or multiple robots acting as a team.
It is not required that the robots are certified for industrial use.
At least one of the robots entered by a team is capable of:
\begin{itemize}
\item mobility and autonomous navigation.
\item manipulate and grasp at least several different task-relevant objects. The specific kind of manipulation and grasping activity required is to be derived from the task specifications.
\end{itemize}
The robot subsystems (mobility, manipulation and grasping) should work with the environment and objects specified in this rule book.
\end{robotSpec}

%-----------
\begin{robotSpec}[Sensor Subsystems]
Any robot used by a team may use any kind of \textbf{onboard} sensor subsystem, provided that the sensor system is admitted for use in the general public, its operation is safe at all times, and it does not interfere with other teams or the environment infrastructure.
A team may use the sensor system in the environment provided by the organizer by using a wireless communication protocol specified for such purpose. Sensor systems used for benchmarking and any other systems intended for exclusive use of the organizers are not accessible by the robot system.
Teams are not allowed to modify the environment or to install their own embedded devices in the environment, e.g., additional sensors or actuators.
\end{robotSpec}

%-----------
\begin{robotSpec}[Communication Subsystems]
	Any robot used by a team may \textbf{internally} use any kind of communication subsystem, provided that the communication system is admitted for use in the general public, its operation is safe at all times, and it does not interfere with other teams or the environment infrastructure.
	A robot team must be able to use the communication system provided \textbf{as part of the environment} by correctly using a protocol specified for such purpose and provided as part of the scenario.
\end{robotSpec}

%-----------
\begin{robotSpec}[Power Supply]
	Any mobile device (esp.~robots) must be designed to be usable with an onboard power supply (e.g.~a battery). The power supply should be sufficient to guarantee electrical autonomy for a duration exceeding the periods foreseen in the various benchmarks, before recharging of batteries is necessary.
	Charging of robot batteries must be done outside of the competition environment. The team members are responsible for safe recharging of batteries.
	If a team plans to use inductive power transmission devices for charging the robots, they need to request permission from the event organizers in advance and at least three months before the competition.
	Detailed specifications about the inductive device need to be supplied with the request for permission.
\end{robotSpec}

%-----------
\begin{robotConstraint}[Computational Subsystems]
	Any robot or device used by a team as part of their solution approach must be suitably equipped with computational devices (such as onboard PCs, microcontrollers, or similar) with sufficient computational power to ensure safe autonomous operation.
	Robots and other devices may use external computational facilities, including Internet services and cloud computing to provide richer functionalities, but the safe operation of robots and devices may not depend on the availability of communication bandwidth and the status of external services.
\end{robotConstraint}
%-----------

\begin{robotConstraint}[Safety and Security Aspects]
	For any device a team brings into the environment and/or the team area, and which features at least one actuator of any kind (mobility subsystems, robot manipulators, grasping devices, actuated sensors, signal-emitting devices, etc.), a mechanisms must be provided to immediately stop its operation in case of an emergency (emergency stop).
	For any device a team brings into the environment and/or the team area, it must guarantee safe and secure operation at all times.
	Event officials must be instructed about the means to stop such devices operating and how to switch them off in case of emergency situations.
\end{robotConstraint}

%-----------
\begin{robotConstraint}[Operation]
In the competition, the robot should perform the tasks autonomously.
An external device is allowed for additional computational power.
It must be clear at all times that no manual or remote control is exerted to influence the behavior of the robots during the execution of tasks.
\end{robotConstraint}

%-----------
\begin{robotConstraint}[Environmental Aspects]
  Robots, devices, and apparatus causing pollution of air, such as combustion engines, or other mechanisms using chemical processes impacting the air, are not allowed.
  Robots, devices, and any apparatus used should minimize noise pollution. In particular, very loud noise as well as well-audible constant noises (humming, etc.) should be avoided. The regulations of the country in which a competition or benchmark is taking place must be obeyed at all times. The event organizers will provide specific information in advance, if applicable. Robots, devices, and any apparatus used should not be the cause of effects that are perceived as a nuisance to humans in the environment. Examples of such effects include causing wind and drafts, strong heat sources or sinks, stenches, or sources for allergic reactions.
\end{robotConstraint}

%--------------------------------------------------------------------
%--------------------------------------------------------------------

\subsection{Benchmarking Equipment in the Robots}
\label{ssec:RobotBenchEquip}

\paragraph{Preliminary Remark:}
Whenever teams are required to install some element provided by \erlir on (or in) their robots, such element will be carefully chosen in order to minimize the work required from teams and the impact on robot performance.

\paragraph{Hardware}
As a general rule, \erlir does not require that teams install additional robotic hardware on their robots. Moreover, permanent change to the robot's hardware is never required. However, \erlir may require that additional standard PC hardware (such as an external, USB-connected hard disk for logging) is temporarily added to the robot in order to collect internal benchmarking data. When this is the case, the additional hardware is provided by \erlir during the competition, and its configuration for use is either automatically performed by the operating system, or very simple.

To allow the acquisition of external benchmarking data about their pose, robots need to be fitted with special reflective markers, mounted in known positions. The teams will be required to prepare their robots to ease the mounting of the markers. Teams will be required to provide the geometric transformation from the position of the marker to the odometric center of the robot\footnote{Benchmarking data related to poses will refer to the marker position: this is why additional information is required to know the position of the base.}.

\paragraph{Software} \erlir may require that robots run \erlir-provided (or publicly available) software during benchmarks. A typical example of such software is a package that logs data provided by the robot, or a client that interfaces with a \erlir server via the wireless network of the testbed. Whenever a team is required to install and run such a package, it will be provided as source code, its usage will be most simple, and complete instruction for installation and use will be provided along with it. All \erlir software is written to have a minimal impact on the performance of a robot, both in terms of required processing power and in terms of (lack of) interaction with other modules. When required by a benchmark, the relevant \erlir software to be run by participating robots is provided well in advance with respect to the competition.

\erlir will make any effort to avoid imposing constraints on the teams participating to the competition in terms of software architecture of their robots. This means that any provided piece of software will be designed to have the widest generality of application. However, this does not mean that the difficulty of incorporating such software into the software architecture of a robot will be independent from such architecture: for technical reasons, differences may emerge. A significant example is that of software for data logging. At the moment, it appears likely that any such software by \erlir will be based on the established \emph{rosbag} software tool, library and file format. As rosbag is part of ROS (Robot Operating System), robots based on ROS can use it to log data without any modification; on the contrary, robots not using ROS will be required to employ the rosbag library to create rosbag files (\emph{bagfiles}) or to develop ad-hoc code to convert their well established logging format into the rosbag one by using the rosbag API. If this will be the case, \erlir will provide tools to ease the introduction of software modules for creation of bagfiles into any software architecture; yet, teams not using ROS will probably have to perform some additional work to use such tools.

\subsection{Robot Communication with Benchmarking Equipment}
\label{ssec:BenchEquipRobotCommunication}
For some types of internal benchmarking data (i.e.~provided by the robot), logging is done on board the robot, and data are collected after the benchmark (for instance, via USB stick). Other types of internal benchmarking data, instead, are communicated by the robot to the testbed during the benchmark. In such cases, communication is done by interfacing the robot with standard wireless network devices (e.g. IEEE 802.11n) that are part of the testbed, and which therefore become a part of the benchmarking equipment of the testbed. However, it must be noted that network equipment is not strictly dedicated to benchmarking: for some benchmarks, in fact, the \wifi ~may be (or exclusively) used to perform interaction between the robot and the testbed.

Due to the need to communicate with the testbed via the \wifi, all robots participating to the \erlir competition are required to:
\begin{enumerate}
\item possess a fully functional IEEE 802.11n network interface\footnote{It must be stressed that full functionality requires that the network interface must not be hampered by electromagnetic obstacles, for instance by mounting it within a metal structure and/or by employing inadequate antenna arrangements. Network spectrum in the competition area is typically very crowded, and network equipment with impaired radio capabilities may not be capable of accessing the testbed \wifi, even if correctly working in less critical conditions.};
\item be able to keep the wireless network interface permanently connected to the testbed \wifi \ for the whole duration of the benchmarks.
\end{enumerate}

\input{ssecGeneralYamlDataFileSpec}

%--------------------------------------------------------------------
% EOF
%--------------------------------------------------------------------

max_stars_repo_name: mhwasil/ProfessionalServiceRobots

max_issues_repo_name: mhwasil/ProfessionalServiceRobots

max_forks_repo_name: mhwasil/ProfessionalServiceRobots


text:
\section{Lessons Learned}
\label{sec-conc-lessons}

In this section, we present a list of general lessons we learned while
working on this dissertation.

%lessons of file-system study
\vspace{0.1in} \noindent \textbf{Large-scale studies are valuable.}
In general, studies drive system designs.  Researchers and
practitioners conducted numerous studies in the past to help
understand system behaviors, workload patterns, and various
design tradeoffs.  These detailed studies can provide practical
motivation and useful design guidelines for next generation systems.

For the file system study project, we found many interesting and
important details after studying a large number of patches across six
file systems. These details can inspire new research opportunities. For
example, once we understand how file systems leak their resources,
we can build a specialized tool to detect them more efficiently. Once
we know how file systems crash, we can improve current systems to
tolerate them more effectively. These vivid examples in the study
really teach us what are the important problems in file systems.

The scale of the study is also very important.  More patches we
studied, more interesting patterns we found. More importantly, only
after a large number of cases are studied, we can make some
observations which may be statistically significant and insightful.

\vspace{0.1in} \noindent \textbf{Conquer a large-scale study with small steps.}
Conducting a large-scale study is definitely time consuming.
The total number of patches we studied comprehensively is
about 2000 (bugs, performance and reliability patches). If we knew in
advance that we need to analyze 2000 hard patches, we may feel
overwhelmed and give up this project early on. The way we handled this
study is starting from small beginnings.

Initially, we were just curious about Ext3's patches, since Ext3 was a
stable and popular file system. We studied 5 versions of Ext3 patches,
and classified them into different categories. We found the results
very interesting and surprising.  Then, we thought that we
need to study more patches of Ext3 to better understand the broader
patterns.  Once we finished all 40 versions of Ext3 in Linux 2.6
series, we wondered that whether Ext4 has similar bugs and performance
techniques as Ext3. After Ext4, we continued to ask that what about
other types of file systems, such as Btrfs (copy-on-write) and XFS
(logical journaling).  In this incremental manner, we grew our study
base from one file system to six popular file systems, and from less
than 100 patches to over 5000 patches in total finally.  It took us
one and half year to finish the study. Thus, a large-scale study is
still feasible and manageable.  Starting from small beginnings and
making consistent progress keep us interested and mentally sane in
this long journey.

\vspace{0.1in} \noindent \textbf{Research should match reality.}
Most previous work of bug studies and bug-finding tools focused on
generic bugs (such as memory bugs, concurrency bugs and error handling
bugs). However, in our study, we found that a majority of file system
bugs are semantic bugs, which require file-system domain knowledge to
understand and fix.  Furthermore, we found that none of these semantic
bugs was detected by existing tools, such as Coverity.  This striking
gap between research and reality demonstrates the importance of
finding and solving real problems.

In our study, we advocated that new tools are highly desired for
semantic bugs in file systems. We also suggested that more attention
may be required to make failure paths more correct.  Fortunately,
following research papers~\cite{MinEtAl15-SOSP,YuanEtAl14-OSDI}
proposed solutions for these two real problems.

\vspace{0.1in} \noindent \textbf{History repeats itself.}
We observed that similar mistakes happened again and again, within a
single file system and across different file systems. Developers of
new file systems even borrowed bug-fixing solutions from patches of
old file systems. We also found that similar performance and
reliability techniques were used across file systems in
different time when performance bottlenecks were detected or data
corruption occurred.

System researchers and developers should not only focus on innovative
designs for future systems, but also respect the history of existing
systems widely deployed and researched. Learning from these rich
history will never be wasting of time; instead, it will provide new
insights and experiences of what worked and what not. More
importantly, the same mistakes can be avoided at the first place.
We should pay more attention to system histories, learn from them, and
build a correct, high-performance and robust next generation systems
from the beginning.

%lessons of icefs
\vspace{0.1in} \noindent \textbf{Inspiration can come from a different area.}
After we finished the file system study, we were looking for what to
work next.  During that period, we occasionally read a security paper
from our colleague~\cite{VaraEtAl12-CCS}, which solved the problem of
performance interference among virtual machines co-located in the same
physical machine in the cloud.  Since there was little isolation
for VMs from different users, it is possible to slow down other VMs
co-located in the same machine by running a carefully design workload
from the attacker VM.

Even though this is a security paper, it immediately inspired us to
think about isolation for VMs or users on the same machine in the
context of file systems. Since we just finished the file system study,
we knew that file systems have many bugs, and bugs cause data
corruption and system crashes, which will affect all VMs or users
relying on the same file system. An interesting research question for
us is that how can we isolate reliability interference in the file
system layer. This is how we started the IceFS project.  Later, we
also extended IceFS to handle the performance interference in the file
system by isolating transactions.

Ideas from a different area may help you think about your research in
a new perspective. Viewing problems in a different angle is hard
without any new source of inputs. These small and random kicks from
other research areas may inspire you in unexpected ways and play an
important role for new research ideas.

\vspace{0.1in} \noindent \textbf{Don't settle for existing abstraction.}
Files and directories are basic and long-standing abstraction provided
by file systems.  However, these logical entities are an illusion; the
underlying physical entanglement in file system data structures and
transactional mechanisms does not provide true isolation.
To provide true isolation within a file system, we proposed a new
abstraction, called cube.  This new abstraction connects the logical
abstraction provided to users and the underlying physical structures
on disk. Based on this new abstraction, it is straightforward for us
to design an isolation file system which can provide both reliability
and transaction performance isolation.

New abstraction fosters new research. If a research problem cannot be
solved by existing abstraction, a new abstraction may be required.
New abstraction should be simple and easy to use.

\vspace{0.1in} \noindent \textbf{Isolation should be a fundamental design goal.}
When we analyzed the shared failures and bundled performance in file
systems, we found the root cause is the entanglement of on-disk
structures and in-memory transactions for different files. In other
words, file systems were not designed to provide isolation at the
first place.  To provide better data locality, metadata from multiple
files is stored together in the same disk block. To provide better I/O
performance, updates from different files are batched in the same
transaction. Data locality and I/O performance were the main goals
when designing file systems.  However, isolation was omitted as a
fundamental design goal.

Isolation is becoming more important in new environments. As the
workloads of the world move to the cloud, as the computing moves to
virtual machines and containers, as the multi-tenant world becomes the
only world we will live in, isolation is the key property to give us
the illusion that we have our own machines. We should rethink systems
underneath our applications at the very basic levels, both in terms of
data layouts and I/O patterns. We should design systems with strong
isolation for well-defined boundaries from the beginning.

\if 0
\vspace{0.1in} \noindent \textbf{Don't miss the big system stack.}
Modern systems in data centers have a large number of stackable layers
due to virtualization, compression, replication, deduplication,
etc. For example, Windows I/O stack has 18 layers between applications and the
device~\cite{thereska2013ioflow}.

We should think any system problem with the whole system stack in
mind.
\fi

%wisckey
\vspace{0.1in} \noindent \textbf{Don't put old software in new hardware.}
Originally, LSM-trees were designed for machines with hard drives and
a small number of cores. As long as the write and read amplification
are smaller than 1000, LSM-trees are good enough for a wide range of
workloads.  With the rise of SSDs on modern servers, while replacing
an HDD with an SSD underneath an LSM-tree does improve performance,
the SSD's true potential goes largely unrealized with the old
LSM-trees as we demonstrated in Chapter~\ref{chap-whiskey}.

We need to evolve old software for new hardware. There are lots of
progresses on building storage systems in last several decades.
Virtually, all of those intelligence was based on hard drives.
Recently, we really transition our storage system to flash based
devices. We should re-evaluate systems designed before, leverage
things worked well, and optimize them further to leverage the new
hardware. In WiscKey, we leverage the good parts of LSM-trees
(such as sequential I/O patterns and rich features), and
further optimize it in new ways for SSDs to get the best of two
worlds.

\vspace{0.1in} \noindent \textbf{Work on systems extremely slow or unreliable.}
At the conference Usenix FAST 2009, Marshall Kirk McKusick said that
the reason he worked on FFS (Fast File System)~\cite{McKusickEtAl-FFS-84} was
that the default UNIX file system that time only utilized 2\% of the device
bandwidth. There was a huge room to improve it. Therefore, FFS was
proposed and it can reach 47\% of the device bandwidth, more than
20$\times$ of the baseline.

WiscKey is also such an example. When our experiments showed that LevelDB
has high I/O amplification, and it can only utilize about 1\% of the
SSD device bandwidth, we felt that it is a great opportunity to make
LevelDB significantly faster. After an array of new designs and
optimization, WiscKey can be over 100$\times$ faster than LevelDB.

We believe that when choosing what to work on, try to choose an
existing system which is extremely slow or unreliable. More
opportunities lie at these corners.


text:
\section{Introduction}

This document describes SASSI, a selective instrumentation framework
for NVIDIA GPUs.  SASSI stands for SASS Instrumenter, where SASS is
NVIDIA's name for its native ISA.  SASSI is a pass in NVIDIA's backend
compiler, \texttt{ptxas}, that selectively inserts instrumentation
code.  The purpose of SASSI is to allow users to measure or modify
\texttt{ptxas}-generated SASS by injecting instrumentation code
\emph{during} code generation.

NVIDIA has many excellent development tools. Why the need for another
tool? NVIDIA's tools such as \texttt{cuda-memcheck} and \texttt{nvvp}
provide excellent, but \emph{fixed-function} inspection of programs.
Tools like \texttt{cuda-memcheck} perform binary patching to insert
instrumentation code.  While they are great at what they are designed
for, the user has to choose from a fixed menu of program
characteristics to measure.  If you want to measure some aspect of
program execution outside the purview of those tools you are out of
luck.  One example that we provide in this guide --- in
Section~\ref{sec:example3} --- is a perfect example of something
that SASSI is good at, that NVIDIA's production tools currently cannot
handle.

SASSI is invoked extremely late in the compiler's flow to minimize any
disruption the instrumentation code has on the code the user wants to
measure. Because SASSI is part of the compiler, it is important for us
to clearly state up front that SASSI is not a \emph{binary
  instrumenter}. SASSI instrumentation of programs requires the source
code (either CUDA, OpenCL, or PTX). As a consequence, any device
libraries (e.g., \texttt{cuFFT}) that your application links in will
not be instrumented unless the user has explicitly recompiled the
library with SASSI. We also note here that SASSI is a fork of the
production backend compiler, and therefore, the code it instruments
may deviate from that of the official \texttt{ptxas}.

As a small research effort however, working within the backend
compiler affords us stability and portability.  NVIDIA's architectures
change dramatically from generation to generation, yet because SASSI
is part of the compiler flow, it can target Fermi, Kepler, and Maxwell
devices, and it runs on Windows and Linux.  \hl{NVIDIA Research is
  releasing SASSI ``as-is'', and users should realize that it is a
  \emph{research prototype} with no promise of support or continuity.}


text:
\documentclass[twocolumn]{article}

\def\topfraction{.85}
\def\dbltopfraction{.85}
\def\textfraction{.12}

\usepackage{natbib}
\usepackage{amsmath}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{url}
\usepackage{rotating}

\def\npup{\ensuremath{S}}
\def\nmaj{\ensuremath{D}}
\def\nprof{\ensuremath{A}}
\def\ngrad{\ensuremath{A^\text{pg}}}
\def\ngrant{\ensuremath{G}}
\def\nisi{\ensuremath{P^\text{WoS}}}
\def\nscielo{\ensuremath{P^\text{S}}}

\def\der#1#2{\frac{\mathrm{d}\,{#1}}{\mathrm{d}#2}}
\def\pder#1#2{\frac{\partial\,{#1}}{\partial#2}}

\def\Fnew{\ensuremath{F^\text{new}}}
\def\nal{\ensuremath{N_\text{pub}}}
\def\nal{\ensuremath{N_\text{alumnos}}}
\def\nal{\ensuremath{N_\text{alumnos}}}
\def\eqref#1{Eq.~(\ref{eq:#1})}
\makeatletter
\def\eqsref#1#2{Eqs.~(\ref{eq:#1}--\ref{eq:#2})}
\makeatother

\usepackage{geometry}
\geometry{left=16mm,top=16mm,right=20mm,bottom=20mm}

\title{Direct Government Contribution to Chilean universities}
\author{Régis Lachaume}

\begin{document}

\maketitle

\section{Introduction}
Aporte Fiscal Directo, or Direct Government Contribution, hereafter AFD.

\section{Mathematical analysis}
The funding consists of two parts: 5\% is allotted to Universities according to a measurement of their current efficiency and 95\% according to their past share of the funding.

\subsection{Efficiency-dependent funding (5\%)}
\subsubsection{Calculation}
\label{sec:metrics}

Art. 2 of Decree with Force of Law 4 of 1980, with modifications from Art. 1 of Ministry of Education Decree 116 of 2002, indicates that 5\% part of the total funding of year $n + 1$ is distributed to University $i$ according to its metrics reported after year $n$\footnote{Some are from year $n$ and others from year $n-1$.}. They involve
\begin{itemize}
\item $\npup_{i,n}$, the number of undergraduate students (``estudiantes de pregrado'');
\item $\nmaj_{i,n}$, the number of bachelor degree disciplines (``carreras'');
\item $\nprof_{i,n}$, the number of equivalent full-time academic staff (``académicos''), i.e. professors;
\item $\ngrad_{i,n}$, the number of equivalent full-time academic staff with a post-graduate title such as master or a PhD;
\item $\ngrant_{i,n}$, the number of research grants (``proyectos'');
\item $\nisi_{i,n}$, the number of Web of Science publications (WoS)\footnote{At the time of the Decree 116 it was known as ISI};
\item and $\nscielo_{i,n}$, the number of non-WoS publications indexed by the Scientific Electronic Library Online (Scielo) Chile.
\end{itemize}

The metrics, defined in the aformentioned decrees, are ratios meant to measure an output v. staff efficiency\footnote{While the number of publications is defined by the number of WoS plublications plus one third of Scielo one by Ministry of Education Decree 116 of 2002, the Ministry has consistently used factor 0.33 instead of 1/3 for the calculation.}
\begin{subequations}
\begin{align}
    x_{i,n,1} &= \npup_{i,n} / \nmaj_{i,n},  \label{eq:x1}             \\
    x_{i,n,2} &= \npup_{i,n} / \nprof_{i,n},                           \\
    x_{i,n,3} &= \ngrad_{i,n} / \nprof_{i,n},                          \\
    x_{i,n,4} &= \ngrant_{i,n} / \nprof_{i,n},                         \\
    x_{i,n,5} &= (\nisi_{i,n} + \frac{33}{100} \nscielo_{i,n}) / \nprof_{i,n}
\end{align}
\end{subequations}

According to Art. 3 of Ministry of Education Decree 128 of 1991,  the
evaluation formula renormalises the aforemention ratios in this
way\footnote{Although not specified by the decree, the Ministry has
consistently used the population variance, not the sample variance, for the calculation.}:
\begin{subequations}
\begin{align}
    \mu_{n,k}    &= \frac1N\sum_j x_{j,n,k}\qquad\text{(mean)} \label{eq:mu}\\
    \sigma_{n,k} &= \sqrt{\frac 1N \Big(\sum_j x_{j,n,k}^2\Big) - N\mu_{n,k}^2}\qquad\text{(std. dev.)} \label{eq:sigma}\\
    \xi_{i,n,k}  &= \frac{x_{i,n,k} - \mu_{n,k} }{\sigma_{n,k}}
\qquad\text{(reduced coeff.)} \label{eq:xi}\\
    y_{i,n,k}    &= \exp \left[ -\frac 75 + \frac{\xi_{i,n,k}}4  \right]^3 \label{eq:transform}
\end{align}
\end{subequations}
where $N$ is the total number of universities.
The transform in \eqref{xi} ensures that Universities are compared by how many standard deviations they are from the mean. The exponential in \eqref{transform} is supposed to simulate a biological growth. Figure~\ref{fig:transform} displays the exponential nature of the rating.

Art.~2 of Decree with Force of Law~4 of 1980 indicates that 5\% of the funding
is indexed on a weighted average of the metrics $y_{i,n,k}$ (k in $1\cdots5$)
(see Sect.~\ref{sec:metrics}). The weights $c_k$ may vary from year to year,
but have been constant since 1998 with $c = (0.01, 0.14, 0.24, 0.25, 0.35)$.  University $i$ is thus assigned a score
\begin{subequations}
\begin{align}
    y_{i,n}    &= \sum_k c_k y_{i,n,k}. \label{eq:y}\\
\intertext{and, using the total score}
    y_{n}      &= \sum_i y_{i,n},\\
\intertext{a funding share}
    f_{i,n}    &= \frac{y_{i,n}}{y_{n}} \label{eq:f}
\end{align}
\end{subequations}

\begin{figure}[t]
\centering
\includegraphics[width=\linewidth]{pdf/total-afd-timeseries.pdf}
\caption{Evolution of total direct State funding to traditional Chilean Universities, in 2020 pesos (inflation-corrected) compared to the evolution of the GDP per capita (World Bank data), the mean real wage (Instituto Nacional de Estadísticas data), the number of undergraduate students and the number of professors.}
\label{fig:total-afd}
\end{figure}

\begin{figure*}[p]
\centering
\includegraphics{pdf/afd-coefficients.pdf}
\caption{Contribution of each metric to the AFD funding of traditional Chilean universities in 2021. \textit{Top panel:} contributions of 2020 metrics to the 5\%. \textit{Bottom panel:} contributions of the recent metrics and historic pre-2005 ones to the total funding. \textit{Left axis:} thousand million Chilean pesos, of the order of million US dollars. \textit{Right axis:} university scores $c_k y_k$ and its total $y = \sum c_k y_k$. The historic funding is not shown for newly minted universities of O'Higgins and Aysén.  The data used to produce the top panel of this figure can be found in Table~\ref{tab:calcdetail}.}
\label{fig:coeff}
\end{figure*}

The 2021 funding via the 5\% is shown in the top panel of Figure~\ref{fig:coeff}, with the contributions of each metrics.

\subsubsection{Marginal earnings}
\label{sec:marginal}

\begin{figure*}[p]
\centering
\includegraphics{pdf/marginal-earnings.pdf}
\caption{Marginal earnings of traditional Universities for each of the following improvements reported in 2020: one additional undergraduate student, one additional one-year contract of a postgraduate professor instead of one without a postgraduate title, one additional one-year research grant, one additional WoS (ex-ISI) publications.  \textit{Left axis:} present value of total earnings in million Chilean pesos, assuming a yearly depreciation of 5\% in real terms and 2\% increase of total funding by the State. \textit{Right axis:} earnings in year 2021. The data used to produce this figure can be found in Table~\ref{tab:marginal}.}
\label{fig:marginal}
\end{figure*}

In this section, I focus on a yearly snapshot and drop the $n$ index in the formulae.  I examine the case where university $i$ decides to increase one of its ratios number $k$ by a small number of standard deviations $\Delta\xi_{i,k}$, so that the ratio $x_{i,k}$ improves by $\Delta x_{i,k} = \sigma_k\Delta\xi_{i,k}$.

For any university $j$, the new value of the score $y_{j,k}$ is usually modified because the mean and standard deviation are changed via $x_{i,k}$.  The difference $\Delta y_{j,k}$ is given by differentiating \eqref{transform}, and in turn \eqsref{mu}{xi} on which it depends.
The calculation, detailed in  in Appendix~\ref{sec:calculus}, yields
\begin{equation}
    \frac{\Delta y_{j,k}}{y_{j,k}} =
        \frac34 \left(\frac{\xi_{j,k}}4 -  \frac75\right)^2
        \left(
            \delta_{ij}
          - \frac 1N - \frac{\xi_{i,k}\xi_{j,k}}{N}
        \right)
        \Delta \xi_{i,k},
        \label{eq:modif}
\end{equation}
where $\delta_{ij} = 1$ if universities $i$ and $j$ are the same and zero otherwise.

The meaning of \eqref{modif} is the following:
\begin{enumerate}
    \item \emph{$(\xi_{j,k}/4 - 7/5)^2$ factor}:  The relative improvement depends on the relative standing of the University in the ranking.  A university lagging behind by 2 standards deviations gets a relative improvement 4,5 times higher than a university standing out by 2 standard deviations. However, due to the exponential nature of $y$ dependency on $\xi$, the absolute improvement is close to zero for universities with a low standing ($\xi \ll 0$) and large for the top tier ones ($\xi \gg 0$).
    \item \emph{$\delta_{ij}$ term:} University $i$ generally benefits from an increase of its own ratio $\Delta x_{i,k}$: the $\delta_{ij}$ (= 1 for $i = j$) term in the equation is the only one that is not in $1/N$ and thus dominates. However, if $|\xi_{i,k}| > \sqrt{N - 1} \approx 5$ standard deviations, University would lose from improving.  Nevertheless, the data of the Ministery from 2006 to 2020 can be used to show that the highest deviation any of the ratio has ever reached is 3.7.
    \item University $j$ may benefit from, or be harmed by, the improvement of University $i$.  There are two effects at play.
    \begin{enumerate}
    \item \emph{$1/N$ term}: The increase of the mean, would on its own hurt all other universities as their position relative to the mean $\xi_{j,k}$ would drop (see the $1/N$ term in the equation).
    \item \emph{$\xi_{i,j}\xi_{j,k}/N$ term}: However, the modification of the standard deviation works both ways. Intuitively, if a university with a high $\xi_{i,k} > 0$ ($x_{i,k} > \mu_k$) improves, it will increase the standard deviation, so that all universities deviate less from the mean: other universities with $\xi_{j,k} > 0$ will lose some of their good standing and lower tier ones with $\xi_{j,k} < 0$ will decrease their lag . Conversely, on can see that the improvement of a University with a lower rank $\xi_{j,k} < 0$, by decreasing the standard deviation of the sample when it goes closer to the mean, will help those with good standing to stand out more and harm other lower tier ones.
\end{enumerate}
    For both effects combined, University $j$ benefits if $\xi_{i,k}\xi_{j,k} < -1$ and is harmed otherwise.
\end{enumerate}

To determine the additional funding fraction $\Delta f_j$, let's propagate
\eqref{modif} into \eqsref{y}{f}:
\begin{equation}
    \frac{\Delta f_j}{f_j} = c_k \left[
                     \left(1 - \frac{y_{j}}y\right)\frac{\Delta y_{j,k}}{y_{j}}
                    - \sum_{l \ne j} \frac{y_l}y \frac{\Delta y_{l,k}}{y_l}
                 \right].
    \label{eq:deltafi}
\end{equation}
The first term in the square brackets has the same sign as $\Delta y_{j,k}$ because, by definition, $y_j < y$.  In most cases, the second term is smaller than the first one because the $\Delta y_{l,k}$ partially cancel out (some positives and some negatives) and $y_l < y$. It means that the funding received by a university that has an improved rating normally receives additional funding.  It is possible, though, that a university with a very small $\Delta y_{j,k}$ (e.g. $\xi_{j,k} < -2$) will be harmed by increasing its score, because the other, larger, $\Delta y_{l,k}$ coould lead to a second term larger than the first term under these circumstances. In years 2006--2021, it has happened exactly twice for Universidad de Aysén, who would have lost 14,000 and 1,000 pesos in 2020 and 2021, respectively, had it had one undergraduate student more in 2018 and 2019. It happens that the university had the two worst standard deviations observed for any metrics with $\xi_{\text{U. de Aysén},2} \approx -2.8$.

The previous determination is an approximation, valid for small values of $\Delta \xi$. To obtain the exact value, the calculations in \eqsref{x1}{afd} are done with the metrics provided by the Ministry (see Sect.~\ref{sec:metrics}) and for the same ones with additional students, professors with a postgraduate title, publications, or grants.  The difference is the marginal earning. This exact calculation is reported in Fig.~\ref{fig:marginal} (scale on the right axis).

\subsection{Historic (95\%) and total funding}

\subsubsection{Evolution of total funding}

The total funding in year $n$, $F_{n}$, is a slowly increasing series (see Fig.~\ref{fig:total-afd}). In half of the years it approximately follows the consumer price index, but it has received a modest boost in other years.  The average inflation-corrected increase has been $1.8$\% per year in period 2006--2021. This increases matches the increase in undergraduate students ($+2.8\%$ in 2004--2019), professors ($+2.6\%$ in 2005--2020), real wages ($+2.1\%$ in 2006--2021), and GDP per capita ($+1.6$\% in 2006--2021). Table~\ref{tab:macro} in Appendix~\ref{sec:macro} gives an overview of the main macroeconomic quantities in this period. Note that the pre-pandemic trends for macroeconomic data and AFD evolution were about 0.2\% higher.

Increase in standard of living and student population are long-term trends that I would expect to hold for at least the next decade, so I assume that University funding by the State will still follow this trend. For predictions, beyond 2021, I will therefore take
\begin{equation}
    F_{n+1} = (1+q) F_n, \label{eq:F}
\end{equation}
where $q = 2$\%.

\subsubsection{University funding (5\% and 95\%)}

Let $F_{i,n}$ be the funding received by university $i$ at year $n$. Art. 2 of
Decree with Force of Law 4 of 1980 indicates that 5\% of the funding is indexed
on metrics $y_{i,n,k}$ and 95\% of the funding is related to the previous year's
share of the total funding.  So,

\begin{align}
    F_{i,n+1} &= \frac{19F_{i,n}}{20F_{n}}\left(F_{n+1} - \Fnew_{n+1}\right)
               + \frac{y_{i,n}}{20y_n} F_{n+1}.
        \label{eq:afd}
\end{align}
where $F_{n+1}^\text{new}$ is the part of the 95\% apportionned to newly admitted traditional universities.  In the period 2006--2021, it has been nonzero in 2018 when State Universities of O'Higgins and Aysén where included (Decree 228 of 2017).

\subsubsection{Funding by metric}

\begin{figure*}[p]
\centering
\includegraphics{pdf/afd-specialisation.pdf}
\caption{Classification of traditional universities according to their teaching v. science specialisation and their established v. surging status. The two newly created institutions have not been included. \textit{Circles:} 2021 standing, area is proportional to the total AFD funding received in 2021. \textit{Gray tracks:} evolution of the universities through years 2014--2021. \textit{Horizontal axis:} research index, i.e. ratio of funding originating from the 2005--2020 science metrics (number of grants and papers) to the one from all 2005--2020 metrics. The vertical line indicates the median value. \textit{Vertical axis:} surging index, i.e. ratio of funding obtained from recent metrics to total funding minus its expected steady state value.  }
\label{fig:classification}
\end{figure*}

Funding received in virtue of a given metric in a given year still yields additional funding in the subsequent years since it propagates via the 95\%.

For an analysis of the strengths and weaknesses of each Universities, it is useful to determine what part of the total AFD funding originates from ``historic'' funding at year $n_0$ and which parts originate from each of the metrics computed for the funding of years $n_0 + 1$ to $n$. Let $H_{i,n}$ be the share of ``historic'' funding of university $i$ in year $n$ and $F_{i,n,k}$ that of the metric number $k$. They can be determined via the initial conditions and recurrence relations:
\begin{subequations}
\begin{align}
  H_{i, n_0}  &= F_{i, n_0},\\
  H_{i,n+1}   &= \frac{19H_{i,n}}{20F_n}   \left(F_{n+1}-\Fnew_{n+1}\right),
                    \label{eq:recH}\\
  F_{i,n_0,k} &= 0,\\
  F_{i,n+1,k} &= \frac{19F_{i,n,k}}{20F_n} \left(F_{n+1} - \Fnew_{n+1}\right)
                  + \frac{c_k y_{i,n,k}}{20y_n} F_{n+1}
                    \label{eq:recF}\\
              &\qquad\qquad \text{for $1 \le k \le 5$}. \notag
\end{align}
\end{subequations}
It is straighforward to check that $F_{i,n} = H_{i,n} + \sum_k F_{i,n,k}$ since the six recurrence equations (Eqs.~\ref{eq:recH}~\& \ref{eq:recF}) sum to Eq.~(\ref{eq:afd}).  The contribution of the pre-2006 funding and the 2005--2020 values of each metric to the total funding is given in the bottom panel of Fig.~\ref{fig:coeff}.

In steady state---ignoring the small non-zero values for $\Fnew$ in 2018---we expect that the historic to total funding ratio decreases by 5\% each year from a value of 1 in year $n_0$, i.e. $H_{i,n} / F_{i,n} = (19/20)^{n-n_0}$. I define the surging index as
\begin{equation}
    \mathcal{S}_{i,n} = \left(\frac{19}{20}\right)^{n-n_0}
                             - \frac{H_{i,n}}{F_{i, n}}.
\end{equation}
Surging universities, i.e. institutions that have improved their metrics faster than the average, feature a positive index $\mathcal{S} > 0$.  Established universities, with less room for improvement, will typically have $\mathcal{S} < 0$.

I also define the research index as the ratio of funding obtained for scientific activities (metrics 4 \& 5: number of grants and papers per staff) to the funding received for all metrics.
\begin{equation}
    \mathcal{R}_{i,n} = \frac {F_{i,n,4} + F_{i,n,5}}
                            {F_{i,n} - H_{i,n}}.
\end{equation}
A value of 1 would be achieved by institutions purely focused on research and a value of 0 by a university only dedicated to teaching.

Figure~\ref{fig:classification} shows the 2021 position of the traditional universities in the research-surging diagram as well as their evolution in the past years.

\subsubsection{Cumulated marginal earnings}

If University $i$ has an additional paper, an additional research grant, or an additional professor with a post-graduate title, in year $n - 1$, it will reflect in the 5\% funding of year $n$. Let us call $\Delta F_{i,n}$ the additional earnings  of the university in that year as determined by Sect.~\ref{sec:marginal}.  In the subsequent years, it will reflect via the 95\% (first term of the right handside of \eqref{afd}) in this way:
\begin{align}
   \Delta F_{i,n+k} &=  \frac{19}{20} \Delta F_{n+k-1}
                                \frac{F_{n+k}}{F_{n+k-1}}, \notag\\
                    &= \Delta F_{n+k-1}  \frac{ 19 (1 + q)} { 20}\notag,\\
                    &= \Delta F_{n} \left(\frac{ 19(1+q)} {20} \right) ^{k}.
\end{align}
In order to obtain the present value  corresponding to these future earnings, we take a yearly depreciation of $d = 5$\% in real terms (i.e. $\approx 8\%$ in pesos).
\begin{equation}
    \Delta F_{i,n+k}^\text{PV} = \Delta F_{n}
                \left(\frac{ 19(1+q)} {20(1+d)} \right) ^{k}
\end{equation}

The additional funding obtained by the university in all years is therefore
\begin{align}
    \Delta F_{i}^\text{PV}
         &= \sum_{k=0}^{+\infty} \Delta F_{i,n+k}, \notag \\
         &= \sum_{k=0}^{+\infty} \left(
                        \frac{19(1 + q)}{20(1 + d)}  \right)^k\Delta F_{i,n} \notag \\
                 &= \frac{20(1+d)}{1 + 20d - 19q} \Delta F_{i,n}, \\
                 &\approx 13 \Delta F_{i,n}. \notag
\end{align}

The cumulated marginal earnings for an additional student, professor with a postgraduate title, research grant, and Web of Science publication are given in Fig.~\ref{fig:marginal} (scale on the left axis).

\subsection{Checks}
\begin{figure}
\centering
\includegraphics[width=.85\linewidth]{pdf/transform.pdf}
\caption{Transformation of the metric $x_{i,n,k}$ into $y_{i,n,k}$, before a weighted sum
$\sum_k c_{i,n,k} y_{i,n,k}$ is performed to determine the rating of university $i$ in year $n$.}
\label{fig:transform}
\end{figure}

\paragraph{Yearly evaluation.} I have checked the calculations of the 5\% using open data from the Eduction Ministry for years 2006 to 2021. For each year since 2011 and 2007--2009, the percentages I
derived match within numerical rounding errors (8 digits) with those of the Ministry. The subsidies I predict for each university differ by at most CLP 1,000 ($\approx 1.20$~USD as of November 2021) with the official ones due to rounding errors, as the accounting unit used in the
official documents is 1,000 Chilean pesos. In 2010, the Ministry used the 2009
calculation with 2008 metrics, instead of 2009 ones, leading to large differences if the 2009 metrics given in the Ministry's spreadsheet are used.  Difference are zero within rounding errors using 2008 data instead. In 2006, there is an unexplained 0.01\% discrepancy between my determination and the Ministry's.  The official spreadsheet file from the ministry, with additional sheets showing my calculations, is available from github project \url{https://github.com/loqueelvientoajuarez/afd}.\footnote{The original ministry file can
be obtained from \url{http://dfi.mineduc.cl/usuarios/MECESUP/File/2021/AFD/AFD_2006_al_2021_MontosVariables5xc.xlsx}.}.

\paragraph{Marginal earnings.}  Marginal earnings have been determined by two methods.
\begin{enumerate}
\item using the differential calculus of Sect.~\ref{sec:marginal};
\item by doing the full calculation of Sect.~\ref{sec:metrics} for both the original metrics and the modified ones, then taking the difference between the two results.
\end{enumerate}
I have checked that both method agree within a few significant digits as long as the variations remain small.

\paragraph{Time-evolution.} I have checked the recurrence formula \eqref{afd} using the total amount given for each year $F_n$.  The 95\% funding is well predicted from year to year, except again for 2010, where I had to substitute 2008 funding percentages to the expected 2009 ones. Because of rounding errors cumulating from year to year, the amounts I predict differ by up to 5,000 pesos ($\approx 6$ USD as of November 2021) with those of the Ministry.

\paragraph{Cumulated marginal earnings.} \citet{RAM12} published an estimates for the present value of a scientific paper. I have tried to compare these findings but there are significant methodological discrepancies that do not allow more than an comparison of the orders of magnitude.  The aforementionned authors
\begin{enumerate}
\item only consider the first five years after the paper is published though their dampening law of $95\% / (1 + 8\%)$ still yields about 50\% of the inital sum at that point, meaning that they underestimate the total revenue obtained with a paper by a factor of $\approx 2$;
\item do not take into account that the total funding increases by IPC + 2\% $\approx 5$\% per year, so they further underestimate the present value of a paper by a factor of $\approx 1.5$;
\item seem to use different values for the coefficients than those published by the Ministry and actually used for the calculations. Their Fig.~4 doesn't match the corrected coefficients I derive for the years prior to their publications (2008--2011). Also, both my data and the Ministry's official figures for years 2006 to 2012 show a systematic discrepancy between U. de Chile and P. U. Católica de Chile between 31 and 60\% in the weighted sum of corrected coefficients and share of the 5\%, while their Figure shows a difference of only about 10\%.
\end{enumerate}

\appendix
\section{Appendix}

\subsection{Derivation of Equation~(\ref{eq:modif})}
\label{sec:calculus}
The variation in $\Delta y_{j,k}$ is linked to $\Delta \xi_{i,k}$ via the
derivative:
\begin{align}
    \Delta y_{j,k}
        &\approx \pder{y_{j,k}}{x_{i,k}}
                 \, \Delta x_{i,k},\\
        &\approx \der{y_{j,k}}{\xi_{i,k}}
                 \, \pder{\xi_{i,k}}{x_{i,k}}
                 \, \sigma_k \Delta \xi_{i,k},\\
\intertext{so, substituting \eqref{xi}, for the second factor}
        &\approx \der{y_{j,k}}{\xi_{i,k}}
                 \left[
                    \pder{x_{j,k}}{x_{i,k}}
                  - \pder{\mu_k}{x_{i,k}}
                  - \frac{x_{j,k}-\mu_k}{\sigma_k}\pder{\sigma_k}{x_{i,k}}
                 \right]
                 \, \Delta \xi_{i,k}\\
\intertext{and, backsubstituting \eqref{xi},}
        &\approx \der{y_{j,k}}{\xi_{i,k}}
                 \left[
                    \pder{x_{j,k}}{x_{i,k}}
                  - \pder{\mu_k}{x_{i,k}}
                  - \xi_{j,k} \pder{\sigma_k}{x_{i,k}}
                 \right]
                 \, \Delta \xi_{i,k}.
\end{align}

The first factor is the derivative of the function in the right handside of Eq.~(\ref{eq:transform}). It is:
\begin{equation}
    \der{y_{i,k}}{\xi_{i,k}} = \frac34 \left[ -\frac75 + \frac{\xi_{i,k}}4 \right] y_{i,k}.
\end{equation}

In the second factor, the first term is one if $i = j$, $x_{j,k}$ and $x_{i,k}$ being then the same variable, and zero otherwise.  The second term is the variation of the mean when one of the term varies, it is therefore $1/N$ the variation of the individual term. So,
\begin{align}
    \pder{x_{j,k}}{x_{i,k}} &= \delta_{ij}, \label{eq:derx}\\
    \pder{\mu_k}{x_{i,k}}   &= \frac 1N \sum_j \pder{x_{j,k}}{x_{i,k}}
                             = \frac 1N \sum_j \delta_{ij}
                             = \frac 1N. \label{eq:dermu}
\end{align}

The last term requires some more calculation. Let's use \eqref{sigma}:
\begin{align}
    \pder{\sigma_k}{x_{i,k}}
        &= \pder{}{x_{i,k}} \sqrt{\frac 1N \Big(\sum_j x_{j,n,k}^2\Big) - \mu_{n,k}^2},\\
        &= \frac 1{2\sigma_k} \pder{}{x_{i,k}}
            \left[
                \frac 1N \Big(\sum_j x_{j,k}^2\Big) - \mu_k^2
            \right],\\
        &= \frac 1{2\sigma_k}
            \left[
                \frac 2N \sum_k x_{j,k} \pder{x_{j,k}}{x_{i,k}}
                - 2 \mu_k \pder{\mu_k}{x_{i,k}}
            \right],\\
\intertext{so, using \eqref{derx} and \eqref{dermu},}
        &= \frac 1{2\sigma_k}
            \left[
                \frac {2\xi_{i,k}}{N} - \frac{2\mu_k}{N}
            \right]
\intertext{and, finally, with \eqref{xi},}
        &= \frac{\xi_{i,k}}N.
\end{align}

\subsection{Tabular material}
\label{sec:macro}

In this section we give the tabular material used to produce the graphics in the paper.

\paragraph{Macroeconomic and university data} (see Fig.~\ref{fig:total-afd}) Unidad de Fomento (UF, a  fiscal currency unit that follows the Chilean consumer price index with a one-month delay  with values from servicio de Impuestos Internos),  the GDP growth per capita (World Bank online database), the growth of the mean wage in real terms (Instituto Nacional de Estadística), the number of undergraduate students and full-time professors in traditional universities, and the total AFD funding to these universities. They are summed up in Table~\ref{tab:macro}.

\paragraph{Determination of the 5\%} (see Fig.~\ref{fig:coeff}, top panel) is detailed in Table~\ref{tab:calcdetail}.

\paragraph{Marginal earnings} (see Fig.~\ref{fig:marginal}) for an additional student, professor with a postgraduate title, research grant, and Web of Science publication are given in Table~\ref{tab:marginal} (2021 earnings and present value of all future earnings).

\begin{table*}[p]
\centering
\caption{Macroeconomic and university data for Chile: UF (price-indexed
fiscal currency unit), economic growth (GDP per capita), purchasing
power growth (real mean wage), number of students and professors in traditional universities, total AFD funding.}
\label{tab:macro}
\input tex/tab-macro.tex
\end{table*}

\begin{sidewaystable*}[p]
\centering
\caption{Calculation details for the 5\% AFD in year $n = 2021$ for university $i$: variables, intermediate calculations $\xi_{i,n,k}$ (standard deviations from mean) and $y_{i,n,k}$ (score) for metric number $k$, total score $y_{i, n}$, and share of funding. The total number of publications $P = \nisi + 0.33 \nscielo$  is used.}
\label{tab:calcdetail}
\setlength{\tabcolsep}{3pt}
\def\arraystretch{1.2}
\footnotesize
\input tex/tab-calcdetail.tex
\end{sidewaystable*}

\begin{table*}[p]
\centering
\caption{Additional earnings in million Chilean pesos for the marginal improvement of the following metrics: an additional undergraduate student, an additional one-year full-time contract of a professor with a postgraduate degree instead of a professor without it, an additional research grant, and an additional Web of Science (ex-ISI) publication with no collaborators from other Traditional Universities.  Assumptions for the all years funding is: State contribution continues to grow by 2\% a year real terms, a yearly depreciation of 5\% in real terms to future earnings is applied.}
\label{tab:marginal}
\setlength\tabcolsep{5pt}
\vskip 5pt
\input tex/tab-incentives.tex
\end{table*}

\section*{Bibliography}
\bibliographystyle{plainnat}
\bibliography{afd}

\end{document}

max_stars_repo_name: loqueelvientoajuarez/afd

max_issues_repo_name: loqueelvientoajuarez/afd

max_forks_repo_name: loqueelvientoajuarez/afd


text:
\documentclass[10pt]{article}

% \usepackage{ctex}
\usepackage{bookmark}
\usepackage{listings}
\usepackage{epsfig}
\usepackage{lscape}
\usepackage{multirow}
\usepackage{longtable}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{graphicx}
\usepackage{color}
\usepackage{placeins}
\usepackage{url}
\usepackage{cases}
\usepackage{hyperref}
\usepackage{setspace}
\usepackage{subfigure}
\usepackage{float}
\usepackage{framed}
\usepackage[c2]{optidef}
\usepackage{tikz}
\usepackage{caption}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{endnotes}
\usepackage{fontspec}
\usepackage{tikz}
\usepackage{amsbsy}

\usepackage{booktabs}

\oddsidemargin 0pt
\evensidemargin 0pt
\marginparwidth 10pt
\marginparsep 10pt
\topmargin -40pt
\textwidth 6.5in
\textheight 8.5in
\parindent = 20pt

\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\minimax}{minimax}

\renewcommand{\algorithmicrequire}{ \textbf{function:}}
\renewcommand{\algorithmicreturn}{ \textbf{end function}}
\newcommand{\blue}[1]{\begin{color}{blue}#1\end{color}}
\newcommand{\magenta}[1]{\begin{color}{magenta}#1\end{color}}
\newcommand{\red}[1]{\begin{color}{red}#1\end{color}}
\newcommand{\green}[1]{\begin{color}{green}#1\end{color}}

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{remark}{Remark}
\newtheorem{assumption}{Assumption}
\newtheorem{definition}{Definition}
%\newenvironment{proof}{{\noindent\it Proof}\quad}{\hfill $\square$\par}

%\usepackage{sidecap}

\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codemauve}{rgb}{0.58,0,0.82}

\lstset{ %
	language=python,                % choose the language of the code
	basicstyle=\footnotesize\ttfamily,       % the size of the fonts that are used for the code
	numbers=left,                   % where to put the line-numbers
	numberstyle=\tiny\color{codegray},      % the size of the fonts that are used for the line-numbers
	stepnumber=1,                   % the step between two line-numbers. If it is 1 each line will be numbered
	numbersep=5pt,                  % how far the line-numbers are from the code
	backgroundcolor=\color{white},  % choose the background color. You must add \usepackage{color}
	showspaces=false,               % show spaces adding particular underscores
	showstringspaces=false,         % underline spaces within strings
	showtabs=false,                 % show tabs within strings adding particular underscores
	frame=single,                   % adds a frame around the code
	tabsize=4,                      % sets default tabsize to 4 spaces
	captionpos=b,                   % sets the caption-position to bottom
	breaklines=true,                % sets automatic line breaking
	breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
	escapeinside={\%*}{*)},
	commentstyle=\color{codegreen},
	keywordstyle=\bfseries\color{magenta},
	stringstyle=\color{red},
	identifierstyle=\color{codemauve},
	keepspaces=true
}

\begin{document}

\title{\bf A Brief Proof to QuickSort Tail Recursion}

\author{Steven}
\date{}
\maketitle

\section{Original Algorithm}

In the classical QuickSort algorithm, we recursively apply the QuickSort to the sub-range
up to the point of division and to the sub-range after it util there is only one element
in the sub-range. So we call QuickSort function for $ 1+2+4+\cdots+n=2n-1 $ times.

\section{Tail Recursion Optimization}

Inspired by the tail recursion, we've got the optimized algorithm as follows.

\begin{lstlisting}[language=C++]
	void QuickSort(int *array, int p, int n) {
		while (n > 1) {
			int r = partition(array, p, n);
			QuickSort(array, p, r);
			*array += r + 1;
			n -= r - 1;
		}
	}
\end{lstlisting}

\begin{center}
	\begin{tikzpicture}[level/.style={sibling distance=45mm/#1}]
		\node [circle,draw] (z){$\boldsymbol{n}$}
		child {node [circle,draw] (a) {$\boldsymbol{\frac{n}{2}}$}
				child {node [circle,draw] (b) {$\boldsymbol{\frac{n}{2^2}}$}
						child {node {$\vdots$}
								child {node [circle,draw] (d) {$\boldsymbol{\frac{n}{2^k}}$}}
								child {node [circle,draw] (e) {$\frac{n}{2^k}$}}
							}
						child {node {$\vdots$}}
					}
				child {node [circle,draw] (g) {$\frac{n}{2^2}$}
						child {node {$\vdots$}}
						child {node {$\vdots$}}
					}
			}
		child {node [circle,draw] (j) {$\frac{n}{2}$}
				child {node [circle,draw] (k) {$\boldsymbol{\frac{n}{2^2}}$}
						child {node {$\vdots$}}
						child {node {$\vdots$}}
					}
				child {node [circle,draw] (l) {$\frac{n}{2^2}$}
						child {node {$\vdots$}}
						child {node (c){$\vdots$}
								child {node [circle,draw] (o) {$\boldsymbol{\frac{n}{2^k}}$}}
								child {node [circle,draw] (p) {$\frac{n}{2^k}$}
										child [grow=right] {node (q) {$=$} edge from parent[draw=none]
												child [grow=right] {node (q) {$\frac{n}{2}$} edge from parent[draw=none]
														child [grow=up] {node (r) {$\vdots$} edge from parent[draw=none]
																child [grow=up] {node (s) {$2$} edge from parent[draw=none]
																		child [grow=up] {node (t) {$1$} edge from parent[draw=none]
																				child [grow=up] {node (u) {$1$} edge from parent[draw=none]}
																			}
																	}
															}
														child [grow=down] {node (v) {$n$}edge from parent[draw=none]}
													}
											}
									}
							}
					}
			};
		\path (o) -- (e) node (x) [midway] {$\cdots$}
		child [grow=down] {
				node (y) {$\displaystyle1+\sum_{i = 0}^{k-1} 2^i$}
				edge from parent[draw=none]
			};
		\path (q) -- (r) node [midway] {+};
		\path (s) -- (r) node [midway] {+};
		\path (s) -- (t) node [midway] {+};
		\path (s) -- (l) node [midway] {=};
		\path (t) -- (u) node [midway] {+};
		\path (z) -- (u) node [midway] {=};
		\path (j) -- (t) node [midway] {=};
		\path (y) -- (x) node [midway] {$\Downarrow$};
		\path (q) -- (v) node [midway] {=};
		\path (e) -- (x) node [midway] {$\cdots$};
		\path (o) -- (x) node [midway] {$\cdots$};
		\path (r) -- (c) node [midway] {$\cdots$};
	\end{tikzpicture}
\end{center}

For each child node pair, only the left node will call QuickSort function, the other one's
function call in original algorithm is replaced by the update of *array and n. And take a
view of the bottom nodes, once we complete the calculation of the left node, the right one
will break the loop because $n\ngtr 1$, and return to their parent node immediately. And if
the parent node is also a right child node, it will complete function execution for the same
reason.

\end{document}

max_stars_repo_path: Homework/A Brief Proof to QuickSort Tail Recursion/A Brief Proof to QuickSort Tail Recursion.tex

max_stars_repo_name: Tequila-Sunrise/FDU-Parallel-Computing

max_issues_repo_name: Tequila-Sunrise/FDU-Parallel-Computing

max_forks_repo_name: Tequila-Sunrise/FDU-Parallel-Computing


text:
\chapter{Conclusion}

The pursuit of making server infrastructure more dynamic, efficient, and cost-effective has led to the evolution of virtualization technologies in multiple dimensions. As a result of this evolution, we now have a diverse set of virtualization platforms to choose from, each prioritizing a different subset of the overall virtualization goals. There is a clear need to analyze and understand the focus of each of these platforms, and to evaluate the platform choices based on factors beyond the set of standard benchmarks. We chose KVM, Xen, and Linux Containers to represent full-virtualization, para-virtualization, and container-based virtualization, respectively. We evaluated the platforms based on (i) the overhead they impose to virtualize CPU, memory, network access, and disk access; (ii) their performance on workload-specific benchmarks; (iii) their performance in virtualizing the Intelligent River\textsuperscript{\textregistered} middleware components; (iv) the flexibility each offers in performing common operational tasks; and (v) the isolation they provide for applications.

Through a detailed experimental analysis, we found that Linux Containers exhibit the least overhead in virtualizing CPU and disk access, whereas KVM exhibits the least overhead with respect to memory. Xen was found to exhibit significant overhead when used to virtualize multi-threaded aplications. KVM, in its current form, exhibits significant overhead in virtualizing disk access; however, we note that the problem is being addressed with major design changes slated for release in the near future. From an operational standpoint, Linux Containers provide a significant advantage by performing the common tasks of provisioning, booting, and rebooting a virtual machine several times faster than both KVM and Xen. Although Linux Containers fare well on most of our evaluation criteria, they come with the downside of providing poor isolation among the containers. Xen was found to offer superior isolation among the virtual machines.

There is no single \emph{best} virtualization platform. Based on our results, we conclude that Linux Containers are preferred to virtualize infrastructure that is dynamic by design, and does not require a high degree of resource isolation. It is important to note, however, that Linux Containers cannot be used in situations where the applications need kernel-level customization. For infrastructure that demands superior resource isolation, KVM is preferred over Xen, if most of the applications are memory intensive; whereas Xen is preferred over KVM if the applications involve significant disk access.