X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=PLAN;h=41930d069e731a846e0d6faa45c951c313c4d0e4;hb=6d21ffb3141e1b934fbe4895e58b9b977616b245;hp=04d7887c30cd916566bf0bd31ca7e1fb57f01334;hpb=bf6ba465dda1426184f98e260be0e87e2b3dced8;p=saga.git

diff --git a/PLAN b/PLAN
index 04d7887..41930d0 100644
--- a/PLAN
+++ b/PLAN
@@ -48,45 +48,29 @@
 
 TODO:
 
+Preface:
+
+- move TOC to the beginning of the book
+- mention notation
+- cite GA booklet
+
 Spanning trees:
 
 - cite Eisner's tutorial \cite{eisner:tutorial}
-- \cite{pettie:onlineverify} online lower bound
-- move the remark on disconnected graphs? separate section?
-- mention graphs with non-unique weights? also in the separate section?
 - Some algorithms (most notably Fredman-Tarjan) do not need flattening
-- citation of mixed Boruvka-Jarnik
 - use the notation for contraction by a set
 - mention bugs in Valeria's verification paper
 - more references on decision trees
-- rename theorem on Minimality by order
-- introduce Cut rule and Cycle rule earlier
 - Lemma: deletion of a non-MST edge does not alter the MST
+- mention that there are only a few algorithms based on the Red rule
 
 Related:
 - practical considerations: katriel:cycle, moret:practice (mention pairing heaps)
 - parallel algorithms: p243-cole (see also remarks in Karger and pettie:minirand), pettie:parallel
 - K best trees
-- random sampling (propp:randommst)
 - degree-restricted cases and arborescences
 - bounded expansion classes?
-- mention matroids
-
-Models:
-
-- bit tricks: reference to HAKMEM
-- mention in-place radix-sorting?
-- consequences of Q-Heaps: Thorup's undirected SSSP etc.
-- add more context from thorup:aczero, also mention FP operations
-- Tarjan79 is mentioned by Pettie to define Pointer machines
-- add references to the C language
-- PM: unify yardsticks
-- all data structures should mention space complexity
-
-Dynamic:
-
-- What is the origin of the semidynamic MSF?
-- lower bounds
+- finding all MST's
 
 Ranking:
 
@@ -95,25 +79,29 @@ Ranking:
 - JN: explain approx scheme
 - JN: 4.5.1:  neslo by preci isolovat nejaky vlstnosti restriction matrices
   tak aby byl speedup? Staci napr predpokladat 4.5.2 (jako to postulovat)
-  co je to vlstne za matice co splnuji 4.5.2
+  co je to vlastne za matice co splnuji 4.5.2
 - JN: bounded-degree restriction graphs; would it imply general speedup?
 
 Notation:
 
+- sort the table
 - G has to be connected, so m=O(n)
 - impedance mismatch in terminology: contraction of G along e vs. contraction of e.
 - use \delta(X) notation
 - unify use of n(G) vs. n
-- use calligraphic letters from ams?
 - 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
 
-Varia:
+Typography:
 
-- cite GA booklet
-- minimize the use of Remarks, use \paran instead
 - formatting of multi-line \algin, \algout
+- use calligraphic letters from ams?
+
+Global:
+
+- each chapter should make clear in which model we work
+- clean up bibliography
+
+Pictures:
+
+- structure of a Q-heap