Introduction to the design and analysis of algorithms / Anany Levitin; international edition contributions by Soumen Mukherjee, Arup Kumar Bhattacharjee.

Includes bibliographical references (pages 519-528) and index.

1.Introduction -- 1.1.What Is an Algorithm? -- Exercises 1.1 -- 1.2.Fundamentals of Algorithmic Problem Solving -- Understanding the Problem -- Ascertaining the Capabilities of the Computational Device -- Choosing between Exact and Approximate Problem Solving -- Algorithm Design Techniques -- Designing an Algorithm and Data Structures -- Methods of Specifying an Algorithm -- Proving an Algorithm's Correctness -- Analyzing an Algorithm -- Coding an Algorithm -- Exercises 1.2 -- 1.3.Important Problem Types -- Sorting -- Searching -- String Processing -- Graph Problems -- Combinatorial Problems -- Geometric Problems -- Numerical Problems -- Exercises 1.3 -- 1.4.Fundamental Data Structures -- Linear Data Structures -- Graphs -- Trees -- Sets and Dictionaries -- Exercises 1.4 -- Summary -- 2.Fundamentals of the Analysis of Algorithm Efficiency -- 2.1.The Analysis Framework -- Measuring an Input's Size -- Units for Measuring Running Time -- Orders of Growth -- Worst-Case, Best-Case, and Average-Case Efficiencies -- Recapitulation of the Analysis Framework -- Exercises 2.1 -- 2.2.Asymptotic Notations and Basic Efficiency Classes -- Informal Introduction -- O-notation -- Ω-notation -- Ξ-notation -- Useful Property Involving the Asymptotic Notations -- Using Limits for Comparing Orders of Growth -- Basic Efficiency Classes -- Exercises 2.2 -- 2.3.Mathematical Analysis of Nonrecursive Algorithms -- Exercises 2.3 -- 2.4.Mathematical Analysis of Recursive Algorithms -- Exercises 2.4 -- 2.5.Example: Computing the nth Fibonacci Number -- Exercises 2.5 -- 2.6.Empirical Analysis of Algorithms -- Exercises 2.6 -- 2.7.Algorithm Visualization -- Summary -- 3.Brute Force and Exhaustive Search -- 3.1.Selection Sort and Bubble Sort -- Selection Sort -- Bubble Sort -- Exercises 3.1 -- 3.2.Sequential Search and Brute-Force String Matching -- Sequential Search -- Brute-Force String Matching -- Exercises 3.2 -- 3.3.Closest-Pair and Convex-Hull Problems by Brute Force -- Closest-Pair Problem -- Convex-Hull Problem -- Exercises 3.3 -- 3.4.Exhaustive Search -- Traveling Salesman Problem -- Knapsack Problem -- Assignment Problem -- Exercises 3.4 -- 3.5.Depth-First Search and Breadth-First Search -- Depth-First Search -- Breadth-First Search -- Exercises 3.5 -- Summary -- 4.Decrease-and-Conquer -- 4.1.Insertion Sort -- Exercises 4.1 -- 4.2.Topological Sorting -- Exercises 4.2 -- 4.3.Algorithms for Generating Combinatorial Objects -- Generating Permutations -- Generating Subsets -- Exercises 4.3 -- 4.4.Decrease-by-a-Constant-Factor Algorithms -- Binary Search -- Fake-Coin Problem -- Russian Peasant Multiplication -- Josephus Problem -- Exercises 4.4 -- 4.5.Variable-Size-Decrease Algorithms -- Computing a Median and the Selection Problem -- Interpolation Search -- Searching and Insertion in a Binary Search Tree -- The Game of Nim -- Exercises 4.5 -- Summary -- 5.Divide-and-Conquer -- 5.1.Mergesort -- Exercises 5.1 -- 5.2.Quicksort -- Exercises 5.2 -- 5.3.Binary Tree Traversals and Related Properties -- Exercises 5.3 -- 5.4.Multiplication of Large Integers and Strassen's Matrix Multiplication -- Multiplication of Large Integers -- Strassen's Matrix Multiplication -- Exercises 5.4 -- 5.5.The Closest-Pair and Convex-Hull Problems by Divide-and-Conquer -- The Closest-Pair Problem -- Convex-Hull Problem -- Exercises 5.5 -- Summary -- 6.Transform-and-Conquer -- 6.1.Presorting -- Exercises 6.1 -- 6.2.Gaussian Elimination -- LU Decomposition -- Computing a Matrix Inverse -- Computing a Determinant -- Exercises 6.2 -- 6.3.Balanced Search Trees -- AVL Trees -- 2-3 Trees -- Exercises 6.3 t