When I took the theory of computation class at CMU in the mid-80s it was in the philosophy department. The professor knew almost nothing about actual computers. Which was pretty cool, honestly.

I am old enough to remember when it was 15-199, taught by Steven Rudich, titled "How to think like a computer scientist".

They had to run it for a few years before they realized CS kids who did poorly in the class dropped the major - the implicit signal being "you don't know how to think like a computer scientist".

It is indeed a weed-out class for the CS majors. It's fairly difficult the whole way through, and the difficulty jump afterwards for required classes is much more manageable. I never struggled with a required CS class after I managed to get an A in this one.

Theory is certainly a weed-out class. I think algorithms is certainly more difficult for a dedicated student tho.