Introduction to Algorithms

Introduction to Algorithms
	Cover of the fourth 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-04630-5

Last updated April 15, 2024

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 ^[1] and is commonly cited as a reference for algorithms in published papers, with over 10,000 citations documented on CiteSeerX,^[2] and over 67,000 citation on Google Scholar as of 2023.^[3] The book sold half a million copies during its first 20 years,^[4] and surpassed a million copies sold in 2022.^[5] Its fame has led to the common use of the abbreviation "CLRS" (Cormen, Leiserson, Rivest, Stein), or, in the first edition, "CLR" (Cormen, Leiserson, Rivest).^[6]

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.^[7]

Editions

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)."^[8] The third edition was published in August 2009. The fourth edition was published in April 2022, which has colors added to improve visual presentations.^[9]

Cover design

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.^[10]An Introduction to Language by Fromkin also uses Calder's mobile on its cover.

Publication history

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:^[11]
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:^[12]
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022) [1990]. Introduction to Algorithms (4th ed.). MIT Press and McGraw-Hill. ISBN 0-262-04630-X. 1312 pp., errata:^[13]

Reviews

Akl, Selim G. (1991). "Review of 1st edition". Mathematical Reviews. MR 1066870.
Mann, C. J. H. (April 2003). "New edition of algorithms book [review of 2nd edition]". Kybernetes. 32 (3). doi:10.1108/k.2003.06732cae.004.
Thimbleby, Harold (December 3, 2009). "No excuse to be illiterate about IT [review of 3rd edition]". Times Higher Education.
El-Sharoud, Walid (September 2019). "Review of 3rd edition". Science Progress. 102 (3): 278–279. doi: 10.1177/0036850419873799b . PMC 10424523 .

Related Research Articles

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

In computer science, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in time. The algorithm was first published by Yefim Dinitz in 1970, and independently published by Jack Edmonds and Richard Karp in 1972. Dinitz's algorithm includes additional techniques that reduce the running time to $.$

In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of greedy algorithms for a problem.

In computational geometry, the gift wrapping algorithm is an algorithm for computing the convex hull of a given set of points.

MacDraw is a discontinued vector graphics 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. It was eventually adapted by Claris and, in the early 1990s, MacDraw Pro was released with color support. MacDraw was the vector-based cousin of MacPaint.

<span class="mw-page-title-main">Graph (abstract data type)</span> Abstract data type in computer science

In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from the field of graph theory within mathematics.

Kenneth Edward Batcher was an American academic who was emeritus professor of Computer Science at Kent State University. He also worked as a computer architect at Goodyear Aerospace in Akron, Ohio for 28 years.

<span class="mw-page-title-main">Iterated logarithm</span> Inverse function to a tower of powers

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 and professor at Massachusetts Institute of Technology (M.I.T.). He specializes in the theory of parallel computing and distributed computing.

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

<span class="mw-page-title-main">Clifford Stein</span> American computer scientist

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.

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 an emeritus 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, and speeding up computations with high latency. In 2022, he was elected as a Democratic member of the New Hampshire House of Representatives.

In computer science, SUHA is a basic assumption that facilitates the mathematical analysis of hash tables. The assumption states that a hypothetical hashing function will evenly distribute items into the slots of a hash table. Moreover, each item to be hashed has an equal probability of being placed into a slot, regardless of the other elements already placed. This assumption generalizes the details of the hash function and allows for certain assumptions about the stochastic system.

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, the Brodal queue is a heap/priority queue structure with very low worst case time bounds: $for insertion, find-minimum, meld and decrease-key and for delete-minimum and general deletion. They are the first heap variant to achieve these bounds without resorting to amortization of operational costs. Brodal queues are named after their inventor Gerth Stølting Brodal.$

In computer science, an order statistic tree is a variant of the binary search tree (or more generally, a B-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.

This is a comparison of the performance of notable data structures, as measured by the complexity of their logical operations. For a more comprehensive listing of data structures, see List of data structures.

References

↑ Introduction to Algorithms. MIT Electrical Engineering and Computer Science. MIT Press. 18 June 1990. ISBN 978-0-262-03141-7 . 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.
↑ "Introduction to Algoritms". Google Scholar. Retrieved 2023-11-26.
↑ Larry Hardesty (August 10, 2011). "Milestone for MIT Press's bestseller". MIT News Office. Retrieved August 16, 2011.
↑ Jane Halpern (February 23, 2022). "Q&A: What makes a bestselling textbook?". MIT News. Massachusetts Institute of Technology. Retrieved 26 November 2023.
↑ "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, Thomas H. (22 March 2022). Introduction to Algorithms (4th ed.). MIT Press. ISBN 9780262046305 . Retrieved August 19, 2022.
↑ 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.
↑ "Errata for Introduction to Algorithms, 4th Edition". mitp-content-server.mit.edu.

External links

Official website on MIT Press

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.

[1] Introduction to Algorithms. MIT Electrical Engineering and Computer Science. MIT Press. 18 June 1990. ISBN 978-0-262-03141-7 . Retrieved 2017-07-02.

[2] "Introduction to Algorithms—CiteSeerX citation query". CiteSeerX . The College of Information Sciences and Technology at Penn State. Retrieved 2012-05-15.

[3] "Introduction to Algoritms". Google Scholar. Retrieved 2023-11-26.

[4] Larry Hardesty (August 10, 2011). "Milestone for MIT Press's bestseller". MIT News Office. Retrieved August 16, 2011.

[5] Jane Halpern (February 23, 2022). "Q&A: What makes a bestselling textbook?". MIT News. Massachusetts Institute of Technology. Retrieved 26 November 2023.

[6] "Eternally Confuzzled - Red/Black Trees". Archived from the original on 2014-11-29. Retrieved 2013-07-17.

[7] Cormen; Leiserson; Riverst; Stein (2009). "Preface". Introduction to Algorithms (3 ed.). Cambridge, Massachusetts: MIT Press. pp. xiii–xiv. ISBN 978-0-262-03384-8.

[8] "V-Business Card". www.csd.uwo.ca.

[9] Cormen, Thomas H. (22 March 2022). Introduction to Algorithms (4th ed.). MIT Press. ISBN 9780262046305 . Retrieved August 19, 2022.

[10] Cormen et al, back cover. See, also, Big Red at the Whitney Museum of American Art web site.

[11] "Introduction to Algorithms, Second Edition". www.cs.dartmouth.edu.

[12] "Introduction to Algorithms, Third Edition". www.cs.dartmouth.edu.

[13] "Errata for Introduction to Algorithms, 4th Edition". mitp-content-server.mit.edu.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]