Introduction to Algorithms: Difference between revisions

Revision as of 15:12, 17 April 2021

Latest revision as of 08:06, 13 December 2024

(47 intermediate revisions by 24 users not shown)

Line 1:

{{Short description|Book on computer programming, used as textbook for algorithms courses}}

{{Infobox book

| name = Introduction to Algorithms

| image = Clrs3Clrs4.jpeg

| caption = Cover of the thirdfourth edition

| author = [[Thomas H. Cormen]]<br />[[Charles E. Leiserson]]<br />[[Ron Rivest|Ronald L. Rivest]]<br />[[Clifford Stein]]

| country = [[United States]]

| language = [[English language|English]]

| subject = [[Algorithm#Computer algorithms|Computer algorithms]]

| publisher = [[MIT Press]]

| pub_date = 1990 (first edition)

| pages = 1312

| isbn = 978-0-262-0338404630-85

}}

'''''Introduction to Algorithms''''' is a book on computer programming by [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ron Rivest|Ronald L. Rivest]], and [[Clifford Stein]]. The book hasis beendescribed widelyby usedits publisher as "the [[textbook]]leading foralgorithms [[algorithm]]stext [[Coursein (education)|courses]]universities atworldwide manyas [[universities]]well as the standard reference for professionals".<ref>{{Cite web |title=Introduction to Algorithms, fourth edition |url=https://mitpress.mit.edu/books9780262046305/introduction-to-algorithms |titleaccess-date=Introduction2024-11-04 to Algorithms|website=MIT Press |language=en-US|access-date=2017-07-02}}</ref> andIt is commonly [[Citation|cited]] as a reference for algorithms in published [[Academic publishing#Scholarly paper|papers]], with over 10,000 citations documented on [[CiteSeerX]].,<ref>{{cite web |url=httphttps://citeseerx.ist.psu.edu/showciting?cid=1910 |title=Introduction to Algorithms&mdash;CiteSeerX citation query |access-date=2012-05-15 |work=[[CiteSeerX]] |publisher=The College of Information Sciences and Technology at Penn State |archive-url=https://web.archive.org/web/20220819003324/https://citeseerx.ist.psu.edu/showciting?cid=1910 |archive-date=2022-08-19 |url-status=dead }}</ref> and over 70,000 citations on Google Scholar as of 2024.<ref>{{Cite web |url=https://scholar.google.com/citations?view_op=view_citation&hl=en&user=V5FJ6pIAAAAJ&citation_for_view=V5FJ6pIAAAAJ:u5HHmVD_uO8C |title=Introduction to Algorithms |access-date=2024-12-13 |website=Google Scholar}}</ref> The book sold half a million copies during its first 20 years.,<ref>{{cite news |url=httphttps://webnews.mit.edu/newsoffice/2011/introduction-to-algorithms-500k-0810.html |title=Milestone for MIT Press's bestseller |author=Larry Hardesty |date=August 10, 2011 |publisher=MIT News Office |access-date=August2024-11-26}}</ref> 16and surpassed a million copies sold in 2022.<ref>{{cite web |title=Q&A: What makes a bestselling textbook? |author=Jane Halpern |date=February 23, 20112022 |url=https://news.mit.edu/2022/qa-what-makes-bestselling-textbook-introduction-algorithms-0223 |website=MIT News |publisher=Massachusetts Institute of Technology |access-date=26 November 2023}}</ref> 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).<ref>{{cite web |url=http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx |title=Eternally Confuzzled - Red/Black Trees |access-date=2013-07-17 |archive-url=https://web.archive.org/web/2014112902431220150210154825/http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx |archive-date=20142015-1102-2910 |url-status=dead}}</ref>

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.<ref>{{Cite book |title=Introduction to Algorithms |lastlast1=Cormen |last2=Leiserson |last3=Riverst |last4=Stein |publisher=MIT Press |year=2009 |isbn=978-0-262-03384-8 |edition=3 |___location=Cambridge, Massachusetts |pages=xiii-xiv |chapter=Preface}}</ref>

==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 [[Book cover|cover]] changed to green, causing the [[nickname]] to be shortened to just "The Big Book (of Algorithms)."<ref>{{cite web |url=httphttps://wwwweb.csdcs.uwodal.ca/~jamie/UWO/.Refs/tech-books.html |title=V-BusinessSome Useful Technical Books Card|website=wwwweb.csdcs.uwodal.ca}}</ref> AThe third edition was published in August 2009. PlansThe for the nextfourth edition startedwas published in 2014April 2022, butwhich thehas fourthcolors editionadded willto notimprove bevisual publishedpresentations.<ref>{{Cite earlierbook than the|last=Cormen |first=Thomas half of 2022H.<ref> |url=https://wwwmitpress.quoramit.comedu/Whenbooks/introduction-will-thealgorithms-fourth-edition-of- |title=Introduction- to- Algorithms |date=22 March 2022 |publisher=MIT Press |isbn=9780262046305 |edition=4th |language=en-beUS |access-releaseddate=August 19, 2022 }}</ref>

==Cover design==

The [[mobile (sculpture)|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]].<ref>Cormen et al, back cover. See, also, [https://whitney.org/collection/works/2826 ''Big Red''] at the Whitney Museum of American Art web site.</ref>

==Table of contents==

*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

==Publication history==

* {{Introduction to Algorithms|1|notitlelink=1}}

* {{Introduction to Algorithms|2|notitlelink=1}} 12 printings up to 2009, errata:<ref>{{cite web |url=httphttps://www.cs.dartmouth.edu/~thc/clrs-bugs/bugs-2e.php |title=Introduction to Algorithms, Second Edition |website=www.cs.dartmouth.edu}}</ref>

* {{Introduction to Algorithms|3|notitlelink=1}} 1320 pp., 5 printings up to 2016), errata:<ref>{{cite web |url=httphttps://www.cs.dartmouth.edu/~thc/clrs-bugs/bugs-3e.php |title=Introduction to Algorithms, Third Edition |website=www.cs.dartmouth.edu}}</ref>

* {{Introduction to Algorithms|4|notitlelink=1}} 1312 pp., errata:<ref>{{cite web |title=Errata for Introduction to Algorithms, 4th Edition |url=https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/11599/e4-bugs.html |website=mitp-content-server.mit.edu}}</ref>

==Reviews==

*{{cite journal

| last = Akl | first = Selim G. | author-link = Selim Akl

| journal = Mathematical Reviews

| mr = 1066870

| title = Review of 1st edition

| year = 1991}}

*{{cite journal

| last = Mann | first = C. J. H.

| date = April 2003

| doi = 10.1108/k.2003.06732cae.004

| issue = 3

| journal = Kybernetes

| title = New edition of algorithms book [review of 2nd edition]

| volume = 32}}

*{{cite news

| last = Thimbleby | first = Harold | author-link = Harold Thimbleby

| date = December 3, 2009

| newspaper = Times Higher Education

| title = No excuse to be illiterate about IT [review of 3rd edition]

| url = https://www.timeshighereducation.com/books/textbook-guides/8-november-2012/introduction-to-algorithms/409350.article}}

*{{cite journal

| last = El-Sharoud | first = Walid

| date = September 2019

| doi = 10.1177/0036850419873799b

| issue = 3

| journal = Science Progress

| pages = 278–279

| title = Review of 3rd edition

| volume = 102| doi-access = free

| pmc = 10424523

}}

==See also==

Line 84 ⟶ 70:

==External links==

* {{Official website|httphttps://mitpress.mit.edu/9780262046305/introduction-to-algorithms}} on [[MIT Press]]

[[Category:1990 non-fiction books]]

[[Category:Computer science books]]

[[Category:MIT Press books]]

{{compu-book-stub}}