Cover of the third edition | |

Author | Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein |
---|---|

Country | United States |

Language | English |

Subject | Computer algorithms |

Publisher | MIT Press |

Publication date | 1990 (first edition) |

Pages | 1312 |

ISBN | 978-0-262-03384-8 |

* Introduction to Algorithms* is a book on computer programming by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The book has been widely used as the textbook for algorithms courses at many universities

In the preface, the authors write about how the book was written to be comprehensive and useful in both teaching and professional environments. Each chapter focuses on an algorithm, and discusses its design techniques and areas of application. Instead of using a specific programming language, the algorithms are written in pseudocode. The descriptions focus on the aspects of the algorithm itself, its mathematical properties, and emphasize efficiency.^{ [5] }

The first edition of the textbook did not include Stein as an author, and thus the book became known by the initialism CLR. It included two chapters ("Arithmetic Circuits" & "Algorithms for Parallel Computers") that were dropped in the second edition. After the addition of the fourth author in the second edition, many began to refer to the book as "CLRS". This first edition of the book was also known as "The Big White Book (of Algorithms)." With the second edition, the predominant color of the cover changed to green, causing the nickname to be shortened to just "The Big Book (of Algorithms)."^{ [6] } A third edition was published in August 2009. Plans for the next edition started in 2014, but the fourth edition will not be published earlier than 2021.^{[ citation needed ]}

The mobile depicted on the cover, *Big Red* (1959) by Alexander Calder, can be found at the Whitney Museum of American Art in New York City.^{ [7] }

- I Foundations
- 1 The Role of Algorithms in Computing
- 2 Getting Started
- 3 Growth of Functions
- 4 Divide-and-Conquer
- 5 Probabilistic Analysis and Randomized Algorithms

- II Sorting and Order Statistics
- 6 Heapsort
- 7 Quicksort
- 8 Sorting in Linear Time
- 9 Medians and Order Statistics

- III Data Structures
- 10 Elementary Data Structures
- 11 Hash Tables
- 12 Binary Search Trees
- 13 Red-Black Trees
- 14 Augmenting Data Structures

- IV Advanced Design and Analysis Techniques
- 15 Dynamic Programming
- 16 Greedy Algorithms
- 17 Amortized Analysis

- V Advanced Data Structures
- 18 B-Trees
- 19 Fibonacci Heap
- 20 Van Emde Boas Trees
- 21 Data Structures for Disjoint Sets

- VI Graph Algorithms
- 22 Elementary Graph Algorithms
- 23 Minimum Spanning Trees
- 24 Single-Source Shortest Paths
- 25 All-Pairs Shortest Paths
- 26 Maximum Flow

- VII Selected Topics
- 27 Multithreaded Algorithms
- 28 Matrix Operations
- 29 Linear Programming
- 30 Polynomials and the FFT
- 31 Number-Theoretic Algorithms
- 32 String Matching
- 33 Computational Geometry
- 34 NP-Completeness
- 35 Approximation Algorithms

- VIII Appendix: Mathematical Background
- A Summations
- B Sets, Etc.
- C Counting and Probability
- D Matrices

- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990).
*Introduction to Algorithms*(1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8. - Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990].
*Introduction to Algorithms*(2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7. 12 printings up to 2009, errata:^{ [8] } - Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990].
*Introduction to Algorithms*(3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4. 1320 pp., 5 printings up to 2016), errata:^{ [9] }

In computer science, a **priority queue** is an abstract data type similar to regular queue or stack data structure in which each element additionally has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of elements with the same priority is undefined.

** Kruskal's algorithm** is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a *minimum spanning forest*.

**Ronald Linn Rivest** is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL). His work has spanned the fields of algorithms and combinatorics, cryptography, machine learning, and election integrity.

**Breadth-first search** (**BFS**) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root, and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

**MacDraw** was a vector graphic drawing application released along with the first Apple Macintosh systems in 1984. MacDraw was one of the first WYSIWYG drawing programs that could be used in collaboration with MacWrite. MacDraw was useful for drawing technical diagrams and floorplans. It was eventually adapted by Claris and, in the early 1990s, MacDraw Pro was released with color support. MacDraw was the vector cousin of MacPaint.

**Stooge sort** is a recursive sorting algorithm. It is notable for its exceptionally bad time complexity of O(*n*^{log 3 / log 1.5 }) = O(*n*^{2.7095...}). The running time of the algorithm is thus slower compared to reasonable sorting algorithms, and is slower than Bubble sort, a canonical example of a fairly inefficient sort. It is however more efficient than Slowsort. The name comes from The Three Stooges.

In computer science, the **iterated logarithm** of , written log* , is the number of times the logarithm function must be iteratively applied before the result is less than or equal to . The simplest formal definition is the result of this recurrence relation:

