"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."
Algorithms, by Jeff Erickson
161–170 of 245 posts
Re: Algorithms, by Jeff Erickson
#162gonna 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...
i'm familiar with this (through stochastic control and reinforcement learning and general econ stuff) but it's not really useful for the whiteboard coding style DP that FAANG asks.
Re: Algorithms, by Jeff Erickson
#163Earlier quoted context omitted.
I graduated with a Comp.Sci bachelor with a similar GPA. Spent around 10 years as a programmer in the industry and came back to get into the masters program. I was almost laughed off (a good thing) stating I would have to do another bachelor. Sold my house, got rid of all my stuff and enrolled in pure math bachelor's. Best decision of my life. I though that in my mid 30s with a lot more discipline, being able to work…
> I graduated with a Comp.Sci bachelor with a similar GPA. Spent around 10 years as a programmer in the industry and came back to get into the masters program. I was almost laughed off (a good thing) stating I would have to do another bachelor. Can you expand on this? I'm similar right now. Want to go back and get my masters. Graduated in CS about 12 years ago. Mid 30's. What do you mean about having to do another ba…
My GPA was 2.37 and I would've had to take so many classes to increase my GPA up to the cut off point of 2.7 (B-). With 90 credits worth of classes, you'd need 90 credits at 3.0 (B average) to make up for the difference, or less if you get better grades and that means you're on the low end of what they accept.
Now I presume if you did 2-3 semester with a B+/A- GPA, they would take that as testifying you can handle the masters and let you in, however I'm enjoying math way too much right now and there are several classes (Algebra 1-3, Topology, Differential Equations and several classes in statistics I intend to pick in the option block) that will come in handy if I head into ML masters I'm also interested in Type Theory and all of Discrete Mathematics. Also, I feel math is a great program to improve at general problem-solving.
The first semester was really challenging, some classes I had in fact already done (Calculus 1 and Linear Algebra) turned out to be surprisingly difficult. I'd say around halfway through the second semester I felt I had gotten my younger brain back.
I don't have expensive habits, have two restaurants meal a week, own a car and live at the university residences (rent is 390$/month, parking 850/year). My cost of life seems to be around 12k CAD/year and am Canadian (tuition costs are 1600/semester) so I really have no idea how much you'd have to have saved up if you are in the USA.
Re: Algorithms, by Jeff Erickson
#164Earlier quoted context omitted.
I graduated with a Comp.Sci bachelor with a similar GPA. Spent around 10 years as a programmer in the industry and came back to get into the masters program. I was almost laughed off (a good thing) stating I would have to do another bachelor. Sold my house, got rid of all my stuff and enrolled in pure math bachelor's. Best decision of my life. I though that in my mid 30s with a lot more discipline, being able to work…
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 the time investment or should I just forget about it and tackle something like your book and spend the rest of my time on other topics?
Re: Algorithms, by Jeff Erickson
#165Jeff 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 acknowledg…
>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.
A friend of mine took a game theory class with this system. Partial credit also given for partially correct solution. Completely wrong bullshit answers would lose 10%, or something like that.
Re: Algorithms, by Jeff Erickson
#166Earlier quoted context omitted.
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.
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.
Now that is something mathematician quickly learn to not be bothered about:
the proof is easy and left as an exercise
The main takeaway I got from Polya's How to Solve it is that properly conceptualizing the problem in your head before attempting to solve it is key.
Re: Algorithms, by Jeff Erickson
#167Earlier 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…
When I was a professor this is the way I would regrade too. I would regrade blind to the first mark so I didn’t bias myself. I don’t think I ever had a regrade that changed more than 5% and most were identical.
I would also grade all exams the first time blind to who the student was and then regrade a half dozen again to make sure that I hadn’t drifted out of grade over the marking process.
I used to play an game with myself (marking is very boring) as to who would get what mark based on my in class knowledge of the student (when you run labs you do get to know the individual students). It was a rare student that got a exam mark more than 10% outside my estimate.
Re: Algorithms, by Jeff Erickson
#168Earlier 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’ve never understood why that’s a good policy. You’re (vindictively) punishing the student for pointing out — albeit selectively — where the teacher, supposedly a bedrock of truth on the course material, has falsely labeled your “training data”.
Re: Algorithms, by Jeff Erickson
#169> 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…
I'm a self learner and I find that having a strong sense about my solution is usually good enough. If I feel my answer is brittle then I should simply review the problem statement or anterior definitions and theorem.
I usually look at the solutions when I've come to the conclusion that the problem is just too difficult and typically discover I hadn't thought of something that made the problem accessible. I would argue that if there are sufficient examples within the chapters, not providing solutions to the exercises shouldn't be a problem.
That is unless you have multi-month/research level problems à la Knuth.
Re: Algorithms, by Jeff Erickson
#170Earlier quoted context omitted.
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’ve never understood why that’s a good policy. You’re (vindictively) punishing the student for pointing out — albeit selectively — where the teacher, supposedly a bedrock of truth on the course material, has falsely labeled your “training data”.
I think you're running under the assumption that all students making the request are doing it for the right reasons.
I could be wrong, but my intuition goes the other way and I'm assuming most students do it to get a better grade, not learn more.