48 ms·

Algorithms, by Jeff Erickson

1463 points by bdr 8y ago

BillyBreen 8y ago
Love his writing style. Accessible yet detailed with fun historical tangents to set context.
_underflow_ 8y ago
> Please do not ask me for solutions to the exercises. Even if you are [an] instructor, I will say no. That's kind of a bummer. I like to be able to check my answers when teaching myself things. Am I somehow alone in that?
- bryanrasmussen 8y ago
  could be a monetization idea/incentive to purchase, purchase the book get unique key, use key to check in to site to see results.
  - jj12345 8y ago
    This is done occasionally in algo books to encourage their adoption in cirricula (e.g. Dasgupta, etc.). As a sibling comment mentions, it's relatively easy to verify your answer for correctness in some cases. The downside of this is that it becomes difficult to assess whether students are actually learning. One way to mitigate this is to withhold answers and assist with other teaching resources like TAs. This also helps teach the aforementioned 'verification' step.
  - jefferickson 8y ago
    Nope. Anything I publish will be available free.
- heinrichhartman 8y ago
  I have seen many people voice that complain. Personally I rarely had issues verifying a solution once I have worked through a problem. What happens much more frequently, is that I get stuck somewhere, and get tempted to look at a solution if one is provided, which in turn nullifies the achievement. In this sense, not having solutions, makes it easier for me to plough through.
  - ryanmonroe 8y ago
    If you prefer not to have solutions, pretend you don't have solutions. Having solutions is strictly better (for the reader. I'm ignoring the cost of producing them to begin with)
    - nf05papsjfVbc 8y ago
      "pretend you don't have solutions" is not a realistic approach. The strength of people's conviction to this will probably fall on a bell curve and few can resist the temptation when the problems get really tough. Accounting for how humans are, I do not see how one can easily say "Having solutions is strictly better". I can easily think of cases where it is indeed better to have solutions but to say "strictly" requires a bit more diligence.
      - heinrichhartman 8y ago
        yes, exactly.
      - thrwthrw93223 8y ago
        Don’t rob the self-learner that doesn’t have access to TAs, fellow students, and professors the ability to check their work, just because someone else doesn’t have the discipline to not abuse it. Textbook solutions are good for those that aren’t in school, aren’t in formal programs and have no other way of receiving feedback. The “you should know if you’re right” mentality doesn’t necessarily fit a person that’s been working for 10-years and has been out of the academic mindset. One that is a beginner and could easily fool themselves into thinking they have a correct answer. It doesn’t allow for correction of false thinking. Anyone can think their proof is correct. But fewer beginners can properly recognize when they are wrong. This sort of mentality is a bit elitist and gate keeping.
        kemiller2002 8y ago
        I had a girlfriend who was doing her PhD in Physics. I remember one night she and her classmates spent all night working on a problem, that was essentially unsolvable. The next day they go to class and all of them made their best attempt, but no one could complete it. The problem? The professor accidentally used the wrong metric on one of the numbers meaning that they couldn't do the steps to what should have been an easy solution. Now they noticed this, they are a smart group of people, but that's not what the problem was, so they spent hours and hours trying to solve what he gave them without any hope of actually doing it. In the end, he was like "Oh my bad," and corrected his mistake. The point of the story is that they were able to essentially ask him for the solution and they were able to check what they'd done, and in the end he made the mistake. In situations like this, he should provide the answer if nothing else to show that he didn't make a mistake in the problem set. People are fallible, no matter how brilliant you are.
- kkarakk 8y ago
  as is the case with all uni oriented textbooks, they can't be used alone if you don't instantly grok the content. i'm sure just searching github for a sample implementation followed by a discussion of the finer points on stackoverflow/programming reddit of choice will do you a 5 minute search gave me this - https://github.com/floyernick/Data-Structures-and-Algorithms https://github.com/floyernick/Data-Structures-and-Algorithms for algos implemented in Go. github is littered with these kindsa samples(some of them highly vetted) https://github.com/topics/algorithms-and-data-structures https://github.com/topics/algorithms-and-data-structures
- dhimes 8y ago
  The author probably agrees with you. He indicates that he provides solutions for most of the problems he assigns to his class.
- porpoisely 8y ago
  The princeton algorithm site has solutions for some of their exercises. Also they have online lectures as well along with animations, visualizations, etc. It's an excellent resource for those who want to learn algorithms. https://algs4.cs.princeton.edu/home/ https://algs4.cs.princeton.edu/home/
- znpy 8y ago
  The book sources are available through GitHub, you or someone else could easily fork the project and add all the content that in your opinion is missing (including answers to exercises).
- p1itopre 8y ago
  No, you are not. The extensive problem sets at the end of each chapter is main contribution of this work (imho). However this is not a shortcoming these days. I spend upto ~1 hour on each problem. And then I google keywords from the questions. Someone somewhere has one possible solution. Usually , this is enough to set me on the right track.
- philonoist 8y ago
  Solutions were stepping stones to my success. I am mature enough to not be tempted without trying out the problem. I sleep over it and then at last looking at the solution, if I ever find myself at my wit's end. That is because I have a firm understanding that there is no shortcuts to success. Having come from a third world country where cheating on oneself is delaying even the basic resources to get a job, I was raised with peers finding the 'peeping at solutions' an abhorrent act. Its a big shameful thing to do in my culture. Solutions are the way I learn the thought process of author if he arrived at the final answer in a better way. Solutions expose errors in questions. Errors and typos in Indian texts were way more a common place in questions than in solutions. There was simply not a chance for a solution to have typo or logical errors. If there are no solutions, I'd simply put it for later until I am proficient in the subject and want to try out the problems with confidence. There is always this insecurity when it comes to dealing with logic. Little things can slip in abstract thinking pretty easily. Silly mistakes take a toll. People like myself prefer to solve problems individually at our own pace. Solutions are a must for me. Of course, that 'later' almost always never comes.
- jefferickson 8y ago
  Hi, I'm the author. I'm honestly seriously torn about this. There is a serious tension between pedagogical needs of students in formal classrooms and the pedagogical needs of self-learners. I've chosen to aim for the former. Yes, I know it's a bummer. (From experience) providing solutions interferes with the learning process of my own students at Illinois. I have to change up homeworks and exam questions every semester, because otherwise students will look up and copy/memorize the answers instead of trying to figuring them out, which means they do worse on the exams where they HAVE to figure things out. Also, a significant majority of the requests I get for solutions are from university students who want to cheat. I do provide solutions to the homework and exam and lab problems I assign in any particular class, after the fact. (And I release those solutions publicly, despite the protests of colleagues at other universities, until the semester ends.) And I have started proving model solutions in the homeworks, so that the students know what kind of answers I'm looking for. (See the course materials page, under CS 374.) In practice, my stance is becoming increasingly moot, as more of my official solutions get uploaded to places like CourseHero and Koofers and their many foreign-language equivalents. I am very likely to include solutions for a subset of problems (maybe three or four per chapter) in a future edition. But that will take a significant amount of time, and I wanted to get something out the door.
  - smarks 8y ago
    Thanks for this explanation. This is one of the things that popped out at me when I looked at the book page. The statement about not providing answers seemed quite dogmatic, and my initial reaction was, why? Turns out it's not so dogmatic, and there's a thoughtful and nuanced explanation. Perhaps you could include some of this on the book page, or provide a link to the explanation elsewhere.
    - _underflow_ 8y ago
      Completely agree - being outside academia has apparently made me ignorant to a lot of the pitfalls to actually posting said solutions. Makes perfect sense when put this way. I also really appreciate the response from the author. I forget the gurus behind books like this often have a presence here on HN.
