One volunteer was the "brain", one volunteer was the "eyes", and one volunteer was the "robot". Both the brain and the robot volunteers were blindfolded. A bright red box was hidden in the front of the lecture hall, and the task was to get the robot to pick it up.

The brain could only do two things: ask simple yes/no questions to the eyes (ie. is the ball straight ahead? is it less than 10 degrees to our left?), and command the robot to move with simple commands (i.e, turn left 10 degrees, move forward until I say stop, put arms out, move your arms together).

This was a whole lot of fun (even for tired college students), and the professor says that no group has ever successfully gotten the box ;) The lesson was that even with the most sophisticated visual sensors and robotic movement capabilities, the "brain" part of AI is really hard.

...

Another example for a hands-on activity is to build a sorting network. Have some students be gates and some students be inputs. The input students are each holding a number written on a card. The gate students decide whether the smaller input goes to their left or right. The students will be amazed that no matter how they go into the network, they seem to end up in sorted order at the end.

If you want to get more theoretical than just the basics of programming, ask them whether the sorting gate is correct for all possible inputs. How would you prove it?