- Understand time & space complexity
    - Security & Encryption
    - Concurrency & why ACID transactions are hard

I've actually worked at a company that wasted millions on a fruitless project because management didn't understand basic automata theory:

    - Finite State Machines / Regular Expressions
    - Stack Machines / Context Free Grammars
    - Turing Machines / Anything Computable

EDIT: Another good thing to study, though I'm not sure if there's a good single source: Why distributed systems are Hard and why distributed transactions are Really Hard. I really didn't care for the teaching style of the professor who staked out that whole area as "turf" so none of my materials were particularly memorable or good, but the information was valuable.

     management didn't understand basic automata theory

IMHO management isn't required to understand much about CS, as long as the relationship with the developers is as between a customer and an engineer (i.e. customer asks for stuff, engineer explains what he can and cannot do).

Most problems with management comes from a disconnect with reality. Even when they know CS theory and/or could understand the complexity involved (ex developers); having bikeshed-style opinions and making demands with an iron fist in spite of developers advising otherwise (or the reverse, having developers on the team without an engineering mindset that can't think for themselves) ... that's the real poison.

    management didn't understand basic automata theory

That company tried to translate code from one programming language to another using only regular expressions. (This was a long time ago when you couldn't almost count on most "regular expression" implementations being Turing Complete.)

Perhaps the problem was really that engineers who understood the futility of the approach didn't speak up or weren't listened to. Still, I'd expect people managing an engineering firm that builds bridges to have some basic grasp of physics. So I don't think it's going too far to have those running a software company to have some basic grasp of the basic laws governing their field.

It might work like this: some programmer working on the project realizes something can't be parsed in a finite state machine, and 'cleverly' separates out one batch of regular expressions into a loop/recursive call. Repeat until the programmers are satisfied with the number of conditions they can handle. I've seen software that was actually written like this. Fortunately, the language it was designed to parse was pretty simple.

It might work like this: some programmer working on the project realizes something can't be parsed in a finite state machine, and 'cleverly' separates out one batch of regular expressions into a loop/recursive call

In this case, you've created an "Augmented Transition Network" which is equivalent in power to a stack machine or a Context Free Grammar. Is this really playing devil's advocate? That would imply setting up something that isn't a straw man whose solution isn't basic automata theory.

This also gives you an idea of how broken the project was, since my understanding is that they'd fix "that particular bug" and keep writing more regular expressions.

You can create a submachine representing the regular expression transition conditions, and just attach that at the state you wanted, resulting in a finite state machine.

Of course this doesn't hold when you are talking about non-standard regular expressions, and it's probably a nice feature to have when creating the automata, but IMHO it still sounds like a silly idea when CFG-tools like ANTLR and YACC are available.

      Wouldn't that still be a finite state automata?

I also hate working with ANTLR/YACC ... heavy, hard to start with, steep learning curve. These tools are designed for industrial-strength compilers, where performance / flexibility matters.

And PEGs are better than CFGs (that's teeshirt material right there :))

The key is the bit about the "recursive call."

If you've got an algorithm that does that, then it cannot be called "iterative".

I.e. backtracking is recursive, no matter how you implement it.

In school textbooks they do differentiate between "recursive" and "iterative" backtracking, to teach you how to get rid of the call-stack and manage your own. But that's another story.

Ha! I know a guy who essentially got a US patent for roughly the same idea. His non technical bosses were so impressed that they gave him a raise and made him "Director of Analytics" at what was (or rather should have been) an Analytics heavy company.

It wasn't just the management to be blamed: it the case of building bridges, engineers / architects can even go to prison if a bridge collapses.

That will be really helpful. Thanks.

Algorithms: Introduction to Algorithms (Cormen, Leiserson, & Rivest) http://amzn.com/0262033844

Security: Applied Cryptography (Schneier) http://amzn.com/0471117099

I cannot find my automata book just now. It's down in the garage, and I want to stay inside where it is warm now. As for concurrency, I got part of that from the Tannenbaum OS book:

http://amzn.com/0131429388

But the rest, I actually got from a coworker on the job! We did cover databases and ACID transactions in school, but that wasn't taught very well and I didn't really get it until I was doing real work.

Do some assembly language. It will give you a key advantage over everyone who is too scared to touch it.

Write a compiler and/or interpreter. This can actually be pretty small, and it will also give you an advantage over those too scared of something so seemingly "esoteric."

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

Thomas recommends Practical Cryptography instead.

"Practical" will be my next technical read.

That would be about right.

I remember that because all my IRC friends immediately got to work on crazy crypto tools with algorithms and ideas cadged from that book. It definitely didn't teach them that crypto was hard.

It's one thing to do some fun project. It's another thing to do something for production. It's yet another thing to read such a book and realize it means there's people who know a lot more about this than you. At the same time, it is a fun read for a techie.

Also, if you have time and passion, write a compiler.

Requiring a degree is popular as it is an easy to implement filter rather than any correlation with ability. (Note that question of whether a CS degree is relevant or not is an other question entirely - I'm a CS graduate and I think the maths & theory heavy course I did is irrelevant to 98% of development jobs even if it has been pretty useful for me).

There are a few tidbits from your education that will save you from serious egg on your face. (See my other post this thread.) This is not just theoretical. I've seen a company suffer major embarrassment because software sold to Fortune 500 companies was written by programmers who thought, "all that poppycock about race conditions/transactions is just academic hot air."

IMHO Computer Science courses deliver value through proving a knowledge of abstractions of software and hardware systems. These formal abstractions remain applicable pretty much forever whereas knowledge of particular technologies are of passing value.

[NB My hardwired knowledge of vi commands, Unix system calls and C was merely pleasant side effects of my CS degree not an end in itself]

The real thing I feel that I miss is not being able to recognise where known algorithms/data structures could help out, something I'm working on fixing.