Tries and String Matching - Stanford University

Tries and String Matching

Where We've Been

¡ñ

Fundamental Data Structures

¡ñ

¡ñ

Isometries

¡ñ

¡ñ

Red/black trees, B-trees, RMQ, etc.

Red/black trees ¡Ô 2-3-4 trees, binomial

heaps ¡Ô binary numbers, etc.

Amortized Analysis

¡ñ

Aggregate, banker's, and potential methods.

Where We're Going

¡ñ

String Data Structures

¡ñ

¡ñ

Randomized Data Structures

¡ñ

¡ñ

Using randomness as a building block.

Integer Data Structures

¡ñ

¡ñ

Data structures for storing and manipulating

text.

Breaking the ¦¸(n log n) sorting barrier.

Dynamic Connectivity

¡ñ

Maintaining connectivity in an changing world.

String Data Structures

Text Processing

¡ñ

String processing shows up everywhere:

¡ñ

¡ñ

¡ñ

Computational biology: Manipulating DNA

sequences.

¡ñ

NLP: Storing and organizing huge text databases.

¡ñ

Computer security: Building antivirus databases.

Many problems have polynomial-time solutions.

Goal: Design theoretically and practically

efficient algorithms that outperform brute-force

approaches.

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download