Commits

Anonymous committed 620d3f2

*** empty log message ***

  • Participants
  • Parent commits 90e8502

Comments (0)

Files changed (14)

 latex-beamer-3.06/AUTHORS
-latex-beamer-3.06/ChangeLog
-latex-beamer-3.06/FILES
-latex-beamer-3.06/INSTALL
-latex-beamer-3.06/README
-latex-beamer-3.06/TODO
 latex-beamer-3.06/base/art/beamericonarticle.20.eps
 latex-beamer-3.06/base/art/beamericonarticle.20.pdf
 latex-beamer-3.06/base/art/beamericonarticle.eps
 latex-beamer-3.06/base/beamerbasenotes.sty
 latex-beamer-3.06/base/beamerbaseoptions.sty
 latex-beamer-3.06/base/beamerbaseoverlay.sty
+latex-beamer-3.06/base/beamerbasercs.sty
 latex-beamer-3.06/base/beamerbasesection.sty
-latex-beamer-3.06/base/beamerbasercs.sty
 latex-beamer-3.06/base/beamerbasetemplates.sty
 latex-beamer-3.06/base/beamerbasethemes.sty
 latex-beamer-3.06/base/beamerbasetheorems.sty
 latex-beamer-3.06/base/beamerbasetoc.sty
 latex-beamer-3.06/base/beamerbasetwoscreens.sty
 latex-beamer-3.06/base/beamerbaseverbatim.sty
+latex-beamer-3.06/ChangeLog
 latex-beamer-3.06/doc/beamercolorthemeexample.tex
 latex-beamer-3.06/doc/beamerfontthemeexample.tex
 latex-beamer-3.06/doc/beamerinnerthemeexample.tex
 latex-beamer-3.06/doc/beamerug-workflow.tex
 latex-beamer-3.06/doc/beameruserguide.pdf
 latex-beamer-3.06/doc/beameruserguide.tex
-latex-beamer-3.06/doc/Makefile
 latex-beamer-3.06/doc/licenses/gnu-free-documentation-license-1.2.txt
 latex-beamer-3.06/doc/licenses/gnu-public-license-2.txt
 latex-beamer-3.06/doc/licenses/latex-project-public-license-1.3c.txt
+latex-beamer-3.06/doc/licenses/LICENSE
+latex-beamer-3.06/doc/licenses/manifest-code.txt
 latex-beamer-3.06/doc/licenses/manifest-documentation.txt
-latex-beamer-3.06/doc/licenses/manifest-code.txt
-latex-beamer-3.06/doc/licenses/LICENSE
+latex-beamer-3.06/doc/Makefile
 latex-beamer-3.06/emulation/beamerfoils.sty
 latex-beamer-3.06/emulation/beamerprosper.sty
 latex-beamer-3.06/emulation/beamerseminar.sty
 latex-beamer-3.06/emulation/examples/beamerexample-prosper.tex
 latex-beamer-3.06/emulation/examples/beamerexample-seminar.tex
 latex-beamer-3.06/emulation/examples/beamerexample-texpower.tex
+latex-beamer-3.06/examples/a-conference-talk/beamerexample-conference-talk.pdf
 latex-beamer-3.06/examples/a-conference-talk/beamerexample-conference-talk.tex
+latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-beamer-version.pdf
 latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-beamer-version.tex
 latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-beamer-version.tex~
 latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-body.tex
-latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-print-version.tex
-latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-style.tex
+latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-logo.pdf
 latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-pic1.jpg
 latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-pic2.jpg
 latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-pic3.jpg
 latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-pic4.jpg
 latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-pic5.jpg
 latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-pic6.jpg
-latex-beamer-3.06/examples/a-conference-talk/beamerexample-conference-talk.pdf
-latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-beamer-version.pdf
-latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-logo.pdf
 latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-print-version.pdf
+latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-print-version.tex
+latex-beamer-3.06/examples/a-lecture/beamerexample-lecture-style.tex
+latex-beamer-3.06/examples/lyx-based-presentation/beamerexample-lyx.lyx
 latex-beamer-3.06/extensions/multimedia/multimedia.sty
 latex-beamer-3.06/extensions/multimedia/multimediasymbols.sty
 latex-beamer-3.06/extensions/multimedia/xmpmulti.sty
+latex-beamer-3.06/FILES
+latex-beamer-3.06/INSTALL
+latex-beamer-3.06/README
+latex-beamer-3.06/solutions/conference-talks/conference-ornate-20min.de.lyx
 latex-beamer-3.06/solutions/conference-talks/conference-ornate-20min.de.tex
-latex-beamer-3.06/solutions/conference-talks/conference-ornate-20min.de.lyx
+latex-beamer-3.06/solutions/conference-talks/conference-ornate-20min.en.lyx
 latex-beamer-3.06/solutions/conference-talks/conference-ornate-20min.en.tex
-latex-beamer-3.06/solutions/conference-talks/conference-ornate-20min.en.lyx
 latex-beamer-3.06/solutions/conference-talks/conference-ornate-20min.fr.tex
 latex-beamer-3.06/solutions/generic-talks/generic-ornate-15min-45min.de.lyx
 latex-beamer-3.06/solutions/generic-talks/generic-ornate-15min-45min.de.tex
 latex-beamer-3.06/solutions/generic-talks/generic-ornate-15min-45min.en.lyx
 latex-beamer-3.06/solutions/generic-talks/generic-ornate-15min-45min.en.tex
 latex-beamer-3.06/solutions/generic-talks/generic-ornate-15min-45min.fr.tex