- commandlinefan 8y ago
  > I like to be able to check my answers when teaching myself things. I agree, although looking at the exercises in this book, they seem to be of the form where the only way to give you the answer is you give you the full solution, and they appear to be phrased in a way that makes it easy enough to verify the answer yourself once you’ve figured out the problem. I always feel like the ideal (for me at least) are problems with numerical answers listed in the back of the book – then I can check my answer with the book’s answer; if I got 42 but they got 5, I know I made a mistake somewhere but it’s still up to me to go back through and figure out where the mistake was. It seems like most of these problems don’t lend themselves to short numerical answers like that.
alsadi 8y ago
The logo on the right is the arabic letters of the word Algorithmi (al-Khwarizmi) the persian muslim scholar after him algorithms and logarithms were named
- delinka 8y ago
  ...after whom...
  - dotancohen 8y ago
    Al Gore. Al-Gore-Ithm
- arketyp 8y ago
  It reminds me of an ashtray design which is famous in Sweden, by Stig Lindberg: https://balstaauktionshall.nu/images/custom/ProductTemplate/53860.jpg https://balstaauktionshall.nu/images/custom/ProductTemplate/... I remember tracing the lines with my finger as a kid, trying to decipher a hidden logic...
- divs1210 8y ago
  that is beautiful! thanks for pointing it out! is it readable for people who can read Arabic?
  - Link- 8y ago
    It still takes a few seconds to identify the word since this is not how Arabic is usually written but yes the word "Al-Khawarizmi" is legible. In fact, the logo contains text both in black and navy blue, the navy blue part is "Al-Khawarizmi" or in Arabic "الخوارزمي". Then the navy blue script is rotated at 90 degrees 3 additional times.
    - alsadi 8y ago
      no, it's very readable because it's a well known calligraphy called kufi as others have pointed out.
kyriakos 8y ago
great job and thanks for keeping this free
yoler 8y ago
Isn’t this the guy that is famous for being admitted to a PhD program with an exceptionally low GPA? If so, why is he the exception and why aren’t more PhD programs looking for non-traditional talent? Edit: I read his blog post. It gave me more insight. It looks possible for people with those sort of grades to be admitted even today, but they seem to need a cheerleader on the inside that will help them.
- willbw 8y ago
  There are a lot more people going to university these days, and grades are inflated. That's the short story. If you have to look at many many applications for a spot at a top university you are more likely to choose someone who is a "traditional" talent.
- a_bonobo 8y ago
  There was a small study that came out recently on biorxiv, with 29 PhD students with GREs all over the place - >GRE scores, while collected at admission, were not used or consulted for admissions decisions and comprise the full range of percentiles from 1% to 91%. We report on the 29 students recruited to the Vanderbilt IMSD from 2007-2011 who have completed the program as of summer 2017. While the data set is not large, the predictive trends between GRE and long-term graduate outcomes (publications, first author publications, time to degree, predoctoral fellowship awards, and faculty evaluations) are remarkably null and there is sufficient precision to rule out even mild relationships between GRE and these outcomes. Career outcomes are encouraging; many students are in postdocs, and the rest are in stage-appropriate career environments for such a cohort, including tenure track faculty, biotech and entrepreneurship careers. Now a GRE isn't a GPA (one's a specific test, one is your grades' average), but both are being used for university admissions, and I reckon both are not good predictors. Edit: Link: https://www.biorxiv.org/content/early/2018/07/20/373225 https://www.biorxiv.org/content/early/2018/07/20/373225
  - frozenport 8y ago
    There is another interpretation. That sadly, grad school has become potlicial and technical appitude doesn't matter. I have accrude a subantial number of high impact publications and can confirm this is the case. On numerous occasions I have been forced to hand over my completed work to facilitate first author publication for visiting scholars or students my Pi liked received co authorship, joint first authorship for no apparent reason. I would also like to reverse this trend.
otachack 8y ago
I took Jeff's Algorithms class in college and he's one of the best professors I've had. I still struggled through the class but definitely made it through with a great experience.
- kyteland 8y ago
  I took CS 173 and 373 from Jeff nearly 20 years ago, with 273 from another great professor. That course sequence along with Combinatorial Game Theory (which I took on a lark) has had a greater impact on me than the rest of my university experience combined. A lot of that is due to the quality of the professors I was lucky enough to have.
  - jimhefferon 8y ago
    Perhaps you might, when you get a chance, email him a brief note to tell him that. That'll make a person's day.
    - CydeWeys 8y ago
      He's in the comments here so I suspect his day is already made! :)
      - kyteland 8y ago
        Yeah, this may the 3rd or 4th time I've said something along those lines in a HN thread he's active in over the last 10 years.
    - jefferickson 8y ago
      Day made!!
    - mesaframe 8y ago
      You know what, your book on linear algebra is really great too. I tried to understand LA from too many books but your book was the one which made sense for me.
sidravi1 8y ago
The historic preludes to the chapters are awesome. The dynamic programming chapter starts with an intro to the study of meters in Sanskrit poetry.
curiousDog 8y ago
The graphs chapter is my favorite. It's not very rudimentary like other text books
nameless912 8y ago
Jeff's CS 374 was one of my favorite classes at U of I. It really opened up my mind to thinking about Computer Science as a branch of mathematics, and completely changed how I approach my work today. The book form of these lectures was in EARLY rough draft when I took the class though-we were proofing chapters for him!
webmaven 8y ago
Great resource, though I wish it was available as an EPUB (or MOBI, or AZW3).
- sharmi 8y ago
  I use moon reader pro on Android. It allows annotating and highlighting pdf text. I am not affiliated except as a long time user.
- qazpot 8y ago
  Why wish, when you can convert PDFs to EPUB very easily using online converters.
  - znpy 8y ago
    Yes, but the resulting documents often are horrendous when rendered on ereaders and similar.
  - piyush_soni 8y ago
    Yeah i tried doing that. The conversion is so bad with multiple random line breaks in a single line, and some unicode characters not getting converted etc. It was a bad experience.
- rezeroed 8y ago
  It is. Follow the internet archive link.
  - webmaven 8y ago
    An automatic conversion to EPUB from PDF or from a scan is not what I was asking for.
- jefferickson 8y ago
  You can get an EPUB and MOBI versions from the Internet Archive (auto-converted from my uploaded pdf), but I can't vouch for its quality. All the fonts are baked into the PDF, so it should be readable anywhere; if it isn't, please submit a bug report! But if you're looking for a format that lets you reflow the text, by changing the margins or font or text size, you're out of luck. The only way to write something like that is to bake it in from the beginning. That's easy for pure text, but hard to impossible for technical documents with lots of displayed equations, big hard-formatted boxes of text (ie, algorithms), and the like. (Boaz Barak managed it by writing his Modern Complexity Theory book entirely in Markdown. The mind boggles.)
lbj 8y ago
Absolute treasuretrove, thanks for sharing!
mpurham 8y ago
Wow students are so lucky for the sheer number of resources available today. Great post and thanks for sharing!
brianzelip 8y ago
> ́ Black spades indicate problems that require a significant amount of gruntwork and/or coding. These are rare. > ∆ Orange stars indicate that you are eating Lucky Charms that were manufactured before 1998. Ew. (p. vi) :) Really like the book already. The preface falls under the category of advice on learning to learn. Thanks for all your work. #stealthisbook
- ZeroCool2u 8y ago
  >Caveat Lector! >Of course, none of those people should be blamed for any >flaws in the resulting >book. Despite many rounds of revision and editing, this >book contains many mistakes, bugs, gaffes, omissions, >snafus, kludges, typos, mathos, grammaros, >thinkos, brain farts, poor design decisions, historical >inaccuracies, anachronisms, >inconsistencies, exaggerations, dithering, blather, >distortions, oversimplification, >nonsense, garbage, cruft, junk, and outright lies, all >of which are entirely Steve Skiena’s fault. Coming from a class where we used a decidedly poor textbook for algorithms, this looks like a joy to read.
