From 7f4437b17752b5965ada10cfb324d8275a96bdc9 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 5 Apr 2008 22:41:36 +0200 Subject: [PATCH] Fixed lots of typos. --- opt.tex | 16 +++++++--------- 1 file changed, 7 insertions(+), 9 deletions(-) diff --git a/opt.tex b/opt.tex index 8977d34..44a9c8c 100644 --- a/opt.tex +++ b/opt.tex @@ -212,7 +212,7 @@ son's list to its parent. Otherwise, we exchange the sons and move the list from new left son to the parent. This way we obey the heap order and at the same time we keep the white left son free of items. -Ocassionally, we repeat this process once again and we concatenate the resulting lists +Occasionally, we repeat this process once again and we concatenate the resulting lists (we append the latter list to the former, using the smaller of the two \'s). This makes the lists grow longer and we want to do that roughly on every other level of the tree. The exact condition will be that either the rank of the current vertex is odd, @@ -222,7 +222,7 @@ If refilling of the left son fails because there are no more items in that subtr (we report this by setting its \ to $+\infty$), the current vertex is no longer needed --- the items would just pass through it unmodified. We therefore want to remove it. Instead of deleting it directly, we rather make it point to its former -grandsons and we remove the (now orhpaned) original son. This helps us to ensure +grandsons and we remove the (now orphaned) original son. This helps us to ensure that both sons always keep the same rank, which will be useful for the analysis. When all refilling is done, we update the suffix minima by walking from the current @@ -296,9 +296,9 @@ satisfies: $$\ell(v) \le \max(1, 2^{\lceil \(v)/2 \rceil - r/2}).$$ \proof -Initially, all item lists contain at most one item, so the ineqality trivially +Initially, all item lists contain at most one item, so the inequality trivially holds. Let us continue by induction. Melds can affect it only in the favorable -direction (they ocassionally move an~item list to a~vertex of a~higher rank) +direction (they occasionally move an~item list to a~vertex of a~higher rank) and so do deletes (they only remove items from lists). The only potentially dangerous place is the \ procedure. @@ -400,7 +400,7 @@ of the regular melds. Before we estimate the time spent on deletions, we analyse the refills. \lemma -Every invokation of the \ procedure takes time $\O(1)$ amortized. +Every invocation of the \ procedure takes time $\O(1)$ amortized. \proof When \ is called from the \ operation, it recurses on a~subtree of the @@ -522,7 +522,7 @@ time complexity is optimal for this choice of~$\varepsilon$. Chazelle \cite{chaz proves that it is optimal for every choice of~$\varepsilon$. The space consumed by the heap need not be linear in the \em{current} number -of items, but if a~case where this matters ever occured, we could fix it easily +of items, but if a~case where this matters ever occurred, we could fix it easily by rebuilding the whole data structure completely after $n/2$ deletes. This increases the number of potentially corrupted items, but at worst twice, so it suffices to decrease~$\varepsilon$ twice. @@ -1028,7 +1028,7 @@ from the previous section. The first two steps of the algorithm are trivial as we have linear time at our disposal. -By the Parititioning theorem (\ref{partthm}), the call to \ with~$\varepsilon$ +By the Partitioning theorem (\ref{partthm}), the call to \ with~$\varepsilon$ set to a~constant takes $\O(m)$ time and it produces a~collection of subgraphs of size at most~$t$ and at most $m/4$ corrupted edges. It also guarantees that the connected components of the union of the $C_i$'s have at least~$t$ vertices @@ -1129,6 +1129,4 @@ There were attempts to derandomize the KKT algorithm, but so far the best result is the randomized algorithm also by Pettie \cite{pettie:minirand} which achieves expected linear time complexity with only $\O(\log^* n)$ random bits. - - \endpart -- 2.39.2