Yes, I didn't take the Automata Theory course, but I learned essentially the same thing in Discrete Mathematics, Control Systems, and Digital Design (albeit with an eye towards Electrical Engineering applications). I remember looking through the courses, as you did, and the only gap I remember noticing was Operating Systems (and maybe graph theory, now that you mention it). It would have been nice to be introduced to machine learning while in school, but that's fine, I ended up learning it on my own.

There could easily be a bias error, but I said what I said simply because everything covered in the CS curriculum seems to also be present in the CE curriculum, but in the CE curriculum more is added. So I see the CE degree as a CS degree plus the essentials of an Electrical Engineering degree.

The advantages, if there are any, can definitely fade away after a few years of real experience, assuming everyone continues to better their knowledge, and those years aren't spent, as is typically the case, repeatedly re-implementing the same solution.