merged draft
authorlammich <lammich@in.tum.de>
Tue, 03 Jul 2018 11:21:09 +0200
changeset 69940 e04bcdda9c3a
parent 69939 a7655a4900e5 (current diff)
parent 69938 29cfd22525c7 (diff)
child 69941 af2719b74080
merged
--- a/SS18/ROOT	Tue Jul 03 11:20:53 2018 +0200
+++ b/SS18/ROOT	Tue Jul 03 11:21:09 2018 +0200
@@ -40,11 +40,10 @@
     Leftist_Heap_Slides
     Braun_Tree_Slides
     Binomial_Heap_Slides
-(*
     Amor_Slides
     Skew_Heap_Slides
     Splay_Tree_Slides
-    Pairing_Heap_Slides*)
+    Pairing_Heap_Slides
   document_files
     "root.tex"
     "root_handout.tex"
--- a/SS18/Slides/Amor_Slides.thy	Tue Jul 03 11:20:53 2018 +0200
+++ b/SS18/Slides/Amor_Slides.thy	Tue Jul 03 11:21:09 2018 +0200
@@ -253,6 +253,28 @@
 \end{center}
 \end{frame}
 %-------------------------------------------------------------
+\begin{frame}{Warning: observer functions}
+\high{\emph{Observer function}}: does not modify data structure\\\pause
+$\Longrightarrow$ Potential difference = 0\\\pause
+$\Longrightarrow$ amortized cost = real cost\\\pause
+$\Longrightarrow$ \bad{Must analyze WCC of observer functions}
+\medskip\pause
+
+This makes sense because
+\begin{center}
+\high{Observer functions do not consume their arguments!}
+\end{center}
+\pause
+
+Legal:
+\begin{tabular}[t]{rlll}
+{\sf\emph{ let}} & \<open>bad\<close> & \<open>=\<close> & create unbalanced data structure\\ &&& with high potential;\\
+      & \<open>_\<close> & \<open>=\<close> & \<open>observer bad;\<close>\\
+      & \<open>_\<close> & \<open>=\<close> & \<open>observer bad;\<close>\\
+      & $\vdots$
+\end{tabular}
+\end{frame}
+%-------------------------------------------------------------
 \subsection{Simple Classical Examples}
 %-------------------------------------------------------------
 \thyfile{Thys/Amortized\char`_Examples}{}
--- a/SS18/Slides/Pairing_Heap_Slides.thy	Tue Jul 03 11:20:53 2018 +0200
+++ b/SS18/Slides/Pairing_Heap_Slides.thy	Tue Jul 03 11:21:09 2018 +0200
@@ -128,9 +128,6 @@
 \begin{frame}{More trees}
 \begin{itemize}
 \pause
-\item Weight-Balanced Trees:\\\pause
-Nievergelt and Reingold 1973 / Dirix 2017
-\pause
 \item Huffman Trees:\\\pause
 Huffman 1952 / Blanchette 2008
 \pause
@@ -155,6 +152,8 @@
 \item Strongly Connected Components:\\\pause
 Tarjan 1972 / Schimpf 2015\\\pause
 Gabow 2000 / Lammich 2014
+\pause
+\item Minimum spanning tree: almost ready
 \end{itemize}
 \end{frame}
 %-------------------------------------------------------------
@@ -172,9 +171,21 @@
 \end{frame}
 %-------------------------------------------------------------
 \begin{frame}{Dynamic programming}
-\begin{center}
-In progress
-\end{center}
+\begin{itemize}
+\item Start with recursive function
+\pause
+\item Automatic translation to memoized version
+      incl.\ correctness theorem
+\pause
+\item Applications
+ \begin{itemize}
+ \item Optimal binary search tree
+ \item Minimum edit distance
+ \item Bellman-Ford (SSSP)
+ \item CYK
+ \item \dots
+ \end{itemize}
+\end{itemize}
 \end{frame}
 %-------------------------------------------------------------
 \begin{frame}{Infrastructure}
--- a/SS18/Slides/document/main.tex	Tue Jul 03 11:20:53 2018 +0200
+++ b/SS18/Slides/document/main.tex	Tue Jul 03 11:21:09 2018 +0200
@@ -36,9 +36,9 @@
 \input{Braun_Tree_Slides}
 \input{Binomial_Heap_Slides}
 
-%\part{Amortized Complexity}
-%\input{Amor_Slides}
-%\input{Skew_Heap_Slides}
-%\input{Splay_Tree_Slides}
-%\input{Pairing_Heap_Slides}
+\part{Amortized Complexity}
+\input{Amor_Slides}
+\input{Skew_Heap_Slides}
+\input{Splay_Tree_Slides}
+\input{Pairing_Heap_Slides}
 \end{document}
--- a/SS18/Thys	Tue Jul 03 11:20:53 2018 +0200
+++ b/SS18/Thys	Tue Jul 03 11:21:09 2018 +0200
@@ -1,1 +1,1 @@
-../../SS18/public/Thys
\ No newline at end of file
+../../SS18/Public/Thys
\ No newline at end of file