Introduction to Algorithms

Last updated
Introduction to Algorithms
Clrs3.jpeg
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)
Pages1312
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 [1] and is commonly cited as a reference for algorithms in published papers, with over 10,000 citations documented on CiteSeerX. [2] The book sold half a million copies during its first 20 years. [3] 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). [4]

Contents

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]

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)." [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 ]

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

Table of contents

Publication history

See also

Related Research Articles

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.

Ron Rivest American cryptographer

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 algorithm for searching the nodes of a graph in order by their hop count from a starting node

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 an inefficient recursive sorting algorithm

Stooge sort is a recursive sorting algorithm. It is notable for its exceptionally bad time complexity of O(nlog 3 / log 1.5 ) = O(n2.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.

Iterated logarithm the 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 E. Leiserson American computer scientist

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 Stein 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.

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.

Closest pair of points problem the problem of finding the two points with minimum distance from a larger finite set of points

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.

Left-child right-sibling binary tree type of binary tree

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.

Fork–join model way of designing and executing parallel computations

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.

References

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