The software development final exam: Mathematics

http://www.daemonology.net/blog/2012-10-10-software-development-final-exam-part-3.html

by cperciva • 14 years ago

35 61 14 years ago

cperciva6• 14 years ago

Apologies to people still waiting for me to grade their part 1 and part 2 answers -- it's a slower process than I hoped for; and I have a big stack (1065 pages, in fact) of scholarship applications which I need to review tonight, so I won't get any more marking done until tomorrow.

_pius3• 14 years ago

Meh.

These questions are indeed trivial, but obviously biased towards security — your area of expertise. What makes these questions anywhere close to a compelling measure of a developer's mathematical knowledge? Seems pretty presumptuous to me.

cperciva6• 14 years ago

These questions are indeed trivial

Software development doesn't need a huge amount of mathematics -- but some basic calculus, probability, and statistics, are pretty essential. I debated whether to include the cryptography questions in this section, but I wanted to include them somewhere and this was the most natural arrangement. (I started out by writing about 25 questions, then threw 5 of them out to get a more balanced set, then tried to figure out how to organize them.)

_pius3• 14 years ago

I debated whether to include the cryptography questions in this section, but I wanted to include them somewhere and this was the most natural arrangement.

Fair enough, but you made some pretty bold statements about what this exam is supposed to measure and I don't think this lives up to it.

For instance, I happened to have taken an intro security course taught by Ron Rivest; thus, I know the difference between a MAC and a hash function. But I wouldn't claim that another developer who didn't have exposure to the material was deficient in basic knowledge, anymore than I would make that claim about a security researcher who didn't know the basics of how a support vector machine works. These things are pretty specialized, even if they're not particularly difficult to learn.

Silhouette2• 14 years ago

Software development doesn't need a huge amount of mathematics -- but some basic calculus, probability, and statistics, are pretty essential.

Sorry, but that's just nonsense. The vast majority of professional software developers could go through an entire career quite happily without any of the above, and no-one would suffer for it.

Moreover, those who do programming work in mathematical or security-related domains probably need a much deeper understanding than the kinds of basic information you're testing for here.

mstepniowski• 14 years ago

Dont't know whether it's good or bad but these questions closely resemble the ones I've been asked during my final exam (Faculty of Mathemathics, Informatics and Mechanics at University of Warsaw).

Of course there were a few nontrivial questions too, like the one abou fixed point theorems.

alexkus4• 14 years ago

Sent my answers in, reminds me how much I've actively avoided stats (I much prefer pure Maths).

delinka3• 14 years ago

What I'm not getting about these is the "don't cheat" bit. First, let's be clear: he's decided the 'rules' for this exam include not researching online or getting other assistance and just answering from memory. "Cheating" is "breaking the rules."