wwarner 8y ago
The section on dynamic programming is exceptionally clear.
azangru 8y ago
From the second page (verso page?): > Download this book at http://jeffe.cs.illinois.edu/teaching/algorithms/ http://jeffe.cs.illinois.edu/teaching/algorithms/ or http://algorithms.wtf http://algorithms.wtf algorithms.wtf is a beautiful url!
neurotrace 8y ago
> Chapter 0 uses induction, and whenever Chapter n−1 uses induction, so does Chapter n I love this.
primitivesuave 8y ago
Jeff Erickson was my algorithms professor in 2012. He exemplifies the articulate, passionate educator that I wish I had for my other CS subjects. I recognize many of these notes having read them many times in preparation for quite difficult exams - a fun anecdote shared among people who've taken the class is the 25% credit given on any exam question just for writing "I don't know", effectively a reward for acknowledging your own shortcoming and for saving the TA the time to decipher a bullshit answer. Professor Erickson, if you're reading this, thank you for being the best educator of my college days and for making your beautifully-written notes available to everyone.
- gricardo99 8y ago
  >25% credit given on any exam question just for writing "I don't know", effectively a reward for acknowledging your own shortcoming and for saving the TA the time to decipher a bullshit answer. That’s brilliant, yet I’ve never heard of it. Should be standard scoring for written exams.
  - Vaslo 8y ago
    Random other point of brilliance I've seen: Our Organic Chem teacher (who was loved universally in the Program) had a rule about test corrections. If you wanted a correction to something you believed you should get credit on, he would only offer to regrade your WHOLE test, which meant you could actually get less points on the regrade because it was he and not a TA regrading (could have worked both ways). It really scared off all those one-off "Can I get an extra point here" requests in a 300 person class.
    - edanm 8y ago
      I think that was the way it worked at my university too, at least officially. Unofficially, very few teachers actually graded that way, and when I saw it happen, people complained about it a lot. Then again, the teachers that did it seemed like they were doing it punitively (e.g. subtracting the exact amount of points they were forced to add.)
    - 8y ago
briefcomment 8y ago
Are algorithms useful to learn for a non-programmer? Is there a benefit to thinking through what is presented in a book like this over solving general problems in a day-to-day context?
- clishem 8y ago
  Please find something you love doing and learn more about that instead of picking up random things.
  - briefcomment 8y ago
    Sound advice. Thinking through the scope of a programming problem to come up with an algorithm sounds like a productive way of using your mind, but may be a waste of time if you don't intend on programming.
  - saagarjha 8y ago
    What if what you love doing is picking up random things ;)
