I would add computability and complexity theory to that list. Some computational complexity should be covered in algorithms and data structures, but theory of computation is not really (as algorithms by definition solves only computable problems). A fundamental knowledge of what is and what isn't computable is quite important in theoretical computer science IMO.
I can't remember if formal languages and automata was an elective or a requirement for me... I think it might have been required. The textbook was the one by Sipser, and I thought it was a pretty good book.