I work in the Real World, where I don't write academic data structures every day, so I don't have this stuff memorized (there's a joke in there that start "I've forgotten more than...") I use APIs to get work done. When I need to be more academic, I search online. The only place anyone's ever required to be so 'academic' about algorithms, data structures, math, etc is in academia. Step out into a job and you have an internet of active developers and useful forums are your disposal. Even if a company hired me to write an 'academic' code library, I'd do the research, write the implementation, and (after sufficient testing, profiling, etc) forget about it.

cperciva6• 14 years ago

What I'm not getting about these is the "don't cheat" bit

If I said "go ahead and use google, wikipedia, textbooks, and talk to your friends", I would have needed to make the questions harder and lengthier to compensate. I thought asking people to spend 15 minutes telling me what they know would be more feasible than asking people to spent 15 hours showing me what they can find out.

delinka3• 14 years ago

I understand. To gather data, you need manageable data. What will this data show you? What are you hoping to learn from this experiment? Perhaps I'm being a little cynical, but it seems to me that this information will tell you little about the craft outside of academia.

P.S. I've refrained from answering the exam precisely because I'd have to refresh my memory from online resources.

scott_s• 14 years ago

Which is reasonable, since it's your time. But consider that I have three degrees in CS (BS, MS and PhD). I am employed doing CS research, primarily in systems and high performance computing. And for at least one question on each subject, I would not feel comfortable answering unless I referred to some reference. (Yes, even the architecture and systems questions, despite that being my "expertise": I can recall very little about coherence algorithms.)

The primary value of a formal education is, I think, not that you know a lot of stuff. Rather, it's knowing what you don't know. Knowing just enough to recognize "Oh, this is related to that other thing, I should go and read about that." I'm constantly doing that, as are the people I work with.

tzs2• 14 years ago

If you have to go to the net for basic things, you are going to be less productive than someone who is able to understand and use those things from memory, because of (1) the time it takes to find the information online, and (2) the interruption in flow.

The majority of his problems were things that I'd say are in the "should be in memory" category for those who work in the general area that the particular question covers.

jules• 14 years ago

More importantly, you don't know what you don't know. If you don't have something in memory, even though that knowledge is readily available on the web, you probably won't notice an opportunity to apply that knowledge. That said, while I can answer these questions, they are pretty specialized knowledge. It's is a common phenomenon to think that the specialized area you work in is a big part of the world because you spend so much time in it. People should not feel bad about not knowing the answers to these questions. A web developer doesn't need to know any of these things, and he would be able to come up with web development questions that would be equally hard to answer if don't happen to be in that area (e.g. In which browsers is css-property-foo supported? or: what is faster, setting innerHTML or inserting a new elment into the DOM?). Even within the area of computer science, the author is asking specialized questions about hardware, security and algorithms. If it was about machine learning, type systems, and parsing you'd have a completely different set of questions. Or it could have been about computer graphics, compiler optimization, human computer interaction, and programming languages.

delinka3• 14 years ago

"Why should a message be "padded" (and not just with zeroes) before being encrypted or signed using RSA?" I just happen to know this one. I know effective developers that don't. This is not 'basic' information.

"What is the expected run-time of quicksort? What is the worst-case run-time?" Who cares? Call the sort method on your array class, call a sort function. Done. I don't need to know this for everyday things.

"Name and describe the four states in MESI cache coherence." This is 'basic' knowledge? Maybe if I wrote a kernel in school, and if I did, I certainly don't remember the details of dealing with cache coherence 25 years later. I'm not a kernel developer now. Nor are a Very Large Percentage of developers in the real world.

"Which of the following two functions is faster, and why? Assume that the C code is translated into machine code in the obvious manner, without optimization." Again, I just happen to know this one. But the "without optimization" almost makes the exercise silly. As your employer, I'd want to know you have the analytical skills to find the bottleneck in the code or to discover the compiler bug whose optimization is causing problems.

"Explain the difference between a mutex and a read-write lock." Sorry, I'm using a higher-level construct. GCD from Apple, go routines in go ... do I 'fail' this question because I don't have to remember this from 15 years back?

alexkus4• 14 years ago

The more you "know" the less you have to go look for, and when you do have to go look for stuff on the Internet (since you're not omniscient) then you'll understand more of the pages you get back as results, and understand them faster since there's less groundwork you need to cover.

An understanding big-O notation is very important if you go searching for sorting algorithms and land on a page that has an overview of sorting functions but listing bogosort as O(n!) and insertion sort as O(n^2), both relatively easy to implement, and this relatively complicated iterative[1] quick sort that's listed as O(n log n). Without other clues someone might just implement the one that looks easiest, and it works fine on their test set of 20 elements, but blows up in the future as their application/site grows and slows to a crawl sorting through millions of rows with an insertion sort.

Or, one of the most recent questions in the Mathematics part of the exam made me snigger because someone I work with was asking what bignum library was easiest to use. Rather than just answering their question (I prefer GMP myself) I asked why; they wanted to do the equivalent of log( x^300 ) and so they needed to compute x^300 first and then take the log of it; floating-point was giving slightly inaccurate answers to what was expected when they took the log of the intermediate result. It was even worse when they tried to do log( x^9125 ) - or whatever exponent is used for daily interest on a 25 year mortgage to account for leap days.

To put it another way. Without the knowledge you end up googling, and implementing, the wrong thing. You may get the right answer/outcome in the end but it may be horribly inefficient. Or, worse, an inaccurate answer/outcome; and you may not even know.

Hammering the insertion sort analogy home; you can profile and optimise an insertion sort all you like, it's still never going to approach the speed of quicksort on mid-large datasets. Huge datasets are another matter, someone stuck with "quicksort is the best" is going to struggle when faced with hundreds of millions of rows and there are things less pessimal than quicksort.

Knowledge of processor architectures, caching and how hash tables are implemented means you know not to use a hash when a simple array will suffice; but I've seen this done plenty of times.

Etc, etc, etc.

Out of the 15 questions so far there's only been two or three that the knowledge of wouldn't have helped me at some point in my development over the last 15 years. Of those that haven't applied to me I can see why they would be important to other fields and other people.

It's one of the major reasons I decided to do a full Maths degree (part-time via correspondence) to complement the Comp Sci degree I got ~15 years ago. It's not just the obvious useful stuff like calculus, group and set theory, graphs and networks, etc. Whilst I thought that the mechanics part of the Maths degree wouldn't be very useful in my job I was surprised at how useful and ubiquitous [non-]homogenous second-order linear differential equations are in modeling things that are relevant to my job (populations -> user base, hysteresis, etc).

No doubt others find huge amounts of other knowledge in other subjects that is directly applicable to IT; psychology, education, design to name but a few.

The right choice of algorithm, and implementation, in a critical part of your code could mean the difference between having 64GB of memory per server or getting by with 16GB. It could mean 100 servers to manage your 1M users, or 10 servers; the difference between 100 servers and 10 servers to manage your 1M users could mean the difference between making a profit and making a loss. These could be the differences between your idea succeeding or disappearing.

1. Another one of my common things I do at work is replacing quicksort implemented using recursion with an iterative version so that the stack doesn't keep getting blown on large datasets. I like it when people encounter this problem and find out that stacks are finitely sized and not as big as they'd hoped they would be. "But that means..." is a great thing to hear.

irahul7• 14 years ago

> Another one of my common things I do at work is replacing quicksort implemented using recursion with an iterative version so that the stack doesn't keep getting blown on large datasets.

What language do you use which doesn't already have an optimized version of quicksort or equivalent?

nadam3• 14 years ago

I am not an expert of this, but:

1. I think the stack usage of Quicksort is O(log(n)). Which means it is impossible to blow up the stack unless your dataset is bigger than the number of atoms in the universe (but in that case how are you keeping it in memory?)

2. For example in Java when you call Arrays.sort() this is called:

http://cr.openjdk.java.net/~alanb/6905046/webrev/src/share/c...

(It apparently uses recursion)

I know quicksort, but not on this level: these guys researched lots of different quicksort implementations and optmized the hell out of it. This implmenetation is way longer to begin with than my naive quicksort implementation would be and is called 'dual pivot quicksort', which I did not hear about until now, despite I know how the traditional quicksort works.

chuppo• 14 years ago

I do not see how a web developer or DBA will feel better about themselves and more confident in what they do if they knew the answer to these questions. It isnt even related to the work a Java EE architect does.

cperciva6• 14 years ago

Since you say web developer... don't you think it's useful for web developers to have some idea how much traffic is needed for A/B testing to produce meaningful results?

mattdeboard• 14 years ago

Hear hear. I think you've done a good job crafting some questions that debunk this hokum.

Also,if you don't think it's applicable to your life, ok. But when you gripe about the questions or take umbrage with the notion that maybe, just maybe, you've forgotten (or never learned) some information that might have some practical application in the real world, you just sound defensive.

I mean, in the first thread there was a guy who was proud of not knowing what big O notation was. C'mon.

pgsandstrom• 14 years ago

Once you decide to do A/B-testing you only need to know enough about probability to know that it is very hard to guess the amount of traffic needed. That's when you google to remind yourself how to do the actual calculations.

kamaal2• 14 years ago

I have immense respect for Dr Collin Percival, and his work. But isn't this getting overboard?

Seriously, calculus? I understand Collin is a computer scientist who is also programmer by co incidence. But this is almost like 'I know it, so you must too'. Most developers are likely to never ever deal with these things at all.

Programming today is so much productivity, discovery and building things. If you face these thing along the way, very well learn them. But to spend the next two years of your life learning calculus which you are likely to never use ever in your career and then only to find you are likely to forget it 2 years down the lane anyway, is a wrong way to be spending your time.

As a programmer what excites me most is a new challenge I've never faced before, And the journey of hard work, discovery, failure and success that follow from such a attempt. I don't mind failing while doing something even if I don't know much about it. I'm likely to learn them by discovering and reading new things, than spending straight 1 years learning all from a book without knowing where they will be ever used up.

The only thing that excites me besides money is the joy of discovering new things, and realizing that I might have solved a real world problem that might be helping someone. Trivia stuff doesn't excite me anymore, I don't see what and how have I changed things around me by merely just knowing more.

Life is really short, I know I have little time to make all the money I want so that I can see the other parts of life. I know coding and math are exciting, but they are among the many things that are exciting in life. Think of it this way, you might have a favorite Ice cream flavor, but unless you taste other flavors how would you ever know if others are better? Or after trying the other flavors you might just discover you have a new favorite flavor!

irahul7• 14 years ago

> But isn't this getting overboard?

Naive bayes, with a relevant dataset, does a very fine job of data classification(sentiment analysis, spam detection...). Also, almost everyone who isn't a liberal arts major would have come across Bayes theorem in high school or college.

The question about A/B testing is solving simple linear equations. I believe anyone in 10th grade or above should be able to solve it.

Hashing and MAC are pretty much application level security - they don't require intrinsic knowledge of how; what and why is something an application developer should know.

That leaves us with that harmonic progression thingy and padding. Padding, I think, is to avoid cryptanalysis(extrapolating from what you know is a part of knowing things:)).

Overall, I won't say he is going overboard with his questions. If anything, to anyone familiar with the topics, his questions are pretty trivial. The only thing under contention is if the topics he considers relevant are actually relevant.

mattmanser• 14 years ago

But what have they got to do with software development.

Zero. Zilch. Nothing. Absolutely sod all.

From the OP's original post, after seeing the questions over the days, his claim:

If you can't answer the majority of the questions on these four papers, and you're working or intend to work as a software developer, you should ask yourself why — most likely you're either you're missing something you really should know, or you're lucky enough to be working within a narrow area where your deficit doesn't matter

So far almost none of the questions on any of the days have been the slightest bit 'important' in software development.

barrkel2• 14 years ago

Don't worry about it. After I saw the first set of questions, I knew I could dismiss them as irrelevant. It's not worth continuing to get in a knot over.

dubya• 14 years ago

> Seriously, calculus?

I think that not knowing calculus would prevent you from working in a lot of interesting areas where there is an optimization component. Coursera's Machine Learning class is actually a little frustrating because the teacher assumes you don't know calculus, so a good chunk of the course is describing very intricate black boxes that reduce to "take the gradient of the error function".

The other big issue with stopping with the math you think you will need is that typically it doesn't completely click until a course or two beyond it. So if you take calculus, you may retain only the vaguest outline, but your algebra skills will be solid. That way when you're lucky enough to find a job requiring calculus you'll just need to review calculus, and not algebra, trig, and calculus.

lignuist• 14 years ago

In my opinion math helps to develop the brain to be better at rational thinking. Even if the methods are not needed directly.

jheriko• 14 years ago

I see very few questions relevant to being able to ship software... interesting for precisely that reason though.

raverbashing• 14 years ago

Well

Some think crypto is essential. Some think it's merely a tool and even though having guidance in using these tools is important, no need to go to a lot of details.

I could point out a lot of mathematics that are important as well and 99% of devs there are oblivious to it.

- Newton-Raphson method

- Gaussian elimination

- Simplex method

- Z transform

- Bezier curves

- Linear algebra in general

- Galois fields

nitrogen3• 14 years ago

I'm surprised by how many comments on cpercival's exam series boil down to "I'll never use this!" Especially since this is Hacker News, almost ground zero for intellectual self improvement. I can't claim to remember (or have even learned, in some cases) much of this stuff, but decisions made without any knowledge of e.g. calculus, probability, etc. will be very sub-optimal.

jasim• 14 years ago

I'd love to know a few of those decisions that you've to take on a day-to-day basis (even once every month) as a software developer, which needs calculus and probability.

irahul7• 14 years ago

> I'd love to know a few of those decisions that you've to take on a day-to-day basis (even once every month) as a software developer, which needs calculus and probability.

Machine learning needs an understanding of basic statistics and probability.

dccoolgai• 14 years ago

I struggled mightily with calulus reuirements when I was getting my CS. I've never really used "pure" calculus more than a handful of times. I'm still glad I took it, though, because the process of learning how to solve complex probelms has been, I believe, very valuable.

nitrogen3• 14 years ago

Since much of my work involves audio and video, practically everything I do can be thought of in mathematical terms. I'm not explicitly writing a function that says "integrate this" or "differentiate that" (except for the Accumulator and Differentiator plugins in my automation logic system[0]). I do write things, both for fun and profit, that have patterns similar to integration and differentiation.

Related to what I said in another comment[1], there's rarely a binary influence from my (admittedly very limited) mathematical and theoretical background, where a decision would go one way with it and another without. Rather, my understanding of calculus and probability shapes the way I think about and approach problems.

For example, when I see a problem that looks like one of gathering data and accumulating a result, I can recognize that it looks similar to a numeric integral, and apply what I know about integration to solving the problem. Integrals and derivatives are also constantly in my mind when I think about the physics of the world around me.

Probability, especially Bayesian reasoning, also influence the way I perceive and approach problems, both in software and in reality. Consciously thinking about prior expectation combined with prior confidence, even if I'm not thinking in numeric terms, helps me to understand how my mind works, know how to communicate new, unintuitive ideas to others, and form more concrete thoughts about my environment.

In summary, a very rudimentary understanding of calculus and probability theory are necessary to understand and reason about (i.e. predict) the physical world. Moreover, I have a general desire to learn all that I can and integrate it into a web of concepts, which I reason about as a combination of directed and undirected graphs, where concepts are vertices, relations between concepts are undirected edges, and influencing concepts and prerequisite knowledge are directed edges.

[0] http://www.nitrogenlogic.com/docs/palace/ [1] https://news.ycombinator.com/item?id=4630006

jaimzob2• 14 years ago

:) This is surely just degenerating into parody now. I can't wait for part 4: "Build a Turing Machine from scratch using paper-clips and sticky tape and send it to me for grading. Remember to show your working and no looking it up on Google."

