String Processing Algorithms

• Introduction
• A String ADT
• String Searching
  • Motivation
  • A Naive Algorithm
  • The Knuth-Morris-Pratt Algorithm
  • The Boyer-Moore Algorithm
  • Tradeoffs and Issues
  • Conclusion
  • Exercise
  • Further Reading
• Pattern Matching
  • Motivation
  • Representing Patterns
  • A Simple Pattern Matcher
  • Further Reading
• Parsing
  • Motivation
  • Context Free Grammars
  • Simple Parsing Methods
    • A Top-Down Parser
    • A Bottom-Up Parser
  • Further Reading
• File Compression
  • Motivation
  • Run-Length Encoding
  • Variable-Length Encoding
  • Substitutional Compressors
  • JPEG and MPEG
  • Summary
    • Further Reading
• Cryptography
  • Motivation
  • A Basic Outline and Terminology
  • Simple Symmetric Methods
  • Asymmetric Systems: Public Key CyptoSystems
  • Summary
  • Exercises
  • Further Reading