I once heard it said:
In our data structures course we read Knuth and ignore the proofs
In our algorithms course we read Knuth and ignore the code.
And indeed, there are many topics where the theory-part is in one course and the programming is in another.
With that in mind, here is a different way to offer courses (some depts already do some of this).
1) A course in Algorithms AND Data Structures. Actually I have seen this title on courses but its usually just a theory course. I mean you REALLY PROOF and CODE. Might need to be a year long.
2) Crypto AND Security. You learn crypto and security together and do both. If you only did the crypto relevant to security it might be a semester long and in fact it might already be being done. But I am thinking of really combining these courses--- code and prove. Might be a year long.
3) Formal lang Theory and Practice of Compilers. You do DFA, NDFA, CFG, but also do compiler design. If you also want to do P, NP, and decidability (spell check thinks that decidability is not a word!) then might not quite connect up with compilers, then again in might with theorems like: CFG equivalence is undecidable. Might be a year long.
4) Machine learning AND Prob/stat.
PROS: Theory and Practice would be more united.
CONS: Having year-long courses is hard for the students scheduling their courses. Would having just one semester of any of the above courses make sense?
CONS: Harder to find someone to teach these courses. I'll confess that I prefer to teach formal lang theory without any programming in it.
CAVEAT: I think theorists coming out now know more of the practical counterpart of their area than I did and perhaps than people of my generation did.
CAVEAT: A much less radical thing to do is to put more security in to crypto, more about compilers into Formal Lang Theory, etc. But thats a bit odd now since we DO have a course in security, and a course in compilers. Even so, seems to be a good idea and this I know many schools are doing.