Joint Advanced Student School (JASS)

Course 1: Complexity Analysis of String Algorithms

	Directors:		Prof. Dr. Y. Matiyasevich, Steklov Institute of Mathematics, St. Petersburg
			Prof. Dr. E.W. Mayr, Institut für Informatik, Technische Universität München
	Contact:		Moritz Maaß, Email: maass@in.tum.de
	Organization:		Every participant is expected to give a talk and to prepare a paper on one of the topics below. Some help is provided on the organizational stuff page.
	Topics:		The course covers advanced techniques for the analysis of string algorithms applied to fundamental algorithms in this area. There will be a special focus on average case analysis and exact analysis (as initiated by D. Knuth). Together with the Russian participants, we plan to cover the following topics:

Data Structures for Pattern Matching. Suffix trees and suffix arrays are a basic data structure in pattern matching.
Article: [Ukk95,KS03]. Book chapter: 6 of [Gus97]. Additionally: [MM93]
Sub-linear Approximate String Matching. A classical algorithm based on the use of suffix trees, lowest common ancestor queries. The complexity analysis uses basic techniques such as the Chernoff bound.
Article: [CL94]. Book chapter: 2 of [Szp00], 6 and 8 of [Gus97]. Additionally: [BFC00] (lca)
Approximate Text Indexing. Using simple mathematical arguments the matching probabilities in the suffix tree are bound and by a clever division of the search pattern sub-linear time is achieved.
Article: [NBY00]. Book chapter: 6 of [Gus97]
Compressed Suffix Arrays. This space efficient index structure is analyzed on a bit level to reveal linear size.
Article: [GV00,Sad00]. Book chapter: 6 of [Szp00].
Asymptotic Properties of Suffix Trees. Analysis of height and feasible path length using probabilistic tools such as 2nd Moment Method.
Article: [Szp93]. Book chapter: 4 of [Szp00].
Sequential Pattern Matching. Analysis of Knuth-Morris-Pratt type algorithms using the Subadditive Ergodic Theorem.
Article: [RS98a]. Book chapter: 5 of [Szp00].
Greedy Algorithms for the SCS Problem. Analysis of some greedy algorithms using tools from information theory such as asymptotic equity property (AEP).
Article: [FS98]. Book chapter: 6 of [Szp00].
Analysis of Pattern Occurances. Analysis of the number of occurances of patterns in text using generating functions.
Article: [GO81,RS98b]. Book chapter: 7 of [Szp00].
Rice's Integrals. Rice's Integrals (already known by Nörlund) are another basic and successful technique to analyze asymptotic behavior of trees.
Article: [FS95]. Book chapter: 8 of [Szp00].
Digital Search Trees. Analysis of different digital trees with Rice's integrals.
Article: [FS86]. Book chapter: 8 of [Szp00].
The Mellin Transform. A very popular technique for the analysis of digital trees and the like.
Article: [FGD95]. Book chapter: 9 of [Szp00].
Automaton Searching on Tries. Analysis of a general search technique using automatons in tries, based on the eigenvalues of the automatons adjacency matrix and Mellin transform.
Article: [BYG96]. Book chapter: 9 of [Szp00].