Any ideas about INTERESTING algorithm problems and examples for my students

Does anyone have any suggestions about problems I could give to my students as a class practice.

I'd like to give them something that's not boring, but will make them think algorithmically and originally. Maybe some real life problems?

I'd like to be able motivate ALL of them, n开发者_运维技巧ot just gifted ones. And I'd like to make them work together on solving the problems, so I'm avoiding sterile statistical problems.

I find backtracking algorithms to solve the 8 queens puzzle and Sudoku puzzles to be very interesting. When my TA ran code that solved a Sudoku and outputted the solution to the puzzle, there wasn't a person in the room who wasn't slightly inspired. Many of the examples of various statistical related algorithms are available at http://inst.eecs.berkeley.edu/~cs188/sp11/lectures.html

The main point of interest for many of the algorithms presented in this class have to do in the context of the Pacman game, using A* to help Pacman find his way through a maze or algorithms that bolster Hidden Markov Models to help Pacman avoid his enemies. This to me during undergraduate studies was a nice departure from the sterile problem sets that many course are notorious for.

Well ymmv as to whether this is interesting, but how about some meta programming? For example an exercise could be to define a syntax to define data types and objects of those types, and then write a program (in some implementation language) that can a/ write definitions of those types in some target languages (eg C and Python), and b/ write target language libraries to, say, print, parse, serialize and unserialize instances of those date types, and maybe c/ write a gui to edit instances of those data types.