SitemapTable of ContentsBackCoverIntroduction to Algorithms, Second EditionPrefaceTo the studentTo the professionalTo our colleaguesChanges for the second editionWeb siteAcknowledgments for the first editionAcknowledgments for the second editionPart I: FoundationsChapter 1: The Role of Algorithms in Computing1.2 Algorithms as a technologyChapter notesChapter 2: Getting Started2.2 Analyzing algorithms2.3 Designing algorithmsChapter notesChapter 3: Growth of Functions3.1 Asymptotic notation3.2 Standard notations and common functionsChapter notesChapter 4: RecurrencesTechnicalities4.1 The substitution method4.2 The recursion-tree method4.3 The master method 4.4: Proof of the master theoremChapter notesChapter 5: Probabilistic Analysis and Randomized Algorithms5.2 Indicator random variables5.3 Randomized algorithms5.4 Probabilistic analysis and further uses of indicator random variablesChapter notesPart II: Sorting and Order StatisticsChapter 6: Heapsort6.1 Heaps6.2 Maintaining the heap property6.3 Building a heap6.4 The heapsort algorithm6.5 Priority queuesChapter notesChapter 7: Quicksort7.2 Performance of quicksort7.3 A randomized version of quicksort7.4 Analysis of quicksortChapter NotesChapter 8: Sorting in Linear Time8.1 Lower bounds for sorting8.2 Counting sort8.3 Radix sortChapter notesChapter 9: Medians and Order Statistics9.1 Minimum and maximum9.2 Selection in expected linear time9.3 Selection in worst-case linear timeChapter notesPart III: Data StructuresChapter 10: Elementary Data Structures10.2 Linked lists10.3 Implementing pointers and objects10.4 Representing rooted treesChapter notesChapter 11: Hash Tables11.1 Direct-address tables11.2 Hash tables11.3 Hash functions11.4 Open addressing11.5 Perfect hashingChapter notesChapter 12: Binary Search Trees12.1 What is a binary search tree?12.2 Querying a binary search tree12.3 Insertion and deletion12.4 Randomly built binary search treesChapter notesChapter 13: Red-Black Trees13.2 Rotations13.3 Insertion13.4 DeletionChapter notesChapter 14: Augmenting Data Structures14.2 How to Augment a Data Structure14.3 Interval TreesChapter NotesPart IV: Advanced Design and Analysis TechniquesChapter 15: Dynamic Programming15.1 Assembly-line scheduling15.2 Matrix-chain multiplication15.3 Elements of dynamic programming15.4 Longest common subsequence15.5 Optimal binary search treesChapter notesChapter 16: Greedy Algorithms16.1 An activity-selection problem16.2 Elements of the greedy strategy16.3 Huffman codes16.4 Theoretical foundations for greedy methods16.5 A task-scheduling problemChapter notesChapter 17: Amortized Analysis17.1 Aggregate analysis17.2 The accounting method17.3 The potential method17.4 Dynamic tablesChapter notesPart V: Advanced Data StructuresChapter 18: B-TreesData structures on secondary storage18.1 Definition of B-trees18.2 Basic operations on B-trees18.3 Deleting a key from a B-treeChapter notesChapter 19: Binomial Heaps19.1 Binomial trees and binomial heaps19.2 Operations on binomial heapsChapter notesChapter 20: Fibonacci Heaps20.1 Structure of Fibonacci heaps20.2 Mergeable-heap operations20.3 Decreasing a key and deleting a node20.4 Bounding the maximum degreeChapter notesChapter 21: Data Structures for Disjoint Sets21.2 Linked-list representation of disjoint sets21.3 Disjoint-set forests21.4 Analysis of union by rank with path compressionChapter notesPart VI: Graph AlgorithmsChapter 22: Elementary Graph Algorithms22.2 Breadth-first search22.3 Depth-first search22.4 Topological sort22.5 Strongly connected componentsChapter notesChapter 23: Minimum Spanning Trees23.1 Growing a minimum spanning tree23.2 The algorithms of Kruskal and PrimChapter notesChapter 24: Single-Source Shortest PathsVariantsOptimal substructure of a shortest pathNegative-weight edgesCyclesRepresenting shortest pathsRelaxationProperties of shortest paths and relaxationChapter outline24.1 The Bellman-Ford algorithm24.2 Single-source shortest paths in directed acyclic graphs24.3 Dijkstra''s algorithm24.4 Difference constraints and shortest paths24.5 Proofs of shortest-paths propertiesChapter notesChapter 25: All-Pairs Shortest PathsChapter outline25.1 Shortest paths and matrix multiplication25.2 The Floyd-Warshall algorithm25.3 Johnson''s algorithm for sparse graphsChapter notesChapter 26: Maximum Flow26.1 Flow networks26.2 The Ford-Fulkerson method26.3 Maximum bipartite matching26.4 Push-relabel algorithms26.5 The relabel-to-front algorithmChapter notesPart VII: Selected TopicsChapter 27: Sorting Networks27.1 Comparison networks27.2 The zero-one principle27.3 A bitonic sorting network27.4 A merging network27.5 A sorting networkChapter notesChapter 28: Matrix Operations28.1 Properties of matrices28.2 Strassen''s algorithm for matrix multiplication28.3 Solving systems of linear equations28.4 Inverting matrices28.5 Symmetric positive-definite matrices and least-squares approximationChapter notesChapter 29: Linear ProgrammingGeneral linear programsAn overview of linear programmingApplications of linear programmingAlgorithms for linear programming29.1 Standard and slack forms29.2 Formulating problems as linear programs29.3 The simplex algorithm29.4 Duality29.5 The initial basic feasible solutionChapter notesChapter 30: Polynomials and the FFTChapter outline30.1 Representation of polynomials30.2 The DFT and FFT30.3 Efficient FFT implementationsChapter notesChapter 31: Number-Theoretic Algorithms31.1 Elementary number-theoretic notions31.2 Greatest common divisor31.3 Modular arithmetic31.4 Solving modular linear equations31.5 The Chinese remainder theorem31.6 Powers of an element31.7 The RSA public-key cryptosystem31.8 Primality testing31.9 Integer factorizationChapter notesChapter 32: String MatchingNotation and terminology32.1 The naive string-matching algorithm32.2 The Rabin-Karp algorithm32.3 String matching with finite automata32.4 The Knuth-Morris-Pratt algorithmChapter notesChapter 33: Computational Geometry33.1 Line-segment properties33.2 Determining whether any pair of segments intersects33.3 Finding the convex hull33.4 Finding the closest pair of pointsChapter notesChapter 34: NP-CompletenessNP-completeness and the classes P and NPOverview of showing problems to be NP-completeDecision problems vs. optimization problemsChapter outline34.1 Polynomial time34.2 Polynomial-time verification34.3 NP-completeness and reducibility34.4 NP-completeness proofs34.5 NP-complete problemsChapter notesChapter 35: Approximation AlgorithmsChapter outline35.1 The vertex-cover problem35.2 The traveling-salesman problem35.3 The set-covering problem35.4 Randomization and linear programming35.5 The subset-sum problemChapter notesPart VIII: Appendix: Mathematical BackgroundAppendix A: SummationsA.1 Summation formulas and propertiesA.2 Bounding summationsChapter notesAppendix B: Sets, Etc.B.2 RelationsB.3 FunctionsB.4 GraphsB.5 TreesChapter notesAppendix C: Counting and ProbabilityC.2 ProbabilityC.3 Discrete random variablesC.4 The geometric and binomial distributionsC.5 The tails of the binomial distributionChapter notesBibliographyIndexIndex_AIndex_BIndex_CIndex_DIndex_EIndex_FIndex_GIndex_HIndex_IIndex_JIndex_KIndex_LIndex_MIndex_NIndex_OIndex_PIndex_QIndex_RIndex_SIndex_TIndex_UIndex_VIndex_WIndex_YIndex_ZList of FiguresList of CorollariesList of ProblemsList of Exercises
لطفا منتظر باشید ...
