Share  Bookmark

 Download from


PURE Aarhus University via PURE Aarhus University (Contribution for newspaper or weekly magazine, 2017)

 Funded by

[1] A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Communications of the ACM, 31:11161127, 1988.
[2] G. S. Brodal. Worstcase efficient priority queues. In Proc. 7th ACM/SIAM Symposium on Discrete Algorithms, SODA '96, pages 5258, 1996.
[3] G. S. Brodal and R. Fagerberg. Lower bounds for external memory dictionaries. In Proc. 14th ACM/SIAM Symposium on Discrete Algorithms, SODA '03, pages 546554, 2003.
[4] J. Brody, A. Chakrabarti, R. Kondapally, D. P. Woodruff, and G. Yaroslavtsev. Beyond set disjointness: The communication complexity of finding the intersection. In Proc. 2014 ACM Symposium on Principles of Distributed Computing, PODC '14, pages 106113, 2014.
[5] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. The MIT Press, Cambridge, Mass., 1990.
[6] R. Fadel, K. V. Jakobsen, J. Katajainen, and J. Teuhola. Heaps and heapsort on secondary storage. Theoretical Computer Science, 220(2):345362, June 1999.
[7] M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596615, July 1987.
[8] Y. Han. Deterministic sorting in o(nlog log n) time and linear space. In Proc. 34th ACM Symposium on Theory of Computation, STOC '02, pages 602608, 2002.
[9] Y. Han and M. Thorup. Integer sorting in O(n√lg lg n) expected time and linear space. In Proc. 43rd IEEE Symposium on Foundations of Computer Science, pages 135144, 2002.
[10] J. Iacono and M. Paˇtra¸scu. Using hashing to solve the dictionary problem (in external memory). In Proc. 23rd ACM/SIAM Symposium on Discrete Algorithms, pages 570582, 2012.