- EnFinlay 8y ago
  As a whole, I doubt a book like this would be of much use to a non-programmer. There are some high level tricks that might be fun to learn, and could be loosely applied to day-to-day thinking (should this be solved in a brute force way, or is there some shortcut). Overall the book (I assume, I haven't read it) is technical and precise solutions to technical problems. Algorithms are just ways of solving technical problems in the most efficient way possible (for various definitions of efficiency). They are deep programming which even most programmers don't use frequently.
  - briefcomment 8y ago
    Suspected this might be the case, thanks for your thoughts.
- akman 8y ago
  You may be interested in the book Algorithms to Live By ( Brian Christian, Tom Griffiths). I thought it was a fun-to-read book, though I don't think there was any code in the book at all.
ausjke 8y ago
After a quick browser it seems a little too academic for daily programmers like myself. Would love to learn more about practical dynamic programming these days, hope there is a book about that extensively.
- deleted 8y ago
  [deleted]
- ibash 8y ago
  Go back and read it - it’s not!
pseudonom- 8y ago
Does anyone have any impressions on how this compares to CLRS? (https://en.wikipedia.org/wiki/Introduction_to_Algorithms https://en.wikipedia.org/wiki/Introduction_to_Algorithms)
- zawerf 8y ago
  In particular are there any new materials that has been invented or widely adopted since the older textbooks? For example, bloom filters were rarely taught maybe 10 years ago but probabilistic data structures are now pretty mandatory in a data structure course. Just wondering if there are sections in this book covering cutting edge stuff for people already familiar with traditional algo
  - jefferickson 8y ago
    Not so much in the book itself, but definitely in the "Director's Cut" notes on the book web site. I cover bloom filters and the like in my more advanced algorithms courses. Teaching that material correctly (without the traditional magical thinking) requires serious comfort with probability, which unfortunately isn't early enough in the CS curriculum at Illinois to be used in our data structures and algorithms courses.
- rbkillea 8y ago
  By Ctrl+F'ing, I find 5 mentions of the word "master", none of which are the master theorem. I prefer this to CLRS as, while it's a neat trick, it tends to result in a bunch of people memorising the cases (and taking a "because the book told me to" level of understanding away from that part of the course).
  - jefferickson 8y ago
    Exactly. The students should be the masters, not the theorem.
konart 8y ago
Maybe that because english is not my native language, but I honestly find this way of material presentation as rather confusing. PS: oh and of course all those 'It’s quite easy to show that the...' and similar 'by this point it should be obvious'. No, it is not... I guess I will never understand or use those algorithms even though I'd like to.
- jefferickson 8y ago
  Hi, I'm the author. If you find any particular claim of "obviousness" unclear, submit an issue request! But please don't confuse "straightforward" with "obvious". Sometimes I deliberately gloss over mechanical details because I think they're a distraction from the main point. I'm NOT claiming that you should immediately know how to fill in the details; I'm claiming that filling in the details is boring.
  - fwip 8y ago
    I would agree that words like "obvious" or "trivial" can be disheartening to a learner. If it's obvious to the reader, they know it whether or not you tell them it's obvious. If it's not obvious to them, then they will try to figure it out. Telling this person "it's obvious" only serves to make them feel bad about not getting it right away.
    - mden 8y ago
      I felt that way when studying math in college, but after sometime I actually came to like the use of "clearly" and the like as it can be used as a check on whether you've spent enough time internalizing the previous information. It's one thing to have a text or a person hold your hand through algorithms or theorems, it's another to be able to do it yourself. So getting hit with a "clearly" that feels unjustified is often a signal to let go of the guiding hand and go back and review until the statement in question does become clear.
      - konart 8y ago
        Sometimes this is th'e case, yes, sometimes it is not. An example: http://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE-2up.pdf http://jeffe.cs.illinois.edu/teaching/algorithms/book/Algori... Page 15 > It’s quite easy to show that the singing time is Θ(n2); in particular,the singer mentions the name of a gift ∑ni=1i=n(n+1)/2times (counting thepartridge in the pear tree). I'm pretty sure that I still remember how to read the formula and I even know what does Θ(n2) means, but it's still unclear for me how do we get n^2 and this formula from the "NDaysOfChristmas(gifts[2..n]):" example.
Zanta 8y ago
I used these lectures as a method for learning algorithms as a phys/mech eng with no CS background. I found them incredibly challenging but the lectures were written exceptionally well. On an internet with thousands of resources on this material, this was the very best I found.
dksf 8y ago
I love how he offers the mnemonic http://algorithms.wtf http://algorithms.wtf Bravo, Jeff!
nythrowaway 8y ago
I managed to get a A- in Ericsson’s 373 as an undergrad (grads took the same class but had their own curve) in 2001. Great class, great experience, great teacher. Pushed me to do algorithms at a difficulty I didnt hunk possible.
mlevental 8y ago
gonna take this opportunity to ask for advice: i have an MS in CS and i've gone through all of CLRS twice (yes really all of it and really twice - once for my grad algos class and once in prep for interviews - and i still don't have whatever intuition i need to be able to effortlessly do DP. it's honestly kind of maddening - mincut/maxflow, RSA, knuth-morris-pratt etc are all completely obvious to me and i can whip them out pretty much effortlessly - but DP i struggle to find the optimal substructure and formulate bottom up (yes i can memoize but that's not clever enough for you know who). what's the magic combinatorial perspective/intuition that enables people to construct dp solutions so quickly??? yes i've read vazirani and gone through the clemson examples and etc. and skiena and sedgwick whatever but the problem is they're mostly all rehashings of the same solutions/perspectives. looking forward to this book's perspective.
- svat 8y ago
  I think if you find those algorithms obvious and you're able to write memoized solutions, then you already know most of what you need to know about dynamic programming. For example, Dijkstra's algorithm for shortest paths can be seen as DP. The main thing is to write down a formulation for the answer for n in terms of answers for smaller n, or the answer for (n, k) in terms of answers for smaller (n, k). (And don't worry about how you'd compute them, just focus on getting a correct expression in terms of smaller ones. http://okasaki.blogspot.com/2008/10/score-one-for-induction.html http://okasaki.blogspot.com/2008/10/score-one-for-induction....) It can be tricky to formulate exactly what you're counting / measuring (e.g. what's "k" and what's the quantity you're optimizing for (n, k)), but once you have that, and once you have the recurrence, you can consider it a separate (and independent) step to figure out in which order to compute the values, so that you have each value by the time you need it (i.e. the bottom-up formulation that you said is the tricky part for you). Beyond that I guess lots of practice with problems… e.g. about a decade ago there used to be weekly(?) TopCoder contests with editorials written later explaining the solutions (and the problems were graded by difficulty and even how many people solved it), and the DPs could get quite tricky. I believe those are still happening, and now there are other resources like LeetCode or whatnot. Do you have an example of a problem that you struggled with, to see what's missing?
kizer 8y ago
I had him as a professor as well. He’s a brilliant guy and educator, but could be a little rough with questions; i.e. making you feel a little dumb. His notes though were always excellent.
setheron 8y ago
I would appreciate a version of the book with the extended material as well! Is there a way to pre-pay advanced copies of the published book?
rbkillea 8y ago
This has always bugged me: what reasons outside of convention do we have for preferring O(V + E) to O(E) on algorithms that only make sense in the context of a single connected component? I know this is slightly OT, but tangentially related.
dotancohen 8y ago
This is a great resource. Though it is dated this month, there seems to have been a mention of it two years ago and a short HN discussion ensued: https://news.ycombinator.com/item?id=12873426 https://news.ycombinator.com/item?id=12873426
raylangivens 8y ago
I have been reading through these and find them really unique in a good way. I got a new perspective on a lot of stuff I already studied I have a Bachelors in CS and graduated 1.5 years ago. It doesn't feel formal like a textbook and yet doesn't sacrifice on the mathematical rigor. I would be trying out the exercise problems which seem equally daunting but fun. I also submitted an issue request on Github and Jeff I have a few questions for you that I put on Quora, I have A2A'd you. Lastly, thanks for taking the time out and putting content like this out for free. It helps millions of autodidacts like me.
vowelless 8y ago
The lecture on Matroids is pretty good.
sqlacid 8y ago
Copyright question, the copyright page says draft published 12/29/2018, but the copyright is 2019; doesn't that mean somebody could have taken the work, published as their own as copyright 2018 on 12/30/2018 which would be earlier than the author's 2019 claim? I'm not a copyright expert by any means, but am always troubled when I see "Copyright $CURRENT_DATE" in electronic works, I thought it was supposed to reflect the earliest date of claim.
- ggggtez 8y ago
  No, because copyright law doesn't care what the copyright date says, or even if you write it at all. As soon as you write something, you have the copyright to what you wrote. If it was challenged in court, he would likely easily be able to show his drafts from prior to 12/29/2018 to prove he was the author.
- flyGuyOnTheSly 8y ago
  You don't actually have to place a copyright on original works like this. Copyright is granted whether you put the little c symbol and date or not.
- jefferickson 8y ago
  Oops. I'd say submit a bug report, but as of yesterday it become moot. As others have said, the copyright notice is only a courtesy/reminder. I've held the copyright on all this stuff from the moment I started writing it (and distributing it) 20 years ago.
azhenley 8y ago
Jeff is also a frequent poster on Academia.StackExchange. He helped me quite a bit by answering my questions about grad school life. https://academia.stackexchange.com/users/65/jeffe https://academia.stackexchange.com/users/65/jeffe
mcguire 8y ago
"Sedgwick’s reformulation [of AA trees] requires that no right child is red. Whatever. Andersson and Sedgwick are strangely silent on which end of the egg to eat first."
Twisol 8y ago
I am, in all likelihood, not in the target audience (having already spent much time with the material being presented), but this textbook has been a joy to read so far. I am only up to page 14, and I already need two hands (in base 1...) to count the number of times I've laughed aloud or cheered a particular point being raised. Most algorithms books are dry, or they're obsessed by particular formal details, or (worse) they implicitly include optimizations in the algorithm without explaining what is needed for correctness and what is needed for efficiency. Having tutored on one of the books mentioned in the prologue, it can be a real struggle to gain a true intuition for algorithms when you can't yet tell the difference. But the sheer personality contained within this book is infectious, and it really is something of a page-turner. (Lest you think I haven't gotten to the stuff that "matters", I have read through the chapter on depth-first search -- again, an enjoyable read!) What a great book. I'm definitely recommending this to my friends.
- tptacek 8y ago
  Same. I fell in love with it instantly and permanently when I got to the "NO, STOP, YOU'RE DONE" part in the Towers of Hanoi. I skipped around the book and the whole thing is like that. It's simultaneously concise and witty in service of the material. The chapter problems look fantastic, too, and are just as well-written (and they cover a lot of ground). It's really something!
mnadel 8y ago
I had the privilege of being an undergrad in Jeff’s class in the late 90s. IIRC, it was his first year teaching. On the last day of class he received a standing ovation. The average grade on the final exam was ~50%. And yet he received a standing ovation. He’s that good.
Topolomancer 8y ago
I love Jeff Erickson's work and would also like to recommend his notes on Computational Topology [1] for further consumption. [1]: http://jeffe.cs.illinois.edu/teaching/comptop/2009/schedule.html http://jeffe.cs.illinois.edu/teaching/comptop/2009/schedule....
sidcool 8y ago
How does this compare to CLRS? I am neck deep in reading CLRS..
skizm 8y ago
What the heck is the trivial one liner to check who will win a chess game given both players play perfect?
- d4rti 8y ago
  I can only come up with a recursive algorithm which depends on a PerfectPlay(state, player) like so: WinnerWithPerfectPlay(state,currentPlayer): if Winner(state) return Winner(state) else nextPlayer <- "white" if currentPlayer = "black" else "black" return WinnerWithPerfectPlay(PerfectPlay(state, player), nextPlayer) Which doesn't allow for stalemate moves.
- kirkules 8y ago
  I suppose the claim of the existence of this one liner might be the same as the claim that one of the players can always force a win, in which the line is something like "return 'white'" or "return 'draw'"
- plin25 8y ago
  I believe this is a trick question. The "standard" chess board is 8x8, with a 32 possible pieces. This gives you a constant (albeit absurdly large) number of configurations, which means that the one-line solution "Brute Force" is an O(1) algorithm.
yangdehang 8y ago
I don't know why your guys think this book is so good, I don't see any new things out of it nor could I appreciate how he composed the content. It is just one of those random textbooks for this topic.

1463 points by bdr 8y ago

Love his writing style. Accessible yet detailed with fun historical tangents to set context.

> Please do not ask me for solutions to the exercises. Even if you are [an] instructor, I will say no. That's kind of a bummer. I like to be able to check my answers when teaching myself things. Am I somehow alone in that?

bryanrasmussen 8y ago
could be a monetization idea/incentive to purchase, purchase the book get unique key, use key to check in to site to see results.
- jj12345 8y ago
  This is done occasionally in algo books to encourage their adoption in cirricula (e.g. Dasgupta, etc.). As a sibling comment mentions, it's relatively easy to verify your answer for correctness in some cases. The downside of this is that it becomes difficult to assess whether students are actually learning. One way to mitigate this is to withhold answers and assist with other teaching resources like TAs. This also helps teach the aforementioned 'verification' step.
- jefferickson 8y ago
  Nope. Anything I publish will be available free.
heinrichhartman 8y ago
I have seen many people voice that complain. Personally I rarely had issues verifying a solution once I have worked through a problem. What happens much more frequently, is that I get stuck somewhere, and get tempted to look at a solution if one is provided, which in turn nullifies the achievement. In this sense, not having solutions, makes it easier for me to plough through.
- ryanmonroe 8y ago
  If you prefer not to have solutions, pretend you don't have solutions. Having solutions is strictly better (for the reader. I'm ignoring the cost of producing them to begin with)
  - nf05papsjfVbc 8y ago
    "pretend you don't have solutions" is not a realistic approach. The strength of people's conviction to this will probably fall on a bell curve and few can resist the temptation when the problems get really tough. Accounting for how humans are, I do not see how one can easily say "Having solutions is strictly better". I can easily think of cases where it is indeed better to have solutions but to say "strictly" requires a bit more diligence.
    - heinrichhartman 8y ago
      yes, exactly.
    - thrwthrw93223 8y ago
      Don’t rob the self-learner that doesn’t have access to TAs, fellow students, and professors the ability to check their work, just because someone else doesn’t have the discipline to not abuse it. Textbook solutions are good for those that aren’t in school, aren’t in formal programs and have no other way of receiving feedback. The “you should know if you’re right” mentality doesn’t necessarily fit a person that’s been working for 10-years and has been out of the academic mindset. One that is a beginner and could easily fool themselves into thinking they have a correct answer. It doesn’t allow for correction of false thinking. Anyone can think their proof is correct. But fewer beginners can properly recognize when they are wrong. This sort of mentality is a bit elitist and gate keeping.
      - kemiller2002 8y ago
        I had a girlfriend who was doing her PhD in Physics. I remember one night she and her classmates spent all night working on a problem, that was essentially unsolvable. The next day they go to class and all of them made their best attempt, but no one could complete it. The problem? The professor accidentally used the wrong metric on one of the numbers meaning that they couldn't do the steps to what should have been an easy solution. Now they noticed this, they are a smart group of people, but that's not what the problem was, so they spent hours and hours trying to solve what he gave them without any hope of actually doing it. In the end, he was like "Oh my bad," and corrected his mistake. The point of the story is that they were able to essentially ask him for the solution and they were able to check what they'd done, and in the end he made the mistake. In situations like this, he should provide the answer if nothing else to show that he didn't make a mistake in the problem set. People are fallible, no matter how brilliant you are.
