The most non-trivial things I have seen in CS

I see computers all around doing many computational jobs and hence finding application in many diverse fields. How then, can such "complex" computing machines be described completely by a very simple mathematical description, that of a Turing Machine? It is amazing how such a simple and abstract mathematical model can capture the entire computing capability that humans have been able to put into machines so far!
What is more surprising is that not just the Turing Machine, but even other seemingly independent models of computation - namely Godel's mu-recursive calculus, Lambda Calculus and others are found to be equivalent to the Turing Machine in terms of their computing power. It all suggests that probably there is something divine, beyond humans, that governs and controls what a man-made machine can do! In some sense, humans cannot push the limit on what man made machines can compute.

In Sohoni Sir's course which I recently took, we learnt about properties of solids and curves. There, we saw that the integration of curvatures taken at all points on a curve equals 2*pi*Turning_Number. The number of holes in a solid, called the genus of the solid was computed and turns out to be just E-F-V+2. The way in which these results were proved were very roundabout and complicated and the simplistic end result which comes out of the calculations is really amazing. It just goes to show that no matter howsoever hard and complicated our theory may become, when we finally apply it to practical bodies around us, we arrive at simple expressions. Maybe there are straightforward ways to explain everything around us, but just that we are not clever enough to spot them?

Other things such as Red Black Trees as a part of data structures course were also amazing examples of great ideas at work. The simple, elegant ideas involved in development of some data structures and algorithms which drastically improve the times taken to solve problems are wonderful to learn.

These are some of the things which have greatly enthused me over the last 4 years. I hope I keep seeing such wonderful things even in the future - wherever I am and whatever I am doing.