[ben7799]

Types of automata and computability

Algorithm proofs around complexity, efficiency, etc..

At least an introduction to the design of languages, parsers, and grammars

Algorithms and concepts in the design of different database designs (not how to use specific databases)

Fundamentals of operating systems and systems programming

Some crossover with computer systems engineering courses. You must know at a basic level how logic gates are implemented, how an ALU is built, and how these blocks are built up to construct a CPU

These are the actual fundamentals of CS and they change at glacial pace compared to languages and design patterns.

[nluken]

I can't speak to your experiences with others from my alma mater but pretty much all of these things are covered in the core CS curriculum at NU (at least the pre-redesigned one). Systems, PL, Algorithms, Algorithmic proofs, automata, ALU design were all part of required courses, and that's before I include the elective CS courses I took.

One area where NU does fall down IMO is that they offer "combined majors" with CS and other subjects that eschew some of these courses to make room for the other half of the major, which will be an unrelated subject. This offering is a mistake because you do miss out on some key concepts. If you're working with a pure CS major, however, they were required to learn all these concepts.