Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Introduction to algorithms a creative approach

INTRODUCTION TO ALGORITHMS A Creative Approach UDIMANBER University ofArizona ? ? ? ADDISON-WESLEY PUBLISHING COMPANY Reading Massachusetts ? Menlo Park California ? New York Don Mills Ontario ? Wokingham England ? Amsterdam Bonn ? Sydney ? Singapore ? Tokyo ? Madrid ? San Juan CCONTENTS Chapter Introduction l Chapter Mathematical Induction Introduction Three Simple Examples Counting Regions in the Plane A Simple Coloring Problem A More Complicated Summation Problem A Simple Inequality Euler's Formula A Problem in Graph Theory Gray Codes Finding Edge-Disjoint Paths in a Graph Arithmetic versus Geometrie Mean Theorem Loop Invariants Converting a Decimal Number to Binary Common Errors Summary Bibliographie Notes and Further Reading Exercises Chapter Analysis of Algorithms Introduction The O Notation Time and Space Complexity Summations Recurrence Relations Intelligent Guesses Divide and Conquer Relations Recurrence Relations with Füll History Useful Facts Summary Bibliographie Notes and Further Reading Exercises IX Cx Contents Chapter Data Structures Introduction Elementary Data Structures Elements Arrays Records Linked Lists Trees Representation of Trees Heaps Binary Search Trees AVL Trees Hashing The Union-Find Problem Graph s Summary Bibliographie Notes and Further Reading Exercises Chapter Design of Algorithms by Induction Introduction Evaluating Polynomials Maximal Induced Subgraph Finding One-to-One Mappings The Celebrity Problem A Divide-and-Conquer Algorithm The Skyline Problem Computing Balance Factors in Binary Trees Finding the Maximum Consecutive Subsequence Strengthening the Induction Hypothesis Dynamic Programming The Knapsack Problem Common Errors Summary Bibliographie Notes and Further Reading Exercises Chapter Algorithms Involving Sequences and Sets Introduction Binary Search and Variations Interpolation Search Sorting Bücket Sort and Radix Sort Insertion Sort and Selection Sort Mergesort CContents xi Quicksort Heapsort A Lower Bound for Sorting Order Statistics Maximum and Minimum Elements Finding the M -Smallest Element Data Compression String Matching Sequence Comparisons Probabilistic Algorithms Random Numbers A Coloring Problem A Technique for Transforming Probabilistic Algorithms into Deterministic Algorithms Finding a Majority Three Problems Exhibiting Interesting Proof Techniques Longest Increasing Subsequence Finding the Two Largest Elements in a Set Computing the Mode of a Multiset Summary Bibliographie Notes and Further Reading Exercises Chapter Graph Algorithms Introduction Eulerian Graphs Graph Traversais Depth-First Search Breadth-First Search Topological Sorting Single-Source Shortest Paths Minimum-Cost Spanning Trees All Shortest Paths Transitive Closure Decompositions of Graphs Biconnected Components Strongly Connected Components Examples of the Use of Graph Decomposition Matching Perfect Matching in Very Dense Graphs Bipartite Matching Network Flows Hamiltonian Tours Reversed Induction Cxii Contents Finding Hamiltonian Cycles in Very Dense Graphs Summary Bibliographie Notes and Further Reading Exercises Chapter Geometrie Algorithms Introduction Determining Whether a Point Is Inside a Polygon Constructing Simple Polygons Convex Hulls A Straightforward Approach Gift Wrapping Graham'sScan Closest Pair Intersections of Horizontal and Vertical Line Segments Summary Bibliographie Notes and Further Reading Exercises Chapter Algebraic and Numeric Algorithms Introduction Exponentiation Euclid's Algorithm Polynomial Multiplication Matrix Multiplication Winograd's Algorithm Strassen's Algorithm Boolean Matrices The Fast Fourier Transform Summary Bibliographie Notes and Further Reading Exercises Chapter Reductions Introduction Examples of Reductions A Simple String-Matching Problem Systems of Distinct Representatives A Reduction Involving Sequence Comparisons Finding a Triangle in Undirected Graphs