**Charles Eric Leiserson** is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof. As part of this effort, he developed the Cilk multithreaded language. He invented the fat-tree interconnection network, a hardware-universal interconnection network used in many supercomputers, including the Connection Machine CM5, for which he was network architect. He helped pioneer the development of VLSI theory, including the retiming method of digital optimization with James B. Saxe and systolic arrays with H. T. Kung. He conceived of the notion of cache-oblivious algorithms, which are algorithms that have no tuning parameters for cache size or cache-line length, but nevertheless use cache near-optimally. He developed the Cilk language for multithreaded programming, which uses a provably good work-stealing algorithm for scheduling. Leiserson coauthored the standard algorithms textbook *Introduction to Algorithms* together with Thomas H. Cormen, Ronald L. Rivest, and Clifford Stein.

**Left rotation** refers to the following

In computational geometry, the **line segment intersection problem** supplies a list of line segments in the Euclidean plane and asks whether any two of them intersect (cross).

**Clifford Seth Stein**, a computer scientist, is a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Science. Stein is chair of the Industrial Engineering and Operations Research Department at Columbia University. Prior to joining Columbia, Stein was a professor at Dartmouth College in New Hampshire.

In computer science, **Kosaraju's algorithm** is a linear time algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to S. Rao Kosaraju and Micha Sharir. Kosaraju suggested it in 1978 but did not publish it, while Sharir independently discovered it and published it in 1981. It makes use of the fact that the transpose graph has exactly the same strongly connected components as the original graph.

**Thomas H. Cormen** is the co-author of *Introduction to Algorithms*, along with Charles Leiserson, Ron Rivest, and Cliff Stein. In 2013, he published a new book titled *Algorithms Unlocked*. He is a professor of computer science at Dartmouth College and former Chairman of the Dartmouth College Department of Computer Science. Between 2004 and 2008 he directed the Dartmouth College Writing Program. His research interests are algorithm engineering, parallel computing, speeding up computations with high latency.

The **closest pair of points problem** or **closest pair problem** is a problem of computational geometry: given *n* points in metric space, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean plane was among the first geometric problems that were treated at the origins of the systematic study of the computational complexity of geometric algorithms.

Every multi-way or k-ary tree structure studied in computer science admits a representation as a binary tree, which goes by various names including **child-sibling representation**, **left-child, right-sibling binary tree**, **doubly chained tree** or **filial-heir chain**.

In computer science, the **worst-case complexity** measures the resources that an algorithm requires given an input of arbitrary size. It gives an upper bound on the resources required by the algorithm.

**Donald Bruce Johnson** was an American computer scientist, a researcher in the design and analysis of algorithms, and the founding chair of the computer science department at Dartmouth College.

In computer science, an **order statistic tree** is a variant of the binary search tree that supports two additional operations beyond insertion, lookup and deletion:

In computer science, a **mergeable heap** is an abstract data type, which is a heap supporting a merge operation.

In parallel computing, the **fork–join model** is a way of setting up and executing parallel programs, such that execution branches off in parallel at designated points in the program, to "join" (merge) at a subsequent point and resume sequential execution. Parallel sections may fork recursively until a certain task granularity is reached. Fork–join can be considered a parallel design pattern. It was formulated as early as 1963.

- ↑ "Introduction to Algorithms".
*MIT Press*. Retrieved 2017-07-02. - ↑ "Introduction to Algorithms—CiteSeerX citation query".
*CiteSeerX*. The College of Information Sciences and Technology at Penn State. Retrieved 2012-05-15. - ↑ Larry Hardesty (August 10, 2011). "Milestone for MIT Press's bestseller". MIT News Office. Retrieved August 16, 2011.
- ↑ "Eternally Confuzzled - Red/Black Trees". Archived from the original on 2014-11-29. Retrieved 2013-07-17.
- ↑ Cormen; Leiserson; Riverst; Stein (2009). "Preface".
*Introduction to Algorithms*(3 ed.). Cambridge, Massachusetts: MIT Press. pp. xiii–xiv. ISBN 978-0-262-03384-8. - ↑ "V-Business Card".
*www.csd.uwo.ca*. - ↑ Cormen et al, back cover. See, also,
*Big Red*at the Whitney Museum of American Art web site. - ↑ "Introduction to Algorithms, Second Edition".
*www.cs.dartmouth.edu*. - ↑ "Introduction to Algorithms, Third Edition".
*www.cs.dartmouth.edu*.

- Official websites
- by MIT Press

- MIT lecture "MIT 6.046J / 18.410J Introduction to Algorithms - Fall 2005". Held in part by coauthor Charles Leiserson. Released as part of MIT OpenCourseWare.
- At OCW.MIT.Edu. Video recordings and transcripts of the lectures.
- At VideoLectures.Net. Video recordings of the lectures. Includes slides automatically synchronized to video content.

- Exercise Solutions
- While there are no official solutions, the following may be helpful:
- Chapters 1 - 11
- Chapters 13 - 26
- GitHub

This article about a computer book or series of books is a stub. You can help Wikipedia by expanding it. |

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.