TY  - BOOK
AU  - Levitin,Anany
AU  - Bhattacharjee,Arup Kumar
AU  - Mukherjee,Soumen
TI  - Introduction to the design and analysis of algorithms
SN  - 027376411X
AV  - QA76.9.A43 L48 2012
PY  - 2012///
CY  - Boston
PB  - Pearson Education
KW  - Computer algorithms
KW  - Algorithmes
N1  - 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
ER  -