Sumários
Matroids
27 maio 2020, 11:00 • Alexandre Francisco
Introduction to matroids. Motivation, problems and examples. Basic concepts and definitions. The greedy algorithm. Intersection of matroids, examples and motivation. The intersection algorithm.
Suffix trees, suffix arrays, and applications
26 maio 2020, 11:00 • Alexandre Francisco
Introduction and motivation to suffix trees and suffix arrays. Time and space. Direct applications. Approximate string matching: the k-mismatches problem. The pairwise k-mismatches problem. More on suffix arrays, LCP, LCE and RMQ.
String matching
20 maio 2020, 11:00 • Alexandre Francisco
String matching, motivation and related problems. KMP algorithm, the prefix function and the strong rule. Correctness analysis and running time analysis of KMP.
FPRAS for #DNF
19 maio 2020, 11:00 • Alexandre Francisco
Approximate counting and the #DNF problem. The technique by Karp, Luby and Madras. An FPRAS for the #DNF problem, details and analysis. Introduction to string processing and string matching.
Approximate counting
13 maio 2020, 11:00 • Alexandre Francisco
Approximate counting, motivation and examples. Approximation schemas and FPRAS. #P class, relation with NP and BPP, #P-hard and main problems. Brief introduction to Chernoff bounds. An FPRAS for approximating Pi. The #DNF problem and a first try to obtain an FPRAS.