Algorithms, by Jeff Erickson
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.
> 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?
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
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.
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.
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.
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.
> Ģ 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
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.
From the second page (verso page?):
> Download this book at http://jeffe.cs.illinois.edu/teaching/algorithms/ or http://algorithms.wtf
algorithms.wtf is a beautiful url!
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.
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!
Jeff is also a frequent poster on Academia.StackExchange. He helped me quite a bit by answering my questions about grad school life.
"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."
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.
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....
Wow students are so lucky for the sheer number of resources available today. Great post and thanks for sharing!
> Chapter 0 uses induction, and whenever Chapter nā1 uses induction, so does Chapter n
I love this.
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.
The historic preludes to the chapters are awesome. The dynamic programming chapter starts with an intro to the study of meters in Sanskrit poetry.
Great resource, though I wish it was available as an EPUB (or MOBI, or AZW3).
I love how he offers the mnemonic http://algorithms.wtf
Bravo, Jeff!
What the heck is the trivial one liner to check who will win a chess game given both players play perfect?
Love his writing style. Accessible yet detailed with fun historical tangents to set context.
Does anyone have any impressions on how this compares to CLRS? (https://en.wikipedia.org/wiki/Introduction_to_Algorithms)
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.
Absolute treasuretrove, thanks for sharing!
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.
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?
The section on dynamic programming is exceptionally clear.
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
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.
The graphs chapter is my favorite. It's not very rudimentary like other text books
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.
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?
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.
great job and thanks for keeping this free
How does this compare to CLRS? I am neck deep in reading CLRS..
The lecture on Matroids is pretty good.
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.