Schedule of Lectures

Venue: 6/202 on Monday (28 Aug) and 6/203 on all other days.

The schedule below is provided to share a rough layout of topics. The tentative schedule of lectures is as follows:

a) On all days except Saturday (2nd September) and Sunday (3rd September), we will have lectues between 9AM and 12.30PM with a short break in between.

b) On Saturday, there will be no lectures. On Sunday, we will have lectures as usual in the morning, and also lectures between 2PM and 4PM.

In the table below, Sessions 1, 2 and 3 are timed at 9-10AM, 10-11AM and 11.30AM-12.30PM, respectively. Sessions 4 and 5 on Sunday are timed from 2PM to 3PM and 3PM to 4PM.

Module A: Matching

Time Topic Materials
28 Aug, Session 1 Definition of the basic pattern matching problem. The naïve method and its shortcomings. Intuition for re-using past information. Intro
28 Aug, Session 2 Definition of the Automata Method. The Knuth-Morris-Pratt algorithm. Time complexity analysis and correctness proof. The Aho and Corasick algorithm and the Boyer-Moore idea. KMP
28 Aug, Session 3 Problem solving session. Proving the linear-time automaton construction. Tries
29 Aug, Session 1 The need for a method scalable in dimensions. Definition of the Dueling Method. The Amir-Benson-Farach algorithm. 2DMatching Witness Table
29 Aug, Session 2 Data structures and complexity of the dueling algorithm. Correctness proof for the dueling algorithm. Dueling
29 Aug, Session 3 Problem solving session. Other uses of dueling method.
30 Aug, Session 1 The need for a local method, e.g. for exploiting parallelism. The Renaming Method. The Karp-Miller-Rosenberg algorithm. Parallelism
30 Aug, Session 2 Proving complexity and correctness of the Karp-Miller-Rosenberg algorithm.
30 Aug, Session 3 The need for handling non-transitive relations. The Convolutions Method. The Fischer-Paterson algorithm. Convolutions
31 Aug, Session 1 The Fast Fourier Transform. Definition and exercises.
31 Aug, Session 2 Proof of complexity and correctness of the Fischer-Paterson algorithm. The shortcomings of the Fischer-Paterson algorithm over infinite alphabets.
31 Aug, Session 3 Bounded Divide-and-Conquer. The Abrahamson and Kosaraju algorithms. Proof of complexity and correctness. More FFT
1 Sep, Session 1 Problem solving session. Using convolutions.
1 Sep, Session 2 Exploiting string regularities. The Fine and Wilf's Periodicity lemma.
1 Sep, Session 3 Using periodicity to speed up parallel pattern matching. The Deterministic Sampling Method. Vishkin's algorithm.
3 Sep, Session 1 Proof of correctness and complexity of Vishkin's algorithm.
3 Sep, Session 2 The need for matching in scaled texts. The Counting Method. Amir- Butman-Lewenstein algorithm. Proof of complexity and correctness of the Amir- Butman-Lewenstein algorithm.
3 Sep, Session 3 Problem solving session. Using, periodicities, pigeonhole principle, and compression.
4 Sep, Session 1 The need for sophisticated multidimensional algorithms. The Geometric Methods. Defining the Amir-Butman-Crochemore-Landau-Schaps algorithm.
4 Sep, Session 2 Analysis of the rotation algorithm, complexity and correctness.

Module B: Indexing

Time Topic
4 Sep, Session 3 Defining the indexing problem. First solution the suffix tree data structure. Weiner's algorithm.
5 Sep, Session 1 Analysis, proof of correctness and complexity of the Weiner algorithm.
5 Sep, Session 2 Problem solving session. Tries, issues in suffix tree construction, uses of suffix trees.
5 Sep, Session 3 Navigating the suffix tree. The Lowest Common Ancestor (LCA) problem.
6 Sep, Session 1 The Range Minimum Problem and its relation to the Lowest Common Ancestor problem. Using the Cartesian Tree data structure to prove equivalence of the LCA problem and the range minimum problem.
6 Sep, Session 2 The Berkman algorithm for the LCA problem. Analysis of algorithm, proof of complexity and correctness.
6 Sep, Session 3 Problem solving session. Using suffix trees and LCA.
7 Sep, Session 1 The definition of efficient indexing. Problems that have efficient indexing Parameterized Matching, Order Preserving Matching. The Amir-Benson- Farach algorithm.
7 Sep, Session 2 Problems that don't have efficient indexing. The Histogram Indexing Tutorial 8 Conditional complexity. The 3-SUM problem.