"Algorithms" book available as free download

Discussions

News: "Algorithms" book available as free download

  1. "Algorithms" book available as free download (25 messages)

    Cedric Beust has pointed out "Algorithms," by Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani. The book is available as a free PDF download. As Cedric says:
    The book is very extensive and covers the most important algorithms you will ever come across in your life as a developer, starting with the introduction of the "big O" notation, and then progressively moving to more complex topics such as graphs, dynamic programming (nothing to do with dynamic languages), linear programming and culminating this area with the Simplex algorithm (I loved this section).
    When he says that it introduces concepts like "big O," he's not kidding - this is one of the best, most concise explanations of the notation Your Humble Editor has ever seen. Cedric's original blog entry on it is "Algorithms."

    Threaded Messages (25)

  2. Excellent![ Go to top ]

    This is really a major contribution by the authors. Books like this are usually quite expensive, and I imagine it is difficult for those unfamiliar with the value of such references to cough up the money. Consequently all too many non-CS people remain all too ignorant. But now it's free! No more excuses. I'll definately add this to my library.
  3. *cough*[ Go to top ]

    This is really a major contribution by the authors. Books like this are usually quite expensive, and I imagine it is difficult for those unfamiliar with the value of such references to cough up the money. Consequently all too many non-CS people remain all too ignorant. But now it's free! No more excuses. I'll definately add this to my library.
    What does non-CS have to do with it? It's about lazy vs diligent. That's not to say non-CS people aren't ignorant. Ignorance about algorithms has little to do with a degree. my bias 2 bits peter
  4. agreed[ Go to top ]

    What does non-CS have to do with it? It's about lazy vs diligent. That's not to say non-CS people aren't ignorant. Ignorance about algorithms has little to do with a degree.
    CS people were forced to study this stuff in order to get a degree, and forced to buy really expensive books. If they were in a decent program, they didn't graduate without solid foundation in algorithms. With others learning or not learning such material is entirely up to their own initiative, discipline, and intelligence. So if I suggest to a person without a background in algorithms that he should go buy a $100 book to learn something he thinks he doesn't need to learn, nothing is going to happen. If I suggest that he look at a free website of the same caliber as a quality print book, he might humor me long enough to recognize the value and start feeling initiative.
  5. Good points[ Go to top ]

    What does non-CS have to do with it? It's about lazy vs diligent. That's not to say non-CS people aren't ignorant. Ignorance about algorithms has little to do with a degree.
    CS people were forced to study this stuff in order to get a degree, and forced to buy really expensive books. If they were in a decent program, they didn't graduate without solid foundation in algorithms. With others learning or not learning such material is entirely up to their own initiative, discipline, and intelligence. So if I suggest to a person without a background in algorithms that he should go buy a $100 book to learn something he thinks he doesn't need to learn, nothing is going to happen. If I suggest that he look at a free website of the same caliber as a quality print book, he might humor me long enough to recognize the value and start feeling initiative.
    You make some good points. On the other side, say someone does pay a lot of money for a degree and buys all those expensive book. Is he really learning the algorithms? I have lots of friends who got a degree in CS, but quite honestly only a small percent really take time to understand any given algorithm. Most just memorized it for a test and then promptly forgot it. Everyone does this in every field of study, so CS students are still students. Take for example Dr. Charles Forgy's RETE algorithm. A ton of people have been forced to read and study the algorithm, but how many understand it well enough to implement a high performance expert system shell? How many people have bothered to read Robert Doorenbos' paper on RETE unlinking and compared it to Dr. Forgy's thesis to a level where they understand all the subtleties? I've spent a large part of the last 5 years studying these papers and algorithms, so 1 semester or even 2 semester isn't going to give a person depth. Even someone getting a masters or phd in AI isn't going to have the time to analyze the differences to sufficient depth as to really get the entire picture. If someone focuses purely on pattern matching algorithms and spends 5 years on a Phd in that narrow field, the individual has the opportunity to gain depth. I would propose the idea that having read or been exposed to an algorithm doesn't make a person less ignorant. In some cases, it may give someone a false sense they understand it and feel they know better than others. Just my bias 2 bits. peter
  6. Re: Good points[ Go to top ]

    Take for example Dr. Charles Forgy's RETE algorithm. A ton of people have been forced to read and study the algorithm, but how many understand it well enough to implement a high performance expert system shell? How many people have bothered to read Robert Doorenbos' paper on RETE unlinking and compared it to Dr. Forgy's thesis to a level where they understand all the subtleties?
    I think we're talking about understanding on two very different levels.
    I would propose the idea that having read or been exposed to an algorithm doesn't make a person less ignorant.
    I disagree. Exposure may not be enough for a person to apply the knowledge directly, but it's often enough to keep a person's eyes from glazing over when they're exposed to it again.
    In some cases, it may give someone a false sense they understand it and feel they know better than others.
    A person has to learn to the point where they feel like they know everything in order to ever reach the point where they realize how very little they truly know. Who hasn't been working on a problem before, and reached a point where all-of-a-sudden everything seemed perfectly clear, only to a short time later realize the full extent of his own naivety? It's part of learning, and it's certainly not a reason to never both starting to learn.
  7. agreed[ Go to top ]

    Yes, we are talking about 2 different levels of understanding, but in my limited experience, I find superficial understanding more dangerous. Atleast someone who has never heard of an algorithm doesn't start from the assumption they know it. I've had a long running debate with various semantic web people about whether or not various semWeb rule engines really implement RETE correctly. Many of them mis-apply RETE unlinking with an incorrect assumption that a 3-tuple approach is appropriate for a domain consisting of n-tuple objects. the end result of their misunderstanding is horrible performance, which they attribute to RETE. In this specific case, superficial understanding is no different than someone who has never heard of RETE. my bias 3 bits peter
  8. Re: agreed[ Go to top ]

    Yes, we are talking about 2 different levels of understanding, but in my limited experience, I find superficial understanding more dangerous. Atleast someone who has never heard of an algorithm doesn't start from the assumption they know it.
    We're also talking about two different levels of algorithms. I'm referring to something like binary search - which most people can pick up rather quickly. The fundamentals - which I'm sure manifest themselves in all sorts of ways in algorithms like RETE.
    I've had a long running debate with various semantic web people about whether or not various semWeb rule engines really implement RETE correctly. Many of them mis-apply RETE unlinking with an incorrect assumption that a 3-tuple approach is appropriate for a domain consisting of n-tuple objects. the end result of their misunderstanding is horrible performance, which they attribute to RETE. In this specific case, superficial understanding is no different than someone who has never heard of RETE.
    Any suggested readings on the topic, preferably online or in places like IEEE or ACM? My employer has a business unit that does semantic web-esque stuff and it's been suggested I go talk to them. It would be nice to impress them with some superficial understanding. I promise if I actually move in that direction I'll strive to actually learn it ;-)
  9. Re: agreed[ Go to top ]

    Yes, we are talking about 2 different levels of understanding, but in my limited experience, I find superficial understanding more dangerous. Atleast someone who has never heard of an algorithm doesn't start from the assumption they know it.
    We're also talking about two different levels of algorithms. I'm referring to something like binary search - which most people can pick up rather quickly. The fundamentals - which I'm sure manifest themselves in all sorts of ways in algorithms like RETE.
    I've had a long running debate with various semantic web people about whether or not various semWeb rule engines really implement RETE correctly. Many of them mis-apply RETE unlinking with an incorrect assumption that a 3-tuple approach is appropriate for a domain consisting of n-tuple objects. the end result of their misunderstanding is horrible performance, which they attribute to RETE. In this specific case, superficial understanding is no different than someone who has never heard of RETE.
    Any suggested readings on the topic, preferably online or in places like IEEE or ACM? My employer has a business unit that does semantic web-esque stuff and it's been suggested I go talk to them. It would be nice to impress them with some superficial understanding. I promise if I actually move in that direction I'll strive to actually learn it ;-)
    If you search for my blog, you'll find a couple hundred entries on RETE. There's 4 entries with detailed analysis of RETE unlinking and how it is mis-used by SemWeb rule engines. I agree with you that many algorithms aren't quite as complex as RETE. Even binary search algorithm isn't so simple that a quick read is sufficient to get a solid understanding. For example, like Josh Bloch's entry http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html which brings me back to my original point. It's about being lazy vs diligent. Exposure to an algorithm is rarely sufficient to get a solid understanding. peter
  10. Re: agreed[ Go to top ]

    Exposure to an algorithm is rarely sufficient to get a solid understanding.
    My personal feeling is that understanding the concepts of time and space complexity are more important that knowing a bunch of algorithms. If a developer can recognize that a given routine has untenable time or space complexity, they can search for an algorithm (and I think this book makes a good resource for that.) Identifying the pain points of your application cannot be done with google. So I guess I kind of agree with your premise here. I do think understanding a few choice algorithms and how they improve on the naive solution is a good thing for all developers. It's really the only way to fully understand time and space complexity. A couple sort algorithms would do. I once was in a meeting where we were discussing a proposed solution where the design called for using a bubble sort. This raised a red-flag with me and it turns out that the input could contain several thousand elements and this was in a batch process on a highly important resource that was constantly stretched thin and we were paying through the nose for more capacity. It turns out that team 'always' used bubble sort because they didn't know any better.
  11. Binary Sort[ Go to top ]

    I agree with you that many algorithms aren't quite as complex as RETE. Even binary search algorithm isn't so simple that a quick read is sufficient to get a solid understanding. For example, like Josh Bloch's entry http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
    Yes, I remember when Josh Bloch posted that blog. It was quite an eye openner. This is quibbling, but I would say it more points out that one must be aware of the underlying hardware/runtime.
    which brings me back to my original point. It's about being lazy vs diligent. Exposure to an algorithm is rarely sufficient to get a solid understanding.
    Ahhh, but exposure is always necessary, even if it is not sufficient. Again, I'm quibbling.
  12. Re: Binary Sort[ Go to top ]

    I agree with you that many algorithms aren't quite as complex as RETE. Even binary search algorithm isn't so simple that a quick read is sufficient to get a solid understanding. For example, like Josh Bloch's entry http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html


    Yes, I remember when Josh Bloch posted that blog. It was quite an eye openner. This is quibbling, but I would say it more points out that one must be aware of the underlying hardware/runtime.

    which brings me back to my original point. It's about being lazy vs diligent. Exposure to an algorithm is rarely sufficient to get a solid understanding.


    Ahhh, but exposure is always necessary, even if it is not sufficient. Again, I'm quibbling.
    Playing devils' advocate is a nasty habit of mine, so please excuse my ramblings. for the most part, I agree exposure is a good thing and having a great reference book is very handy. peter
  13. Re: agreed[ Go to top ]

    Atleast someone who has never heard of an algorithm doesn't start from the assumption they know it.
    You're in for some serious surprises ...
  14. Re: agreed[ Go to top ]

    Atleast someone who has never heard of an algorithm doesn't start from the assumption they know it.
    You're in for some serious surprises ...
    yeah, I have come across people like that. On one occasion I had the person fired. people like that generally kill productivity and make work hell. peter
  15. Awesome...[ Go to top ]

    Thanks a ton guys for investing your valuable time and efforts. And especially for sharing this fruit with community. Amit Sun always rises from EAST..:)
  16. Fills an Urgent Need[ Go to top ]

    While in graduate school, the study of algorithms always seemed like a field of study waiting for a decent textbook, and my instructors likely agreed judging by the amount of time they committed to producing their own reference notes and sample solutions for what should be well documented problems. A quick review of Dasgupta, Papadimitriou, and Vazirani makes me suspect that a decent textbook has arrived, which should make it possible for students to come as quickly up to speed with the state of the art as has long been possible in other computer science disciplines.
  17. Knowledge is too vast. You can't understand it all. I defend the idea that you don't need to understand every little details to be able to use someting. What is an algorigthm? A clever way of doing something. You don't need to know HOW it works to be able to USE it successfully. More an more I realize that I have not the time to understand it all. Some other developers will implement classes with these clever algorithm and I will use them.
  18. Hi James,
    Knowledge is too vast. You can't understand it all.

    I defend the idea that you don't need to understand every little details to be able to use someting.

    What is an algorigthm? A clever way of doing something. You don't need to know HOW it works to be able to USE it successfully.

    More an more I realize that I have not the time to understand it all. Some other developers will implement classes with these clever algorithm and I will use them.
    That's a fair and valid position, and I agree that a lot of developers don't need to understand most of what's in this book. However, this bit of extra knowledge is very often what makes the difference between an average developer and a good one. Most of all, to me, algorithms are like mathematics: not really something you use first-hand in your daily job, but a field that has a surprisingly broad reach that, somehow, you find yourself reusing over and over again, sometimes without even realizing it. I look at it as a mental work out that keeps your mind sharp. -- Cedric http://testng.org
  19. The study of math, physics, strategy, and in general, complex problems is never bad excerise for a mind of any age or person in any role.
  20. The study of math, physics, strategy, and in general, complex problems is never bad excerise for a mind of any age or person in any role.
    I don't know about that...I find the greater my understanding the greater the pain of working in a larger corporate environment. So far seeking knowledge has proven to be an entirely masochistic exercise.

  21. I don't know about that...I find the greater my understanding the greater the pain of working in a larger corporate environment. So far seeking knowledge has proven to be an entirely masochistic exercise.
    There should be a FEDX package with a cell phone in it arriving shortly ...
  22. More an more I realize that I have not the time to understand it all. Some other developers will implement classes with these clever algorithm and I will use them.
    You have to know what they are, what they're for, their performance characteristics, the assumptions they make about the data they receive, etc. all before successfully using them. Often times learning how to implement the algorithms (and implementing them!!!!) is the best way to really understand this knowledge, even if you'll never need to implement them again.
  23. At the risk of exposing my ignorance: Any recomendations on sites or books that can help me more easily understand the notation in the formulas?
  24. At the risk of exposing my ignorance:

    Any recomendations on sites or books that can help me more easily understand the notation in the formulas?
    Did you see section 0.3 (in the prologue) of that book?
  25. Is this correct?[ Go to top ]

    I started reading the preface and was surprised by this statement about recursively calculating fibonacci numbers: "Let's be a little more concrete about just how bad exponential time is. To compute F200, the fib1 algorithm executes T(200) >= F200 >= 2^138 elementary computer steps. How long this actually takes depends, of course, on the computer used. At this time, the fastest computer in the world is the NEC Earth Simulator, which clocks 40 trillion steps per second. Even on this machine, fib1(200) would take at least 2^92 seconds. This means that, if we start the computation today, it would still be going long after the sun turns into a red giant star." If this is saying (as I understand it) that to calculate the 200th fibonacci number would take 292+ seconds on the fastest computer in the world, they're missing something. That's just 200 recursions of adding two numbers. True, it's a bit trickier since the numbers will oveflow (the 200th fibonacci number is 280,571,172,992,510,140,037,611,932,413,038,677,189,525 and the max java long is 9,223,372,036,854,775,807.) But even working around that issue, the processing time would be negligible.
  26. Oops...should have read further[ Go to top ]

    It turns out that the assumptions behind the algorithm the book was referring to in the passage I quoted is one no one would think to use. It's clarified afterwards.