From cjh@cs.purdue.edu Tue May 4 13:42:01 2004 X-UIDL: 4211fe0e0e522d5dfdf2dc2225cb9021 Return-Path: Received: from newman.cs.purdue.edu (IDENT:0@newman.cs.purdue.edu [128.10.2.6]) by lukasz.cs.purdue.edu (8.12.9/8.12.9/PURDUE_CS-2.0) with ESMTP id i44Ig1GG008846 for ; Tue, 4 May 2004 13:42:01 -0500 (EST) Received: from NEMO.ad.cs.purdue.edu (nemo.cs.purdue.edu [128.10.9.45]) by newman.cs.purdue.edu (8.12.9/8.12.9/PURDUE_CS-2.0) with ESMTP id i44Ig16G023693 for ; Tue, 4 May 2004 13:42:01 -0500 (EST) Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----_=_NextPart_001_01C43207.99BDD6AF" X-MimeOLE: Produced By Microsoft Exchange V6.5.6944.0 Subject: RE: Date: Tue, 4 May 2004 13:42:49 -0500 Message-ID: X-MS-Has-Attach: yes X-MS-TNEF-Correlator: Thread-Index: AcQx/VVPUgvbyLG7TFOdXA1MUCa+IwACjLFw From: "Connie Wilson" To: "Wojciech Szpankowski" Status: RO Content-Length: 7175 This is a multi-part message in MIME format. ------_=_NextPart_001_01C43207.99BDD6AF Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Attached is the file in html format. Connie -----Original Message----- From: Wojciech Szpankowski [mailto:spa@cs.purdue.edu]=20 Sent: Tuesday, May 04, 2004 12:29 PM To: Connie Wilson Subject:=20 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,=20 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.) =20 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, =20 On asymptotics of certain recurrences arising in universal coding,=20 Problems of Information Transmission, 34, No.2, 142-146, 1998. W. Szpankowski, Average Case Analysis of Algorithms on Sequences,=20 John Wiley & Sons, New York, 2001. (Chap. 8.7) =20 3. Error Resilient LZ'77 and Tries/Suffix Trees Analysis (3h, Friday) Math techniques (a) Recurrences=20 (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)=20 ------_=_NextPart_001_01C43207.99BDD6AF Content-Type: text/html; name="file.html" Content-Transfer-Encoding: base64 Content-Description: file.html Content-Disposition: attachment; filename="file.html" IAo8SFRNTD4KPEJPRFk+CiAKPE9MPgo8TEk+IEFuYWx5c2lzIG9mIEV4YWN0IFBhdHRlcm4gTWF0 Y2hpbmcgPC9MST4gCjxQPgogCjxCPiBNYXRoIHRlY2huaXF1ZXM8L0I+OiAKPFA+CjxPTCBUWVBF PWE+IAo8TEk+IENvbWJpbmF0b3JpYWwgQ2FsY3VsdXMgKGxhbmd1YWdlcykgPC9MST4KPExJPiBH ZW5lcmF0aW5nIGZ1bmN0aW9ucyA8L0xJPgo8TEk+IFNpbXBsZSBjb21wbGV4IGFzeW1wdG90aWNz IC0tIHBvbGVzKSA8L0xJPgo8TEk+IE1vbWVudCBhbmFseXNpcyA8L0xJPgo8L09MPiAKPFA+CiAK PEI+IEhvbWV3b3JrIC0gUHJvYmxlbXMgPC9CPiAKPFA+CjxPTCBUWVBFID0gYT4KPExJPiBEZXRh aWxzIG9mIGRlcml2YXRpb25zIDwvTEk+IAo8TEk+IExpbWl0aW5nIGRpc3RyaWJ1dGlvbiAgPC9M ST4KPExJPiBFeHRlbnNpb24gdG8gTWFya292IDwvTEk+IAo8TEk+IEFub3RoZXIgZXhhbXBsZSBv ZiBjb21iaW5hdG9yaWFsIGNhbGN1bHVzIChqb2ludCBkaXN0cmlidXRpb24pCjwvTEk+IAo8L09M Pgo8UD4KIAo8SDU+IFJlZmVyZW5jZXM8L0g1PiAoYWxsIGNhbiBiZSBkb3dubG9hZGVkIGZyb20g aHR0cDovL3d3dy5jcy5wdXJkdWUuZWR1L3Blb3BsZS9zcGEpIAoKPE9MPgo8TEk+IE0uIFJlZ25p ZXIgYW5kIFcuIFN6cGFua293c2tpLiAKT24gUGF0dGVybiBGcmVxdWVuY3kgT2NjdXJyZW5jZXMg aW4gYSBNYXJrb3ZpYW4gU2VxdWVuY2UgQWxnb3JpdGhtaWNhLCAyMiwgNjMxLTY0OSwgMTk5OC4g Cmh0dHA6Ly93d3cuY3MucHVyZHVlLmVkdSA8L0xJPgo8QlI+CiAKPExJPiBXLiBTenBhbmtvd3Nr aS4gCjxJPiBBdmVyYWdlIENhc2UgQW5hbHlzaXMgb2YgQWxnb3JpdGhtcyBvbiBTZXF1ZW5jZXMg PC9JPi4gSm9obiBXaWxleSAmIFNvbnMsIE5ldyBZb3JrLCAyMDAxLiAKKENoYXAuIDcuMSBhbmQg OC4zKS4KaHR0cDovL3d3dy5jcy5wdXJkdWUuZWR1PiA8L0xJCjxCUj4KCjxMST4gUC4gSmFjcXVl dCBhbmQgVy4gU3pwYW5rb3dza2kuIApBbmFseXRpYyBBcHByb2FjaCB0byBQYXR0ZXJuIE1hdGNo aW5nLiBJbiA8ST4gQXBwbGllZCBDb21iaW5hdG9yaWNzIG9uIFdvcmRzIDwvST4gKGVkcy4gTG90 aGFpcmUpLCBDYW1icmlkZ2UgVW5pdmVyc2l0eSBQcmVzcyAoRW5jeWNsLiBvZiBNYXRoZW1hdGlj cyBhbmQgSXRzIEFwcGxpY2F0aW9ucyksIDIwMDQuIApodHRwOi8vd3d3LmNzLnB1cmR1ZS5lZHUg PC9MST4KPC9PTD4KPFA+CiAKPExJPiBXb3JzdCBDYXNlIE1pbmltYXggUmVkdW5kYW5jeSBmb3Ig bWVtb3J5bGVzcyBTb3VyY2VzIDwvTEk+IAo8UD4gICAgCgo8Qj4gTWF0aCB0ZWNobmlxdWVzIDwv Qj46IAo8UD4KPE9MIFRZUEU9YT4KPExJPiBTaHRhcmtvdiBib3VuZCA8L0xJPiAKPExJPiBUcmVl LWxpa2UgZ2VuZXJhdGluZyBmdW5jdGlvbnMgPC9MST4KPExJPiBTaW5ndWxhcml0eSBhbmFseXNp cyA8L0xJPgo8L09MPgo8UD4KIAo8Qj4gSG9tZXdvcmsgLSBQcm9ibGVtcyA8L0I+IAo8UD4KPE9M IFRZUEU9YT4KPExJPiBTaW5ndWxhcml0eSBleHBhbnNpb24gZm9yIDxJPiBUKHopIDwvST4gYW5k IDxJPiBCKHopIDwvST4gPC9MST4gCjxMSSBFeHRyYWN0aW9uIG9mIGNvZWZmaWNpZW50cyBmb3Ig PEk+IEIgPHN1cD4gbSA8L3N1cD4gKHopIDwvST4gLS0gZGV0YWlscyA8L0xJPiAKPE9MPgo8UD4K IAo8SDU+IFJlZmVyZW5jZXMgPC9INT46CjxQPgoKPE9MPgo8TEk+IFcuIFN6cGFua293c2tpLiAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIApPbiBBc3lt cHRvdGljcyBvZiBDZXJ0YWluIFJlY3VycmVuY2VzIEFyaXNpbmcgaW4gVW5pdmVyc2FsIENvZGlu Zy4KPEk+IFByb2JsZW1zIG9mIEluZm9ybWF0aW9uIFRyYW5zbWlzc2lvbiA8L0k+LCAzNCwgTm8u MiwgMTQyLTE0NiwgMTk5OC4KaHR0cDovL3d3dy5jcy5wdXJkdWUuZWR1IDwvTEk+CjxCUj4KCjxM ST4gVy4gU3pwYW5rb3dza2kuIDxJPiBBdmVyYWdlIENhc2UgQW5hbHlzaXMgb2YgQWxnb3JpdGht cyBvbiBTZXF1ZW5jZXMgPC9JPi4gSm9obiBXaWxleSAmIFNvbnMsIE5ldyBZb3JrLCAyMDAxLiAo Q2hhcC4gOC43KS4gCmh0dHA6Ly93d3cuY3MucHVyZHVlLmVkdSA8L0xJPiAKPC9PTD4KPFA+Cgo8 TEk+IEVycm9yIFJlc2lsaWVudCBMWic3NyBhbmQgVHJpZXMvU3VmZml4IFRyZWVzIEFuYWx5c2lz IDwvTEk+CjxQPgogCjxCPiBNYXRoIHRlY2huaXF1ZXMgPC9CPgo8UD4KPE9MIFRZUEU9YT4KPExJ PiBSZWN1cnJlbmNlcyA8L0xJPiAKPExJPiBQb2lzc29uaXphdGlvbiA8L0xJPiAKPExJPiBNZWxs aW4gdHJhbnNmb3JtIDwvTEk+IAo8TEk+IERlcG9pc3Nvbml6YXRpb24gPC9MST4gCjwvT0w+CjxQ PgogCjxCPiBIb21ld29yayAtIFByb2JsZW1zIDwvQj46IAo8UD4KPE9MIFRZUEU9YT4KPExJPiBT b2x2ZSBzb21lIG90aGVyIHRyaWUgbGlrZSByZWN1cnJlbmNlcyAoQ2hhcC4gNy42LjEpIDwvTEk+ IAo8TEk+IE1lbGxpbiB0cmFuc2Zvcm0gZXhlcmNpc2VzIChDaGFwIDkpIDwvTEk+IAo8TEk+IERl cG9pc3Nvbml6YXRpb24gZXhhbXBsZXMgKENoYXAgMTApIDwvTEk+IAo8TEk+IExpbWl0aW5nIGRp c3RyaWJ1dGlvbiBvZiA8ST4gTSA8c3ViPiBuIDwvc3ViPiA8L0k+LiA8L0xJPiAKPC9PTD4KPFA+ Cgo8SDU+IFJlZmVyZW5jZXMgPC9INT46IAo8UD4KCjxPTD4KPExJPiBNLiBXYXJkIGFuZCBXLiBT enBhbmtvd3NraS4gQW5hbHlzaXMgb2YgYSBSYW5kb21pemVkIFNlbGVjdGlvbiBBbGdvcml0aG0g TW90aXZhdGVkIGJ5IHRoZSBMWic3NyBTY2hlbWUuIAo8ST4gVGhlIEZpcnN0IFdvcmtzaG9wIG9u IEFuYWx5dGljIEFsZ29yaXRobWljcyBhbmQgQ29tYmluYXRvcmljcwo8L0k+LCAoQU5BTENPMDQp LCBOZXcgT3JsZWFucywgSmFudWFyeSAxMCwgMjAwNC4gCmh0dHA6Ly93d3cuY3MucHVyZHVlLmVk dSA8L0xJPgo8QlI+CiAKPExJPiBXLiBTenBhbmtvd3NraS4gCjxJPiBBdmVyYWdlIENhc2UgQW5h bHlzaXMgb2YgQWxnb3JpdGhtcyBvbiBTZXF1ZW5jZXMgPC9JPi4gCkpvaG4gV2lsZXkgJiBTb25z LCBOZXcgWW9yaywgMjAwMS4gCihDaGFwLiA5IGFuZCAxMCkuIDwvTEk+ICAKPC9PTD4KCjwvT0w+ CiAKPC9CT0RZPgo8L0hUTUw+Cg== ------_=_NextPart_001_01C43207.99BDD6AF--