Algorithms: Design Techniques and Analysis

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.

Table of Contents

PART 1 Basic Concepts and Introduction to Algorithms
Chapter 1 Basic Concepts in Algorithmic Analysis
Chapter 2 Data Structures
Chapter 3 Heaps and the Disjoint Sets Data Structures

PART 2 Techniques Based on Recursion
Chapter 4 Induction
Chapter 5 Divide and Conquer
Chapter 6 Dynamic Programming

PART 3 First-Cut Techniques
Chapter 7 The Greedy Approach
Chapter 8 Graph Traversal

PART 4 Complexity of Problems
Chapter 9 NP-complete Problems
Chapter 10 Introduction to Computational Complexity
Chapter 11 Lower Bounds

PART 5 Coping with Hardness
Chapter 12 Backtracking
Chapter 13 Randomized Algorithms
Chapter 14 Approximation Algorithms

PART 6 Iterative Improvement for Domain-Specific Problems
Chapter 15 Network Flow
Chapter 16 Matching

PART 7 Techniques in Computational Geometry
Chapter 17 Geometric Sweeping
Chapter 18 Voronoi Diagrams

Appendix A Mathematical Preliminaries
Appendix B Introduction to Discrete Probability