But the question is one and the same in this instance: they're asking what should be taught in "the" math class for a CS degree. If that doesn't contain the math that all CS-people need to know, then what should it contain?

The OP describes universal algebra and term rewriting, which is what I claim is the logicish type that is not as crucial as, say, linear algebra if you want to find widely applicable mathematics for CS/programming.