Skip to content

Introduction to Algorithms

Spend $50 to get a free DVD!

ISBN-10: 0262033844

ISBN-13: 9780262033848

Edition: 3rd 2009

Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

List price: $99.00
Shipping box This item qualifies for FREE shipping.
Blue ribbon 30 day, 100% satisfaction guarantee!
Alternate versions
true
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!

Customers also bought

Book details

List price: $99.00
Edition: 3rd
Copyright year: 2009
Publisher: MIT Press
Publication date: 7/31/2009
Binding: Hardcover
Pages: 1312
Size: 8.50" wide x 9.50" long x 2.00" tall
Weight: 5.236
Language: English

Thomas H. Cormen received a Ph. D. from MIT in 1992. He is an associate professor at Dartmouth College. Cormen is one of the authors of Introduction to Algorithms.

Preface
Foundations
Introduction
The Role of Algorithms in Computing
Algorithms
Algorithms as a technology
Getting Started
Insertion sort
Analyzing algorithms
Designing algorithms
Growth of Functions
Asymptotic notation
Standard notations and common functions
Divide-and-Conquer
The maximum-subarray problem
Strassen's algorithm for matrix multiplication
The substitution method for solving recurrences
The recursion-tree method for solving recurrences
The master method for solving recurrences
Proof of the master theorem
Probabilistic Analysis and Randomized Algorithms
The hiring problem
Indicator random variables
Randomized algorithms
Probabilistic analysis and further uses of indicator random variables
Sorting and Order Statistics
Introduction
Heapsort
Heaps
Maintaining the heap property
Building a heap
The heapsort algorithm
Priority queues
Quicksort
Description of quicksort
Performance of quicksort
A randomized version of quicksort
Analysis of quicksort
Sorting in Linear Time
Lower bounds for sorting
Counting sort
Radix sort
Bucket sort
Medians and Order Statistics
Minimum and maximum
Selection in expected linear time
Selection in worst-case linear time
Data Structures
Introduction
Elementary Data Structures
Stacks and queues
Linked lists
Implementing pointers and objects
Representing rooted trees
Hash Tables
Direct-address tables
Hash tables
Hash functions
Open addressing
Perfect hashing
Binary Search Trees
What is a binary search tree?
Querying a binary search tree
Insertion and deletion
Randomly built binary search trees
Red-Black Trees
Properties of red-black trees
Rotations
Insertion
Deletion
Augmenting Data Structures
Dynamic order statistics
How to augment a data structure
Interval trees
Advanced Design and Analysis Techniques
Introduction
Dynamic Programming
Rod cutting
Matrix-chain multiplication
Elements of dynamic programming
Longest common subsequence
Optimal binary search trees
Greedy Algorithms
An activity-selection problem
Elements of the greedy strategy
Huffman codes
Matroids and greedy methods
A task-scheduling problem as a matroid
Amortized Analysis
Aggregate analysis
The accounting method
The potential method
Dynamic tables
Advanced Data Structures
Introduction
B-Trees
Definition of B-trees
Basic operations on B-trees
Deleting a key from a B-tree
Fibonacci Heaps
Structure of Fibonacci heaps
Mergeable-heap operations
Decreasing a key and deleting a node
Bounding the maximum degree
van Emde Boas Trees
Preliminary approaches
A recursive structure
The van Emde Boas tree
Data Structures for Disjoint Sets
Disjoint-set operations
Linked-list representation of disjoint sets
Disjoint-set forests
Analysis of union by rank with path compression
Graph Algorithms
Introduction
Elementary Graph Algorithms
Representations of graphs
Breadth-first search
Depth-first search
Topological sort
Strongly connected components
Minimum Spanning Trees
Growing a minimum spanning tree
The algorithms of Kruskal and Prim
Single-Source Shortest Paths
The Bellman-Ford algorithm
Single-source shortest paths in directed acyclic graphs
Dijkstra's algorithm
Difference constraints and shortest paths
Proofs of shortest-paths properties
All-Pairs Shortest Paths
Shortest paths and matrix multiplication
The Floyd-Warshall algorithm
Johnson's algorithm for sparse graphs
Maximum Flow
Flow networks
The Ford-Fulkerson method
Maximum bipartite matching
Push-relabel algorithms
The relabel-to-front algorithm
Selected Topics
Introduction
Multithreaded Algorithms
The basics of dynamic multithreading
Multithreaded matrix multiplication
Multithreaded merge sort
Matrix Operations
Solving systems of linear equations
Inverting matrices
Symmetric positive-definite matrices and least-squares approximation
Linear Programming
Standard and slack forms
Formulating problems as linear programs
The simplex algorithm
Duality
The initial basic feasible solution
Polynomials and the FFT
Representing polynomials
The DFT and FFT
Efficient FFT implementations
Number-Theoretic Algorithms
Elementary number-theoretic notions
Greatest common divisor
Modular arithmetic
Solving modular linear equations
The Chinese remainder theorem
Powers of an element
The RSA public-key cryptosystem
Primality testing
Integer factorization
String Matching
The naive string-matching algorithm
The Rabin-Karp algorithm
String matching with finite automata
The Knuth-Morris-Pratt algorithm
Computational Geometry
Line-segment properties
Determining whether any pair of segments intersects
Finding the convex hull
Finding the closest pair of points
NP-Completeness
Polynomial time
Polynomial-time verification
NP-completeness and reducibility
NP-completeness proofs
NP-complete problems
Approximation Algorithms
The vertex-cover problem
The traveling-salesman problem
The set-covering problem
Randomization and linear programming
The subset-sum problem
Appendix: Mathematical Background
Introduction
Summations
Summation formulas and properties
Bounding summations
Sets, Etc.
Sets
Relations
Functions
Graphs
Trees
Counting and Probability
Counting
Probability
Discrete random variables
The geometric and binomial distributions
The tails of the binomial distribution
Matrices
Matrices and matrix operations
Basic matrix properties
Bibliography
Index