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

121–130 of 245 posts

Re: Algorithms, by Jeff Erickson

#121

Post by svat »

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

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?

Re: Algorithms, by Jeff Erickson

#122

Post by bradleyjg »

saagarjha wrote: post #109
bradleyjg wrote: post #99

Earlier quoted context omitted.

I had a similar thing happen in high school physics. We were were suppose to figure out where and when a projectile was going to land. The only problem was that it was never going to land—-the initial velocity was too high. In retrospect I think it was a great lesson for my future career as a data engineer. Doesn’t matter what the source is, any datum can be just plain wrong.

> The only problem was that it was never going to land—-the initial velocity was too high. As in, it escaped the gravitational field?

Yep.

Re: Algorithms, by Jeff Erickson

#123

Post by dirtybird04 »

yoler wrote: post #9

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.

Link for the uninitiated: https://3dpancakes.typepad.com/ernie/2005/03/re_phd_with_low...

Re: Algorithms, by Jeff Erickson

#124

Post by edanm »

Vaslo wrote: post #100
gricardo99 wrote: post #69

Earlier quoted context omitted.

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

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

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

Re: Algorithms, by Jeff Erickson

#125

Post by alach11 »

jefferickson wrote: post #86
_underflow_ wrote: post #3

> 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?

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

>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've found that whether or not a professor releases solutions to assignments (or even tests), some segment of the student population will have access to the solutions. Releasing them publicly ensures the access is universal, instead of limited to those with the right connections/access.

Re: Algorithms, by Jeff Erickson

#126

Post by ssalazar »

justadudeama wrote: post #118
jefferickson wrote: post #93

Earlier quoted context omitted.

Yes, that's me. Admissions committees are looking for evidence of future success. Admitting applicants with spotty (not merely "nontraditional") backgrounds is risky -- they might be a diamond in the rough, or they might really be a weak student. And (at least departments like mine) there are far too many applicants with stellar backgrounds to justify taking that risk. At least, that's the usual argument.

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.

Context: Got bad grades in undergrad courses related to my particular specialty (digital audio signal processing), but also did all of these, and was admitted to a top PhD program in my field.

Also, a lot of people in my program had success with this one:

- Applying for a masters in a related field or at a department that also has a PhD program that you're interested in, and having success there.

Re: Algorithms, by Jeff Erickson

#127

Post by bhl »

jefferickson wrote: post #86
_underflow_ wrote: post #3

> 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?

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

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

While I understand the desire of a professor to help out their own students, at what point does this become a matter of individual responsibility? Shouldn’t it be the student who refrains from memorizing answers?

When I took my algorithms course, we had a reference textbook with questions at the end of the chapter, but no solutions. Some people at the beginning of the semester tried to crowdsource the answers using a Google doc but that effort failed. It didn’t really matter though, since our homework and exam questions were always renewed each semester through the work of course staff and the instructing professor. In hindsight, I may have taken this for granted as it seems other schools don’t have a “training” and a “testing” set of problems - I would say having both is better than only having one.

Re: Algorithms, by Jeff Erickson

#128

Post by daveFNbuck »

saagarjha wrote: post #110
daveFNbuck wrote: post #68

Earlier quoted context omitted.

That professor probably had produced the answer already, using the metric he had initially intended. Having a set of answers doesn't mean you didn't make a mistake in the questions.

But it does clue you into whether the professor used a different set of assumptions than you did.

Presumably you wouldn't see the answers until after you spent all night on the assignment.

Re: Algorithms, by Jeff Erickson

#129

Post by dunham »

emidln wrote: post #120
Eridrus wrote: post #111

Earlier quoted context omitted.

This is functionally equivalent to being given negative marks for getting answers wrong, which I've seen on multiple choice tests.

Only if no partial credit is offered, which is not how his exam[0] reads to me: As usual, answering any (sub)problem with “I don’t know” (and nothing else) is worth 25% partial credit. Yes, even for problem 1. Correct, complete, but suboptimal solutions are always worth more than 25%. A blank answer is not the same as “I don’t know” [0] http://jeffe.cs.illinois.edu/teaching/algorithms/hwex/s18/fi...

I had a math prof who would give negative marks on proofs, preferring you say “I don’t know how to do this step” and finishing the proof over trying to BS the step.

Re: Algorithms, by Jeff Erickson

#130

Post by aklemm »

jefferickson wrote: post #86
_underflow_ wrote: post #3

> 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?

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

You could consider providing answers and feedback in a premium priced forum or email subscription.
Post reply on HN