The software development final exam: Algorithms and Data Structures

I used to think so too, and yet...

- My current team created a project that lets you run complicated, multi-dependency Java code in an non-blocking manner. Internally, the framework uses topological sorting of a graph of nodes, where each node is a method with potentially blocking code and the dependencies between the nodes are the edges of the graph. The framework is able to set up callbacks automatically in the right order given the above.

- iOS6 auto-layouts internally use constraint solving on a set of linear equations so that you can write code to set the layout of your UI elements in terms of equations (so that you can basically just say that your button should be at 40px left of center of its superview, and with a 100px padding from the bottom).

- I wrote code to improve the accuracy of models at my previous job by employing various machine learning algorithms (thanks Andrew Ng and Coursera).

These might be isolated examples, but my point is that some of the best code I have seen uses a lot of math and CS concepts (sometimes in clever ways).

Have you considered that it's teaching you a way to think outside of your normal range, so that you can comprehend and imagine more complex designs that are easier to build and maintain?

> we can see from the trival case f(n)=3^n that O(3^n) is not a subset O(2^n) since 3^n > 2^n for all n as n approaches infinity, or there is no k such that is exists an n0, such that all n > n0 implies 3^n For what it's worth, this isn't really acceptable as a proof. The first half of your argument would go through equally well for 3n and 2n in place of 3^n and 2^n even though O(2n) = O(3n). The second half is simply a re-statement of what it means to say that 3^n is not in O(2^n) and doesn't actually prove it. The pertinent fact is that there is no constant k such that k >= (3/2)^n for all sufficiently large n because (3/2)^n goes to infinity as n goes to infinity. Compare this to the situation with 2n and 3n where (3n/2n) = 3/2 is a constant and hence bounded. A less trivial example would be something like n^2 + n versus n^2 where the ratio 1 + 1/n isn't constant but is nevertheless bounded for n >= 1.

I have to agree that this question set sits in between "useful CS topics" and "domain knowledge." Although a lot of people are building off of software libraries that use some heavy-duty CS knowledge, they need only be aware of the first-order implications - that there are different types of trees and sorts, that hashes, lists, and trees can expose similar interfaces while having different properties, that algorithm running time can be described with big-O notation. The fine differences are easy enough to research, and a responsible library author will document the expected runtime characteristics of their code.

On the other hand, something I'd expect to see on the final exam - and is already clearly absent based on the outline - is compiler design. If most of the world is doing web development and doing a lot of "slopping around of data between formats", parsing becomes important. Type systems become important. Code generation _may_ be important. And here, again, they don't have to be in-depth questions about the differences between LALR and packrat parsers, or describing the eight sides of the lambda cube. Simply demonstrating awareness of doing something other than mashing out a bad regex for every parsing problem would be an advance over the status quo.

You're correct that most programmers don't have to write sort functions by hand but there are certainly a few issues.

Big O notation , or at least a Big O way of thinking is definitely useful when doing things like optimising queries and data structures etc.

For example I've solved performance issues in the past with DBs with poor indexing strategies (or no index at all). When I read the DB manual and it talks about different types of indexes and says "doing X will cause Y or doing Z will cause A". Knowing something about Big O notation and related things means that I can immediately intuitively understand what they key differences between Y and A would be.

Thinking about performance in terms of growth also helps me guess which parts of the application require the most optimisation. For example which parts have a roughly fixed n and which parts n will grow with time.

Abstractions leak, especially when you are dealing with parallel processing which will become increasingly important as time goes on. How you store and think about your data is going to have huge implications for just about everyone in software in the coming years when having to scale sort operations etc over hundreds of discreet CPU cores becomes the norm.

I think a degree in CS is not intended to teach you "what you will need to be a successful software developer today" but more "here are the tools to think about whatever the problems may be for software developers in 10 years time".

I agree that maybe there is going to be a gap between what is required for a CRUD implementer vs what is required for someone who designs DBMS systems for oracle and that employers want people qualified in the latter to perform the former.

OTOH I feel that this is something that the free market will correct over time and is already beginning to do so. I know a few programmers who are productively employed who are not well versed in CS theory but are still payed well because they can bring other skills to the table.