More Adaptive Sorting and Reductions between (Pb,m)
Jérémy Barbay 1 Abr 201001/04/10 a las 20:44 hrs.2010-04-01 20:44:01
More Adaptive Sorting and Reductions between (Pb,m)
===================================================
Author: Jérémy Barbay
Date: 2010-04-01 20:42:22 CLST
<2010-04-01 Thu 14:30-16:00>
1) Another Adaptive Sorting Algorithm
1. Straight Insertion Sort
2. Local Insertion Sort
- Using a Finger Search Tree [Brown and Tarjan, "A
representation for linear lists with movable Fingers"]
- Using a Splay Tree [Sleator and Tarjan "Self Adjusting Binary Search Tree"]
- or a variant of it [Demaine, Harmon, Iacono, Patrascu, "Dynamic Optimality--Almost"]
3. Measure of Difficulty /Inv/
2) Which (adaptive) algorithm is "the best"?
1. So far we saw three "adaptive" algorithms and their measures:
- merge sort for ascending runs, adaptive to /nRuns/
- merge sort for SUS (Shuffled Up Sequences), adaptive to /SUS/
- adaptive insertiong sort, adaptive to /Inv/
Which one is "the best"?
2. Reduction between pairs (Pb, measure): Example
- It is easy to see that /SUS/\leq /nRuns/
- Hence O(n\lg SUS) \subset O(n\lg nRuns)
- Any algorithm asymptotically optimal for SUS is asymptotically optimal for nRuns.
- we say that "SUS \leq_{alg} nRuns"
3. Independance between pairs (Pb, measure): Example
- Given an algorithm A_1 optimal for the measure \delta_1
and an algorithm A_2 optimal for the measure \delta_2
- For each $n$, find
- an instance I_1 where algorithm A_1 outperforms algorithm A_2
- an instance I_2 where algorithm A_2 outperforms algorithm A_1
- (Sorting,Exc) is incomparable with (Sorting,Runs)
- Can we do that for (Sorting, Inv) and (Sorting, nRuns)?
3) The partial map of adaptive sorting algorithms
1. List of measures of difficulty
Dis largest distance determined by an inversion
Max largest distance an element must travel to reach its sorted position
*Inv* number of inversions in a sequence
Exc minimum number of exchanges required to sort a sequence
Rem minimum number of elements thant must be removed to obtain a sorted subsequence
*Runs* number of ascending runs
SUS minimum number of ascending subsequences
SMS minimum number of monotone subsequences
Enc number of sorted lists constructed by Melsort
Osc the oscillation of large and small elements (in Heapsort)
2. Placing some relations
* we already know
- Inv <> Runs
- Runs < SUS
* Can guess
- SUS < SMS
- Dis < Max < Inv (in fact Dis = Max)
3. Giving the complete map.
1 References
~~~~~~~~~~~~~
1.1 On trees supporting "Finger Search"
========================================
1.1.1 The first definition of Finger Search, for 2-3 trees.
------------------------------------------------------------
@Article{designAndAnalysisOfADataStructureForRepresentingSortedLists,
author = "Mark R. Brown and Robert E. Tarjan",
title = "Design and analysis of a data structure for
representing sorted lists",
journal = "SIAM Journal of Computing",
volume = "9",
number = "3",
pages = "594--614",
year = "1980",
CODEN = "SMJCAT",
ISSN = "0097-5397 (print), 1095-7111 (electronic)",
MRclass = "68H05 (68C25 68E05)",
MRnumber = "82e:68101",
MRreviewer = "Eberhard L{\"u}dde",
bibdate = "Sat Jan 18 18:03:50 MST 1997",
acknowledgement = ack-nhfb,
}
1.1.2 Splay Trees :READING:
---------------------------
@article{selfAdjustingBinarySearchTrees,
author = {Daniel Dominic Sleator and Robert Endre Tarjan},
title = {Self-adjusting binary search trees},
journal = {J. ACM},
volume = 32,
number = 3,
year = 1985,
issn = {0004-5411},
pages = {652--686},
doi = {[doi.acm.org/10.1145/3828.3835}],
publisher = {ACM},
address = {New York, NY, USA},
}
1.1.3 Recursive Dynamic Search Trees :READING:OPEN:
---------------------------------------------------
@article{dynamicOptimalityAlmost,
author = {Erik D. Demaine and Dion Harmon and John Iacono and Mihai P{\v a}tra{\c s}cu},
title = {Dynamic Optimality---Almost},
journal = {SIAM J. Comput.},
volume = 37,
number = 1,
year = 2007,
issn = {0097-5397},
pages = {240--251},
doi = {[dx.doi.org/10.1137/S0097539705447347}],
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
}
1.1.4 Optimal "Splay" Trees :READING:OPEN:
------------------------------------------
@inproceedings{theGeometryOfBinarySearchTrees,
author = "Erik D. Demaine and Dion Harmon and John Iacono and Daniel Kane and Mihai P{\v a}tra{\c s}cu",
title = "The Geometry of Binary Search Trees",
booktitle = "Proc. 20th ACM/SIAM Symposium on Discrete Algorithms (SODA)",
pages = "496-505",
year = "2009"
}
1.2 On Sorting
===============
@Article{petersson,
author = {Ola Petersson and Alistair Moffat},
title = {A framework for adaptive sorting},
journal = {Discrete Applied Mathematics},
year = {1995},
volume = {59},
pages = {153--179},
}
@article{estivillcastro92survey,
author = "Vladimir Estivill-Castro and Derick Wood",
title = "A Survey of Adaptive Sorting Algorithms",
journal = "ACM Computing Surveys",
volume = "24",
number = "4",
pages = "441--476",
year = "1992",
url = "citeseer.nj.nec.com/ ... -castro92survey.html"
}
===================================================
Author: Jérémy Barbay
Date: 2010-04-01 20:42:22 CLST
<2010-04-01 Thu 14:30-16:00>
1) Another Adaptive Sorting Algorithm
1. Straight Insertion Sort
2. Local Insertion Sort
- Using a Finger Search Tree [Brown and Tarjan, "A
representation for linear lists with movable Fingers"]
- Using a Splay Tree [Sleator and Tarjan "Self Adjusting Binary Search Tree"]
- or a variant of it [Demaine, Harmon, Iacono, Patrascu, "Dynamic Optimality--Almost"]
3. Measure of Difficulty /Inv/
2) Which (adaptive) algorithm is "the best"?
1. So far we saw three "adaptive" algorithms and their measures:
- merge sort for ascending runs, adaptive to /nRuns/
- merge sort for SUS (Shuffled Up Sequences), adaptive to /SUS/
- adaptive insertiong sort, adaptive to /Inv/
Which one is "the best"?
2. Reduction between pairs (Pb, measure): Example
- It is easy to see that /SUS/\leq /nRuns/
- Hence O(n\lg SUS) \subset O(n\lg nRuns)
- Any algorithm asymptotically optimal for SUS is asymptotically optimal for nRuns.
- we say that "SUS \leq_{alg} nRuns"
3. Independance between pairs (Pb, measure): Example
- Given an algorithm A_1 optimal for the measure \delta_1
and an algorithm A_2 optimal for the measure \delta_2
- For each $n$, find
- an instance I_1 where algorithm A_1 outperforms algorithm A_2
- an instance I_2 where algorithm A_2 outperforms algorithm A_1
- (Sorting,Exc) is incomparable with (Sorting,Runs)
- Can we do that for (Sorting, Inv) and (Sorting, nRuns)?
3) The partial map of adaptive sorting algorithms
1. List of measures of difficulty
Dis largest distance determined by an inversion
Max largest distance an element must travel to reach its sorted position
*Inv* number of inversions in a sequence
Exc minimum number of exchanges required to sort a sequence
Rem minimum number of elements thant must be removed to obtain a sorted subsequence
*Runs* number of ascending runs
SUS minimum number of ascending subsequences
SMS minimum number of monotone subsequences
Enc number of sorted lists constructed by Melsort
Osc the oscillation of large and small elements (in Heapsort)
2. Placing some relations
* we already know
- Inv <> Runs
- Runs < SUS
* Can guess
- SUS < SMS
- Dis < Max < Inv (in fact Dis = Max)
3. Giving the complete map.
1 References
~~~~~~~~~~~~~
1.1 On trees supporting "Finger Search"
========================================
1.1.1 The first definition of Finger Search, for 2-3 trees.
------------------------------------------------------------
@Article{designAndAnalysisOfADataStructureForRepresentingSortedLists,
author = "Mark R. Brown and Robert E. Tarjan",
title = "Design and analysis of a data structure for
representing sorted lists",
journal = "SIAM Journal of Computing",
volume = "9",
number = "3",
pages = "594--614",
year = "1980",
CODEN = "SMJCAT",
ISSN = "0097-5397 (print), 1095-7111 (electronic)",
MRclass = "68H05 (68C25 68E05)",
MRnumber = "82e:68101",
MRreviewer = "Eberhard L{\"u}dde",
bibdate = "Sat Jan 18 18:03:50 MST 1997",
acknowledgement = ack-nhfb,
}
1.1.2 Splay Trees :READING:
---------------------------
@article{selfAdjustingBinarySearchTrees,
author = {Daniel Dominic Sleator and Robert Endre Tarjan},
title = {Self-adjusting binary search trees},
journal = {J. ACM},
volume = 32,
number = 3,
year = 1985,
issn = {0004-5411},
pages = {652--686},
doi = {[doi.acm.org/10.1145/3828.3835}],
publisher = {ACM},
address = {New York, NY, USA},
}
1.1.3 Recursive Dynamic Search Trees :READING:OPEN:
---------------------------------------------------
@article{dynamicOptimalityAlmost,
author = {Erik D. Demaine and Dion Harmon and John Iacono and Mihai P{\v a}tra{\c s}cu},
title = {Dynamic Optimality---Almost},
journal = {SIAM J. Comput.},
volume = 37,
number = 1,
year = 2007,
issn = {0097-5397},
pages = {240--251},
doi = {[dx.doi.org/10.1137/S0097539705447347}],
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
}
1.1.4 Optimal "Splay" Trees :READING:OPEN:
------------------------------------------
@inproceedings{theGeometryOfBinarySearchTrees,
author = "Erik D. Demaine and Dion Harmon and John Iacono and Daniel Kane and Mihai P{\v a}tra{\c s}cu",
title = "The Geometry of Binary Search Trees",
booktitle = "Proc. 20th ACM/SIAM Symposium on Discrete Algorithms (SODA)",
pages = "496-505",
year = "2009"
}
1.2 On Sorting
===============
@Article{petersson,
author = {Ola Petersson and Alistair Moffat},
title = {A framework for adaptive sorting},
journal = {Discrete Applied Mathematics},
year = {1995},
volume = {59},
pages = {153--179},
}
@article{estivillcastro92survey,
author = "Vladimir Estivill-Castro and Derick Wood",
title = "A Survey of Adaptive Sorting Algorithms",
journal = "ACM Computing Surveys",
volume = "24",
number = "4",
pages = "441--476",
year = "1992",
url = "citeseer.nj.nec.com/ ... -castro92survey.html"
}
Reading List
Jérémy Barbay 31 Mar 201031/03/10 a las 21:35 hrs.2010-03-31 21:35:31
Reading list
============
Table of Contents
=================
1 Adaptive Searching
1.1 An Almost Optimal Algorithm for Unbounded Searching
1.2 Splay Trees
1.3 Recursive Dynamic Search Trees
1.4 Optimal "Splay" Trees
2 Adaptive Sorting
2.1 A framework for adaptive sorting
2.2 A Survey of Adaptive Sorting Algorithms
2.3 Best sorting algorithm for nearly sorted lists
2.4 Compressed Representations of Permutations, and Applications
2.5 Encroaching Lists as a measure of presortedness
2.6 Measures of Presortedness and Optimal Sorting Algorithms
2.7 Smoothsort
2.8 Sorting and recognition problems for ordered sets
2.9 Sorting and Selection in Posets
2.10 Sorting presorted files
2.11 Sorting Shuffled Monotone Sequences
3 Output Sensitive Complexity in Computational Geometry
3.1 The Ultimate Planar Convex Hull Algorithm?
3.2 Output-Sensitive Results on Convex Hulls, Extreme Points, and Related Problems
3.3 Output-Sensitive Construction of Polytopes in Four Dimensions and Clipped Voronoi Diagrams in Three.
3.4 Instance-optimal geometric algorithms
3.5 Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions
3.6 Dynamic planar convex hull operations in near-logarithmic amortized time
4 Parameterized Complexity
4.1 Invitation to Fixed-Parameter Algorithms
4.2 Parameterized Complexity Theory,
5 Adaptive Union and Intersection
5.1 Adaptive Intersection and t-Threshold Problems
5.2 Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents
5.3 Adaptive set intersections, unions, and differences
5.4 Experiments on Adaptive Set Intersections for Text Retrieval Systems
5.5 Hyperbolic Dovetailing (can be used for Intersection)
5.6 Merge Source Coding by Bruno T Avila and Eduardo S. Laber,
5.7 Optimality of Randomized Algorithms for the Intersection Problem
6 Instance Optimality
6.1 Optimal aggregation algorithms for middleware, Fagin et al.
6.2 Best-fit bin-packing with random order, Kenyon Claire
7 Competitive Analysis
7.1 Online Computation and Competitive Analysis (Book)
7.2 On the Separation and Equivalence of Paging Strategies
1 Adaptive Searching
~~~~~~~~~~~~~~~~~~~~~
1.1 An Almost Optimal Algorithm for Unbounded Searching :READING:
=================================================================
J. L. Bentley and A. C.-C. Yao. "An Almost Optimal Algorithm
for Unbounded Searching." Information Processing Letters,
Vol. 5, pp. 82-87, 1976.
@article{anAlmostOptimalAlgorithmForUnboundedSearching,
author = {Jon Louis Bentley and Andrew Chi-Chih Yao},
title = {An almost optimal algorithm for unbounded searching},
journal = {Information processing letters},
year = {1976},
OPTkey = {},
volume = {5},
number = {3},
pages = {82--87},
OPTmonth = {},
OPTnote = {},
OPTannote = {}
}
1.2 Splay Trees :READING:
=========================
@article{selfAdjustingBinarySearchTrees,
author = {Daniel Dominic Sleator and Robert Endre Tarjan},
title = {Self-adjusting binary search trees},
journal = {J. ACM},
volume = 32,
number = 3,
year = 1985,
issn = {0004-5411},
pages = {652--686},
doi = {[doi.acm.org/10.1145/3828.3835}],
publisher = {ACM},
address = {New York, NY, USA},
}
1.3 Recursive Dynamic Search Trees :READING:OPEN:
=================================================
@article{dynamicOptimalityAlmost,
author = {Erik D. Demaine and Dion Harmon and John Iacono and Mihai P{\v a}tra{\c s}cu},
title = {Dynamic Optimality---Almost},
journal = {SIAM J. Comput.},
volume = 37,
number = 1,
year = 2007,
issn = {0097-5397},
pages = {240--251},
doi = {[dx.doi.org/10.1137/S0097539705447347}],
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
}
1.4 Optimal "Splay" Trees :READING:OPEN:
========================================
@inproceedings{theGeometryOfBinarySearchTrees,
author = "Erik D. Demaine and Dion Harmon and John Iacono and Daniel Kane and Mihai P{\v a}tra{\c s}cu",
title = "The Geometry of Binary Search Trees",
booktitle = "Proc. 20th ACM/SIAM Symposium on Discrete Algorithms (SODA)",
pages = "496-505",
year = "2009"
}
2 Adaptive Sorting
~~~~~~~~~~~~~~~~~~~
2.1 A framework for adaptive sorting :READING:
==============================================
@Article{petersson,
author = {Ola Petersson and Alistair Moffat},
title = {A framework for adaptive sorting},
journal = {Discrete Applied Mathematics},
year = {1995},
volume = {59},
pages = {153--179},
}
2.2 A Survey of Adaptive Sorting Algorithms
============================================
@article{estivillcastro92survey,
author = "Vladimir Estivill-Castro and Derick Wood",
title = "A Survey of Adaptive Sorting Algorithms",
journal = "ACM Computing Surveys",
volume = "24",
number = "4",
pages = "441--476",
year = "1992",
url = "citeseer.nj.nec.com/ ... -castro92survey.html"
}
2.3 Best sorting algorithm for nearly sorted lists
===================================================
@Article{cook,
author = {C.R. Cool and D.J. Kim},
title = {Best sorting algorithm for nearly sorted lists},
journal = {Communication of ACM},
year = {1980},
volume = {23},
pages = {620--624},
}
2.4 Compressed Representations of Permutations, and Applications :READING:
==========================================================================
@InProceedings{compressedRepresentationsOfPermutationsAndApplicationsSTACS,
author = {J{\'e}r{\'e}my Barbay and
Gonzalo Navarro},
title = {Compressed Representations of Permutations, and Applications},
booktitle = {STACS},
year = {2009},
pages = {111-122},
ee = {[drops.dagstuhl.de/ ... olltexte/2009/1814}],
crossref = {DBLP:conf/stacs/2009},
bibsource = {DBLP, [dblp.uni-trier.de}],
note = {See also the Technical Report TR/DCC-2008-018.pdf, December 3rd 2008. },
annote = {[www.cs.uwaterloo.ca/ ... onsAndApplications}],
abstract= {
We explore various techniques to compress a permutation pi over n
integers, taking advantage of ordered subsequences in pi, while
supporting its application pi(i) and the application of its inverse
pi^{-1}(i) in small time. Our compression schemes yield several
interesting byproducts, in many cases matching, improving or
extending the best existing results on applications such as the
encoding of a permutation in order to support iterated applications
pi^{k}(i) of it, of integer functions, and of inverted lists and
suffix arrays.}
}
@proceedings{DBLP:conf/stacs/2009,
editor = {Susanne Albers and
Jean-Yves Marion},
title = {26th International Symposium on Theoretical Aspects of Computer
Science, STACS 2009, February 26-28, 2009, Freiburg, Germany,
Proceedings},
booktitle = {STACS},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany Internationales Begegnungs- und Forschungszentrum fuer Informatik
(IBFI), Schloss Dagstuhl, Germany},
series = {Dagstuhl Seminar Proceedings},
volume = {09001},
year = {2009},
isbn = {978-3-939897-09-5},
ee = {[stacs2009.informatik.uni-freiburg.de/ ... proceedings.php}],
bibsource = {DBLP, [dblp.uni-trier.de}]
}
2.5 Encroaching Lists as a measure of presortedness
====================================================
@Article{encroachingListsAsAMeasureOfPresortedness,
author = {S. S. Skiena},
title = {Encroaching lists as a measure of presortedness},
journal = {BIT},
year = 1988,
volume = 28,
number = 4,
pages = {775-784}
}
2.6 Measures of Presortedness and Optimal Sorting Algorithms
=============================================================
@InProceedings{measuresOfPresortednessAndOptimalSortingAlgorithms,
author = {Heikki Mannila},
title = {Measures of Presortedness and Optimal Sorting Algorithms.},
booktitle = {IEEE Trans. Comput.},
pages = {318--325},
year = {1985},
volume = {34},
}
2.7 Smoothsort :READING:
========================
@Article{dijkstra,
author = {Edsger W. Dijkstra},
title = {Smoothsort, an alternative for sorting in situ},
journal = {Science of Computer Programming},
year = {1982},
volume = {1},
number = {3},
pages = {223--233},
month = {May},
}
2.8 Sorting and recognition problems for ordered sets :READING:OPEN:
====================================================================
@article{sortingAndRecognitionProblemsForOrderedSets,
author = {Faigle, U. and Tur\'{a}n, G.},
title = {Sorting and recognition problems for ordered sets},
journal = {SIAM J. Comput.},
volume = {17},
number = {1},
year = {1988},
issn = {0097-5397},
pages = {100--113},
doi = {[dx.doi.org/10.1137/0217007}],
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
}
2.9 Sorting and Selection in Posets :READING:OPEN:
==================================================
@inproceedings{sortingAndSelectionInPosets,
author = {Daskalakis, Constantinos and Karp, Richard M. and Mossel, Elchanan and Riesenfeld, Samantha and Verbin, Elad},
title = {Sorting and selection in posets},
booktitle = {SODA '09: Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms},
year = {2009},
pages = {392--401},
location = {New York, New York},
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
}
2.10 Sorting presorted files :READING:
======================================
@InProceedings{mehlhorn,
author = {Kurt Mehlhorn},
title = {Sorting presorted files},
booktitle = {Proceedings of the 4th GI-Conference on Theoretical Computer Science},
pages = {199--212},
year = {1979},
editor = {Springer},
volume = {67},
series = {Lecture Notes in Computer Science},
}
2.11 Sorting Shuffled Monotone Sequences
=========================================
@article{sortingShuffledMonotoneSequences,
author = {Christos Levcopoulos and
Ola Petersson},
title = {Sorting Shuffled Monotone Sequences},
journal = {Inf. Comput.},
volume = {112},
number = {1},
year = {1994},
pages = {37-50},
bibsource = {DBLP, [dblp.uni-trier.de}]
}
3 Output Sensitive Complexity in Computational Geometry
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3.1 The Ultimate Planar Convex Hull Algorithm? :READING:
========================================================
@article{kirkpatrick,
title = {The Ultimate Planar Convex Hull Algorithm?},
author = {David G. Kirkpatrick and Raimund Seidel},
journal = {SIAM J. Comput.},
year = {1986},
note = {15(1):287--299}
}
3.2 Output-Sensitive Results on Convex Hulls, Extreme Points, and Related Problems :READING:
============================================================================================
Timothy M. Chan: Output-Sensitive Results on Convex Hulls,
Extreme Points, and Related Problems. Discrete & Computational
Geometry 16(4): 369-387 (1996)
3.3 Output-Sensitive Construction of Polytopes in Four Dimensions and Clipped Voronoi Diagrams in Three. :READING:
==================================================================================================================
Timothy M. Chan, Jack Snoeyink, Chee-Keng Yap:
Output-Sensitive Construction of Polytopes in Four Dimensions
and Clipped Voronoi Diagrams in Three. SODA 1995: 282-291
3.4 Instance-optimal geometric algorithms :READING:OPEN:
========================================================
@InProceedings{instanceOptimalGeometricAlgorithmsFOCS,
author = {Peyman Afshani and Jeremy Barbay and Timothy Chan},
title = {Instance-optimal geometric algorithms},
booktitle = {Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS)},
year = 2009,
note = {2009-FOCS-InstanceOptimalGeometricAlgorithms-AfshaniBarbayChan.pdf},
annote = {Preliminary version on [www.cs.uwaterloo.ca/~tmchan/abc_4_09.ps}],
abstract = {We prove the existence of an algorithm A for computing 2-d or 3-d convex hulls that is optimal for every point set in the following sense: for every set S of n points and for every algorithm A' in a certain class C, the maximum running time of A on input s_1,...,s_n is at most a constant factor times the maximum running time of A' on s_1,...,s_n, where the maximum is taken over all permutations s_1,...,s_n of S. In fact, we can establish a stronger property: for every S and A', the maximum running time of A is at most a constant factor times the average running time of A' over all permutations of S. We call algorithms satisfying these properties instance-optimal in the order-oblivious and random-order setting. Such instance-optimal algorithms simultaneously subsume output-sensitive algorithms and distribution-dependent average-case algorithms, and all algorithms that do not take advantage of the order of the input or that assume the input is given in a random order.
The class C under consideration consists of all algorithms in a decision tree model where the tests involve only multilinear functions with a constant number of arguments. To establish an instance-specific lower bound, we deviate from traditional Ben-Or-style proofs and adopt an interesting adversary argument. For 2-d convex hulls, we prove that a version of the well known algorithm by Kirkpatrick and Seidel (1986) or Chan, Snoeyink, and Yap (1995) already attains this lower bound. For 3-d convex hulls, we propose a new algorithm.
To demonstrate the potential of the concept, we further obtain instance-optimal results for a few other standard problems in computational geometry, such as maxima in 2-d and 3-d, orthogonal line segment intersection in 2-d, finding bichromatic L_\infty-close pairs in 2-d, off-line orthogonal range searching in 2-d, off-line dominance reporting in 2-d and 3-d, off-line halfspace range reporting in 2-d and 3-d, and off-line point location in 2-d.
}
}
3.5 Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions :READING:
=========================================================================================
@article{optimalOutputSensitiveConvexHullAlgorithmsInTwoAndThreeDimensions,
author = "Timothy Chan",
title = "Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions",
journal = "GEOMETRY: Discrete \& Computational Geometry",
volume = 16,
year = 1996,
url = "citeseer.ist.psu.edu/ ... e/chan96optimal.html"
}
3.6 Dynamic planar convex hull operations in near-logarithmic amortized time :READING:
======================================================================================
@article{ chan01dynamic,
author = "Timothy M. Chan",
title = "Dynamic planar convex hull operations in near-logarithmic amortized time",
journal = "Journal of the ACM",
volume = "48",
number = "1",
pages = "1--12",
year = "2001",
url = "citeseer.ist.psu.edu/ ... e/chan00dynamic.html"
}
4 Parameterized Complexity
~~~~~~~~~~~~~~~~~~~~~~~~~~~
4.1 Invitation to Fixed-Parameter Algorithms :READING:
======================================================
R. Niedermeier,
Invitation to Fixed-Parameter Algorithms, Oxford, 2006.
[www-fs.informatik.uni-tuebingen.de/ ... ications/habil.ps.gz]
4.2 Parameterized Complexity Theory,
=====================================
@book{parameterizedComplexityTheory,
author = {J. Flum and M. Grohe},
title = {Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)},
year = {2006},
isbn = {3540299521},
publisher = {Springer-Verlag New York, Inc.},
address = {Secaucus, NJ, USA},
}
5 Adaptive Union and Intersection
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
5.1 Adaptive Intersection and t-Threshold Problems :READING:
============================================================
@InProceedings{adaptiveIntersectionAndTThresholdProblems,
author = {J{\'e}r{\'e}my Barbay and Claire Kenyon},
title = {Adaptive Intersection and t-Threshold Problems},
booktitle = {Proceedings of the thirteenth ACM-SIAM Symposium On Discrete Algorithms ({SODA})},
key = {Adaptive Algorithms, Random Lower Bounds},
pages = {390--399},
year = 2002,
month = {January},
organization = {ACM-SIAM},
publisher = {ACM},
postscript = {[www.lri.fr/ ... /intersection.ps.gz}]
}
5.2 Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents :READING:
=====================================================================================================
@InProceedings{adaptiveSearchingInSuccinctlyEncodedBinaryRelationsAndTreeStructuredDocuments,
author = {J{\'e}r{\'e}my Barbay and Alexander Golynski and J. Ian Munro and S. Srinivasa Rao},
title = {Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents},
booktitle = {Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching ({CPM})},
year = 2006,
pages = {24-35},
series = {Lecture Notes in Computer Science (LNCS)},
volume = 4009,
publisher = {Springer-Verlag},
postscript = {[www.cs.uwaterloo.ca/ ... StringsAndTrees.ps}],
pdf = {[www.cs.uwaterloo.ca/ ... ringsAndTrees.pdf}],
note = {(Later extended in \cite{adaptiveSearchingInSuccinctlyEncodedBinaryRelationsAndTreeStructuredDocumentsTCS})},
abstract = { The methods most heavily used by search engines to
answer conjunctive queries on binary relations (such as one
associating keywords with web pages) are based on computing the
intersection of inverted lists stored as sorted arrays and using
variants of binary search. We show that a succinct representation of
the binary relation permits much better results, while using less
space than traditional methods. We apply our results not only to
conjunctive queries on binary relations, but also to queries on
semi-structured documents such as XML documents or file-system
indexes, using a variant of an adaptive algorithm used to solve
conjunctive queries on binary relations.} }
5.3 Adaptive set intersections, unions, and differences :READING:
=================================================================
@InProceedings{dlm,
author = {Erik~D.~Demaine and Alejandro~L{\'o}pez-Ortiz and J.~Ian~Munro},
title = {Adaptive set intersections, unions, and differences},
booktitle = {Proceedings of the $11^{th}$ ACM-SIAM Symposium on Discrete
Algorithms ({SODA})},
pages = {743--752},
year = {2000}
}
5.4 Experiments on Adaptive Set Intersections for Text Retrieval Systems
=========================================================================
@InProceedings{dlmAlenex,
author = {Erik~D.~Demaine and Alejandro~L{\'o}pez-Ortiz and J.~Ian~Munro},
title = {Experiments on Adaptive Set Intersections for Text Retrieval Systems},
booktitle = {Proceedings of the 3rd Workshop on Algorithm Engineering and Experiments,
Lecture Notes in Computer Science},
pages = {5--6},
year = {2001},
address = {Washington DC},
month = {January}
}
5.5 Hyperbolic Dovetailing (can be used for Intersection) :READING:OPEN:
========================================================================
Hyperbolic Dovetailing
Book Series Lecture Notes in Computer Science
Publisher Springer Berlin / Heidelberg
ISSN 0302-9743 (Print) 1611-3349 (Online)
Volume Volume 5757/2009
Book Algorithms - ESA 2009
DOI 10.1007/978-3-642-04128-0
Copyright 2009
ISBN 978-3-642-04127-3
DOI 10.1007/978-3-642-04128-0_46
Pages 516-527
Subject Collection Computer Science
SpringerLink Date Saturday, September 19, 2009
@inproceedings{DBLP:conf/esa/Kirkpatrick09,
author = {David G. Kirkpatrick},
title = {Hyperbolic Dovetailing},
booktitle = {ESA},
year = {2009},
pages = {516-527},
ee = {[dx.doi.org/10.1007/978-3-642-04128-0_46}],
crossref = {DBLP:conf/esa/2009},
bibsource = {DBLP, [dblp.uni-trier.de}]
}
@proceedings{DBLP:conf/esa/2009,
editor = {Amos Fiat and
Peter Sanders},
title = {Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen,
Denmark, September 7-9, 2009. Proceedings},
booktitle = {ESA},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {5757},
year = {2009},
isbn = {978-3-642-04127-3},
ee = {[dx.doi.org/10.1007/978-3-642-04128-0}],
bibsource = {DBLP, [dblp.uni-trier.de}]
}
5.6 Merge Source Coding by Bruno T Avila and Eduardo S. Laber, :READING:OPEN:
=============================================================================
@inproceedings{mergeSourceCoding,
author = {\'{A}vila, Bruno T. and Laber, Eduardo S.},
title = {Merge source coding},
booktitle = {ISIT'09: Proceedings of the 2009 IEEE international conference on Symposium on Information Theory},
year = {2009},
isbn = {978-1-4244-4312-3},
pages = {214--218},
location = {Coex, Seoul, Korea},
publisher = {IEEE Press},
address = {Piscataway, NJ, USA},
}
5.7 Optimality of Randomized Algorithms for the Intersection Problem
=====================================================================
@InProceedings{optimalityOfRandomizedAlgorithmsForTheIntersectionProblem,
author = {J{\'e}r{\'e}my Barbay},
title = {Optimality of Randomized Algorithms for the Intersection Problem},
booktitle = {Proceedings of the Symposium on Stochastic Algorithms, Foundations and Applications (SAGA)},
pages = {26--38},
year = 2003,
editor = {Andreas Albrecht },
volume = {2827 / 2003},
month = {November},
organization = {Lecture Notes in Computer Science (LNCS)},
publisher = {Springer-Verlag Heidelberg},
annote = {[www.springerlink.com/ ... olume=2827&spage=26}]
}
6 Instance Optimality
~~~~~~~~~~~~~~~~~~~~~~
6.1 Optimal aggregation algorithms for middleware, Fagin et al.
================================================================
@inproceedings{ fagin01optimal,
author = "Ronald Fagin and Amnon Lotem and Moni Naor",
title = Optimal aggregation algorithms for middleware",
booktitle = "Symposium on Principles of Database Systems",
year = "2001",
url = [www.almaden.ibm.com/ ... ple/fagin/jcss03.pdf]
}
6.2 Best-fit bin-packing with random order, Kenyon Claire :READING:
===================================================================
@inproceedings{bestFitBinPackingWithRandomOrder,
author = {Kenyon,, Claire},
title = {Best-fit bin-packing with random order},
booktitle = {SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms},
year = {1996},
isbn = {0-89871-366-8},
pages = {359--364},
location = {Atlanta, Georgia, United States},
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
}
7 Competitive Analysis
~~~~~~~~~~~~~~~~~~~~~~~
7.1 Online Computation and Competitive Analysis (Book)
=======================================================
@book{onlineComputationAndCompetitiveAnalysis,
author = {A. Borodin and R. El-Yaniv},
title = {Online Computation and Competitive Analysis},
year = {1998},
publisher = {Cambridge University Press}
}
7.2 On the Separation and Equivalence of Paging Strategies :READING:
====================================================================
On the Separation and Equivalence of Paging Strategies", Spyros
Angelopoulos, Reza Dorrigiv, and A. Lopez-Ortiz. To appear in
Proceedings of 18th ACM-SIAM Symposium on Discrete Algorithms (SODA),
2007.
[cs.uwaterloo.ca/ ... quiv_LRU/index.html]
============
Table of Contents
=================
1 Adaptive Searching
1.1 An Almost Optimal Algorithm for Unbounded Searching
1.2 Splay Trees
1.3 Recursive Dynamic Search Trees
1.4 Optimal "Splay" Trees
2 Adaptive Sorting
2.1 A framework for adaptive sorting
2.2 A Survey of Adaptive Sorting Algorithms
2.3 Best sorting algorithm for nearly sorted lists
2.4 Compressed Representations of Permutations, and Applications
2.5 Encroaching Lists as a measure of presortedness
2.6 Measures of Presortedness and Optimal Sorting Algorithms
2.7 Smoothsort
2.8 Sorting and recognition problems for ordered sets
2.9 Sorting and Selection in Posets
2.10 Sorting presorted files
2.11 Sorting Shuffled Monotone Sequences
3 Output Sensitive Complexity in Computational Geometry
3.1 The Ultimate Planar Convex Hull Algorithm?
3.2 Output-Sensitive Results on Convex Hulls, Extreme Points, and Related Problems
3.3 Output-Sensitive Construction of Polytopes in Four Dimensions and Clipped Voronoi Diagrams in Three.
3.4 Instance-optimal geometric algorithms
3.5 Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions
3.6 Dynamic planar convex hull operations in near-logarithmic amortized time
4 Parameterized Complexity
4.1 Invitation to Fixed-Parameter Algorithms
4.2 Parameterized Complexity Theory,
5 Adaptive Union and Intersection
5.1 Adaptive Intersection and t-Threshold Problems
5.2 Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents
5.3 Adaptive set intersections, unions, and differences
5.4 Experiments on Adaptive Set Intersections for Text Retrieval Systems
5.5 Hyperbolic Dovetailing (can be used for Intersection)
5.6 Merge Source Coding by Bruno T Avila and Eduardo S. Laber,
5.7 Optimality of Randomized Algorithms for the Intersection Problem
6 Instance Optimality
6.1 Optimal aggregation algorithms for middleware, Fagin et al.
6.2 Best-fit bin-packing with random order, Kenyon Claire
7 Competitive Analysis
7.1 Online Computation and Competitive Analysis (Book)
7.2 On the Separation and Equivalence of Paging Strategies
1 Adaptive Searching
~~~~~~~~~~~~~~~~~~~~~
1.1 An Almost Optimal Algorithm for Unbounded Searching :READING:
=================================================================
J. L. Bentley and A. C.-C. Yao. "An Almost Optimal Algorithm
for Unbounded Searching." Information Processing Letters,
Vol. 5, pp. 82-87, 1976.
@article{anAlmostOptimalAlgorithmForUnboundedSearching,
author = {Jon Louis Bentley and Andrew Chi-Chih Yao},
title = {An almost optimal algorithm for unbounded searching},
journal = {Information processing letters},
year = {1976},
OPTkey = {},
volume = {5},
number = {3},
pages = {82--87},
OPTmonth = {},
OPTnote = {},
OPTannote = {}
}
1.2 Splay Trees :READING:
=========================
@article{selfAdjustingBinarySearchTrees,
author = {Daniel Dominic Sleator and Robert Endre Tarjan},
title = {Self-adjusting binary search trees},
journal = {J. ACM},
volume = 32,
number = 3,
year = 1985,
issn = {0004-5411},
pages = {652--686},
doi = {[doi.acm.org/10.1145/3828.3835}],
publisher = {ACM},
address = {New York, NY, USA},
}
1.3 Recursive Dynamic Search Trees :READING:OPEN:
=================================================
@article{dynamicOptimalityAlmost,
author = {Erik D. Demaine and Dion Harmon and John Iacono and Mihai P{\v a}tra{\c s}cu},
title = {Dynamic Optimality---Almost},
journal = {SIAM J. Comput.},
volume = 37,
number = 1,
year = 2007,
issn = {0097-5397},
pages = {240--251},
doi = {[dx.doi.org/10.1137/S0097539705447347}],
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
}
1.4 Optimal "Splay" Trees :READING:OPEN:
========================================
@inproceedings{theGeometryOfBinarySearchTrees,
author = "Erik D. Demaine and Dion Harmon and John Iacono and Daniel Kane and Mihai P{\v a}tra{\c s}cu",
title = "The Geometry of Binary Search Trees",
booktitle = "Proc. 20th ACM/SIAM Symposium on Discrete Algorithms (SODA)",
pages = "496-505",
year = "2009"
}
2 Adaptive Sorting
~~~~~~~~~~~~~~~~~~~
2.1 A framework for adaptive sorting :READING:
==============================================
@Article{petersson,
author = {Ola Petersson and Alistair Moffat},
title = {A framework for adaptive sorting},
journal = {Discrete Applied Mathematics},
year = {1995},
volume = {59},
pages = {153--179},
}
2.2 A Survey of Adaptive Sorting Algorithms
============================================
@article{estivillcastro92survey,
author = "Vladimir Estivill-Castro and Derick Wood",
title = "A Survey of Adaptive Sorting Algorithms",
journal = "ACM Computing Surveys",
volume = "24",
number = "4",
pages = "441--476",
year = "1992",
url = "citeseer.nj.nec.com/ ... -castro92survey.html"
}
2.3 Best sorting algorithm for nearly sorted lists
===================================================
@Article{cook,
author = {C.R. Cool and D.J. Kim},
title = {Best sorting algorithm for nearly sorted lists},
journal = {Communication of ACM},
year = {1980},
volume = {23},
pages = {620--624},
}
2.4 Compressed Representations of Permutations, and Applications :READING:
==========================================================================
@InProceedings{compressedRepresentationsOfPermutationsAndApplicationsSTACS,
author = {J{\'e}r{\'e}my Barbay and
Gonzalo Navarro},
title = {Compressed Representations of Permutations, and Applications},
booktitle = {STACS},
year = {2009},
pages = {111-122},
ee = {[drops.dagstuhl.de/ ... olltexte/2009/1814}],
crossref = {DBLP:conf/stacs/2009},
bibsource = {DBLP, [dblp.uni-trier.de}],
note = {See also the Technical Report TR/DCC-2008-018.pdf, December 3rd 2008. },
annote = {[www.cs.uwaterloo.ca/ ... onsAndApplications}],
abstract= {
We explore various techniques to compress a permutation pi over n
integers, taking advantage of ordered subsequences in pi, while
supporting its application pi(i) and the application of its inverse
pi^{-1}(i) in small time. Our compression schemes yield several
interesting byproducts, in many cases matching, improving or
extending the best existing results on applications such as the
encoding of a permutation in order to support iterated applications
pi^{k}(i) of it, of integer functions, and of inverted lists and
suffix arrays.}
}
@proceedings{DBLP:conf/stacs/2009,
editor = {Susanne Albers and
Jean-Yves Marion},
title = {26th International Symposium on Theoretical Aspects of Computer
Science, STACS 2009, February 26-28, 2009, Freiburg, Germany,
Proceedings},
booktitle = {STACS},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany Internationales Begegnungs- und Forschungszentrum fuer Informatik
(IBFI), Schloss Dagstuhl, Germany},
series = {Dagstuhl Seminar Proceedings},
volume = {09001},
year = {2009},
isbn = {978-3-939897-09-5},
ee = {[stacs2009.informatik.uni-freiburg.de/ ... proceedings.php}],
bibsource = {DBLP, [dblp.uni-trier.de}]
}
2.5 Encroaching Lists as a measure of presortedness
====================================================
@Article{encroachingListsAsAMeasureOfPresortedness,
author = {S. S. Skiena},
title = {Encroaching lists as a measure of presortedness},
journal = {BIT},
year = 1988,
volume = 28,
number = 4,
pages = {775-784}
}
2.6 Measures of Presortedness and Optimal Sorting Algorithms
=============================================================
@InProceedings{measuresOfPresortednessAndOptimalSortingAlgorithms,
author = {Heikki Mannila},
title = {Measures of Presortedness and Optimal Sorting Algorithms.},
booktitle = {IEEE Trans. Comput.},
pages = {318--325},
year = {1985},
volume = {34},
}
2.7 Smoothsort :READING:
========================
@Article{dijkstra,
author = {Edsger W. Dijkstra},
title = {Smoothsort, an alternative for sorting in situ},
journal = {Science of Computer Programming},
year = {1982},
volume = {1},
number = {3},
pages = {223--233},
month = {May},
}
2.8 Sorting and recognition problems for ordered sets :READING:OPEN:
====================================================================
@article{sortingAndRecognitionProblemsForOrderedSets,
author = {Faigle, U. and Tur\'{a}n, G.},
title = {Sorting and recognition problems for ordered sets},
journal = {SIAM J. Comput.},
volume = {17},
number = {1},
year = {1988},
issn = {0097-5397},
pages = {100--113},
doi = {[dx.doi.org/10.1137/0217007}],
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
}
2.9 Sorting and Selection in Posets :READING:OPEN:
==================================================
@inproceedings{sortingAndSelectionInPosets,
author = {Daskalakis, Constantinos and Karp, Richard M. and Mossel, Elchanan and Riesenfeld, Samantha and Verbin, Elad},
title = {Sorting and selection in posets},
booktitle = {SODA '09: Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms},
year = {2009},
pages = {392--401},
location = {New York, New York},
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
}
2.10 Sorting presorted files :READING:
======================================
@InProceedings{mehlhorn,
author = {Kurt Mehlhorn},
title = {Sorting presorted files},
booktitle = {Proceedings of the 4th GI-Conference on Theoretical Computer Science},
pages = {199--212},
year = {1979},
editor = {Springer},
volume = {67},
series = {Lecture Notes in Computer Science},
}
2.11 Sorting Shuffled Monotone Sequences
=========================================
@article{sortingShuffledMonotoneSequences,
author = {Christos Levcopoulos and
Ola Petersson},
title = {Sorting Shuffled Monotone Sequences},
journal = {Inf. Comput.},
volume = {112},
number = {1},
year = {1994},
pages = {37-50},
bibsource = {DBLP, [dblp.uni-trier.de}]
}
3 Output Sensitive Complexity in Computational Geometry
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3.1 The Ultimate Planar Convex Hull Algorithm? :READING:
========================================================
@article{kirkpatrick,
title = {The Ultimate Planar Convex Hull Algorithm?},
author = {David G. Kirkpatrick and Raimund Seidel},
journal = {SIAM J. Comput.},
year = {1986},
note = {15(1):287--299}
}
3.2 Output-Sensitive Results on Convex Hulls, Extreme Points, and Related Problems :READING:
============================================================================================
Timothy M. Chan: Output-Sensitive Results on Convex Hulls,
Extreme Points, and Related Problems. Discrete & Computational
Geometry 16(4): 369-387 (1996)
3.3 Output-Sensitive Construction of Polytopes in Four Dimensions and Clipped Voronoi Diagrams in Three. :READING:
==================================================================================================================
Timothy M. Chan, Jack Snoeyink, Chee-Keng Yap:
Output-Sensitive Construction of Polytopes in Four Dimensions
and Clipped Voronoi Diagrams in Three. SODA 1995: 282-291
3.4 Instance-optimal geometric algorithms :READING:OPEN:
========================================================
@InProceedings{instanceOptimalGeometricAlgorithmsFOCS,
author = {Peyman Afshani and Jeremy Barbay and Timothy Chan},
title = {Instance-optimal geometric algorithms},
booktitle = {Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS)},
year = 2009,
note = {2009-FOCS-InstanceOptimalGeometricAlgorithms-AfshaniBarbayChan.pdf},
annote = {Preliminary version on [www.cs.uwaterloo.ca/~tmchan/abc_4_09.ps}],
abstract = {We prove the existence of an algorithm A for computing 2-d or 3-d convex hulls that is optimal for every point set in the following sense: for every set S of n points and for every algorithm A' in a certain class C, the maximum running time of A on input s_1,...,s_n is at most a constant factor times the maximum running time of A' on s_1,...,s_n, where the maximum is taken over all permutations s_1,...,s_n of S. In fact, we can establish a stronger property: for every S and A', the maximum running time of A is at most a constant factor times the average running time of A' over all permutations of S. We call algorithms satisfying these properties instance-optimal in the order-oblivious and random-order setting. Such instance-optimal algorithms simultaneously subsume output-sensitive algorithms and distribution-dependent average-case algorithms, and all algorithms that do not take advantage of the order of the input or that assume the input is given in a random order.
The class C under consideration consists of all algorithms in a decision tree model where the tests involve only multilinear functions with a constant number of arguments. To establish an instance-specific lower bound, we deviate from traditional Ben-Or-style proofs and adopt an interesting adversary argument. For 2-d convex hulls, we prove that a version of the well known algorithm by Kirkpatrick and Seidel (1986) or Chan, Snoeyink, and Yap (1995) already attains this lower bound. For 3-d convex hulls, we propose a new algorithm.
To demonstrate the potential of the concept, we further obtain instance-optimal results for a few other standard problems in computational geometry, such as maxima in 2-d and 3-d, orthogonal line segment intersection in 2-d, finding bichromatic L_\infty-close pairs in 2-d, off-line orthogonal range searching in 2-d, off-line dominance reporting in 2-d and 3-d, off-line halfspace range reporting in 2-d and 3-d, and off-line point location in 2-d.
}
}
3.5 Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions :READING:
=========================================================================================
@article{optimalOutputSensitiveConvexHullAlgorithmsInTwoAndThreeDimensions,
author = "Timothy Chan",
title = "Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions",
journal = "GEOMETRY: Discrete \& Computational Geometry",
volume = 16,
year = 1996,
url = "citeseer.ist.psu.edu/ ... e/chan96optimal.html"
}
3.6 Dynamic planar convex hull operations in near-logarithmic amortized time :READING:
======================================================================================
@article{ chan01dynamic,
author = "Timothy M. Chan",
title = "Dynamic planar convex hull operations in near-logarithmic amortized time",
journal = "Journal of the ACM",
volume = "48",
number = "1",
pages = "1--12",
year = "2001",
url = "citeseer.ist.psu.edu/ ... e/chan00dynamic.html"
}
4 Parameterized Complexity
~~~~~~~~~~~~~~~~~~~~~~~~~~~
4.1 Invitation to Fixed-Parameter Algorithms :READING:
======================================================
R. Niedermeier,
Invitation to Fixed-Parameter Algorithms, Oxford, 2006.
[www-fs.informatik.uni-tuebingen.de/ ... ications/habil.ps.gz]
4.2 Parameterized Complexity Theory,
=====================================
@book{parameterizedComplexityTheory,
author = {J. Flum and M. Grohe},
title = {Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)},
year = {2006},
isbn = {3540299521},
publisher = {Springer-Verlag New York, Inc.},
address = {Secaucus, NJ, USA},
}
5 Adaptive Union and Intersection
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
5.1 Adaptive Intersection and t-Threshold Problems :READING:
============================================================
@InProceedings{adaptiveIntersectionAndTThresholdProblems,
author = {J{\'e}r{\'e}my Barbay and Claire Kenyon},
title = {Adaptive Intersection and t-Threshold Problems},
booktitle = {Proceedings of the thirteenth ACM-SIAM Symposium On Discrete Algorithms ({SODA})},
key = {Adaptive Algorithms, Random Lower Bounds},
pages = {390--399},
year = 2002,
month = {January},
organization = {ACM-SIAM},
publisher = {ACM},
postscript = {[www.lri.fr/ ... /intersection.ps.gz}]
}
5.2 Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents :READING:
=====================================================================================================
@InProceedings{adaptiveSearchingInSuccinctlyEncodedBinaryRelationsAndTreeStructuredDocuments,
author = {J{\'e}r{\'e}my Barbay and Alexander Golynski and J. Ian Munro and S. Srinivasa Rao},
title = {Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents},
booktitle = {Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching ({CPM})},
year = 2006,
pages = {24-35},
series = {Lecture Notes in Computer Science (LNCS)},
volume = 4009,
publisher = {Springer-Verlag},
postscript = {[www.cs.uwaterloo.ca/ ... StringsAndTrees.ps}],
pdf = {[www.cs.uwaterloo.ca/ ... ringsAndTrees.pdf}],
note = {(Later extended in \cite{adaptiveSearchingInSuccinctlyEncodedBinaryRelationsAndTreeStructuredDocumentsTCS})},
abstract = { The methods most heavily used by search engines to
answer conjunctive queries on binary relations (such as one
associating keywords with web pages) are based on computing the
intersection of inverted lists stored as sorted arrays and using
variants of binary search. We show that a succinct representation of
the binary relation permits much better results, while using less
space than traditional methods. We apply our results not only to
conjunctive queries on binary relations, but also to queries on
semi-structured documents such as XML documents or file-system
indexes, using a variant of an adaptive algorithm used to solve
conjunctive queries on binary relations.} }
5.3 Adaptive set intersections, unions, and differences :READING:
=================================================================
@InProceedings{dlm,
author = {Erik~D.~Demaine and Alejandro~L{\'o}pez-Ortiz and J.~Ian~Munro},
title = {Adaptive set intersections, unions, and differences},
booktitle = {Proceedings of the $11^{th}$ ACM-SIAM Symposium on Discrete
Algorithms ({SODA})},
pages = {743--752},
year = {2000}
}
5.4 Experiments on Adaptive Set Intersections for Text Retrieval Systems
=========================================================================
@InProceedings{dlmAlenex,
author = {Erik~D.~Demaine and Alejandro~L{\'o}pez-Ortiz and J.~Ian~Munro},
title = {Experiments on Adaptive Set Intersections for Text Retrieval Systems},
booktitle = {Proceedings of the 3rd Workshop on Algorithm Engineering and Experiments,
Lecture Notes in Computer Science},
pages = {5--6},
year = {2001},
address = {Washington DC},
month = {January}
}
5.5 Hyperbolic Dovetailing (can be used for Intersection) :READING:OPEN:
========================================================================
Hyperbolic Dovetailing
Book Series Lecture Notes in Computer Science
Publisher Springer Berlin / Heidelberg
ISSN 0302-9743 (Print) 1611-3349 (Online)
Volume Volume 5757/2009
Book Algorithms - ESA 2009
DOI 10.1007/978-3-642-04128-0
Copyright 2009
ISBN 978-3-642-04127-3
DOI 10.1007/978-3-642-04128-0_46
Pages 516-527
Subject Collection Computer Science
SpringerLink Date Saturday, September 19, 2009
@inproceedings{DBLP:conf/esa/Kirkpatrick09,
author = {David G. Kirkpatrick},
title = {Hyperbolic Dovetailing},
booktitle = {ESA},
year = {2009},
pages = {516-527},
ee = {[dx.doi.org/10.1007/978-3-642-04128-0_46}],
crossref = {DBLP:conf/esa/2009},
bibsource = {DBLP, [dblp.uni-trier.de}]
}
@proceedings{DBLP:conf/esa/2009,
editor = {Amos Fiat and
Peter Sanders},
title = {Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen,
Denmark, September 7-9, 2009. Proceedings},
booktitle = {ESA},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {5757},
year = {2009},
isbn = {978-3-642-04127-3},
ee = {[dx.doi.org/10.1007/978-3-642-04128-0}],
bibsource = {DBLP, [dblp.uni-trier.de}]
}
5.6 Merge Source Coding by Bruno T Avila and Eduardo S. Laber, :READING:OPEN:
=============================================================================
@inproceedings{mergeSourceCoding,
author = {\'{A}vila, Bruno T. and Laber, Eduardo S.},
title = {Merge source coding},
booktitle = {ISIT'09: Proceedings of the 2009 IEEE international conference on Symposium on Information Theory},
year = {2009},
isbn = {978-1-4244-4312-3},
pages = {214--218},
location = {Coex, Seoul, Korea},
publisher = {IEEE Press},
address = {Piscataway, NJ, USA},
}
5.7 Optimality of Randomized Algorithms for the Intersection Problem
=====================================================================
@InProceedings{optimalityOfRandomizedAlgorithmsForTheIntersectionProblem,
author = {J{\'e}r{\'e}my Barbay},
title = {Optimality of Randomized Algorithms for the Intersection Problem},
booktitle = {Proceedings of the Symposium on Stochastic Algorithms, Foundations and Applications (SAGA)},
pages = {26--38},
year = 2003,
editor = {Andreas Albrecht },
volume = {2827 / 2003},
month = {November},
organization = {Lecture Notes in Computer Science (LNCS)},
publisher = {Springer-Verlag Heidelberg},
annote = {[www.springerlink.com/ ... olume=2827&spage=26}]
}
6 Instance Optimality
~~~~~~~~~~~~~~~~~~~~~~
6.1 Optimal aggregation algorithms for middleware, Fagin et al.
================================================================
@inproceedings{ fagin01optimal,
author = "Ronald Fagin and Amnon Lotem and Moni Naor",
title = Optimal aggregation algorithms for middleware",
booktitle = "Symposium on Principles of Database Systems",
year = "2001",
url = [www.almaden.ibm.com/ ... ple/fagin/jcss03.pdf]
}
6.2 Best-fit bin-packing with random order, Kenyon Claire :READING:
===================================================================
@inproceedings{bestFitBinPackingWithRandomOrder,
author = {Kenyon,, Claire},
title = {Best-fit bin-packing with random order},
booktitle = {SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms},
year = {1996},
isbn = {0-89871-366-8},
pages = {359--364},
location = {Atlanta, Georgia, United States},
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
}
7 Competitive Analysis
~~~~~~~~~~~~~~~~~~~~~~~
7.1 Online Computation and Competitive Analysis (Book)
=======================================================
@book{onlineComputationAndCompetitiveAnalysis,
author = {A. Borodin and R. El-Yaniv},
title = {Online Computation and Competitive Analysis},
year = {1998},
publisher = {Cambridge University Press}
}
7.2 On the Separation and Equivalence of Paging Strategies :READING:
====================================================================
On the Separation and Equivalence of Paging Strategies", Spyros
Angelopoulos, Reza Dorrigiv, and A. Lopez-Ortiz. To appear in
Proceedings of 18th ACM-SIAM Symposium on Discrete Algorithms (SODA),
2007.
[cs.uwaterloo.ca/ ... quiv_LRU/index.html]
Adaptive Sorting and Coding: Merge Sort and Permutations
2
Jérémy Barbay 30 Mar 201030/03/10 a las 17:59 hrs.2010-03-30 17:59:30
Adaptive Sorting and Coding: Merge Sort and Permutations
========================================================
Author: Jérémy Barbay
Date: 2010-03-30 21:59:40 XXX
<2010-03-30 Tue 14:30-16:00>
1) Merge Sort
1. O(n \lg n)
2. O(n \lg \rho)
3. O(n H(Runs))
2) Adaptivity and Compression
1. Wavelet Tree
2. Compressed Wavelet Tree
3. Compression of Permutations
3) Other types of adaptive sorting
1. Insertion Sort
2. SUS, SMS
3. Adaptive Analysis of HeapSort?
1 References: (Many)
~~~~~~~~~~~~~~~~~~~~~
@InProceedings{mehlhorn,
author = {Kurt Mehlhorn},
title = {Sorting presorted files},
booktitle = {Proceedings of the 4th GI-Conference on Theoretical Computer Science},
pages = {199--212},
year = {1979},
editor = {Springer},
volume = {67},
series = {Lecture Notes in Computer Science},
}
@Article{encroachingListsAsAMeasureOfPresortedness,
author = {S. S. Skiena},
title = {Encroaching lists as a measure of presortedness},
journal = {BIT},
year = 1988,
volume = 28,
number = 4,
pages = {775-784}
}
@article{sortingShuffledMonotoneSequences,
author = {Christos Levcopoulos and
Ola Petersson},
title = {Sorting Shuffled Monotone Sequences},
journal = {Inf. Comput.},
volume = {112},
number = {1},
year = {1994},
pages = {37-50},
bibsource = {DBLP, [dblp.uni-trier.de}]
}
@Article{cook,
author = {C.R. Cool and D.J. Kim},
title = {Best sorting algorithm for nearly sorted lists},
journal = {Communication of ACM},
year = {1980},
volume = {23},
pages = {620--624},
}
@Article{dijkstra,
author = {Edsger W. Dijkstra},
title = {Smoothsort, an alternative for sorting in situ},
journal = {Science of Computer Programming},
year = {1982},
volume = {1},
number = {3},
pages = {223--233},
month = {May},
}
@InProceedings{measuresOfPresortednessAndOptimalSortingAlgorithms,
author = {Heikki Mannila},
title = {Measures of Presortedness and Optimal Sorting Algorithms.},
booktitle = {IEEE Trans. Comput.},
pages = {318--325},
year = {1985},
volume = {34},
}
========================================================
Author: Jérémy Barbay
Date: 2010-03-30 21:59:40 XXX
<2010-03-30 Tue 14:30-16:00>
1) Merge Sort
1. O(n \lg n)
2. O(n \lg \rho)
3. O(n H(Runs))
2) Adaptivity and Compression
1. Wavelet Tree
2. Compressed Wavelet Tree
3. Compression of Permutations
3) Other types of adaptive sorting
1. Insertion Sort
2. SUS, SMS
3. Adaptive Analysis of HeapSort?
1 References: (Many)
~~~~~~~~~~~~~~~~~~~~~
@InProceedings{mehlhorn,
author = {Kurt Mehlhorn},
title = {Sorting presorted files},
booktitle = {Proceedings of the 4th GI-Conference on Theoretical Computer Science},
pages = {199--212},
year = {1979},
editor = {Springer},
volume = {67},
series = {Lecture Notes in Computer Science},
}
@Article{encroachingListsAsAMeasureOfPresortedness,
author = {S. S. Skiena},
title = {Encroaching lists as a measure of presortedness},
journal = {BIT},
year = 1988,
volume = 28,
number = 4,
pages = {775-784}
}
@article{sortingShuffledMonotoneSequences,
author = {Christos Levcopoulos and
Ola Petersson},
title = {Sorting Shuffled Monotone Sequences},
journal = {Inf. Comput.},
volume = {112},
number = {1},
year = {1994},
pages = {37-50},
bibsource = {DBLP, [dblp.uni-trier.de}]
}
@Article{cook,
author = {C.R. Cool and D.J. Kim},
title = {Best sorting algorithm for nearly sorted lists},
journal = {Communication of ACM},
year = {1980},
volume = {23},
pages = {620--624},
}
@Article{dijkstra,
author = {Edsger W. Dijkstra},
title = {Smoothsort, an alternative for sorting in situ},
journal = {Science of Computer Programming},
year = {1982},
volume = {1},
number = {3},
pages = {223--233},
month = {May},
}
@InProceedings{measuresOfPresortednessAndOptimalSortingAlgorithms,
author = {Heikki Mannila},
title = {Measures of Presortedness and Optimal Sorting Algorithms.},
booktitle = {IEEE Trans. Comput.},
pages = {318--325},
year = {1985},
volume = {34},
}
Searching and Coding: Unbounded Search and Delta Codes
Jérémy Barbay 24 Mar 201024/03/10 a las 19:39 hrs.2010-03-24 19:39:24
<2010-03-25 Thu 14:30-16:00>
1) What did we see
1. Parametrisation
2. Tarea: Complexity of the Disk Pile Pb?
3. Formalisation of Adaptive Algorithms
2) A basic problem: Searching in a sorted array
1. Binary Search
2. Doubling Search
3. Unbounded Search
3) Extension: Searching is coding
1. Unary Code
2. Binary Code
3. Delta Code
***** References:
J. L. Bentley and A. C.-C. Yao. "An Almost Optimal Algorithm
for Unbounded Searching." Information Processing Letters,
Vol. 5, pp. 82-87, 1976.
@article{anAlmostOptimalAlgorithmForUnboundedSearching,
author = {Jon Louis Bentley and Andrew Chi-Chih Yao},
title = {An almost optimal algorithm for unbounded searching},
journal = {Information processing letters},
year = {1976},
OPTkey = {},
volume = {5},
number = {3},
pages = {82--87},
OPTmonth = {},
OPTnote = {},
OPTannote = {}
}
1) What did we see
1. Parametrisation
2. Tarea: Complexity of the Disk Pile Pb?
3. Formalisation of Adaptive Algorithms
2) A basic problem: Searching in a sorted array
1. Binary Search
2. Doubling Search
3. Unbounded Search
3) Extension: Searching is coding
1. Unary Code
2. Binary Code
3. Delta Code
***** References:
J. L. Bentley and A. C.-C. Yao. "An Almost Optimal Algorithm
for Unbounded Searching." Information Processing Letters,
Vol. 5, pp. 82-87, 1976.
@article{anAlmostOptimalAlgorithmForUnboundedSearching,
author = {Jon Louis Bentley and Andrew Chi-Chih Yao},
title = {An almost optimal algorithm for unbounded searching},
journal = {Information processing letters},
year = {1976},
OPTkey = {},
volume = {5},
number = {3},
pages = {82--87},
OPTmonth = {},
OPTnote = {},
OPTannote = {}
}
Introduccion
Jérémy Barbay 24 Mar 201024/03/10 a las 19:38 hrs.2010-03-24 19:38:24
<2010-03-23 Tue 14:30-16:00>
1) Who are we?
1. Who am I
2. Who are you
3. What is this course about.
2) A first Basic Problem
1. Torre de Hanoi
2. Disk Pile Problem
3. Parameterized Analysis
TAREA: what is the optimal complexity?
- for n fixed
- for n,h fixed
- for h,n_1,\ldots,n_h fixed
3) Organisation of the course
1. Calendar of the semester
+ Part 1
- Seminar of Essential paper
- Personal Survey
+ Part 2
- Seminar of Open Ended papers
- Personal Essay
2. Evaluation
1) Who are we?
1. Who am I
2. Who are you
3. What is this course about.
2) A first Basic Problem
1. Torre de Hanoi
2. Disk Pile Problem
3. Parameterized Analysis
TAREA: what is the optimal complexity?
- for n fixed
- for n,h fixed
- for h,n_1,\ldots,n_h fixed
3) Organisation of the course
1. Calendar of the semester
+ Part 1
- Seminar of Essential paper
- Personal Survey
+ Part 2
- Seminar of Open Ended papers
- Personal Essay
2. Evaluation
