That sounds exactly like the sort of degree I mean. It's not all that common though, in my experience, to find a CS degree with that sort of curriculum.
Do you just cross me off the list because I have a CS degree.
That's silly :) You may have noted from my post that I do hire CS majors.
but do they understand the inner workings of a computer? Do they understand complexity, even the basic data structures.
Yes, usually a lot better than most CS graduates. Because generally speaking in the real world these are engineering problems rather than pure problems.
This is just my observation, but I don't think I am wrong - CS majors are generally worse programmers (and usually more full of themselves, but that's another matter) than CS engineers.
I would consider you (based on your post) an engineer; as you explain, you were part of the engineering dept.
(that's not to say CS majors are all bad - I've met some extremely good ones. The problem is that the majority of CS is taught as a pure subject with a smattering of applied theory. There is a distinct lack of problem solving involved. Traditional disclaimer: YMMV)
Also I should point out that being an engineer does not automatically make you a great programmer. Clearly you need an interest, an amount of aptitude and the ability/willingness to learn the pure subjects (if they were not part of your degree). The last of those isn't all that important - to be a good programmer you only need the amount of pure theory that is required (and you learn to pick it up as you go) - this is a common trait of all engineering.