Upcoming Courses
Upcoming Courses
This is a course on string algorithms from a theoretical point of view. We will start with basic [exact] string matching algorithms like the Boyer-Moore algorithm, Knuth-Morris-Pratt algorithm, Aho-Corasick algorithm, etc., and move on to their advanced versions (string matching under edits/mismatches) and related lower bounds. We will then cover basic data structures (e.g., suffix trees and suffix arrays), their construction algorithms, and advanced data structures based on the Burrows-Wheeler Transform for compressed text indexing (e.g., FM-index) and applications. Finally, we will study some (NP) hard problems on strings, such as the shortest common superstring, center/median string problems, etc., and efficient approximation algorithms.
Algorithm design techniques: use of data structures, divide and conquer, dynamic programming, greedy techniques, local and global search. Complexity and analysis of algorithms: asymptotic analysis, worst case and average case, recurrences, lower bounds, NP-completeness. Algorithms for classical problems including sorting, searching and graph problems (connectivity, shortest paths, minimum spanning trees).
Click here for video lectures on selected topics.Â