Algorithms

This comprehensive compendium provides a rigorous framework to tackle the daunting challenges of designing correct and efficient algorithms. It gives a uniform approach to the design, analysis, optimization, and verification of algorithms. The volume also provides essential tools to understand algorithms and their associated data structures.

This useful reference text describes a way of thinking that eases the task of proving algorithm correctness. Working through a proof of correctness reveals an algorithm's subtleties in a way that a typical description does not. Algorithm analysis is presented using careful definitions that make the analyses mathematically rigorous.

Contents:

• Fundamentals:

  • Introduction
  • Proving Algorithm Correctness
  • Analyzing Algorithms

• Data Structures:

  • Basic Techniques for Data Structures
  • Priority Queues
  • Storage/Retrieval I: Ordered Keys
  • Storage/Retrieval II: Unordered Keys
  • Disjoint Sets
  • Graphs

• Algorithm Design Techniques:

  • Divide and Conquer
  • Optimization I: Greedy Algorithms
  • Optimization II: Dynamic Programming

• Common Reduction Targets:

  • Depth-First Search
  • Network Flow and Matching
  • * The Fast Fourier Transform

• Intractable Problems:

  • NP-Completeness
  • Approximation Algorithms

Readership: Researchers, professionals, academics, undergraduate and graduate students in theoretical computer science.

Dettagli