Program
| The 1st Day (2006/6/17): String Processing |
| 8:00-8:50 |
Introduction to Suffix Tree and its Applications |
§d®iºÓ |
| 9:00-9:50 |
The KMP algorithm and a constant space KMP algorithm for exact matching |
³¯§»ªN |
| 10:10-11:00 |
The Boyer and Moore algorithm for exact matching |
¤ýºûÛ |
| 11:10-12:00 |
The Best Substring Matching Problem and the Approximate String Matching Problem |
³\§»»x |
| 12:00-13:10 Lunch Break |
| 13:10-14:00 |
The Automata Approach for Exact Matching |
·Å¤å§» |
| 14:10-15:00 |
The Convolution Approach for Exact and Approximate Matching |
§d¬f§» |
| 15:00-15:20 Coffee Break |
| 15:20-16:10 |
The Hashing Approach for Exact Matching |
³¯®¶«Â |
| 16:20-17:10 |
The Suffix Tree and Divide-and-Conquer Approaches for the Tandem Repeat Finding Problem ¡® the Longest Tandem Repeat Subsequence problem |
¼ï¥@¼ý |
| 17:20-18:10 |
The Manacher Algorithm and Suffix Tree Method for the Palindrome Finding Problem |
¨¿²z¬w |
| |
| The 2nd Day (2006/6/24): Approximation Algorithms |
| 8:00-8:40 |
Introduction -- Approximation Classes and Basic Complexity Theory |
Á餹ª@ |
| 8:40-9:10 |
Approximation Techniques (I) -- Greedy Method, Sequential Algorithms and Local Search |
¸®xº³ |
| 9:20-10:10 |
Approximation Techniques (II) -- Linear Programming and Randomization |
§f¬R¿« |
| 10:20-11:10 |
Input Dependent and Asymptotic Approximation Algorithms |
¶À«ÛµÙ |
| 11:20-12:00 |
Approximation Preserving Reduction |
´å³ÕµÏ |
| 12:00-13:00 Lunch Break |
| 13:00-13:50 |
More on Randomization -- Semidefinite Programming and Derandomization |
¶À´¼¨^ |
| 14:00-14:50 |
NP, PCP and Inapproximability |
±Z·_¤å |