kkarakk 8y ago
as is the case with all uni oriented textbooks, they can't be used alone if you don't instantly grok the content. i'm sure just searching github for a sample implementation followed by a discussion of the finer points on stackoverflow/programming reddit of choice will do you a 5 minute search gave me this - https://github.com/floyernick/Data-Structures-and-Algorithms https://github.com/floyernick/Data-Structures-and-Algorithms for algos implemented in Go. github is littered with these kindsa samples(some of them highly vetted) https://github.com/topics/algorithms-and-data-structures https://github.com/topics/algorithms-and-data-structures
dhimes 8y ago
The author probably agrees with you. He indicates that he provides solutions for most of the problems he assigns to his class.
porpoisely 8y ago
The princeton algorithm site has solutions for some of their exercises. Also they have online lectures as well along with animations, visualizations, etc. It's an excellent resource for those who want to learn algorithms. https://algs4.cs.princeton.edu/home/ https://algs4.cs.princeton.edu/home/
znpy 8y ago
The book sources are available through GitHub, you or someone else could easily fork the project and add all the content that in your opinion is missing (including answers to exercises).
p1itopre 8y ago
No, you are not. The extensive problem sets at the end of each chapter is main contribution of this work (imho). However this is not a shortcoming these days. I spend upto ~1 hour on each problem. And then I google keywords from the questions. Someone somewhere has one possible solution. Usually , this is enough to set me on the right track.
philonoist 8y ago
Solutions were stepping stones to my success. I am mature enough to not be tempted without trying out the problem. I sleep over it and then at last looking at the solution, if I ever find myself at my wit's end. That is because I have a firm understanding that there is no shortcuts to success. Having come from a third world country where cheating on oneself is delaying even the basic resources to get a job, I was raised with peers finding the 'peeping at solutions' an abhorrent act. Its a big shameful thing to do in my culture. Solutions are the way I learn the thought process of author if he arrived at the final answer in a better way. Solutions expose errors in questions. Errors and typos in Indian texts were way more a common place in questions than in solutions. There was simply not a chance for a solution to have typo or logical errors. If there are no solutions, I'd simply put it for later until I am proficient in the subject and want to try out the problems with confidence. There is always this insecurity when it comes to dealing with logic. Little things can slip in abstract thinking pretty easily. Silly mistakes take a toll. People like myself prefer to solve problems individually at our own pace. Solutions are a must for me. Of course, that 'later' almost always never comes.
jefferickson 8y ago
Hi, I'm the author. I'm honestly seriously torn about this. There is a serious tension between pedagogical needs of students in formal classrooms and the pedagogical needs of self-learners. I've chosen to aim for the former. Yes, I know it's a bummer. (From experience) providing solutions interferes with the learning process of my own students at Illinois. I have to change up homeworks and exam questions every semester, because otherwise students will look up and copy/memorize the answers instead of trying to figuring them out, which means they do worse on the exams where they HAVE to figure things out. Also, a significant majority of the requests I get for solutions are from university students who want to cheat. I do provide solutions to the homework and exam and lab problems I assign in any particular class, after the fact. (And I release those solutions publicly, despite the protests of colleagues at other universities, until the semester ends.) And I have started proving model solutions in the homeworks, so that the students know what kind of answers I'm looking for. (See the course materials page, under CS 374.) In practice, my stance is becoming increasingly moot, as more of my official solutions get uploaded to places like CourseHero and Koofers and their many foreign-language equivalents. I am very likely to include solutions for a subset of problems (maybe three or four per chapter) in a future edition. But that will take a significant amount of time, and I wanted to get something out the door.
- smarks 8y ago
  Thanks for this explanation. This is one of the things that popped out at me when I looked at the book page. The statement about not providing answers seemed quite dogmatic, and my initial reaction was, why? Turns out it's not so dogmatic, and there's a thoughtful and nuanced explanation. Perhaps you could include some of this on the book page, or provide a link to the explanation elsewhere.
  - _underflow_ 8y ago
    Completely agree - being outside academia has apparently made me ignorant to a lot of the pitfalls to actually posting said solutions. Makes perfect sense when put this way. I also really appreciate the response from the author. I forget the gurus behind books like this often have a presence here on HN.
