|
Analysis of Algorithms and Information Theory
MSRI, California, USA
|
|
|
|
Analysis of Algorithms and Information Theory
MSRI, California, USA
|
|
This MSRI graduate course is on analysis of algorithms and information theory.
The interplay between IT and CS dates back to the founding father of information theory, Claude E. Shannon. Ever since Shannon's work on both information theory and computer science, the research in the interplay between IT and CS has continued and expanded in a positive manner. Notably, A. Lempel (a computer scientist) and J. Ziv (an information theorist) worked together in the later part of the 1970s in order to develop compression algorithms widely referred to as Lempel-Ziv algorithms, which count amongst the most popular algorithms for lossless data compression. Recently the analysis of algorithm group (e.g., P. Flajolet, P. Jacquet, H. Prodinger, W. Szpankowski, B. Vallee) known also as AofA group has contributed to solutions of some open problem in the area.
This graduate course has three components. In the first series of lectures Philippe Flajolet (INRIA, French Academy of Science) will establish foundation of analytic combinatorics. He will talk about generating functions, complex asymptotics (e.g., singularity analysis), and limit laws in relation to random discrete structures. Then Gadiel Seroussi and Mercelo Weinberger (HPL, Palo Alto) will introduce basic concepts of information theory such as entropy and redundancy. Some universal source coding algorithms will be discussed and connection to algorithmics will be established. Finally, Wojtek Szpankowski (Purdue U.) will use the analytic tools introduced by Flajolet and apply them to source coding algorithms discussed by Seroussi and Weinberger. In particular, he will analyze the worst case minimax redundancy for memoryless sources and and Lempel-Ziv 77 algorithm. In addition, various pattern matching algorithms on strings and their analyses will be discussed.
Teaching Assistance: Mark Ward (Purdue U.)