From 78d9f562c038d28c7de1206df80354db4f5ac1e4 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 19 Apr 2008 15:08:52 +0200 Subject: [PATCH] Capitalize PM. --- PLAN | 1 - adv.tex | 2 +- opt.tex | 14 +++++++------- ram.tex | 8 ++++---- 4 files changed, 12 insertions(+), 13 deletions(-) diff --git a/PLAN b/PLAN index bef6665..c11700f 100644 --- a/PLAN +++ b/PLAN @@ -103,7 +103,6 @@ Notation: - change the notation for contractions -- use double slash instead of the dot? - introduce \widehat\O early - unify { x ; ... }, { x | ...} and { x : ... } -- capitalize Pointer Machine - Ackermann: which of the Tarjan's set union papers should we cite? - Ackermann function vs. Ackermann's function diff --git a/adv.tex b/adv.tex index 4221348..0f2d5d9 100644 --- a/adv.tex +++ b/adv.tex @@ -1037,7 +1037,7 @@ which is $\O(m)$ by Theorem \ref{verify}. \rem\id{pmverify}% Buchsbaum et al.~\cite{buchsbaum:verify} have recently shown that linear-time -verification can be achieved even on the Pointer machine. They first solve the +verification can be achieved even on the Pointer Machine. They first solve the problem of finding the lowest common ancestors for a~set of pairs of vertices by batch processing: They combine an~algorithm of time complexity $\O(m\timesalpha(m,n))$ based on the Disjoint Set Union data structure with the framework of topological graph diff --git a/opt.tex b/opt.tex index 7d236c6..fc80d9e 100644 --- a/opt.tex +++ b/opt.tex @@ -8,7 +8,7 @@ Recently, Chazelle \cite{chazelle:ackermann} and Pettie \cite{pettie:ackermann} have presented algorithms for the MST with worst-case time complexity -$\O(m\timesalpha(m,n))$ on the Pointer machine. We will devote this chapter to their results +$\O(m\timesalpha(m,n))$ on the Pointer Machine. We will devote this chapter to their results and especially to another algorithm by Pettie and Ramachandran \cite{pettie:optimal}, which is provably optimal. @@ -354,7 +354,7 @@ We will show that if we charge $\O(r)$ time against every element inserted, it i to cover the cost of all other operations. All heap operations use only pointer operations, so it will be easy to derive the time -bound in the Pointer machine model. The notable exception is however that the procedures +bound in the Pointer Machine model. The notable exception is however that the procedures often refer to the ranks, which are integers on the order of $\log n$, so they cannot fit in a~single memory cell. For the time being, we will assume that the ranks can be manipulated in constant time, postponing the proof for later. @@ -479,7 +479,7 @@ It remains to take care of the calculation with ranks: \lemma\id{shyards}% Every manipulation with ranks performed by the soft heap operations can be -implemented on the Pointer machine in constant amortized time. +implemented on the Pointer Machine in constant amortized time. \proof We create a~``yardstick'' --- a~double linked list whose elements represent the possible @@ -503,7 +503,7 @@ Now we can put the bits together and laurel our effort with the following theore \thmn{Performance of soft heaps, Chazelle \cite{chazelle:softheap}}\id{softheap}% A~soft heap with error rate~$\varepsilon$ ($0<\varepsilon\le 1/2$) processes a~sequence of operations starting with an~empty heap and containing $n$~\s -in time $\O(n\log(1/\varepsilon))$ on the Pointer machine. At every moment, the +in time $\O(n\log(1/\varepsilon))$ on the Pointer Machine. At every moment, the heap contains at most $\varepsilon n$ corrupted items. \proof @@ -839,7 +839,7 @@ trees only for very small subgraphs. \lemman{Construction of optimal decision trees}\id{odtconst}% An~optimal MST decision tree for a~graph~$G$ on~$n$ vertices can be constructed on -the Pointer machine in time $\O(2^{2^{4n^2}})$. +the Pointer Machine in time $\O(2^{2^{4n^2}})$. \proof We will try all possible decision trees of depth at most $2n^2$ @@ -859,7 +859,7 @@ of the known algorithms and comparing it with the result given by the decision t The number of permutations does not exceed $(n^2)! \le (n^2)^{n^2} \le n^{2n^2} \le 2^{n^3}$ and each permutation can be checked in time $\O(\poly(n))$. -On the Pointer machine, trees and permutations can be certainly enumerated in time +On the Pointer Machine, trees and permutations can be certainly enumerated in time $\O(\poly(n))$ per object. The time complexity of the whole algorithm is therefore $\O(2^{2^{3n^2}} \cdot 2^{n^3} \cdot \poly(n)) = \O(2^{2^{4n^2}})$. \qed @@ -1020,7 +1020,7 @@ resulting graph. Correctness of this algorithm immediately follows from the Partitioning theorem (\ref{partthm}) and from the proofs of the respective algorithms used as subroutines. Let us take a~look at -the time complexity. We will be careful to use only the operations offered by the Pointer machine. +the time complexity. We will be careful to use only the operations offered by the Pointer Machine. \lemma\id{optlemma}% The time complexity $T(m,n)$ of the Optimal algorithm satisfies the following recurrence: diff --git a/ram.tex b/ram.tex index 61db822..651ad74 100644 --- a/ram.tex +++ b/ram.tex @@ -312,7 +312,7 @@ Then we reset all pairs and re-insert the values back in their increasing order. This is also $\O(n+m)$. \paran{Tree isomorphism}% -Another nice example of pointer-based radix sorting is a~Pointer machine algorithm for +Another nice example of pointer-based radix sorting is a~Pointer Machine algorithm for deciding whether two rooted trees are isomorphic. Let us assume for a~moment that the outdegree of each vertex is at most a~fixed constant~$k$. We begin by sorting the subtrees of both trees by their depth. This can be accomplished by running depth-first search to calculate @@ -363,7 +363,7 @@ other situations, so we will state it as a~separate lemma: \lemman{Sequence unification}\id{suniflemma}% Partitioning of a~collection of sequences $S_1,\ldots,S_n$, whose elements are arbitrary pointers and symbols from a~finite alphabet, to equality classes can -be performed on the Pointer machine in time $\O(n + \sum_i \vert S_i \vert)$. +be performed on the Pointer Machine in time $\O(n + \sum_i \vert S_i \vert)$. \rem The first linear-time algorithm that partitions all subtrees to isomorphism equivalence @@ -400,7 +400,7 @@ Decompositions are usually implemented on the RAM, because subgraphs can be easi encoded in numbers, which can be then used to index arrays containing the precomputed results. As the previous algorithm for subtree isomorphism shows, indexing is not strictly required for identifying equivalent microtrees and it can be replaced by bucket -sorting on the Pointer machine. Buchsbaum et al.~\cite{buchsbaum:verify} have extended +sorting on the Pointer Machine. Buchsbaum et al.~\cite{buchsbaum:verify} have extended this technique to general graphs in form of so called topological graph computations. Let us define them. @@ -455,7 +455,7 @@ the collection and $\Vert\C\Vert$ as their total size, i.e., $\Vert\C\Vert = \su \lemman{Graph unification}\id{guniflemma}% A~collection~$\C$ of labeled graphs can be partitioned into classes which share the same -canonical encoding in time $\O(\Vert\C\Vert)$ on the Pointer machine. +canonical encoding in time $\O(\Vert\C\Vert)$ on the Pointer Machine. \proof Construct canonical encodings of all the graphs and then apply the Sequence unification lemma -- 2.39.2