From 802f93909c137f302259783d69565a7d5c6796f2 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 5 Apr 2008 23:42:09 +0200 Subject: [PATCH] \paran redefined. --- macros.tex | 2 +- opt.tex | 12 ++++++------ 2 files changed, 7 insertions(+), 7 deletions(-) diff --git a/macros.tex b/macros.tex index 19972c8..be78b1f 100644 --- a/macros.tex +++ b/macros.tex @@ -376,7 +376,7 @@ \def\problemn{\problem\labelx} \def\remn{\rem\labelx} -\def\paran#1{\para {\sl #1:}} +\def\paran#1{\para {\sl #1:\/}\enspace} \def\proof{\noindent {\sl Proof.}\enspace} \def\proofsketch{\noindent {\sl Proof sketch.}\enspace} diff --git a/opt.tex b/opt.tex index 44a9c8c..b0540e3 100644 --- a/opt.tex +++ b/opt.tex @@ -280,7 +280,7 @@ Let us translate these ideas to real (pseudo)code: all queues in the heap, walks the trees and the item lists of all vertices. It records all items seen, the corrupted ones are those that different from their \. -\paran{Analysis of accuracy} +\paran{Analysis of accuracy}% The description of the operations is now complete, so let us analyse their behavior and verify that we have delivered what we promised --- first the accuracy of the structure, then the time complexity of operations. In the whole analysis, @@ -348,7 +348,7 @@ last expression is less than $2^{k-r+2}$. Since the tree contains $n_k=2^k$ blac this makes less than $n_k/2^{r-2}$ corrupted items as we asserted. \qed -\paran{Analysis of time complexity} +\paran{Analysis of time complexity}% Now we will examine the amortized time complexity of the individual operations. We will show that if we charge $\O(r)$ time against every element inserted, it is enough to cover the cost of all other operations. @@ -859,7 +859,7 @@ $\O(\poly(k))$ per object. The time complexity of the whole algorithm is therefo $\O(2^{k^2} \cdot 2^{2^{3k^2}} \cdot 2^{k^3} \cdot \poly(k)) = \O(2^{2^{4k^2}})$. \qed -\paran{Basic properties of decision trees} +\paran{Basic properties of decision trees}% The following properties will be useful for analysis of algorithms based on precomputed decision trees. We will omit some technical details, referring the reader to section 5.1 of the Pettie's paper \cite{pettie:optimal}. @@ -1052,7 +1052,7 @@ The remaining steps of the algorithm can be easily performed in linear time eith or in case of the contractions by the bucket-sorting techniques of Section \ref{bucketsort}. \qed -\paran{Optimality} +\paran{Optimality}% The properties of decision tree complexity, which we have proven in the previous section, will help us show that the time complexity recurrence is satisfied by the decision tree complexity $D(m,n)$ itself. This way, we prove the following theorem: @@ -1080,7 +1080,7 @@ The other inequality is obvious as $D(m,n)$ is an~asymptotic lower bound for the time complexity of every comparison-based algorithm. \qed -\paran{Complexity of MST} +\paran{Complexity of MST}% As we have already noted, the exact decision tree complexity $D(m,n)$ of the MST problem is still open and so is therefore the time complexity of the optimal algorithm. However, every time we come up with another comparison-based algorithm, we can use its complexity @@ -1113,7 +1113,7 @@ independently on the other edges) or $G_{n,m}$ (we draw the graph uniformly at r set of all graphs with~$n$ vertices and $m$~edges), it runs in linear time with high probability, regardless of the edge weights. -\paran{Models of computation} +\paran{Models of computation}% Another important consequence of the optimal algorithm is that when we aim for a~linear-time MST algorithm (or for proving that it does not exist), we do not need to care about computational models at all. The elaborate RAM data structures of Chapter \ref{ramchap}, which have helped us -- 2.39.2