Look at the latex template given below.
1) Edit the file in an emacs buffer (or whatever your favorite editor is--
you can use your favorite wordprocessor on OSX if you make sure to save it
as a plain text file with no extra formatting characters)
2) When you are done, type
pdflatex filename.tex
3) This will produce a file called filename.pdf which is an ordinary
pdf file that can be printed or viewed.
4) Once you have a draft of the notes, please EMAIL ME the plain .tex
file. I will insert my comments/suggested changes directly in the
document with %%%% (the latex comment character) and email it
back to you for revisions. After 1-2 iterations, we will have classnotes.
Here is the template. It starts with a bunch of wierd stuff
that basically creates the header. Then you just type text.
You get a new paragraph by skipping a line. Formatting commands
start with a \ as in \begin{center} \end{center}
For equations, math mode begins and ends with a $ as in
$a \in S$ produces a "is an element symbol" S.
For a complete list of symbols, etc. type latex tutorial or latex manual
into google and you will get the full symbol table.
One final note: the goal of this exercise is not for you to convince me
you can produce beautiful latex documents, it's to come up with a great
set of class notes for everyone. If there's something you want to do and
can't figure out how to format, don't waste your time, just ask me by email.
I'm a latex expert. We are going to go through several iterations anyway,
as we improve the text and the presentation of the notes.
Best, Lenore
(template follows)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% -*- LaTeX -*- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Template for scribing Advanced Algorithms
%
% Spring, 2016
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%**start of header
\documentclass[12pt]{article}
\usepackage{epsfig}
\newtheorem{theorem}{Theorem}[subsection]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proof}[theorem]{Proof} %XXX hack
\newlength{\toppush}
\setlength{\toppush}{2\headheight}
\addtolength{\toppush}{\headsep}
%\doheading{2}{title}{Last Revised: September, 1990}
%\htitle{title}
\def\subjnum{Comp 260}
\def\subjname{Advanced Algorithms}
\def\doheading#1#2#3{\vfill\eject\vspace*{-\toppush}%
\vbox{\hbox to\textwidth{{\bf} \subjnum: \subjname \hfil Prof. Lenore Cowen}%
\hbox to\textwidth{{\bf} Tufts University, Fall 2021 \hfil#3\strut}%
\hrule}}
\newcommand{\htitle}[1]{\vspace*{3.25ex plus 1ex minus .2ex}%
\begin{center}
{\large\bf #1}
\end{center}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\doheading{2}{title}{Scribe: Your Name Here}
\htitle{Lecture 3: Lecture Title}
\bigskip
\bigskip
\setlength{\parskip}{0.125in}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% START TYPING BELOW THIS LINE (THE TEXT THAT IS HERE NOW IS %
% FROM LECTURE 1 OF LAST TIME THE COURSE WAS TAUGHT) %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Arthur-Merlin Story}
In the land ruled by the legendary King Arthur, there existed one
hundred knights and one hundred ladies. King Arthur proclaimed that
all knights and ladies should get married. He soon asked each of the
knights to write down a list of which of the ladies they would be
willing to wed, and then hand him their preferences.
King Arthur took all of the knights preferences and went back to his
castle. He called for his magician, the legendary Merlin, who had
access to all the elves, faries, and other mystical creatures. Arthur
ordered Merlin to find an marriage so that there would be a perfect
matching of the one hundred knights to the one hundred ladies so that
each knight is matched to a lady he finds acceptable. Soon enough by
way of magic, Merlin obtained a result and handed the list of
acceptable marriages to Arthur. However, Arthur wanted to check over
Merlin's work and to make sure that each knight was married off acceptably. But
how much time is required for Arthur to check each of the knight's
list and match them with Merlin's list? The following is Arthur's
algorithm to check if Merlin's list is legitimate:
Arthur's Algorithm
\begin{itemize}
\item Looks at each list
\item Checks if lady that Merlin matches knight is on knight's list
\end{itemize}
That works great if there is a marriage. But what if there isn't?
Soon enough, Merlin stormed to Arthur and told him ``Wait, it's
impossible. It'll never work. The problem is that no matter what I
do, some knights will always be left out.'' Arthur was dumbfound and
told Merlin: ``How is that possible. You need to find a way to marry
every one off else you'll lose your head.''
\subsection{The NP Decision Question}
The decision question presented in the Arthur-Merlin story is: ``Given
a bipartite graph with $n$ knights and $n$ ladies does there exist a
perfect marriage?''
Now let's go back to Arthur and his algorithm to check if that each
knight is married off correctly according to Merlin's results and the
preferences of each knight. Arthur is willing to sit through a
polynomial time algorithm of $O(n^c)$ where $c$ is a constant.
\begin{definition}
{\bf NP} is the set of decision problems for which Merlin can present
a proof when, the answer is yes, that Arthur can verify in polynomial
time.
\end{definition}
\begin{definition}
{\bf Co-NP} is the set of problems for which Merlin can present a
proof of a no answer to Arthur.
\end{definition}
\begin{definition}
{\bf P} is the set of problems Arthur can do without Merlin.
\end{definition}
\begin{definition}
A problem $X$ is {\bf NP-Hard} if $X \in P \Rightarrow P=NP$.
\end{definition}
So NP-hard problems are the ones we can think are hard for Arthur.
\begin{definition}
A problem $X$ is {\bf NP-Complete} if $X \in NP$ and $X$ is NP-Hard.
\end{definition}
So NP-complete problems are the ones we think are hard for Arthur
without Merlin's help, but easy with Merlin's help.
We do know as a fact that $P \subseteq NP$ (anything Arthur can check
on his own, he can check with Merlin's help). The infamous P-NP
problem is: ``Does or does not P=NP?'' We suspect that $P \ne NP$
but we cannot prove it.
\subsection{Saving Merlin's Head}
Merlin's head will be saved if he can prove to Arthur that there is no
perfect matching, i.e., if perfect matching is in co-NP. In this
section, we will use the terms ``perfect matching'' and ``perfect
marriage'' interchangeably.
\begin{definition}
For any set $S$ of vertices in $G$, the \textbf{neighbor set} of $G$
is all vertices adjacent to vertices in $S$, written $N_G(S)$.
\end{definition}
\begin{definition}
A vertex is called \textbf{saturated} if it is matched and
\textbf{unsaturated} otherwise.
\end{definition}
\begin{theorem}[Hall's Theorem]
Let $G$ be a bipartite graph with bipartition $(X, Y)$. Then $G$
contains a matching that saturates all the vertices of X if and only
if $|N(S)| \geq |S|$ for all $S \subseteq X$.
\end{theorem}
\noindent
{\bf Proof.} On direction is obvious. Clearly if there is a set of
$k$ knights who only like $k$-1 ladies between them, there can be no
marriage. What is less obvious is the second half of Hall's theorem,
which says if $G$ contains no perfect matching, then there must exist
a set $S$ such that $|S| \le |N(S)|$. We prove this now by
contradiction.
Suppose $G$ is a bipartite graph such that $|N(S)| \geq |S|$ for all
$S$, but $G$ contains no matching saturating all the vertices in
$X$. Let $M*$ be a maximum matching in $G$. $M*$ isn't perfect, so there
exists some $\mu \in X$ that isn't matched.
Consider the set of {\em alternating paths} that originates from $\mu$
where alternating paths are paths of edges in $G$ that alternates
between unmatched and matched (in $M*$) edges. Let $S$ be the set of
all vertices in $X$ (including $\mu$) reached by any one of these
paths and $T$ be the set of all such vertices in $Y$.
\begin{claim}
$M*$ matches $T$ perfectly with $S-\mu$.
\end{claim}
\noindent
{\bf Proof.}
First observe that these alternating paths reach $Y$ along edges not in
$M*$ and reach $\mu$ along the edges in $M$. In other words, every vertex of
$S-\mu$ is reached along an edge in $M*$ from a vertex in $T$ such that $S-\mu$ is
all matched. But, is $T$ all matched? Suppose not, i.e. there is some
unsaturated vertex in $T$. But then we could have swapped along the alternating path
and created a new matching $M$ with one more edge than $M*$. This proves the claim.
This claim implies that $|T| = |S-\mu|$. We also know that $T = N(S)$ by definition, so $|N(S)| = |T| = |S-\mu| \le |S|$ and we have found our bad set S. QED.
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%