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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%