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"
}
| Última Modificación | 1 Abr 201001/04/10 a las 20:44 hrs.2010-04-01 20:44:01 |
|---|---|
| Vistas Únicas | 0 |
| Compartir |
