Or more realistically, taking a more layered approach to each course. So you could have the basic "code algorithm X to pass the tests" level (the kind of work most people will be doing later anyway), and then the "let's prove properties of X / come up with an alternative with the same properties" for people who can pass the first part in their sleep.

The best courses I've taken work like that already, plenty of extra challenges if you finish early. But it takes a dedicated instructor to make it work, and most of them unfortunately seem dedicated to getting by with minimum effort.

I ask because data structures usually comes in the 2nd or 3rd semester of a CS curriculum, and for most CS students, they can't apply the proofs and theory because it obscures where it applies in the problem domain. They can't draw the line between the theory and practical application, unless they already have written a good bit of code.

Maybe this doesn't apply to all CS students, but I would say the majority.

For instance, I recall my professor being wired up about some esoteric sorting algorithm, that had better asymptotic performance than qsort. Except, the constant factors involved in a real implementation made it slower for anything but stupidly big datasets. We spent like a week going over that one...