Image from Google Jackets

Introduction to algorithms / Thomas H. Cormen.

By: Cormen, Thomas HContributor(s): Leiserson, Charles E | Rivest, Ronald L | Stein, CliffordMaterial type: TextTextPublisher: Cambridge : MIT Press, 2022Copyright date: 2022Edition: 4th editionDescription: 1 online resource (1277 pages)Content type: text Media type: computer Carrier type: online resourceISBN: 9780262367509Genre/Form: Electronic books.Additional physical formats: Print version:: Introduction to Algorithms, Fourth EditionDDC classification: 005.13 Online access: Open e-book
Contents:
Intro -- Copyright -- Contents -- Preface -- I Foundations -- Introduction -- 1 The Role of Algorithms in Computing -- 1.1 Algorithms -- 1.2 Algorithms as a technology -- 2 Getting Started -- 2.1 Insertion sort -- 2.2 Analyzing algorithms -- 2.3 Designing algorithms -- 3 Characterizing Running Times -- 3.1 O-notation, (S](B-notation, and (SK(B-notation -- 3.2 Asymptotic notation: formal definitions -- 3.3 Standard notations and common functions -- 4 Divide-and-Conquer -- 4.1 Multiplying square matrices -- 4.2 Strassen's algorithm for matrix multiplication -- 4.3 The substitution method for solving recurrences -- 4.4 The recursion-tree method for solving recurrences -- 4.5 The master method for solving recurrences -- 4.6 Proof of the continuous master theorem -- 4.7 Akra-Bazzi recurrences -- 5 Probabilistic Analysis and Randomized Algorithms -- 5.1 The hiring problem -- 5.2 Indicator random variables -- 5.3 Randomized algorithms -- 5.4 Probabilistic analysis and further uses of indicator random variables -- II Sorting and Order Statistics -- Introduction -- 6 Heapsort -- 6.1 Heaps -- 6.2 Maintaining the heap property -- 6.3 Building a heap -- 6.4 The heapsort algorithm -- 6.5 Priority queues -- 7 Quicksort -- 7.1 Description of quicksort -- 7.2 Performance of quicksort -- 7.3 A randomized version of quicksort -- 7.4 Analysis of quicksort -- 8 Sorting in Linear Time -- 8.1 Lower bounds for sorting -- 8.2 Counting sort -- 8.3 Radix sort -- 8.4 Bucket sort -- 9 Medians and Order Statistics -- 9.1 Minimum and maximum -- 9.2 Selection in expected linear time -- 9.3 Selection in worst-case linear time -- III Data Structures -- Introduction -- 10 Elementary Data Structures -- 10.1 Simple array-based data structures: arrays, matrices, stacks, queues -- 10.2 Linked lists -- 10.3 Representing rooted trees -- 11 Hash Tables -- 11.1 Direct-address tables.
11.2 Hash tables -- 11.3 Hash functions -- 11.4 Open addressing -- 11.5 Practical considerations -- 12 Binary Search Trees -- 12.1 What is a binary search tree? -- 12.2 Querying a binary search tree -- 12.3 Insertion and deletion -- 13 Red-Black Trees -- 13.1 Properties of red-black trees -- 13.2 Rotations -- 13.3 Insertion -- 13.4 Deletion -- IV Advanced Design and Analysis Techniques -- Introduction -- 14 Dynamic Programming -- 14.1 Rod cutting -- 14.2 Matrix-chain multiplication -- 14.3 Elements of dynamic programming -- 14.4 Longest common subsequence -- 14.5 Optimal binary search trees -- 15 Greedy Algorithms -- 15.1 An activity-selection problem -- 15.2 Elements of the greedy strategy -- 15.3 Huffman codes -- 15.4 Offline caching -- 16 Amortized Analysis -- 16.1 Aggregate analysis -- 16.2 The accounting method -- 16.3 The potential method -- 16.4 Dynamic tables -- V Advanced Data Structures -- Introduction -- 17 Augmenting Data Structures -- 17.1 Dynamic order statistics -- 17.2 How to augment a data structure -- 17.3 Interval trees -- 18 B-Trees -- 18.1 Definition of B-trees -- 18.2 Basic operations on B-trees -- 18.3 Deleting a key from a B-tree -- 19 Data Structures for Disjoint Sets -- 19.1 Disjoint-set operations -- 19.2 Linked-list representation of disjoint sets -- 19.3 Disjoint-set forests -- 19.4 Analysis of union by rank with path compression -- VI Graph Algorithms -- Introduction -- 20 Elementary Graph Algorithms -- 20.1 Representations of graphs -- 20.2 Breadth-first search -- 20.3 Depth-first search -- 20.4 Topological sort -- 20.5 Strongly connected components -- 21 Minimum Spanning Trees -- 21.1 Growing a minimum spanning tree -- 21.2 The algorithms of Kruskal and Prim -- 22 Single-Source Shortest Paths -- 22.1 The Bellman-Ford algorithm -- 22.2 Single-source shortest paths in directed acyclic graphs -- 22.3 Dijkstra's algorithm.
22.4 Difference constraints and shortest paths -- 22.5 Proofs of shortest-paths properties -- 23 All-Pairs Shortest Paths -- 23.1 Shortest paths and matrix multiplication -- 23.2 The Floyd-Warshall algorithm -- 23.3 Johnson's algorithm for sparse graphs -- 24 Maximum Flow -- 24.1 Flow networks -- 24.2 The Ford-Fulkerson method -- 24.3 Maximum bipartite matching -- 25 Matchings in Bipartite Graphs -- 25.1 Maximum bipartite matching (revisited) -- 25.2 The stable-marriage problem -- 25.3 The Hungarian algorithm for the assignment problem -- VII Selected Topics -- Introduction -- 26 Parallel Algorithms -- 26.1 The basics of fork-join parallelism -- 26.2 Parallel matrix multiplication -- 26.3 Parallel merge sort -- 27 Online Algorithms -- 27.1 Waiting for an elevator -- 27.2 Maintaining a search list -- 27.3 Online caching -- 28 Matrix Operations -- 28.1 Solving systems of linear equations -- 28.2 Inverting matrices -- 28.3 Symmetric positive-definite matrices and least-squares approximation -- 29 Linear Programming -- 29.1 Linear programming formulations and algorithms -- 29.2 Formulating problems as linear programs -- 29.3 Duality -- 30 Polynomials and the FFT -- 30.1 Representing polynomials -- 30.2 The DFT and FFT -- 30.3 FFT circuits -- 31 Number-Theoretic Algorithms -- 31.1 Elementary number-theoretic notions -- 31.2 Greatest common divisor -- 31.3 Modular arithmetic -- 31.4 Solving modular linear equations -- 31.5 The Chinese remainder theorem -- 31.6 Powers of an element -- 31.7 The RSA public-key cryptosystem -- 31.8 Primality testing -- 32 String Matching -- 32.1 The naive string-matching algorithm -- 32.2 The Rabin-Karp algorithm -- 32.3 String matching with finite automata -- 32.4 The Knuth-Morris-Pratt algorithm -- 32.5 Suffix arrays -- 33 Machine-Learning Algorithms -- 33.1 Clustering -- 33.2 Multiplicative-weights algorithms.
33.3 Gradient descent -- 34 NP-Completeness -- 34.1 Polynomial time -- 34.2 Polynomial-time verification -- 34.3 NP-completeness and reducibility -- 34.4 NP-completeness proofs -- 34.5 NP-complete problems -- 35 Approximation Algorithms -- 35.1 The vertex-cover problem -- 35.2 The traveling-salesperson problem -- 35.3 The set-covering problem -- 35.4 Randomization and linear programming -- 35.5 The subset-sum problem -- VIII Appendix: Mathematical Background -- Introduction -- A Summations -- A.1 Summation formulas and properties -- A.2 Bounding summations -- B Sets, Etc. -- B.1 Sets -- B.2 Relations -- B.3 Functions -- B.4 Graphs -- B.5 Trees -- C Counting and Probability -- C.1 Counting -- C.2 Probability -- C.3 Discrete random variables -- C.4 The geometric and binomial distributions -- C.5 The tails of the binomial distribution -- D Matrices -- D.1 Matrices and matrix operations -- D.2 Basic matrix properties -- Bibliography -- Index.
Holdings
Item type Current library Home library Class number Status Date due Barcode Item reservations
E-book E-book Electronic publication Electronic publication Available
Total reservations: 0

Intro -- Copyright -- Contents -- Preface -- I Foundations -- Introduction -- 1 The Role of Algorithms in Computing -- 1.1 Algorithms -- 1.2 Algorithms as a technology -- 2 Getting Started -- 2.1 Insertion sort -- 2.2 Analyzing algorithms -- 2.3 Designing algorithms -- 3 Characterizing Running Times -- 3.1 O-notation, (S](B-notation, and (SK(B-notation -- 3.2 Asymptotic notation: formal definitions -- 3.3 Standard notations and common functions -- 4 Divide-and-Conquer -- 4.1 Multiplying square matrices -- 4.2 Strassen's algorithm for matrix multiplication -- 4.3 The substitution method for solving recurrences -- 4.4 The recursion-tree method for solving recurrences -- 4.5 The master method for solving recurrences -- 4.6 Proof of the continuous master theorem -- 4.7 Akra-Bazzi recurrences -- 5 Probabilistic Analysis and Randomized Algorithms -- 5.1 The hiring problem -- 5.2 Indicator random variables -- 5.3 Randomized algorithms -- 5.4 Probabilistic analysis and further uses of indicator random variables -- II Sorting and Order Statistics -- Introduction -- 6 Heapsort -- 6.1 Heaps -- 6.2 Maintaining the heap property -- 6.3 Building a heap -- 6.4 The heapsort algorithm -- 6.5 Priority queues -- 7 Quicksort -- 7.1 Description of quicksort -- 7.2 Performance of quicksort -- 7.3 A randomized version of quicksort -- 7.4 Analysis of quicksort -- 8 Sorting in Linear Time -- 8.1 Lower bounds for sorting -- 8.2 Counting sort -- 8.3 Radix sort -- 8.4 Bucket sort -- 9 Medians and Order Statistics -- 9.1 Minimum and maximum -- 9.2 Selection in expected linear time -- 9.3 Selection in worst-case linear time -- III Data Structures -- Introduction -- 10 Elementary Data Structures -- 10.1 Simple array-based data structures: arrays, matrices, stacks, queues -- 10.2 Linked lists -- 10.3 Representing rooted trees -- 11 Hash Tables -- 11.1 Direct-address tables.

11.2 Hash tables -- 11.3 Hash functions -- 11.4 Open addressing -- 11.5 Practical considerations -- 12 Binary Search Trees -- 12.1 What is a binary search tree? -- 12.2 Querying a binary search tree -- 12.3 Insertion and deletion -- 13 Red-Black Trees -- 13.1 Properties of red-black trees -- 13.2 Rotations -- 13.3 Insertion -- 13.4 Deletion -- IV Advanced Design and Analysis Techniques -- Introduction -- 14 Dynamic Programming -- 14.1 Rod cutting -- 14.2 Matrix-chain multiplication -- 14.3 Elements of dynamic programming -- 14.4 Longest common subsequence -- 14.5 Optimal binary search trees -- 15 Greedy Algorithms -- 15.1 An activity-selection problem -- 15.2 Elements of the greedy strategy -- 15.3 Huffman codes -- 15.4 Offline caching -- 16 Amortized Analysis -- 16.1 Aggregate analysis -- 16.2 The accounting method -- 16.3 The potential method -- 16.4 Dynamic tables -- V Advanced Data Structures -- Introduction -- 17 Augmenting Data Structures -- 17.1 Dynamic order statistics -- 17.2 How to augment a data structure -- 17.3 Interval trees -- 18 B-Trees -- 18.1 Definition of B-trees -- 18.2 Basic operations on B-trees -- 18.3 Deleting a key from a B-tree -- 19 Data Structures for Disjoint Sets -- 19.1 Disjoint-set operations -- 19.2 Linked-list representation of disjoint sets -- 19.3 Disjoint-set forests -- 19.4 Analysis of union by rank with path compression -- VI Graph Algorithms -- Introduction -- 20 Elementary Graph Algorithms -- 20.1 Representations of graphs -- 20.2 Breadth-first search -- 20.3 Depth-first search -- 20.4 Topological sort -- 20.5 Strongly connected components -- 21 Minimum Spanning Trees -- 21.1 Growing a minimum spanning tree -- 21.2 The algorithms of Kruskal and Prim -- 22 Single-Source Shortest Paths -- 22.1 The Bellman-Ford algorithm -- 22.2 Single-source shortest paths in directed acyclic graphs -- 22.3 Dijkstra's algorithm.

22.4 Difference constraints and shortest paths -- 22.5 Proofs of shortest-paths properties -- 23 All-Pairs Shortest Paths -- 23.1 Shortest paths and matrix multiplication -- 23.2 The Floyd-Warshall algorithm -- 23.3 Johnson's algorithm for sparse graphs -- 24 Maximum Flow -- 24.1 Flow networks -- 24.2 The Ford-Fulkerson method -- 24.3 Maximum bipartite matching -- 25 Matchings in Bipartite Graphs -- 25.1 Maximum bipartite matching (revisited) -- 25.2 The stable-marriage problem -- 25.3 The Hungarian algorithm for the assignment problem -- VII Selected Topics -- Introduction -- 26 Parallel Algorithms -- 26.1 The basics of fork-join parallelism -- 26.2 Parallel matrix multiplication -- 26.3 Parallel merge sort -- 27 Online Algorithms -- 27.1 Waiting for an elevator -- 27.2 Maintaining a search list -- 27.3 Online caching -- 28 Matrix Operations -- 28.1 Solving systems of linear equations -- 28.2 Inverting matrices -- 28.3 Symmetric positive-definite matrices and least-squares approximation -- 29 Linear Programming -- 29.1 Linear programming formulations and algorithms -- 29.2 Formulating problems as linear programs -- 29.3 Duality -- 30 Polynomials and the FFT -- 30.1 Representing polynomials -- 30.2 The DFT and FFT -- 30.3 FFT circuits -- 31 Number-Theoretic Algorithms -- 31.1 Elementary number-theoretic notions -- 31.2 Greatest common divisor -- 31.3 Modular arithmetic -- 31.4 Solving modular linear equations -- 31.5 The Chinese remainder theorem -- 31.6 Powers of an element -- 31.7 The RSA public-key cryptosystem -- 31.8 Primality testing -- 32 String Matching -- 32.1 The naive string-matching algorithm -- 32.2 The Rabin-Karp algorithm -- 32.3 String matching with finite automata -- 32.4 The Knuth-Morris-Pratt algorithm -- 32.5 Suffix arrays -- 33 Machine-Learning Algorithms -- 33.1 Clustering -- 33.2 Multiplicative-weights algorithms.

33.3 Gradient descent -- 34 NP-Completeness -- 34.1 Polynomial time -- 34.2 Polynomial-time verification -- 34.3 NP-completeness and reducibility -- 34.4 NP-completeness proofs -- 34.5 NP-complete problems -- 35 Approximation Algorithms -- 35.1 The vertex-cover problem -- 35.2 The traveling-salesperson problem -- 35.3 The set-covering problem -- 35.4 Randomization and linear programming -- 35.5 The subset-sum problem -- VIII Appendix: Mathematical Background -- Introduction -- A Summations -- A.1 Summation formulas and properties -- A.2 Bounding summations -- B Sets, Etc. -- B.1 Sets -- B.2 Relations -- B.3 Functions -- B.4 Graphs -- B.5 Trees -- C Counting and Probability -- C.1 Counting -- C.2 Probability -- C.3 Discrete random variables -- C.4 The geometric and binomial distributions -- C.5 The tails of the binomial distribution -- D Matrices -- D.1 Matrices and matrix operations -- D.2 Basic matrix properties -- Bibliography -- Index.

Description based on publisher supplied metadata and other sources.

Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2023. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.

There are no comments on this title.

to post a comment.