Introduction to Algorithms, 3rd Edition (MIT Press)

Category: Programming
Author: Thomas H. Cormen
4.3
All Stack Overflow 54
This Year Reddit 59
This Month Reddit 4

About This Book

Some books on algorithms are rigorous but incomplete; others cover masses of material but lack rigor. Introduction to Algorithms uniquely combines rigor and comprehensiveness. The book covers a broad range of algorithms in depth, yet makes their design and analysis accessible to all levels of readers. Each chapter is relatively self-contained and can be used as a unit of study. The algorithms are described in English and in a pseudocode designed to be readable by anyone who has done a little programming. The explanations have been kept elementary without sacrificing depth of coverage or mathematical rigor.

The first edition became a widely used text in universities worldwide as well as the standard reference for professionals.

The second edition featured new chapters on the role of algorithms, probabilistic analysis and randomized algorithms, and linear programming.

The third edition has been revised and updated throughout. It includes two completely new chapters, on van Emde Boas trees and multithreaded algorithms, substantial additions to the chapter on recurrence (now called "Divide-and-Conquer"), and an appendix on matrices. It features improved treatment of dynamic programming and greedy algorithms and a new notion of edge-based flow in the material on flow networks. Many new exercises and problems have been added for this edition. As of the third edition, this textbook is published exclusively by the MIT Press.

Comments

by pietremalvo1   2019-08-24

Best book: Introduction to Algorithms https://www.amazon.it/dp/0262033844/ref=cm_sw_r_cp_apa_i_PB1YCbFSV6BFK

It goes through data structures, algorithms and their cost (time, space etc..)

by forzrin   2019-08-24

It was a few years ago, but lots of entire series of lectures are online. I got through most of the "core" CS concepts in ~2 years of doing intense academic learning alongside actually writing code (and releasing some stuff to small groups or to app stores). Picking straightforward, small projects with a specific academic challenge like a game with a simple concept but needs pathfinding algorithms (and implementing them myself instead of using a framework)

e.g. Data Structures (YouTube)

You can also find series of lectures like the above on algorithms. Than do basic research on what the most common/industry standard textbooks for these topics are, like Introduction to Algorithms (Amazon link) and buy them or download PDFs or whatever.

The important thing is to actually do the work, suggested tasks/projects, etc. Personal accountability is the driver, here.

Then there are one off books like Code: Hidden Language (Amazon link) that explore specific topics or walk you through certain ideas and concepts at a kind of introductory level. If you find the topic interesting or it is important for your work, it's a good starting point to learn about the lowest level stuff.

by panicClark   2019-08-24

Io lavoro come sviluppatore ormai da diversi anni, anch'io non laureato (o meglio, laureato lo sarei, ma in un ambito piuttosto distante dall'informatica).

Le difficoltà maggiori all'inizio le ho incontrate quando si trattava di andare un pelino oltre al "giocare col lego" con linguaggi e framework (rigorosamente di alto livello): i fondamentali di come funzionano le reti e i protocolli, le strutture dati e gli algoritmi. Il primo ambito sto ancora cercando di approfondirlo bene, per strutture dati e algoritmi all'epoca mi consigliarono Introduction to Algorithms e devo dire che mi ci sono trovato abbastanza bene, seppure l'ho trovato noioso da seguire.

Mi è tornato relativamente più utile approfondire i linguaggi funzionali. Il classico in tal senso è Purely Functional Data Structures, ma a me è piaciuto di più Functional Programming in Scala.

by drchlt   2019-07-21

El de Cormen es uno de los que más se usan a nivel de postgrado.

Por mucho es lo más completo qué hay.

Edit: aquí está https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844

by jaimeandresb   2019-07-21

Cormen’s intro to Algorithms. A classic https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844

by IT-Vagabond   2019-07-21

https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844

besis

by anonymous   2019-07-21

