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 6

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 WeirdMexican1   2019-11-17

I was just finished my courses from my math degree, so I started reading Introduction to Algorithms, and totally change the things I want to do.

I learned that in my university the people that work in algorithms work in Computation Geometry and Data structures. Where can I find a master in algorithm desing thats is best suited for a matematician and what other themes are studied. I´m don´t know anything about this field of math and computer science.( Only for what I read)

by richi10820   2019-11-17

When I took the class we used this textbook which helped me a lot. Also, for practice problems I usually went to leetcode or geeksforgeeks (for example I used this for dynamic programming practice). Hope it helps!

by hextree   2019-11-17

Well it's been almost a decade since I read them, so I may not be the most up-to-date source. Introduction to Algorithms is a solid choice and gets mentioned a lot here. After you've understood the fundamentals, Skiena's Algorithm Design Manual is a good next step. It covers more advanced design theory, in particular there are some descriptions of real-life case studies and how Skiena approached them with algorithms design.

For Theory of Computation (Turing Machines, P vs NP, etc), I used Computational Complexity: A Modern Approach, because the draft is free on their website. It's pretty comprehensive and has a good selection of exercises. It's a draft though, so has a few typos or incomplete bits. Certainly companies aren't going to ask you questions about advanced theory, but the way I see it, if you can get through this book then you'll have mastered any Big Oh questions.

Alongside all that, Leetcode and Hackerrank are certainly great to test your knowledge practically. I practise them occasionally (I much prefer Hackerrank's interface and consistency), I just don't go overboard with grinding.

A more 'competitive coding' oriented book I've been looking at recently is: http://www.lookingforachallengethebook.com/ It has a few problems set at a far more advanced level than Leetcode.

by Fizz-Buzzkill   2019-11-17

Tom Cormen co-authored it also. He's one of the authors of the famous textbook Introduction to Algorithms

by BICHO_CHICKEN_   2019-11-17

Unless you're gifted with coding and algorithms, don't expect to be able to land an interview and then land a job. Interviews will test you on algorithms, and coding.

If I were you, I'd just focus on learning Java syntax very well, then move on to OOP principles, and then move on to MVC principles.

Assuming you already have the required math background, you need to open this book, and starting going through the important parts in each chapter, and committing it to memory. You will be tested on things from this book during job interviews. You are expected to code them as well. Amazon specifically ask about Linear Programming whereas Google might ask about other stuff.

Not many make it without a CS degree. I have made a few bucks selling game apps, but there is always better things to do out there.

Algorithms book, considered to the holy bible in CS

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

Start using Java, and commit things to memory.

You will need at least 9 months of prep time.

Use this book to learn java https://www.amazon.com/Introduction-Programming-Structures-Comprehensive-Version/dp/0134670949/ref=sr_1_3?keywords=liang+java&qid=1564003011&s=books&sr=1-3

Use this other book as well:

http://www.deitel.com/Books/Java/JavaHowtoProgram11e/tabid/3683/Default.aspx

I assume you already know how to study and memorize and take good notes.

To get started on making game apps, visit this, and download it, it may help to fund you https://www.scirra.com/

by Lapompaelpompei   2019-11-17

There are many courses on the internet. Coursera, Udemy, etc.. I recommend you to read at least a book about it. It really helps you to understand the logic and complexity. For data structures, I also recommend you to implement them by your self.

This is a very good book: https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844

This is the full MIT course: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/

I strongly recommend you to follow the course and read the book.

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