commandlinefan 8y ago
> I like to be able to check my answers when teaching myself things. I agree, although looking at the exercises in this book, they seem to be of the form where the only way to give you the answer is you give you the full solution, and they appear to be phrased in a way that makes it easy enough to verify the answer yourself once you’ve figured out the problem. I always feel like the ideal (for me at least) are problems with numerical answers listed in the back of the book – then I can check my answer with the book’s answer; if I got 42 but they got 5, I know I made a mistake somewhere but it’s still up to me to go back through and figure out where the mistake was. It seems like most of these problems don’t lend themselves to short numerical answers like that.

alsadi 8y ago

The logo on the right is the arabic letters of the word Algorithmi (al-Khwarizmi) the persian muslim scholar after him algorithms and logarithms were named

delinka 8y ago
...after whom...
- dotancohen 8y ago
  Al Gore. Al-Gore-Ithm
arketyp 8y ago
It reminds me of an ashtray design which is famous in Sweden, by Stig Lindberg: https://balstaauktionshall.nu/images/custom/ProductTemplate/53860.jpg https://balstaauktionshall.nu/images/custom/ProductTemplate/... I remember tracing the lines with my finger as a kid, trying to decipher a hidden logic...
divs1210 8y ago
that is beautiful! thanks for pointing it out! is it readable for people who can read Arabic?
- Link- 8y ago
  It still takes a few seconds to identify the word since this is not how Arabic is usually written but yes the word "Al-Khawarizmi" is legible. In fact, the logo contains text both in black and navy blue, the navy blue part is "Al-Khawarizmi" or in Arabic "الخوارزمي". Then the navy blue script is rotated at 90 degrees 3 additional times.
  - alsadi 8y ago
    no, it's very readable because it's a well known calligraphy called kufi as others have pointed out.

kyriakos 8y ago

great job and thanks for keeping this free

yoler 8y ago

Isn’t this the guy that is famous for being admitted to a PhD program with an exceptionally low GPA? If so, why is he the exception and why aren’t more PhD programs looking for non-traditional talent? Edit: I read his blog post. It gave me more insight. It looks possible for people with those sort of grades to be admitted even today, but they seem to need a cheerleader on the inside that will help them.

willbw 8y ago
There are a lot more people going to university these days, and grades are inflated. That's the short story. If you have to look at many many applications for a spot at a top university you are more likely to choose someone who is a "traditional" talent.
a_bonobo 8y ago
There was a small study that came out recently on biorxiv, with 29 PhD students with GREs all over the place - >GRE scores, while collected at admission, were not used or consulted for admissions decisions and comprise the full range of percentiles from 1% to 91%. We report on the 29 students recruited to the Vanderbilt IMSD from 2007-2011 who have completed the program as of summer 2017. While the data set is not large, the predictive trends between GRE and long-term graduate outcomes (publications, first author publications, time to degree, predoctoral fellowship awards, and faculty evaluations) are remarkably null and there is sufficient precision to rule out even mild relationships between GRE and these outcomes. Career outcomes are encouraging; many students are in postdocs, and the rest are in stage-appropriate career environments for such a cohort, including tenure track faculty, biotech and entrepreneurship careers. Now a GRE isn't a GPA (one's a specific test, one is your grades' average), but both are being used for university admissions, and I reckon both are not good predictors. Edit: Link: https://www.biorxiv.org/content/early/2018/07/20/373225 https://www.biorxiv.org/content/early/2018/07/20/373225
- frozenport 8y ago
  There is another interpretation. That sadly, grad school has become potlicial and technical appitude doesn't matter. I have accrude a subantial number of high impact publications and can confirm this is the case. On numerous occasions I have been forced to hand over my completed work to facilitate first author publication for visiting scholars or students my Pi liked received co authorship, joint first authorship for no apparent reason. I would also like to reverse this trend.

otachack 8y ago

I took Jeff's Algorithms class in college and he's one of the best professors I've had. I still struggled through the class but definitely made it through with a great experience.

kyteland 8y ago
I took CS 173 and 373 from Jeff nearly 20 years ago, with 273 from another great professor. That course sequence along with Combinatorial Game Theory (which I took on a lark) has had a greater impact on me than the rest of my university experience combined. A lot of that is due to the quality of the professors I was lucky enough to have.
- jimhefferon 8y ago
  Perhaps you might, when you get a chance, email him a brief note to tell him that. That'll make a person's day.
  - CydeWeys 8y ago
    He's in the comments here so I suspect his day is already made! :)
    - kyteland 8y ago
      Yeah, this may the 3rd or 4th time I've said something along those lines in a HN thread he's active in over the last 10 years.
  - jefferickson 8y ago
    Day made!!
  - mesaframe 8y ago
    You know what, your book on linear algebra is really great too. I tried to understand LA from too many books but your book was the one which made sense for me.

sidravi1 8y ago

The historic preludes to the chapters are awesome. The dynamic programming chapter starts with an intro to the study of meters in Sanskrit poetry.

curiousDog 8y ago

The graphs chapter is my favorite. It's not very rudimentary like other text books

nameless912 8y ago

Jeff's CS 374 was one of my favorite classes at U of I. It really opened up my mind to thinking about Computer Science as a branch of mathematics, and completely changed how I approach my work today. The book form of these lectures was in EARLY rough draft when I took the class though-we were proofing chapters for him!

webmaven 8y ago

Great resource, though I wish it was available as an EPUB (or MOBI, or AZW3).

sharmi 8y ago
I use moon reader pro on Android. It allows annotating and highlighting pdf text. I am not affiliated except as a long time user.
qazpot 8y ago
Why wish, when you can convert PDFs to EPUB very easily using online converters.
- znpy 8y ago
  Yes, but the resulting documents often are horrendous when rendered on ereaders and similar.
- piyush_soni 8y ago
  Yeah i tried doing that. The conversion is so bad with multiple random line breaks in a single line, and some unicode characters not getting converted etc. It was a bad experience.
rezeroed 8y ago
It is. Follow the internet archive link.
- webmaven 8y ago
  An automatic conversion to EPUB from PDF or from a scan is not what I was asking for.
jefferickson 8y ago
You can get an EPUB and MOBI versions from the Internet Archive (auto-converted from my uploaded pdf), but I can't vouch for its quality. All the fonts are baked into the PDF, so it should be readable anywhere; if it isn't, please submit a bug report! But if you're looking for a format that lets you reflow the text, by changing the margins or font or text size, you're out of luck. The only way to write something like that is to bake it in from the beginning. That's easy for pure text, but hard to impossible for technical documents with lots of displayed equations, big hard-formatted boxes of text (ie, algorithms), and the like. (Boaz Barak managed it by writing his Modern Complexity Theory book entirely in Markdown. The mind boggles.)

lbj 8y ago

Absolute treasuretrove, thanks for sharing!

mpurham 8y ago

Wow students are so lucky for the sheer number of resources available today. Great post and thanks for sharing!

brianzelip 8y ago

> ́ Black spades indicate problems that require a significant amount of gruntwork and/or coding. These are rare. > ∆ Orange stars indicate that you are eating Lucky Charms that were manufactured before 1998. Ew. (p. vi) :) Really like the book already. The preface falls under the category of advice on learning to learn. Thanks for all your work. #stealthisbook

ZeroCool2u 8y ago
>Caveat Lector! >Of course, none of those people should be blamed for any >flaws in the resulting >book. Despite many rounds of revision and editing, this >book contains many mistakes, bugs, gaffes, omissions, >snafus, kludges, typos, mathos, grammaros, >thinkos, brain farts, poor design decisions, historical >inaccuracies, anachronisms, >inconsistencies, exaggerations, dithering, blather, >distortions, oversimplification, >nonsense, garbage, cruft, junk, and outright lies, all >of which are entirely Steve Skiena’s fault. Coming from a class where we used a decidedly poor textbook for algorithms, this looks like a joy to read.

