From flajolet@blagny.inria.fr Mon May 3 12:44:01 2004 X-UIDL: 4ab004823d8f5ee5056a4c2652788879 Return-Path: Received: from mailslot.cs.purdue.edu (IDENT:0@mailslot.cs.purdue.edu [128.10.19.22]) by lukasz.cs.purdue.edu (8.12.9/8.12.9/PURDUE_CS-2.0) with ESMTP id i43Hi0GG005107 for ; Mon, 3 May 2004 12:44:00 -0500 (EST) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by mailslot.cs.purdue.edu (8.12.9/8.12.9/PURDUE_CS-2.0) with ESMTP id i43HhwLk022851 for ; Mon, 3 May 2004 12:43:58 -0500 (EST) Received: from nuits.inria.fr (nuits.inria.fr [128.93.8.31]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i43HhpEV011668; Mon, 3 May 2004 19:43:51 +0200 Received: by nuits.inria.fr (Postfix, from userid 20032) id 649D340BF7; Mon, 3 May 2004 13:43:51 -0400 (EDT) From: Philippe Flajolet MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <16534.34007.349849.230139@nuits.inria.fr> Date: Mon, 3 May 2004 19:43:51 +0200 To: Wojciech Szpankowski Cc: Philippe.Flajolet@inria.fr, marcelo@hpl.hp.com, seroussi@hpl.hp.com, gadiel@seroussi.net, mward@math.purdue.edu Subject: preliminary program of my part for the MSRI course In-Reply-To: <200404171837.i3HIbjTW021190@lukasz.cs.purdue.edu> References: <200404171837.i3HIbjTW021190@lukasz.cs.purdue.edu> X-Mailer: VM 7.07 under 21.4 (patch 12) "Portable Code" XEmacs Lucid X-Miltered: at nez-perce with ID 409684D7.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Virus-Scanned: clamd / ClamAV version 0.70, clamav-milter version 0.70j X-Spam-Status: No, hits=0.0 required=6.0 tests=none autolearn=no version=2.63 X-Spam-Checker-Version: SpamAssassin 2.63 (2004-01-11) on mailslot.cs.purdue.edu Status: RO Content-Length: 3846 Dear All, I have developed a page regarding the MSRI course. You can access it at: http://algo.inria.fr/flajolet/Teach/berkeley-index.html As you can see, I plan to cover quite classical stuff from my view point. Some of the basic math techniques should be covered by me, so that it leaves to Wojtek the possibility of focussing more on the specific aspcts of his problems for his Parts 1 & 2. As regards Wojtek's Part 3, they should have a prepartion in the form of a refresher in complex analysis but I won't have time to cover Mellin. At this late stage, we should probably aim at converging soon on all aspects of the course so that we can update the MSRI page, which , at the moment, doesn't seem to correspond to what we plan to do. [A quick hack would be to reduce in size its long preamble on what AofA is and suppress the mention of DMTCS that is confusing...] Our course director is fleeing & defecting to Poland at the end of the week, I understand... Cheers, Philippe %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Wojciech Szpankowski writes: > Dear All: > > Let me start ... > > Topics covered by Wojtek (Wed, Th, F, June 9-11) > > 1. Analysis of Exact Pattern Matching (3h, Wednesday?) > > Math techniques: > (a) Combinatorial Calculus (languages) > (b) Generating functions > (c) simple complex asymptotics -- poles) > (d) Moment analysis > > Homework - Problems (for Mark to cover) > (a) Details of derivations > (b) Limiting distribution > (c) Extension to Markov > (d) Another example of combinatorial calculus (joint distribution) > > References (all can be downloaded from http://www.cs.purdue.edu/people/spa) > M. Regnier and W. Szpankowski, > On pattern frequency occurrences in a Markovian sequence > Algorithmica, 22, 631-649, 1998. > > W. Szpankowski, > Average Case Analysis of Algorithms on Sequences, > John Wiley & Sons, New York, 2001. > (Chap. 7.1 and 8.3) > > P. Jacquet and W. Szpankowski > "Analytic Approach to Pattern Matching", > in Applied Combinatorics on Words > (eds. Lothaire), Cambridge University Press (Encycl. of Mathematics and > Its Applications), 2004. > > > 2. Worst Case Minimax Redundancy for memoryless Sources (3h, Thurs.) > > > Math techniques: > (a) Shtarkov bound > (b) Tree-like generating functions > (c) Singularity analysis > > Homework - Problems > (a) Singularity expansion for T(z) and B(z) > (b) Extraction of coefficients for B^m(z) -- details > > References: > W. Szpankowski, > On asymptotics of certain recurrences arising in universal coding, > Problems of Information Transmission, > 34, No.2, 142-146, 1998. > > W. Szpankowski, > Average Case Analysis of Algorithms on Sequences, > John Wiley & Sons, New York, 2001. > (Chap. 8.7) > > > > 3. Error Resilient LZ'77 and Tries/Suffix Trees Analysis (3h, Friday) > > Math techniques > (a) Recurrences > (b) Poissonization > (c) Mellin transform > (d) Depoissonization > > Homework - Problems: > (a) Solve some other trie like recurrences (Chap. 7.6.1) > (b) Mellin transform exercises (Chap 9) > (c) Depoissonization examples (Chap 10) > (d) Limiting distribution of M_n. > > References: > M. Ward and W. Szpankowski > Analysis of a Randomized Selection Algorithm Motivated by the LZ'77 Scheme > The First Workshop on Analytic Algorithmics and Combinatorics, (ANALCO04), > New Orleans, January 10, 2004. > > W. Szpankowski, > Average Case Analysis of Algorithms on Sequences, > John Wiley & Sons, New York, 2001. > (Chap. 9 and 10) >