irahul7• 14 years ago

Most of the questions are pretty trivial and relevant(may be not to you but that doesn't make it irrelevant or a parody).

http://news.ycombinator.com/item?id=4635946

orangethirty2• 14 years ago

It is irrelevant because the real world is composed of CRUD apps in [Java, C#, PHP], and you don't need to know most of the subjects the OP talks in his "tests." It is a parody, because the OP seems to not have worked a common software position, where most time is spent building new UIs for marketing or management, making complex and awkward joins, and making sure changes don't break the spaghetti. It all sounds like academia talk, which is fine (and valuable), but not a real sign of real world programming.

I will say that the tests have been fun to complete, and have helped me fill in the gaps here and there. But as someone who is hiring programmers at this very moment, I would not hire someone with such an approach to programming. This person would (I assume from experience) write complex code all day to show off his/her knowledge of advanced CS topics. Then not document it because the code is just obvious to read. And finally quit after a month because the job is not up to his/her standards or challenging. They would then write a blog post ranting about how programming has turned into a circus or produce a series of "tests" to show off their superior knowledge.

pja2• 14 years ago

This fun. I'd forgotten how much of this stuff I used to know.

(ps, for Q3: if you know the formula for the Harmonic series then you can answer this one very easily. If you don't, you're probably going to be a bit stuck.)

tptacek2• 14 years ago

Weirdly, I do better on these questions than I did on "Operating Systems", despite having ~15 years of systems programming (including some kernel work) and having barely high school math.

I have never needed to know the specifics of MESI cache coherence (I've benefited from knowing about cache coherence, but not in fine detail), and the problems I've worked on professionally have lent themselves better to commit protocols than to pthreads synchronization.

On the other hand, I do a lot of crypto pentesting, so hashes versus MACs, RSA padding, and basic stat are straightforward.

I don't have Colin's academic background but if I was him I'd be disquieted by the fact that someone like me comes out OK on his math and less well on his arch/OS stuff.

cperciva6• 14 years ago

I'm not particularly surprised. The mathematics here is generally pretty basic material which other things build on top of -- and as you say, your crypto background helps with those questions.

I don't remember seeing any emails from you... did you submit your answers?

tptacek2• 14 years ago

Of course not. :)

The software development final exam: Mathematics

Related Stories