Algorithms

Design Techniques and Analysis(Revised Edition)

Problem solving is an essential part of every scientific discipline. It has two components: (1) problem identification and formulation, and (2) the solution to the formulated problem. One can solve a problem on its own using ad hoc techniques or by following techniques that have produced efficient solutions to similar problems. This requires the understanding of various algorithm design techniques, how and when to use them to formulate solutions, and the context appropriate for each of them.

Algorithms: Design Techniques and Analysis advocates the study of algorithm design by presenting the most useful techniques and illustrating them with numerous examples — emphasizing on design techniques in problem solving rather than algorithms topics like searching and sorting. Algorithmic analysis in connection with example algorithms are explored in detail. Each technique or strategy is covered in its own chapter through numerous examples of problems and their algorithms.

Readers will be equipped with problem solving tools needed in advanced courses or research in science and engineering.

Contents:

• Basic Concepts and Introduction to Algorithms:

  • Basic Concepts in Algorithmic Analysis
  • Data Structures
  • Heaps and the Disjoint Sets Data Structures

• Techniques Based on Recursion:

  • Induction
  • Divide and Conquer
  • Dynamic Programming

• First-Cut Techniques:

  • The Greedy Approach
  • Graph Traversal

• Complexity of Problems:

  • NP-Complete Problems
  • Introduction to Computational Complexity
  • Lower Bounds

• Coping with Hardness:

  • Backtracking
  • Randomized Algorithms
  • Approximation Algorithms

• Iteractive Improvement for Domain-Specific Problems:

  • Network Flow
  • Matching

• Techniques in Computational Geometry:

  • Geometric Sweeping
  • Voronoi Diagrams

• Appendices:

  • Mathematical Preliminaries
  • Introduction to Discrete Probability

Readership: Senior undergraduates, graduate students and professionals in software development. Readers in advanced courses or research in science and engineering.
Key Features:

• It covers many topics that are not in any other book on algorithms
• It covers a wide range of design techniques each in its own chapter