3 ms·
For the record, I took this section and scored 22/25. I took the other 3 parts and expect to score much worse on at least 2 of them. On question 1 I really th
by btilly 14y ago
For the record, I took this section and scored 22/25. I took the other 3 parts and expect to score much worse on at least 2 of them.
On question 1 I really think that Colin is wrong and my answer was right. As http://en.wikipedia.org/wiki/Big_O_notation#Equals_sign http://en.wikipedia.org/wiki/Big_O_notation#Equals_sign says, with citations, equality in big-O notation is usually used in an asymmetric way. Sure, Colin's preferred notation would be theoretically better, but the common usage supported by authorities up to and including Knuth is that, for instance, O(n) = O(n^2) but not O(n^2) = O(n). Using the definitions that lead to that, I demonstrated that O(2^n) = O(3^n) but that the reverse is not true.
On question 3, I knew full well about the disk win, but failed to say it. :-( Oh well...
Anyways, as others have said, thank you Colin for being willing to put this together and do the work.
- gjm11 14y agoIf you actually literally did that, then I think Colin should have given you full marks for Q1 since the only difference between what he wanted and what you did was terminological. (Personally, I would write O(2^n) = O(3^n) but would not say that O(2^n) is equal to O(3^n). Which, yes, is rather weird.)
- cperciva 14y agoequality in big-O notation is usually used in an asymmetric way The equals sign is used in an asymmetric way, to represent something which is not equality. There was a reason I asked "is O(2^n) equal to O(3^n)?" rather than "is O(2^n) = O(3^n)?". But I gave you 4/5 on that question anyway, since you obviously had the right idea.
- btilly 14y agoTo me equality is whatever an = sign represents. shrug But this reminds me of something amusing. I will never forget how hard it was for me to understand the distinction between isomorphic and naturally isomorphic. You see I thought of "isomorphic" as meaning "the same as". But then how could these two vector spaces be more the same than those two vector spaces? After all they're the same, right?
- Evbn 14y agoIn C++, = is the operation that invokes the copy constructor. Is that equality? In C++ , == is equality, insofar as equality has meaning in a mutable language.
- Evbn 14y agoI would expect Knuth of all people to discard that broken notation. He has he smarts and chutzpah to do better. I always hard that notation.
- joshhart 14y agoI also scored 22/25. I also agree that I will not be able to replicate that score, except for maybe on the last test. I find it interesting that I generally got lower scores on questions I didn't even have to think about at all, because I didn't bother to put in sufficient amounts of justification to my answer. I'm not sure what I think about the test as a metric for software engineers OR of the results we'll get. Colin is a Putnam fellow - probably not the guy you want writing a math test :) For the results - first, people on HN aren't a representative sample. Second, people had the opportunity to look at the exam before deciding to take it. My hunch is that people who would not have done well may have decided it wasn't worth their time to hear about it. Not sure what we can make of this. Perhaps if Colin was disappointed, he's not as disappointed as he could have been. And also if he was disappointed, it may not actually matter. Regardless, if I built my own startup and were hiring, I do think I'd want people who have demonstrated that they're fast, dedicated, and could probably get above 50% of the marks on this exam.