The software development final exam: Algorithms and Data Structures

I have a CS degree from a respectable CS department. I got straight A's in my major and never crammed for a CS test. I am sure I could have answered these questions in 1997. Today, I can answer the first two questions. I think I can get partial credit on the third. I believe I knew the fourth once. I don't even remember what bipartite means [see edit below]. And that's with having implemented a topological sort within the last few years.

I would like to believe that if I came across a problem where knowing this material would help solve the problem, some part of my brain would activate and put me in the position of "Oh, I know I don't know this anymore" and I'd go look it up. Vs "not knowing what I don't know" and just bumbling along ignorantly.

I guess this is a long-winded way of saying I'm glad to have a CS degree and I think it puts me a leg up over software developers who haven't studied CS, but I'm still not sure how applicable these questions are to most developers.

Edit: On most exams I've taken, the fifth question would have been asked like this: A bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; i.e. U and V are each independent sets. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. Describe an algorithm that determines if a graph is bipartite.

There is a difference between knowing what a meal tastes like, and how to cook it.

What you are arguing for is knowledge of what meals taste like (e.g. two primary taste dimensions being space and time). I think this is really useful; so I agree with you.

But what Colin (and I mean OP) is asking for is knowledge of how to cook two specific meals, themselves rarely asked for.

I personally think CS education is mostly useless. Big-O notation and a survey of the field (a taste test of the meals, if you will) are all you really need bring along with you from discrete math, in my very humble opinion.

Cooking some of the meals while learning will teach you the general skill of following a recipe; a few more applied challenges will develop your improvisation skills. But the more applied it gets, the less CS it is.

The field is too broad, IMHO, for deeper knowledge of only a handful of things to be very useful. I know a lot about hash tables, for example, but that's because they were very useful in my job, and critical for performance. It would be a waste of time for me to know as much as I know about them now, coming out of college, never mind 10+ years later. I wouldn't come down like a ton of bricks on a recent graduate for not being able to name 3 different collision resolution approaches off the top of his head, never mind someone 10+ years out; even for a job that required their use and impromptu implementation, as mine did.

This is a very good book: http://www.amazon.com/Introduction-Algorithms-Third-Edition-...

I will say though, it's really intense on theory, and it requires a good background in math. A lot of people will recommend this book though. Also, it's physically heavy :)

I agree, non-algorithmic work is the vast majority of programming work today because most of it is related to Application Programming.

The reason for this is that most Application Programming emphasizes the use and sufficient knowledge of a framework, rather than a full understanding of CS fundamentals.

While those with CS have a head start in understanding frameworks quickly and utilizing them effectively, self-taught programmers can catch up rather quickly if the framework is well written and geared towards them. And fast majority of frameworks trend towards this.

Application programmers generally need to know the ins and outs of a framework and this knowledge often carries them further than the fundamentals.

All that being said, after 10 years of application programming, I'm slowly trying to re-learn much of my CS material out of my own personal interest and get off the framework treadmill. It's been a fun process to rediscover fundamentals after learning them over 10 years ago.

But let's be realistic about it, most app programmers have no interest in CS fundamentals or theory unless it has some direct context to their daily work.

Why do people who like to ask O(N) questions have this obsession with sorting algorithms?