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

141–150 of 245 posts

Re: Algorithms, by Jeff Erickson

#141

Post by thfuran »

dunham wrote: post #129
emidln wrote: post #120

Earlier quoted context omitted.

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.

How do you skip a step in a proof? You just say "assuming I can prove this assertion, this other stuff follows"? That seems to risk accidentally skipping way more steps than you thought you were skipping and quite probably the meat of the proof.

Re: Algorithms, by Jeff Erickson

#142

Post by dragonwriter »

thfuran wrote: post #141
dunham wrote: post #129

Earlier quoted context omitted.

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.

How do you skip a step in a proof? You just say "assuming I can prove this assertion, this other stuff follows"? That seems to risk accidentally skipping way more steps than you thought you were skipping and quite probably the meat of the proof.

> How do you skip a step in a proof?

Well, from the math profs I've seen, the usual method is to interpose “it is intuitively obvious” in place of the skipped step(s).

The tricky part is having a correct intuition as to what you should be skipping to, sure, but that's the same problem as you have doing a proof (minus actually figuring out the justification) since humans don't generally do proofs by exhaustively listing every possible next step from what is already proven in a BFS until getting the desired result and then pruning all the other paths.

Re: Algorithms, by Jeff Erickson

#143

Post by zerr »

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…

Maybe for some problems it is possible to include just the final answers? e.g set of possible inputs and expected outputs - so one can test the solution.

Re: Algorithms, by Jeff Erickson

#144

Post by __MatrixMan__ »

thfuran wrote: post #141
dunham wrote: post #129

Earlier quoted context omitted.

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.

How do you skip a step in a proof? You just say "assuming I can prove this assertion, this other stuff follows"? That seems to risk accidentally skipping way more steps than you thought you were skipping and quite probably the meat of the proof.

Prompted with:

    Given A, prove Z
You'd append

    Assume G => H
...to the prompt, then you'd prove A=>G, and you'd prove H=>Z.

You're essentially just using one-too-many axioms to get the job done, which is less elegant, but correct.

Re: Algorithms, by Jeff Erickson

#145

Post by dunham »

thfuran wrote: post #141
dunham wrote: post #129

Earlier quoted context omitted.

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.

How do you skip a step in a proof? You just say "assuming I can prove this assertion, this other stuff follows"? That seems to risk accidentally skipping way more steps than you thought you were skipping and quite probably the meat of the proof.

Essentially that. There is a risk a skipping a majority of the proof and hence a majority of the points, but point-wise it would work out better than handwaving the step and getting negative points.

It's been about 25 years, so my memory is a bit fuzzy, but it was an analysis class. I don't remember if I ever availed myself of this. I did have a classmate who completed, but didn't turn in his homework a couple of times. (I don't recall if it was the entire problem set or just a couple of problems that he omitted, but he got the paper out to consult while the prof was going over the answers.)

The teacher was competent but quirky - he also required the students to purchase a stapler (to staple their homework) and locked the door after class started (if you were late, tough luck).

Re: Algorithms, by Jeff Erickson

#147

Post by earthicus »

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…

Here's an old mathematical perspective that treats dynamic programming as analogous to the calculus of variations. Very different from a how it's usually talked about, I think. I haven't read much of it, but perhaps the change in perspective will be helpful to you:

https://www.rand.org/content/dam/rand/pubs/reports/2006/R441...

Re: Algorithms, by Jeff Erickson

#148

Post by [deleted] »

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…

[deleted]

Re: Algorithms, by Jeff Erickson

#149

Post by jperras »

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…

This was the policy for any final exam at my alma mater.

You had to be rather certain that you were sufficiently wronged overall, otherwise a few points more on one question could be offset by a large number of negated points from other questions where the professor thought that the TA might have been too generous.

Re: Algorithms, by Jeff Erickson

#150

Post by GlickWick »

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'm honestly somewhat surprised that you-know-who is asking DP problems with that degree of complexity. Are you applying for a research/math-heavy role? If you're unlucky enough to see DP, usually it's pretty basic and memoization is considered fine, unless things have changed very recently. If they required that degree of rigor for regular SWE jobs, a lot of people I know certainly wouldn't be there.
Post reply on HN