Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Algorithms, by Jeff Erickson

jeffe.cs.illinois.edu

Post reply on HN
Print view View original

191–200 of 245 posts

Re: Algorithms, by Jeff Erickson

#191

Post by jefferickson »

mlevental wrote: post #92

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 t…

Forget about efficiency for the moment and focus on discovering the underlying recursive problem.

LOTS of people struggle with dynamic programming. But in my experience, 90% of the difficulty with dynamic programming is actually discomfort with recursion, which is why I talk about recursive backtracking first.

Try reading Chapter 2. My goal in that chapter is to show the process of deriving recursive solutions---how to think about the problem, and what questions to ask---rather than just presenting the solution as a fait accompli.

I do have to assume that you believe in the Recursion Fairy, though. That's probably the hardest step. Computer scientists are TERRIBLE at delegating.

Re: Algorithms, by Jeff Erickson

#192

Post by jefferickson »

svat wrote: post #121
mlevental wrote: post #92

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 t…

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 w…

"Dijkstra's algorithm for shortest paths can be seen as DP"

Really? Sure, if the graph is a dag, but then Dijkstra is overkill.

Hmm. I'll have to think about this one.

+1 for the Okasaki shoutout.

Re: Algorithms, by Jeff Erickson

#193

Post by tptacek »

Twisol wrote: post #187

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 (wors…

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!

Re: Algorithms, by Jeff Erickson

#194

Post by jefferickson »

jimhefferon wrote: post #51
kyteland wrote: post #45

Earlier quoted context omitted.

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.

Perhaps you might, when you get a chance, email him a brief note to tell him that. That'll make a person's day.

Day made!!

Re: Algorithms, by Jeff Erickson

#195

Post by jefferickson »

davidgrenier wrote: post #164
jefferickson wrote: post #94

Earlier quoted context omitted.

Well done!

Jeff, I'd be curious to know. Going through TAOCP is on my lifetime-to-do and feel I am getting close to tackling it again however I have no time right now. There's also so many other things I want to go over (some higher order logic, TAPL, PFPL, the Software Foundations books, compiler design and probably won't pass up some category theory being abstract algebra seems accessible to me). Do you feel TAOCP is worth th…

I'm not sure I can answer that question for anyone but myself. I've worked through quite a few pieces of TAOCP when I've needed to understand a particular topic, but I always find that I lose interest.

But then I've never been able to learn anything by just reading. I always have to have a target problem in front of me, and then I'll read (and get frustrated by) every book ever written to figure out the best way to think about that problem. (Which means I've read a few dozen pages from hundreds of books, and I have pretty huge gaps in my math background -- abstract algebra and category theory being two big examples.)

For some target problems, TOACP has been incredibly helpful, but for most of them it really hasn't. Knuth and I just care about different things.

For the same reason, I can't recommend that anyone work through EVERY problem in my book, either. Find the parts that are interesting and/or useful to you, and work on those. If you get tired or frustrated, work on something else; maybe you'll discover another reason to pick up my book again later. Or not.

Climbing the mountain is much more rewarding than studying the trail map.

Re: Algorithms, by Jeff Erickson

#196

Post by mesaframe »

jimhefferon wrote: post #51
kyteland wrote: post #45

Earlier quoted context omitted.

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.

Perhaps you might, when you get a chance, email him a brief note to tell him that. That'll make a person's day.

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.

Re: Algorithms, by Jeff Erickson

#197

Post by austhrow743 »

thrwthrw93223 wrote: post #34
nf05papsjfVbc wrote: post #28

Earlier quoted context omitted.

"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" require…

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…

It might be an elitist and gate keeping mentality but I have to say that calling providing a free resource to someone, but not tailoring it to fit their exact situation, "robbing" is a very entitled one.

Re: Algorithms, by Jeff Erickson

#198

Post by jefferickson »

ssalazar wrote: post #126
justadudeama wrote: post #118

Earlier quoted context omitted.

What advice would you give to undergraduates that are interested in getting a Ph.D who don't have the best of grades?

- Work on, or help out with, a research project of a professor/established researcher in your field of interest. - Related, getting authorship (first or otherwise) for an academic publication as an undergraduate is a promising signal of future research success. - Also related, having great references from undergrad professors who are involved in research. - Connect with faculty in the PhD program you're interested in…

Yep, all this. Let me add two more points:

- Own your past mistakes. They happened. Don't pretend they didn't. Figure out the underlying cause of those mistakes, and gather EVIDENCE that you've resolved that cause.

(In my case, I was a LAZY undergrad. I'd never had to work in high school, and so I didn't know how to work in college. And then I got a real job, and it was either do the damn work or it'll be there tomorrow only the boss will be there in my office wondering why the hell I'm costing the company hundreds of thousands of dollars a day and why can't you just get this shit DONE already. And so when I applied for grad school the second time I had "smart but lazy" letters from my old professors, stellar GRE scores, and "smart and works hard" letters from my managers.)

- APPLY WIDELY. You are at a significant disadvantage compared to other students with stronger backgrounds. Do not imagine that your passion and good intentions and maturity are enough to get you into the top programs, or even into any particular program. You're playing a lottery that's stacked against you; buy more tickets.

Re: Algorithms, by Jeff Erickson

#199

Post by jefferickson »

rbkillea wrote: post #117
pseudonom- wrote: post #76

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

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).

Exactly. The students should be the masters, not the theorem.

Re: Algorithms, by Jeff Erickson

#200

Post by svat »

jefferickson wrote: post #192
svat wrote: post #121

Earlier quoted context omitted.

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 w…

"Dijkstra's algorithm for shortest paths can be seen as DP" Really? Sure, if the graph is a dag, but then Dijkstra is overkill. Hmm. I'll have to think about this one. +1 for the Okasaki shoutout.

Hmm, I wrote that from vague memory, and perhaps that's debatable! (There seem to be different communities that use “dynamic programming” slightly differently.)

But my main point was: if one can look at the shortest-path problem and formulate something like

distance(v) = min_{u->v} (distance(u) + edge_length(u, v))

then one probably has a handle on whatever it is that's hard about dynamic programming. Actually Wikipedia cites some references that consider Dijkstra's algorithm a case of DP: https://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algo... and the same text (Wikipedia doesn't care about “self-plagiarism”) is also on the DP page where Dijkstra's algorithm is given as the first example: https://en.wikipedia.org/w/index.php?title=Dynamic_programmi...

Post reply on HN