wwarner 8y ago

The section on dynamic programming is exceptionally clear.

azangru 8y ago

From the second page (verso page?): > Download this book at http://jeffe.cs.illinois.edu/teaching/algorithms/ http://jeffe.cs.illinois.edu/teaching/algorithms/ or http://algorithms.wtf http://algorithms.wtf algorithms.wtf is a beautiful url!

neurotrace 8y ago

> Chapter 0 uses induction, and whenever Chapter n−1 uses induction, so does Chapter n I love this.

primitivesuave 8y ago

Jeff Erickson was my algorithms professor in 2012. He exemplifies the articulate, passionate educator that I wish I had for my other CS subjects. I recognize many of these notes having read them many times in preparation for quite difficult exams - a fun anecdote shared among people who've taken the class is the 25% credit given on any exam question just for writing "I don't know", effectively a reward for acknowledging your own shortcoming and for saving the TA the time to decipher a bullshit answer. Professor Erickson, if you're reading this, thank you for being the best educator of my college days and for making your beautifully-written notes available to everyone.

gricardo99 8y ago
>25% credit given on any exam question just for writing "I don't know", effectively a reward for acknowledging your own shortcoming and for saving the TA the time to decipher a bullshit answer. That’s brilliant, yet I’ve never heard of it. Should be standard scoring for written exams.
- Vaslo 8y ago
  Random other point of brilliance I've seen: Our Organic Chem teacher (who was loved universally in the Program) had a rule about test corrections. If you wanted a correction to something you believed you should get credit on, he would only offer to regrade your WHOLE test, which meant you could actually get less points on the regrade because it was he and not a TA regrading (could have worked both ways). It really scared off all those one-off "Can I get an extra point here" requests in a 300 person class.
  - edanm 8y ago
    I think that was the way it worked at my university too, at least officially. Unofficially, very few teachers actually graded that way, and when I saw it happen, people complained about it a lot. Then again, the teachers that did it seemed like they were doing it punitively (e.g. subtracting the exact amount of points they were forced to add.)
  - 8y ago

briefcomment 8y ago

Are algorithms useful to learn for a non-programmer? Is there a benefit to thinking through what is presented in a book like this over solving general problems in a day-to-day context?

clishem 8y ago
Please find something you love doing and learn more about that instead of picking up random things.
- briefcomment 8y ago
  Sound advice. Thinking through the scope of a programming problem to come up with an algorithm sounds like a productive way of using your mind, but may be a waste of time if you don't intend on programming.
- saagarjha 8y ago
  What if what you love doing is picking up random things ;)