+latex-beamer-3.06/solutions/short-talks/speaker_introduction-ornate-2min.de.lyx
 latex-beamer-3.06/solutions/short-talks/speaker_introduction-ornate-2min.de.tex
-latex-beamer-3.06/solutions/short-talks/speaker_introduction-ornate-2min.de.lyx
+latex-beamer-3.06/solutions/short-talks/speaker_introduction-ornate-2min.en.lyx
 latex-beamer-3.06/solutions/short-talks/speaker_introduction-ornate-2min.en.tex
-latex-beamer-3.06/solutions/short-talks/speaker_introduction-ornate-2min.en.lyx
 latex-beamer-3.06/solutions/short-talks/speaker_introduction-ornate-2min.fr.tex
 latex-beamer-3.06/themes/color/beamercolorthemealbatross.sty
+latex-beamer-3.06/themes/color/beamercolorthemebeaver.sty
 latex-beamer-3.06/themes/color/beamercolorthemebeetle.sty
-latex-beamer-3.06/themes/color/beamercolorthemebeaver.sty
 latex-beamer-3.06/themes/color/beamercolorthemecrane.sty
 latex-beamer-3.06/themes/color/beamercolorthemedefault.sty
 latex-beamer-3.06/themes/color/beamercolorthemedolphin.sty
 latex-beamer-3.06/themes/outer/beamerouterthemesmoothtree.sty
 latex-beamer-3.06/themes/outer/beamerouterthemesplit.sty
 latex-beamer-3.06/themes/outer/beamerouterthemetree.sty
+latex-beamer-3.06/themes/theme/beamerthemeAnnArbor.sty
 latex-beamer-3.06/themes/theme/beamerthemeAntibes.sty
-latex-beamer-3.06/themes/theme/beamerthemeAnnArbor.sty
+latex-beamer-3.06/themes/theme/beamerthemeBergen.sty
 latex-beamer-3.06/themes/theme/beamerthemeBerkeley.sty
 latex-beamer-3.06/themes/theme/beamerthemeBerlin.sty
-latex-beamer-3.06/themes/theme/beamerthemeBergen.sty
 latex-beamer-3.06/themes/theme/beamerthemeBoadilla.sty
+latex-beamer-3.06/themes/theme/beamerthemeboxes.sty
 latex-beamer-3.06/themes/theme/beamerthemeCambridgeUS.sty
 latex-beamer-3.06/themes/theme/beamerthemeCopenhagen.sty
 latex-beamer-3.06/themes/theme/beamerthemeDarmstadt.sty
+latex-beamer-3.06/themes/theme/beamerthemedefault.sty
 latex-beamer-3.06/themes/theme/beamerthemeDresden.sty
 latex-beamer-3.06/themes/theme/beamerthemeFrankfurt.sty
 latex-beamer-3.06/themes/theme/beamerthemeGoettingen.sty
 latex-beamer-3.06/themes/theme/beamerthemeSingapore.sty
 latex-beamer-3.06/themes/theme/beamerthemeSzeged.sty
 latex-beamer-3.06/themes/theme/beamerthemeWarsaw.sty
-latex-beamer-3.06/themes/theme/beamerthemeboxes.sty
-latex-beamer-3.06/themes/theme/beamerthemedefault.sty
 latex-beamer-3.06/themes/theme/compatibility/beamerthemebars.sty
 latex-beamer-3.06/themes/theme/compatibility/beamerthemeclassic.sty
 latex-beamer-3.06/themes/theme/compatibility/beamerthemecompatibility.sty
 latex-beamer-3.06/themes/theme/compatibility/beamerthemesidebar.sty
 latex-beamer-3.06/themes/theme/compatibility/beamerthemesplit.sty
 latex-beamer-3.06/themes/theme/compatibility/beamerthemetree.sty
+latex-beamer-3.06/TODO

File examples/beamerexample4.pdf

Binary file removed.

File examples/lyx-based-presentation/beamerexample-lyx.lyx