Based on my limited study, (we haven't reached Amortization so this might be where Jim has the rest correct), but basically you just go based on whoever is slowest of the overall algorithm.

This seems to be a good book on the subject of Algorithms (I haven't got much to compare to): http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844/ref=sr_1_1?ie=UTF8&qid=1303528736&sr=8-1

Also MIT has a full course on the Algorithms on their site here is the link for that too! http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/

I've actually found it helpful, it might not answer specifically your question, but I think it will help get you more confident seeing some of the topics explained a few times.

by anonymous   2019-07-21

The O(1) refers to complexity during runtime. Usually, procedures which execute in O(1) time are said to execute in constant time. In this case, the documentation claims that the time needed for push_back to execute is constant with respect to the length of the list; that is, its execution time will be a fixed constant time independent of the list's length.

On the other hand, if the documentation had claimed that push_back executed with O(n) complexity, that would have indicated that push_back's execution time could be approximated by a linear function of the list's length, where the list's length here is n. Functions that fall in this complexity category are said to execute in linear time.

Wikipedia has a good introduction to the O(n) notation [1]. A good introductory text is "An Introduction to Algorithms" by Cormen, Lieverson, and Rivest.

  • [1] http://en.wikipedia.org/wiki/Big_oh_notation.
  • [2] http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844
by anonymous   2019-07-21

Theta bound means that it is a tight asymptotic bound, that bounds the running time both from above and below. In your example, N^2 is both a lower and upper bound on the running time, and hence it is a theta bound on the running time.

More formally:

there exists k1 and k2 such that:

N^2 * k1 <= N(N+1)/2 <= N^2 * k2

for N > some value N0.

Ps. This book gives a pretty good explanation of the different asymptotic bounds: http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844/ref=sr_1_1?ie=UTF8&qid=1295777605&sr=8-1

by PlanZSmiles   2019-07-21

Hey bud, I'll try to answer them the best I can!

  1. I'm reading CLRS (https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844) which is a Data structures and algorithms book that is highly recommended by like all of reddit it seems. The only resource I can recommend for Interfaces and OOP principles is codegym.cc as that's how I learned and understood them. Head First Java is also really good even though its dated.

  2. I did not, it ended up not being necessary. It's probably a great course but it seemed too basic when I started it and it wasn't engaging enough for me.

  3. Yes, all the time. Actually when I got stuck extending the Chad Darby CRUD application as a personal project, I ended up wasting 2 weeks because I just didn't want to open up IntelliJ and look at code anymore lol. I was really frustrated and when I came back to it and eventually realized that I'm not getting anywhere trying to solve it so I might as well just put it down. I'm confident I'll be able to go back later and solve it.

Best thing I can suggest, is don't get caught up in the theory too much because you will get bored/discouraged/anyothernegativefeeling due to you not being able to see it put in practice. Start using a framework and build things and build more things, brainstorm ideas for those things, and then research how to make those ideas.

Just remember to make it part of your life and not something you're trying to do. You're a developer, you just need to prove it to a hiring manager. Be consistent and you'll get there just trust the process :)

And thank you man, we can both do it keep going!

edit:

  • Start building things with a framework once you understand java syntax and are familiar with java core. Spring framework, JavaFX, Swing, etc.
by Freonr2   2019-07-21

https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844

by dullchristmas   2019-07-21

I will always and forever tell CS students here to take Algorithm Design with Alper Ungor. If you feel somewhat confident with data structures and discrete math, the class will level you up in terms of interview prep and give you an appreciation for the mathematical side of the major in general.

The class goes over a lot of the topics in the Introduction To Algorithms textbook, starting with sorting algorithms and getting into topics related to dynamic programming, graph traversal, computational geometry, P=NP, etc. Ungor seems to have relaxed with how strict he is with undergraduates, he expressed many times that he prefers teaching undergrads and wanted to make the class more appealing to a larger crowd. He also respected the class a ton and took feedback very seriously

by anonymous   2019-07-21

If you look at the OpenCV source code for the partition function, you will see the following comments:

// This function splits the input sequence or set into one or more equivalence classes and
// returns the vector of labels - 0-based class indexes for each element.
// predicate(a,b) returns true if the two sequence elements certainly belong to the same class.
//
// The algorithm is described in "Introduction to Algorithms"
// by Cormen, Leiserson and Rivest, the chapter "Data structures for disjoint sets"
template<typename _Tp, class _EqPredicate> int partition( const vector<_Tp>& _vec, vector<int>& labels, _EqPredicate predicate=_EqPredicate())
{
    // ... etc.
}

This gives you both the source code, and the reference for the algorithm.

So, that's Chapter 21 in this book.

by anonymous   2019-07-21

The ascii values can be computed so essentially this is an integer sort. Comparison based sorting routines will at best get you O(n lg n) - Merge Sort (with additional space needed for creating two more arrays of size n/2) or O(n^2) at worst (insertion sort, quicksort, but they have no additional space complexity). These are asymptotically slower than a linear sorting algorithm. I recommend looking at CLRS (http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844). The chapter on sorting in linear time. O(n) is probably the best you can do in this scenario. Also, this post might help. Sorting in linear time?

I'd check out radix sort. http://en.wikipedia.org/wiki/Radix_sort

by anonymous   2019-07-21

You may find a good answer in this book - http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844 - I'll summarize what I recall for you.

Basically you'll have two arrays of equal size (hopefully larger than n where n=number of elements you want to store). We'll call them Array A and Array B.

Array A[i] holds the data value. Array B[i] holds the 'next' value 'k' such that A[i]->next = A[k].

Hopefully this helps.

by joycian   2019-06-23
Read this book:

https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press...

It's all in there. Put away a week of time to really start digging into it, get into the habit of learning from a book. I'd say it's worth it.

by CodeSheikh   2019-01-20
Nice list. Appreciate it. But I see there are a few amazing software books missing from the list such as:

- Clean Code (by "Uncle Bob")) [https://www.amazon.com/Clean-Code-Handbook-Software-Craftsma...]

- Design Patterns (by "Gang of 4") [https://www.amazon.com/Design-Patterns-Elements-Reusable-Obj...]

- Introduction to Algorithms (by "CLRS") [https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press...]

by alphaglosined   2019-01-13

I would recommend not looking for C# specific books. Language specific books tend to get out-dated very fast and won't be as high of quality.

For this reason you want books like [https://toptalkedbooks.com/amzn/0262033844) and [https://toptalkedbooks.com/amzn/0321751043)

&#x200B;

I'm personally in the market for data structure books, sadly its a slippery slope when you already have a few.

by bautin   2019-01-13

Start here and I'm not joking.

It's a game about programming essentially. The first few levels will seem fairly cakewalk and they are, but the later levels can get tricky. Then there are the size and speed challenges for each level.

And I know it's not C++, but python is a good place to start.

Also, pick up Introduction to Algorithms . I don't know your situation monetarily. I see that you're 15.

by PixelizedPlayer   2019-01-13

Well i saw this :

https://toptalkedbooks.com/amzn/0262033844

But its a bit over kill and its not easy to understand some of the syntax since they use computer science type language that i also see in some papers when trying to understand shaders and thats also hard to read too.

Unless you have a good suggestion that covers the information thats accessible for those without CS knowledge?