A BRICS Mini-Course
May 26, 27 and 29, June 2 and 3, 1998
Lectures by
Arne Andersson
LTH (Lund Institute of Technology), Sweden
This course will deal with data structures and algorithms for sorting and searching. An important issue to cover (and to discuss through the course) is: what is a reasonable model of computation for designing fast algorithms? During the course it will be shown that, when viewing data as binary strings stored in memory cells, we can derive very efficient algorithms, both in theory and practice.
The course will include some assignments. We will also try to create some lively, inspiring, discussions.
A. Andersson, P.B. Miltersen, and M. Thorup. Fusion trees can be implemented with AC0 instructions. to appear in Theoretical Computer Science.
A. Andersson and S. Nilsson. A new efficient radix sort. In Proc. 35th Annual IEEE Symposium on Foundations of Computer Science, pages 714721. IEEE Computer Society Press, 1994.
A. Andersson. Sublogarithmic searching without multiplications. In Proc. 36th IEEE Symposium on Foundations of Computer Science, pages 655-663. ACM Press, 1995.
A. Andersson. Faster deterministic sorting and searching in linear space. In Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996.
A. Andersson and O. Peterson. Approximate indexed lists. to appear in Journal of Algorithms. Preliminary version appeared in Proc. SODA`95.
A. Andersson and Th. Ottmann. New tight bounds on uniquely represented dictionaries. SIAM Journal of Computing, 24(5):1091-1103, 1995. A preliminary version appears in Proc. 32nd IEEE Sympos. Foundations of Computer Science, IEEE Computer Society Press, 1991.
A. Andersson and Ch. Mattsson. Dynamic interpolation search in o(loglogn) time. In Proc. 20th International Colloquium on Automata, Languages and Programming. Springer Verlag, 1993.
A. Andersson and S. Nilsson. Faster searching in tries and quadtrees, an analysis of level compression. In Proc. 2nd Annual European Symposium on Algorithms, pages 82-93. Springer Verlag, 1994.
A. Andersson and S. Nilsson. Implementing radixsort. In Proc.Workshop on Algorithm Engineering, WAE '97, 1997.
A. Andersson and S. Nilsson. Improved behaviour of tries by adaptive branching.Information Processing Letters, 46:295-300, 1993.