+#LyX 1.3 created this file. For more info see http://www.lyx.org/
+\lyxformat 221
+\textclass beamer
+\begin_preamble
+\beamertemplateshadingbackground{red!5}{structure!5}
+
+\usepackage{beamerthemeshadow}
+\usepackage{pgfnodes,pgfarrows,pgfheaps}
+
+\beamertemplatetransparentcovereddynamicmedium
+
+
+\pgfdeclareimage[width=0.6cm]{icsi-logo}{beamer-icsi-logo}
+\logo{\pgfuseimage{icsi-logo}}
+
+
+
+
+\newcommand{\Class}[1]{\operatorname{\mathchoice
+  {\text{\small #1}}
+  {\text{\small #1}}
+  {\text{#1}}
+  {\text{#1}}}}
+
+\newcommand{\Lang}[1]{\operatorname{\text{\textsc{#1}}}}
+
+\newcommand{\tape}[3]{%
+  \color{structure!30!averagebackgroundcolor}
+  \pgfmoveto{\pgfxy(-0.5,0)}
+  \pgflineto{\pgfxy(-0.6,0.1)}
+  \pgflineto{\pgfxy(-0.4,0.2)}
+  \pgflineto{\pgfxy(-0.6,0.3)}
+  \pgflineto{\pgfxy(-0.4,0.4)}
+  \pgflineto{\pgfxy(-0.5,0.5)}
+  \pgflineto{\pgfxy(4,0.5)}
+  \pgflineto{\pgfxy(4.1,0.4)}
+  \pgflineto{\pgfxy(3.9,0.3)}
+  \pgflineto{\pgfxy(4.1,0.2)}
+  \pgflineto{\pgfxy(3.9,0.1)}
+  \pgflineto{\pgfxy(4,0)}
+  \pgfclosepath
+  \pgffill
+
+  \color{structure}  
+  \pgfputat{\pgfxy(0,0.7)}{\pgfbox[left,base]{#1}}
+  \pgfputat{\pgfxy(0,-0.1)}{\pgfbox[left,top]{#2}}
+
+  \color{black}
+  \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
+}
+
+\newcommand{\shorttape}[3]{%
+  \color{structure!30!averagebackgroundcolor}
+  \pgfmoveto{\pgfxy(-0.5,0)}
+  \pgflineto{\pgfxy(-0.6,0.1)}
+  \pgflineto{\pgfxy(-0.4,0.2)}
+  \pgflineto{\pgfxy(-0.6,0.3)}
+  \pgflineto{\pgfxy(-0.4,0.4)}
+  \pgflineto{\pgfxy(-0.5,0.5)}
+  \pgflineto{\pgfxy(1,0.5)}
+  \pgflineto{\pgfxy(1.1,0.4)}
+  \pgflineto{\pgfxy(0.9,0.3)}
+  \pgflineto{\pgfxy(1.1,0.2)}
+  \pgflineto{\pgfxy(0.9,0.1)}
+  \pgflineto{\pgfxy(1,0)}
+  \pgfclosepath
+  \pgffill
+
+  \color{structure}  
+  \pgfputat{\pgfxy(0.25,0.7)}{\pgfbox[center,base]{#1}}
+  \pgfputat{\pgfxy(0.25,-0.1)}{\pgfbox[center,top]{#2}}
+
+  \color{black}
+  \pgfputat{\pgfxy(-.1,0.25)}{\pgfbox[left,center]{\texttt{#3}}}%
+}
+
+\pgfdeclareverticalshading{heap1}{\the\paperwidth}%
+  {color(0pt)=(black); color(1cm)=(structure!65!white)}
+\pgfdeclareverticalshading{heap2}{\the\paperwidth}%
+  {color(0pt)=(black); color(1cm)=(structure!55!white)}
+\pgfdeclareverticalshading{heap3}{\the\paperwidth}%
+  {color(0pt)=(black); color(1cm)=(structure!45!white)}
+\pgfdeclareverticalshading{heap4}{\the\paperwidth}%
+  {color(0pt)=(black); color(1cm)=(structure!35!white)}
+\pgfdeclareverticalshading{heap5}{\the\paperwidth}%
+  {color(0pt)=(black); color(1cm)=(structure!25!white)}
+\pgfdeclareverticalshading{heap6}{\the\paperwidth}%
+  {color(0pt)=(black); color(1cm)=(red!35!white)}
+
+\newcommand{\heap}[5]{%
+  \begin{pgfscope}
+    \color{#4}
+    \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
+    \pgfclip
+    \begin{pgfmagnify}{1}{#1}
+      \pgfputat{\pgfpoint{-.5\paperwidth}{0pt}}{\pgfbox[left,base]{\pgfuseshading{heap#5}}}
+    \end{pgfmagnify}
+  \end{pgfscope}
+  %\pgffill
+  
+  \color{#4}
+  \pgfheappath{\pgfxy(0,#1)}{\pgfxy(-#2,0)}{\pgfxy(#2,0)}
+  \pgfstroke
+
+  \color{white}
+  \pgfheaplabel{\pgfxy(0,#1)}{#3}%
+}
+
+
+\newcommand{\langat}[2]{%
+  \color{black!30!beamerexample}
+  \pgfsetlinewidth{0.6pt}
+  \pgfsetendarrow{\pgfarrowdot}
+  \pgfline{\pgfxy(-3.5,#1)}{\pgfxy(0.05,#1)}
+  \color{beamerexample}
+  \pgfputat{\pgfxy(-3.6,#1)}{\pgfbox[right,center]{#2}}%
+}
+
+\newcommand{\langatother}[2]{%
+  \color{black!30!beamerexample}
+  \pgfsetlinewidth{0.6pt}
+  \pgfsetendarrow{\pgfarrowdot}
+  \pgfline{\pgfxy(3.5,#1)}{\pgfxy(-0.05,#1)}
+  \color{beamerexample}
+  \pgfputat{\pgfxy(3.6,#1)}{\pgfbox[left,center]{#2}}%
+}
+
+
+\pgfdeclaremask{knight1-mask}{beamer-knight1-mask} \pgfdeclareimage[height=2cm,mask=knight1-mask]{knight1}{beamer-knight1} \pgfdeclaremask{knight2-mask}{beamer-knight2-mask} \pgfdeclareimage[height=2cm,mask=knight2-mask]{knight2}{beamer-knight2} \pgfdeclaremask{knight3-mask}{beamer-knight3-mask} \pgfdeclareimage[height=2cm,mask=knight3-mask,interpolate=true]{knight3}{beamer-knight3} \pgfdeclaremask{knight4-mask}{beamer-knight4-mask} \pgfdeclareimage[height=2cm,mask=knight4-mask,interpolate=true]{knight4}{beamer-knight4}
+
+
+\pgfdeclareradialshading{graphnode}
+  {\pgfpoint{-3pt}{3.6pt}}%
+  {color(0cm)=(beamerexample!15);
+    color(2.63pt)=(beamerexample!75);
+    color(5.26pt)=(beamerexample!70!black);
+    color(7.6pt)=(beamerexample!50!black);
+    color(8pt)=(beamerexample!10!averagebackgroundcolor)}
+
+\newcommand{\graphnode}[2]{
+  \pgfnodecircle{#1}[virtual]{#2}{8pt}
+  \pgfputat{#2}{\pgfbox[center,center]{\pgfuseshading{graphnode}}}
+}
+\end_preamble
+\options notes=show
+\language english
+\inputencoding auto
+\fontscheme times
+\graphics default
+\paperfontsize default
+\spacing single 
+\papersize Default
+\paperpackage a4
+\use_geometry 0
+\use_amsmath 1
+\use_natbib 0
+\use_numerical_citations 0
+\paperorientation portrait
+\secnumdepth 2
+\tocdepth 2
+\paragraph_separation indent
+\defskip medskip
+\quotes_language english
+\quotes_times 2
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+
+\layout Title
+
+The Complexity of
+\newline 
+Finding Paths in Tournaments
+\layout Author
+
+Till Tantau
+\layout Institute
+
+International Computer Schience Institute
+\newline 
+Berkeley, California
+\begin_inset OptArg
+collapsed true
+
+\layout Standard
+
+ICSI
+\end_inset 
+
+
+\layout Date
+
+January 30th, 2004
+\layout BeginFrame
+
+Outline
+\layout Standard
+
+
+\begin_inset LatexCommand \tableofcontents{}
+
+\end_inset 
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+[pausesections]
+\end_inset 
+
+
+\layout EndFrame
+
+\layout Standard
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+% Show the table of contents at the beginning
+\layout Standard
+% of every subsection.
+\layout Standard
+
+\backslash 
+AtBeginSubsection[]{
+\layout Standard
+  
+\backslash 
+frame<handout:0>{ 
+\layout Standard
+    
+\backslash 
+frametitle{Outline}   
+\layout Standard
+    
+\backslash 
+tableofcontents[current,currentsubsection] 
+\layout Standard
+  }
+\layout Standard
+}
+\end_inset 
+
+
+\layout Section
+
+Introduction
+\layout Subsection
+
+What are Tournaments?
+\layout BeginFrame
+
+Tournaments Consist of Jousts Between Knights
+\layout Columns
+
+\begin_deeper 
+\layout Column
+
+5.75cm
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash 
+begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm}      
+\layout Standard
+  
+\backslash 
+pgfnodebox{A}[virtual]{
+\backslash 
+pgfxy(2,1)}{
+\backslash 
+pgfuseimage{knight1}}{2pt}{2pt}
+\layout Standard
+  
+\backslash 
+pgfnodebox{B}[virtual]{
+\backslash 
+pgfxy(6,1)}{
+\backslash 
+pgfuseimage{knight2}}{2pt}{2pt}
+\layout Standard
+  
+\backslash 
+pgfnodebox{C}[virtual]{
+\backslash 
+pgfxy(4,-1)}{
+\backslash 
+pgfuseimage{knight3}}{2pt}{2pt}
+\layout Standard
+  
+\backslash 
+pgfnodebox{D}[virtual]{
+\backslash 
+pgfxy(4,3)}{
+\backslash 
+pgfuseimage{knight4}}{2pt}{2pt}
+\layout Standard
+
+\layout Standard
+  
+\backslash 
+color{beamerexample}
+\layout Standard
+  
+\backslash 
+only<3->{
+\backslash 
+pgfsetendarrow{
+\backslash 
+pgfarrowto}}
+\layout Standard
+  
+\backslash 
+only<2->{
+\layout Standard
+    
+\backslash 
+pgfsetlinewidth{0.6pt}
+\layout Standard
+    
+\backslash 
+pgfnodeconnline{A}{B}
+\layout Standard
+    
+\backslash 
+pgfnodeconnline{A}{C}
+\layout Standard
+    
+\backslash 
+pgfnodeconnline{D}{A}
+\layout Standard
+    
+\backslash 
+pgfnodeconnline{C}{B}
+\layout Standard
+    
+\backslash 
+pgfnodeconnline{B}{D}
+\layout Standard
+    
+\backslash 
+pgfnodeconnline{C}{D}}
+\layout Standard
+
+\backslash 
+end{pgfpicture} 
+\end_inset 
+
+
+\layout Column
+
+6cm
+\layout Block
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{What is a Tournament?}
+\end_inset 
+
+
+\begin_deeper 
+\layout Itemize
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<1->
+\end_inset 
+
+A group of knights.
+\layout Itemize
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<2->
+\end_inset 
+
+Every pair has a joust.
+\layout Itemize
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<3->
+\end_inset 
+
+In every joust one knight wins.
+\end_deeper 
+\end_deeper 
+\layout BeginFrame
+
+Tournaments are Complete Directed Graphs
+\layout Columns
+
+\begin_deeper 
+\layout Column
+
+5cm
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash 
+begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm}
+\layout Standard
+  
+\backslash 
+color{beamerexample}
+\layout Standard
+  
+\backslash 
+pgfsetlinewidth{0.6pt}
+\layout Standard
+  
+\backslash 
+graphnode{A}{
+\backslash 
+pgfxy(2.5,1)}
+\layout Standard
+  
+\backslash 
+graphnode{B}{
+\backslash 
+pgfxy(5.5,1)}
+\layout Standard
+  
+\backslash 
+graphnode{C}{
+\backslash 
+pgfxy(4,-0.5)}
+\layout Standard
+  
+\backslash 
+graphnode{D}{
+\backslash 
+pgfxy(4,2.5)}
+\layout Standard
+
+\layout Standard
+  
+\backslash 
+color{white}
+\layout Standard
+  
+\backslash 
+pgfputat{
+\backslash 
+pgfnodecenter{A}}{
+\backslash 
+pgfbox[center,center]{$v_2$}}
+\layout Standard
+  
+\backslash 
+pgfputat{
+\backslash 
+pgfnodecenter{B}}{
+\backslash 
+pgfbox[center,center]{$v_3$}}
+\layout Standard
+  
+\backslash 
+pgfputat{
+\backslash 
+pgfnodecenter{C}}{
+\backslash 
+pgfbox[center,center]{$v_4$}}
+\layout Standard
+  
+\backslash 
+pgfputat{
+\backslash 
+pgfnodecenter{D}}{
+\backslash 
+pgfbox[center,center]{$v_1$}}
+\layout Standard
+
+\layout Standard
+  
+\backslash 
+color{beamerexample}
+\layout Standard
+  
+\backslash 
+pgfsetendarrow{
+\backslash 
+pgfarrowto}
+\layout Standard
+  
+\backslash 
+pgfnodesetsepstart{2pt}
+\layout Standard
+  
+\backslash 
+pgfnodesetsepend{4pt}
+\layout Standard
+  
+\backslash 
+pgfnodeconnline{A}{B}
+\layout Standard
+  
+\backslash 
+pgfnodeconnline{A}{C}
+\layout Standard
+  
+\backslash 
+pgfnodeconnline{D}{A}
+\layout Standard
+  
+\backslash 
+pgfnodeconnline{C}{B}
+\layout Standard
+  
+\backslash 
+pgfnodeconnline{B}{D} 
+\layout Standard
+  
+\backslash 
+pgfnodeconnline{D}{C}
+\layout Standard
+
+\backslash 
+end{pgfpicture} 
+\end_inset 
+
+
+\layout Column
+
+6cm
+\layout Definition
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<2->
+\end_inset 
+
+A 
+\color red
+tournament
+\color default
+ is a
+\begin_deeper 
+\layout Enumerate
+
+directed graphs,
+\layout Enumerate
+
+with exactly one edge between
+\newline 
+any two different vertices.
+\end_deeper 
+\end_deeper 
+\layout BeginFrame
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+[<+>]
+\end_inset 
+
+Tournaments Arise Naturally in Different Situations
+\layout ExampleBlock
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Applicatins in Ordering Theory}
+\end_inset 
+
+
+\begin_deeper 
+\layout Standard
+
+Elements in a set need to be sorted.
+ 
+\newline 
+The comparison relation may be cyclic, however.
+\end_deeper 
+\layout Separator
+
+\layout ExampleBlock
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Applications in Sociology}
+\end_inset 
+
+
+\begin_deeper 
+\layout Standard
+
+Several candidates apply for a position.
+\newline 
+Reviewers decide for any two candidates whom they prefer.
+ 
+\end_deeper 
+\layout Separator
+
+\layout ExampleBlock
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Applications in Structural Complexity Theory}
+\end_inset 
+
+
+\begin_deeper 
+\layout Standard
+
+A language 
+\begin_inset Formula $L$
+\end_inset 
+
+ is given and a selector function 
+\begin_inset Formula $f$
+\end_inset 
+
+.
+\newline 
+It chooses from any two words the one more likely to be in 
+\begin_inset Formula $f$
+\end_inset 
+
+.
+\end_deeper 
+\layout Subsection
+
+What Does ``Finding Paths'' Mean?
+\layout BeginFrame
+
+``Finding Paths'' is Ambiguous
+\layout Block
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{
+\backslash 
+strut Input for 
+\backslash 
+ignorespaces
+\backslash 
+def
+\backslash 
+par{}% because LyX inserts superfluous paragraphs
+\layout Standard
+
+\backslash 
+only<1>{Path Finding Problems}
+\backslash 
+ignorespaces
+\layout Standard
+
+\backslash 
+only<2-3>{$
+\backslash 
+Lang{reach}$}
+\backslash 
+ignorespaces
+\layout Standard
+
+\backslash 
+only<4-5>{the Construction Problem}
+\backslash 
+ignorespaces
+\layout Standard
+
+\backslash 
+only<6-7>{the Optimization Problem}
+\backslash 
+ignorespaces
+\layout Standard
+
+\backslash 
+only<8-9>{$
+\backslash 
+Lang{distance}$}
+\backslash 
+ignorespaces
+\layout Standard
+
+\backslash 
+only<10->{the Approximation Problem}}
+\end_inset 
+
+
+\begin_deeper 
+\layout Itemize
+
+A 
+\color red
+graph
+\color default
+ 
+\begin_inset Formula $G=(V,E)$
+\end_inset 
+
+, a 
+\color red
+source
+\color default
+ 
+\begin_inset Formula $s\in V$
+\end_inset 
+
+ and a 
+\color red
+target
+\color default
+ 
+\begin_inset Formula $t\in V$
+\end_inset 
+
+.
+\layout Itemize
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<only@-9| visible@8->
+\end_inset 
+
+A 
+\color red
+maximum distance
+\color default
+\SpecialChar ~
+
+\begin_inset Formula $d$
+\end_inset 
+
+.
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+
+\backslash 
+phantom{p}
+\end_inset 
+
+
+\layout Itemize
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<only@10->
+\end_inset 
+
+An 
+\color red
+approximation ratio
+\color default
+ 
+\begin_inset Formula $r>1$
+\end_inset 
+
+.
+\end_deeper 
+\layout Standard
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+
+\backslash 
+nointerlineskip
+\end_inset 
+
+
+\layout Overprint
+
+\begin_deeper 
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash 
+onslide<1,3,5,7,9,11-12>
+\end_inset 
+
+
+\layout Columns
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+[t,onlytextwidth]
+\end_inset 
+
+
+\begin_deeper 
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash 
+alt<1-2>{
+\backslash 
+column{
+\backslash 
+textwidth}}{
+\backslash 
+column{5cm}}
+\end_inset 
+
+
+\layout ExampleBlock
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Example Input}
+\end_inset 
+
+
+\begin_deeper 
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash 
+begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
+\layout Standard
+  
+\backslash 
+color{beamerexample}
+\layout Standard
+  
+\backslash 
+pgfsetlinewidth{0.6pt}
+\layout Standard
+  
+\backslash 
+graphnode{A}{
+\backslash 
+pgfxy(3,1)}
+\layout Standard
+  
+\backslash 
+graphnode{B}{
+\backslash 
+pgfxy(5,1)}
+\layout Standard
+  
+\backslash 
+graphnode{C}{
+\backslash 
+pgfxy(4,0)}
+\layout Standard
+  
+\backslash 
+graphnode{D}{
+\backslash 
+pgfxy(4,2)}
+\layout Standard
+
+\layout Standard
+  
+\backslash 
+color{white}
+\layout Standard
+  
+\backslash 
+pgfputat{
+\backslash 
+pgfnodecenter{B}}{
+\backslash 
+pgfbox[center,center]{$t$}}
+\layout Standard
+  
+\backslash 
+pgfputat{
+\backslash 
+pgfnodecenter{D}}{
+\backslash 
+pgfbox[center,center]{$s$}}
+\layout Standard
+
+\layout Standard
+  
+\backslash 
+color{beamerexample}
+\layout Standard
+  
+\backslash 
+pgfsetendarrow{
+\backslash 
+pgfarrowto}
+\layout Standard
+  
+\backslash 
+pgfnodesetsepstart{2pt}
+\layout Standard
+  
+\backslash 
+pgfnodesetsepend{4pt}
+\layout Standard
+  
+\backslash 
+pgfnodeconnline{A}{B}
+\layout Standard
+  
+\backslash 
+pgfnodeconnline{A}{C}
+\layout Standard
+  
+\backslash 
+pgfnodeconnline{D}{A}
+\layout Standard
+  
+\backslash 
+pgfnodeconnline{C}{B}
+\layout Standard
+  
+\backslash 
+pgfnodeconnline{B}{D}
+\layout Standard
+  
+\backslash 
+pgfnodeconnline{D}{C}
+\layout Standard
+
+\layout Standard
+  
+\backslash 
+only<9> {
+\backslash 
+pgfputat{
+\backslash 
+pgfxy(5.3,1)}{
+\backslash 
+pgfbox[left,center]{, $d=2$}}}
+\layout Standard
+  
+\backslash 
+only<11>{
+\backslash 
+pgfputat{
+\backslash 
+pgfxy(5.3,1)}{
+\backslash 
+pgfbox[left,center]{, $r=1.5$}}}
+\layout Standard
+  
+\backslash 
+only<12>{
+\backslash 
+pgfputat{
+\backslash 
+pgfxy(5.3,1)}{
+\backslash 
+pgfbox[left,center]{, $r=1.25$}}}
+\layout Standard
+
+\backslash 
+end{pgfpicture}
+\end_inset 
+
+
+\end_deeper 
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash 
+only<3->{
+\backslash 
+column{5cm}}
+\end_inset 
+
+
+\layout ExampleBlock
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+<only@3->{Example Output}
+\end_inset 
+
+
+\begin_deeper 
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash 
+begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm}
+\layout Standard
+  
+\backslash 
+only<5-8,10->{
+\layout Standard
+    
+\backslash 
+color{beamerexample}
+\layout Standard
+    
+\backslash 
+pgfsetlinewidth{0.6pt}
+\layout Standard
+    
+\backslash 
+graphnode{A}{
+\backslash 
+pgfxy(3,1)}
+\layout Standard
+    
+\backslash 
+graphnode{B}{
+\backslash 
+pgfxy(5,1)}
+\layout Standard
+    
+\backslash 
+graphnode{C}{
+\backslash 
+pgfxy(4,0)}
+\layout Standard
+    
+\backslash 
+graphnode{D}{
+\backslash 
+pgfxy(4,2)}
+\layout Standard
+
+\layout Standard
+    
+\backslash 
+color{white}
+\layout Standard
+    
+\backslash 
+pgfputat{
+\backslash 
+pgfnodecenter{B}}{
+\backslash 
+pgfbox[center,center]{$t$}}
+\layout Standard
+    
+\backslash 
+pgfputat{
+\backslash 
+pgfnodecenter{D}}{
+\backslash 
+pgfbox[center,center]{$s$}}
+\layout Standard
+
+\layout Standard
+    
+\backslash 
+color{beamerexample}
+\layout Standard
+    
+\backslash 
+pgfsetendarrow{
+\backslash 
+pgfarrowto}
+\layout Standard
+    
+\backslash 
+pgfnodesetsepstart{2pt}
+\layout Standard
+    
+\backslash 
+pgfnodesetsepend{4pt}
+\layout Standard
+                      
+\layout Standard
+    
+\backslash 
+alert<7,12>{
+\backslash 
+pgfnodeconnline{A}{B}}
+\layout Standard
+    
+\backslash 
+alert<5,11>{
+\backslash 
+pgfnodeconnline{A}{C}}
+\layout Standard
+    
+\backslash 
+alert<5,7,11-12>{
+\backslash 
+pgfnodeconnline{D}{A}}
+\layout Standard
+    
+\backslash 
+alert<5,11>{
+\backslash 
+pgfnodeconnline{C}{B}}
+\layout Standard
+    
+\backslash 
+pgfnodeconnline{B}{D}
+\layout Standard
+    
+\backslash 
+pgfnodeconnline{D}{C}
+\layout Standard
+  }
+\layout Standard
+  
+\backslash 
+only<3,9>{
+\backslash 
+pgfputat{
+\backslash 
+pgfxy(2.75,1)}{
+\backslash 
+pgfbox[left,center]{
+\backslash 
+alert{``Yes''}}}}
+\layout Standard
+
+\backslash 
+end{pgfpicture}
+\end_inset 
+
+
+\end_deeper 
+\end_deeper 
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash 
+onslide<2,4,6,8,10>
+\end_inset 
+
+
+\layout Block
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Variants of Path Finding Problems}
+\end_inset 
+
+
+\begin_deeper 
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash 
+usedescriptionitemofwidthas{Approximation Problem:}
+\end_inset 
+
+
+\layout Description
+
+Reachability\SpecialChar ~
+Problem: 
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<2->
+\end_inset 
+
+Is there a path from 
+\begin_inset Formula $s$
+\end_inset 
+
+ to\SpecialChar ~
+
+\begin_inset Formula $t$
+\end_inset 
+
+?
+\layout Description
+
+Construction\SpecialChar ~
+Problem: 
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<4->
+\end_inset 
+
+Construct a path from 
+\begin_inset Formula $s$
+\end_inset 
+
+ to\SpecialChar ~
+
+\begin_inset Formula $t$
+\end_inset 
+
+? 
+\layout Description
+
+Optimization\SpecialChar ~
+Problem: 
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<6->
+\end_inset 
+
+Construct a shortest path from 
+\begin_inset Formula $s$
+\end_inset 
+
+ to\SpecialChar ~
+
+\begin_inset Formula $t$
+\end_inset 
+
+.
+\layout Description
+
+Distance\SpecialChar ~
+Problem: 
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<8->
+\end_inset 
+
+Is the distance of 
+\begin_inset Formula $s$
+\end_inset 
+
+ and\SpecialChar ~
+
+\begin_inset Formula $t$
+\end_inset 
+
+ at most\SpecialChar ~
+
+\begin_inset Formula $d$
+\end_inset 
+
+?
+\layout Description
+
+Approximation\SpecialChar ~
+Problem: 
+\begin_inset ERT
+status Collapsed
+
+\layout Standard
+<10->
+\end_inset 
+
+Construct a path from 
+\begin_inset Formula $s$
+\end_inset 
+
+ to\SpecialChar ~
+
+\begin_inset Formula $t$
+\end_inset 
+
+ of length
+\newline 
+approximately their distance.
+\end_deeper 
+\end_deeper 
+\layout Section
+
+Review
+\layout Subsection
+
+Standard Complexity Classes
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash 
+pgfdeclaremask{computer-mask}{beamer-g4-mask} 
+\backslash 
+pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer-g4} 
+\end_inset 
+
+
+\layout BeginFrame
+
+The Classes L and NL are Defined via
+\newline 
+Logspace Turing Machines
+\layout Standard
+
+
+\begin_inset ERT
+status Open
+
+\layout Standard
+
+\backslash 
+begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm}
+\layout Standard
+  
+\backslash 
+pgfputat{
+\backslash 
+pgfxy(0,4)}{
+\backslash 
+tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}} 
+\layout Standard
+  
+\backslash 
+uncover<2->{
+\layout Standard
+    
+\backslash 
+pgfputat{
+\backslash 
+pgfxy(0,0.5)}{
+\backslash 
+tape{}{output tape (write only)}{10690836937182}}}
+\layout Standard
+  
+\backslash 
+uncover<3->{
+\layout Standard
+    
+\backslash 
+pgfputat{
+\backslash 
+pgfxy(7,2)}{
+\backslash 
+shorttape{work tape (read/write), $O(
+\backslash 
+log n)$ symbols}{}{42}}
+\layout Standard
+    
+\backslash 
+pgfputat{
+\backslash 
+pgfxy(1.75,2.5)}{
+\backslash 
+pgfbox[center,center]{
+\backslash 
+pgfuseimage{computer}}}
+\layout Standard
+  }
+\layout Standard
+  
+\backslash 
+pgfsetlinewidth{0.6pt}
+\layout Standard
+
+\layout Standard
+  
+\backslash 
+color{structure}
+\layout Standard
+  
+\backslash 
+pgfsetendarrow{
+\backslash 
+pgfarrowto}
+\layout Standard
+  
+\backslash 
+pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85)
+\layout Standard
+  
+\backslash 
+uncover<2->{
+\backslash 
+pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)}
+\layout Standard
+  
+\backslash 
+uncover<3->{
+\backslash 
+pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)}
+\layout Standard
+
+\backslash 
+end{pgfpicture}   
+\end_inset 
+
+
+\layout BeginFrame
+
+Logspace Turing Machines Are Quite Powerful
+\layout Block
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Deterministic logspace machines can compute}
+\end_inset 
+
+
+\begin_deeper 
+\layout Itemize
+
+addition, multiplication, and even division
+\layout Itemize
+
+reductions used in completeness proofs,
+\layout Itemize
+
+reachability in forests.
+\end_deeper 
+\layout Pause
+
+\layout Block
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+{Non-deterministic logspace machines can compute}
+\end_inset 
+
+
+\begin_deeper 
+\layout Itemize
+
+reachability in graphs,
+\layout Itemize
+
+non-reachability in graphs,
+\layout Itemize
+
+satisfiability with two literals per clause.
+\end_deeper 
+\layout BeginFrame
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+<1>[label=hierarchy]
+\end_inset 
+
+The Complexity Class Hierarchy
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash 
+begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm}
+\layout Standard
+  
+\backslash 
+pgfsetlinewidth{0.8pt}
+\layout Standard
+  
+\backslash 
+heap{5.5}{3.5}{$
+\backslash 
+Class P$}{black}{1}
+\layout Standard
+  
+\backslash 
+pgfsetdash{{2pt}}{0pt}
+\layout Standard
+  
+\backslash 
+only<2->{
+\backslash 
+heap{4.5}{3}{$
+\backslash 
+Class{NC}^2$}{black!50!structure}{2}}
+\layout Standard
+  
+\backslash 
+heap{3.5}{2.5}{$
+\backslash 
+Class{NL}$}{black!50!structure}{3}
+\layout Standard
+  
+\backslash 
+heap{2.5}{2}{$
+\backslash 
+Class{L}$}{black!50!structure}{4}
+\layout Standard
+  
+\backslash 
+only<2->{
+\backslash 
+heap{1.75}{1.5}{$
+\backslash 
+vphantom{A}
+\backslash 
+smash{
+\backslash 
+Class{NC}^1}$}{black!50!structure}{5}}
+\layout Standard
+  
+\backslash 
+pgfsetdash{}{0pt}
+\layout Standard
+  
+\backslash 
+only<2->{
+\backslash 
+heap{1.1}{1}{$
+\backslash 
+vphantom{A}
+\backslash 
+smash{
+\backslash 
+Class{AC}^0}$}{black}{6}}
+\layout Standard
+
+\layout Standard
+  
+\backslash 
+pgfsetlinewidth{1.0pt}
+\layout Standard
+  
+\backslash 
+color{black}
+\layout Standard
+  
+\backslash 
+pgfxyline(-5,0)(5,0)
+\layout Standard
+
+\layout Standard
+  
+\backslash 
+only<1-2>{
+\backslash 
+langat{3.375}{$
+\backslash 
+Lang{reach}$}}
+\layout Standard
+  
+\backslash 
+only<1-2>{
+\backslash 
+langat{2.375}{$
+\backslash 
+Lang{reach}_{
+\backslash 
+operatorname{forest}}$}}
+\layout Standard
+
+\layout Standard
+  
+\backslash 
+only<2>{
+\backslash 
+langat{0.975}{$
+\backslash 
+Lang{addition}$}}
+\layout Standard
+  
+\backslash 
+only<2>{
+\backslash 
+langatother{1.6}{
+\backslash 
+vbox{
+\backslash 
+hbox{$
+\backslash 
+Lang{division}$,}
+\backslash 
+hbox{$
+\backslash 
+Lang{parity}$}}}}
+\layout Standard
+  
+\backslash 
+only<3-5>{
+\backslash 
+langat{3.375}{
+\backslash 
+vbox{
+\backslash 
+hbox{$
+\backslash 
+Lang{distance}$,}
+\backslash 
+hbox{$
+\backslash 
+Lang{reach}$}}}}
+\layout Standard
+  
+\backslash 
+only<4->{
+\backslash 
+langatother{2.375}{
+\backslash 
+vbox{
+\backslash 
+ignorespaces
+\layout Standard
+    
+\backslash 
+hbox{$
+\backslash 
+Lang{distance}_{
+\backslash 
+operatorname{forest}}$,}
+\backslash 
+ignorespaces
+\layout Standard
+    
+\backslash 
+hbox{$
+\backslash 
+Lang{reach}_{
+\backslash 
+operatorname{forest}}$,}
+\backslash 
+ignorespaces
+\layout Standard
+    
+\backslash 
+hbox{$
+\backslash 
+Lang{distance}_{
+\backslash 
+operatorname{path}}$,}
+\backslash 
+ignorespaces
+\layout Standard
+    
+\backslash 
+hbox{$
+\backslash 
+Lang{reach}_{
+\backslash 
+operatorname{path}}$}}}}
+\layout Standard
+  
+\backslash 
+only<5->{
+\backslash 
+langat{0.975}{$
+\backslash 
+Lang{reach}_{
+\backslash 
+operatorname{tourn}}$}}
+\layout Standard
+  
+\backslash 
+only<6->{
+\backslash 
+langat{3.375}{
+\backslash 
+vbox{
+\backslash 
+ignorespaces
+\layout Standard
+    
+\backslash 
+hbox{$
+\backslash 
+Lang{distance}_{
+\backslash 
+operatorname{tourn}}$,}
+\backslash 
+ignorespaces
+\layout Standard
+    
+\backslash 
+hbox{$
+\backslash 
+Lang{distance}$,}
+\backslash 
+ignorespaces
+\layout Standard
+    
+\backslash 
+hbox{$
+\backslash 
+Lang{reach}$}}}}
+\layout Standard
+  
+\backslash 
+only<7->{
+\backslash 
+pgfsetdash{{1pt}}{0pt}
+\backslash 
+langat{2.375}{``$
+\backslash 
+Lang{approx}_{
+\backslash 
+operatorname{tourn}}$''}}
+\layout Standard
+
+\backslash 
+end{pgfpicture} 
+\end_inset 
+
+
+\layout BeginFrame
+
+The Circuit Complexity Classes AC
+\begin_inset Formula $^{0}$
+\end_inset 
+
+, NC
+\begin_inset Formula $^{1}$
+\end_inset 
+
+, and NC
+\begin_inset Formula $^{2}$
+\end_inset 
+
+
+\newline 
+Limit the Circuit Depth
+\layout Standard
+
+
+\begin_inset ERT
+status Inlined
+
+\layout Standard
+
+\backslash 
+setlength
+\backslash 
+leftmargini{1em}
+\layout Standard
+
+\backslash 
+nointerlineskip 
+\end_inset 
+
+
+\layout Columns
+
+
+\begin_inset ERT
+status Collapsed
+
+\layout Standard