Informatics Seminar (Perspective in Informatics 4B) 2011 - 2012
October 13 (Thu), 14:45 - 16:15
- Place:
Lecture Hall 1, Faculty of Engineering Bldg. No.10, Main Campus
- Title:
Designing Algorithms with Limited Work Space
- Speaker:
Tetsuo Asano (JAIST)
- Abstract:
Recent progress in computer systems has provided programmers with virtually unlimited amount of work storage for their programs. This leads to space-inefficient programs that use too much storage and become too slow if sufficiently large memory is not available. Thus, I believe that space-efficient algorithms or memory-constrained algorithms deserve more attention.
Constant-work-space algorithms have been extensively studied under a different name, log-space algorithms. Input data are given on a read-only array of $n$ elements, each having O(log n) bits, and work space is limited to O(log n) bits, in other words, a constant number of pointers and counters, each of O(log n) bits. This memory constraint in the log-space algorithms may be too severe for practice applications. For problems related to an image with n pixels, for example, it is quite reasonable to use work space of the order of square root of n, which amounts to a constant number of rows and columns.
I will start my talk with a simple algorithm for detecting a cycle in a graph using only some constant amount of work space (more exactly, O(log n) bits in total) and then its applications. Then, I will introduce some paradigms for designing such memory-constrained algorithms and their applications to interesting problems including those in computational geometry and computer vision.
Kyoto University
> Graduate School of Informatics
> International Courses
> Informatics Seminar