EnFinlay 8y ago
As a whole, I doubt a book like this would be of much use to a non-programmer. There are some high level tricks that might be fun to learn, and could be loosely applied to day-to-day thinking (should this be solved in a brute force way, or is there some shortcut). Overall the book (I assume, I haven't read it) is technical and precise solutions to technical problems. Algorithms are just ways of solving technical problems in the most efficient way possible (for various definitions of efficiency). They are deep programming which even most programmers don't use frequently.
- briefcomment 8y ago
  Suspected this might be the case, thanks for your thoughts.
akman 8y ago
You may be interested in the book Algorithms to Live By ( Brian Christian, Tom Griffiths). I thought it was a fun-to-read book, though I don't think there was any code in the book at all.

ausjke 8y ago

After a quick browser it seems a little too academic for daily programmers like myself. Would love to learn more about practical dynamic programming these days, hope there is a book about that extensively.

deleted 8y ago
[deleted]
ibash 8y ago
Go back and read it - it’s not!

pseudonom- 8y ago

Does anyone have any impressions on how this compares to CLRS? (https://en.wikipedia.org/wiki/Introduction_to_Algorithms https://en.wikipedia.org/wiki/Introduction_to_Algorithms)

zawerf 8y ago
In particular are there any new materials that has been invented or widely adopted since the older textbooks? For example, bloom filters were rarely taught maybe 10 years ago but probabilistic data structures are now pretty mandatory in a data structure course. Just wondering if there are sections in this book covering cutting edge stuff for people already familiar with traditional algo
- jefferickson 8y ago
  Not so much in the book itself, but definitely in the "Director's Cut" notes on the book web site. I cover bloom filters and the like in my more advanced algorithms courses. Teaching that material correctly (without the traditional magical thinking) requires serious comfort with probability, which unfortunately isn't early enough in the CS curriculum at Illinois to be used in our data structures and algorithms courses.
rbkillea 8y ago
By Ctrl+F'ing, I find 5 mentions of the word "master", none of which are the master theorem. I prefer this to CLRS as, while it's a neat trick, it tends to result in a bunch of people memorising the cases (and taking a "because the book told me to" level of understanding away from that part of the course).
- jefferickson 8y ago
  Exactly. The students should be the masters, not the theorem.

konart 8y ago

Maybe that because english is not my native language, but I honestly find this way of material presentation as rather confusing. PS: oh and of course all those 'It’s quite easy to show that the...' and similar 'by this point it should be obvious'. No, it is not... I guess I will never understand or use those algorithms even though I'd like to.

jefferickson 8y ago
Hi, I'm the author. If you find any particular claim of "obviousness" unclear, submit an issue request! But please don't confuse "straightforward" with "obvious". Sometimes I deliberately gloss over mechanical details because I think they're a distraction from the main point. I'm NOT claiming that you should immediately know how to fill in the details; I'm claiming that filling in the details is boring.
- fwip 8y ago
  I would agree that words like "obvious" or "trivial" can be disheartening to a learner. If it's obvious to the reader, they know it whether or not you tell them it's obvious. If it's not obvious to them, then they will try to figure it out. Telling this person "it's obvious" only serves to make them feel bad about not getting it right away.
  - mden 8y ago
    I felt that way when studying math in college, but after sometime I actually came to like the use of "clearly" and the like as it can be used as a check on whether you've spent enough time internalizing the previous information. It's one thing to have a text or a person hold your hand through algorithms or theorems, it's another to be able to do it yourself. So getting hit with a "clearly" that feels unjustified is often a signal to let go of the guiding hand and go back and review until the statement in question does become clear.
    - konart 8y ago
      Sometimes this is th'e case, yes, sometimes it is not. An example: http://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE-2up.pdf http://jeffe.cs.illinois.edu/teaching/algorithms/book/Algori... Page 15 > It’s quite easy to show that the singing time is Θ(n2); in particular,the singer mentions the name of a gift ∑ni=1i=n(n+1)/2times (counting thepartridge in the pear tree). I'm pretty sure that I still remember how to read the formula and I even know what does Θ(n2) means, but it's still unclear for me how do we get n^2 and this formula from the "NDaysOfChristmas(gifts[2..n]):" example.

Zanta 8y ago

I used these lectures as a method for learning algorithms as a phys/mech eng with no CS background. I found them incredibly challenging but the lectures were written exceptionally well. On an internet with thousands of resources on this material, this was the very best I found.

dksf 8y ago

I love how he offers the mnemonic http://algorithms.wtf http://algorithms.wtf Bravo, Jeff!

nythrowaway 8y ago

I managed to get a A- in Ericsson’s 373 as an undergrad (grads took the same class but had their own curve) in 2001. Great class, great experience, great teacher. Pushed me to do algorithms at a difficulty I didnt hunk possible.

mlevental 8y ago

gonna take this opportunity to ask for advice: i have an MS in CS and i've gone through all of CLRS twice (yes really all of it and really twice - once for my grad algos class and once in prep for interviews - and i still don't have whatever intuition i need to be able to effortlessly do DP. it's honestly kind of maddening - mincut/maxflow, RSA, knuth-morris-pratt etc are all completely obvious to me and i can whip them out pretty much effortlessly - but DP i struggle to find the optimal substructure and formulate bottom up (yes i can memoize but that's not clever enough for you know who). what's the magic combinatorial perspective/intuition that enables people to construct dp solutions so quickly??? yes i've read vazirani and gone through the clemson examples and etc. and skiena and sedgwick whatever but the problem is they're mostly all rehashings of the same solutions/perspectives. looking forward to this book's perspective.

svat 8y ago
I think if you find those algorithms obvious and you're able to write memoized solutions, then you already know most of what you need to know about dynamic programming. For example, Dijkstra's algorithm for shortest paths can be seen as DP. The main thing is to write down a formulation for the answer for n in terms of answers for smaller n, or the answer for (n, k) in terms of answers for smaller (n, k). (And don't worry about how you'd compute them, just focus on getting a correct expression in terms of smaller ones. http://okasaki.blogspot.com/2008/10/score-one-for-induction.html http://okasaki.blogspot.com/2008/10/score-one-for-induction....) It can be tricky to formulate exactly what you're counting / measuring (e.g. what's "k" and what's the quantity you're optimizing for (n, k)), but once you have that, and once you have the recurrence, you can consider it a separate (and independent) step to figure out in which order to compute the values, so that you have each value by the time you need it (i.e. the bottom-up formulation that you said is the tricky part for you). Beyond that I guess lots of practice with problems… e.g. about a decade ago there used to be weekly(?) TopCoder contests with editorials written later explaining the solutions (and the problems were graded by difficulty and even how many people solved it), and the DPs could get quite tricky. I believe those are still happening, and now there are other resources like LeetCode or whatnot. Do you have an example of a problem that you struggled with, to see what's missing?

kizer 8y ago

I had him as a professor as well. He’s a brilliant guy and educator, but could be a little rough with questions; i.e. making you feel a little dumb. His notes though were always excellent.

setheron 8y ago

I would appreciate a version of the book with the extended material as well! Is there a way to pre-pay advanced copies of the published book?

rbkillea 8y ago

This has always bugged me: what reasons outside of convention do we have for preferring O(V + E) to O(E) on algorithms that only make sense in the context of a single connected component? I know this is slightly OT, but tangentially related.

dotancohen 8y ago

This is a great resource. Though it is dated this month, there seems to have been a mention of it two years ago and a short HN discussion ensued: https://news.ycombinator.com/item?id=12873426 https://news.ycombinator.com/item?id=12873426

raylangivens 8y ago

I have been reading through these and find them really unique in a good way. I got a new perspective on a lot of stuff I already studied I have a Bachelors in CS and graduated 1.5 years ago. It doesn't feel formal like a textbook and yet doesn't sacrifice on the mathematical rigor. I would be trying out the exercise problems which seem equally daunting but fun. I also submitted an issue request on Github and Jeff I have a few questions for you that I put on Quora, I have A2A'd you. Lastly, thanks for taking the time out and putting content like this out for free. It helps millions of autodidacts like me.

vowelless 8y ago

The lecture on Matroids is pretty good.

sqlacid 8y ago

Copyright question, the copyright page says draft published 12/29/2018, but the copyright is 2019; doesn't that mean somebody could have taken the work, published as their own as copyright 2018 on 12/30/2018 which would be earlier than the author's 2019 claim? I'm not a copyright expert by any means, but am always troubled when I see "Copyright $CURRENT_DATE" in electronic works, I thought it was supposed to reflect the earliest date of claim.

ggggtez 8y ago
No, because copyright law doesn't care what the copyright date says, or even if you write it at all. As soon as you write something, you have the copyright to what you wrote. If it was challenged in court, he would likely easily be able to show his drafts from prior to 12/29/2018 to prove he was the author.
flyGuyOnTheSly 8y ago
You don't actually have to place a copyright on original works like this. Copyright is granted whether you put the little c symbol and date or not.
jefferickson 8y ago
Oops. I'd say submit a bug report, but as of yesterday it become moot. As others have said, the copyright notice is only a courtesy/reminder. I've held the copyright on all this stuff from the moment I started writing it (and distributing it) 20 years ago.

azhenley 8y ago

Jeff is also a frequent poster on Academia.StackExchange. He helped me quite a bit by answering my questions about grad school life. https://academia.stackexchange.com/users/65/jeffe https://academia.stackexchange.com/users/65/jeffe

mcguire 8y ago

"Sedgwick’s reformulation [of AA trees] requires that no right child is red. Whatever. Andersson and Sedgwick are strangely silent on which end of the egg to eat first."

Twisol 8y ago

I am, in all likelihood, not in the target audience (having already spent much time with the material being presented), but this textbook has been a joy to read so far. I am only up to page 14, and I already need two hands (in base 1...) to count the number of times I've laughed aloud or cheered a particular point being raised. Most algorithms books are dry, or they're obsessed by particular formal details, or (worse) they implicitly include optimizations in the algorithm without explaining what is needed for correctness and what is needed for efficiency. Having tutored on one of the books mentioned in the prologue, it can be a real struggle to gain a true intuition for algorithms when you can't yet tell the difference. But the sheer personality contained within this book is infectious, and it really is something of a page-turner. (Lest you think I haven't gotten to the stuff that "matters", I have read through the chapter on depth-first search -- again, an enjoyable read!) What a great book. I'm definitely recommending this to my friends.

tptacek 8y ago
Same. I fell in love with it instantly and permanently when I got to the "NO, STOP, YOU'RE DONE" part in the Towers of Hanoi. I skipped around the book and the whole thing is like that. It's simultaneously concise and witty in service of the material. The chapter problems look fantastic, too, and are just as well-written (and they cover a lot of ground). It's really something!

mnadel 8y ago

I had the privilege of being an undergrad in Jeff’s class in the late 90s. IIRC, it was his first year teaching. On the last day of class he received a standing ovation. The average grade on the final exam was ~50%. And yet he received a standing ovation. He’s that good.

Topolomancer 8y ago

I love Jeff Erickson's work and would also like to recommend his notes on Computational Topology [1] for further consumption. [1]: http://jeffe.cs.illinois.edu/teaching/comptop/2009/schedule.html http://jeffe.cs.illinois.edu/teaching/comptop/2009/schedule....

sidcool 8y ago

How does this compare to CLRS? I am neck deep in reading CLRS..

skizm 8y ago

What the heck is the trivial one liner to check who will win a chess game given both players play perfect?

d4rti 8y ago
I can only come up with a recursive algorithm which depends on a PerfectPlay(state, player) like so: WinnerWithPerfectPlay(state,currentPlayer): if Winner(state) return Winner(state) else nextPlayer <- "white" if currentPlayer = "black" else "black" return WinnerWithPerfectPlay(PerfectPlay(state, player), nextPlayer) Which doesn't allow for stalemate moves.
kirkules 8y ago
I suppose the claim of the existence of this one liner might be the same as the claim that one of the players can always force a win, in which the line is something like "return 'white'" or "return 'draw'"
plin25 8y ago
I believe this is a trick question. The "standard" chess board is 8x8, with a 32 possible pieces. This gives you a constant (albeit absurdly large) number of configurations, which means that the one-line solution "Brute Force" is an O(1) algorithm.

yangdehang 8y ago

I don't know why your guys think this book is so good, I don't see any new things out of it nor could I appreciate how he composed the content. It is just one of those random textbooks for this topic.