I don't know how it's out there, but where I'm from, we don't get a lot of practical classes. The curriculum has tried to include practical alongside theory but its just not working. All we do is theory and more theory. Maybe include a major portion of marks for practicals rather than theory. And yes, please no coding in paper.

Another major thing we lack is teaching logical thinking. I have met final year under grads who find using a (!foo) to invert the value of foo mind blowing. They would rather use a full blown if-then statement to do the same. I think we need to incorporate chapters that motivates students into logical thinking to make better programmers.

Another essential part CS education around here lacks is in relevant examples and chances for internship. If you're studying something, I believe you would understand it much better if you see and experience it. Curriculum should include a real world project that you would use in a daily basis. Maybe break down and analyse a successful application and its component.