Any idea that is interesting and non-trivial is potentially possible, so you don't need to limit yourself to this list. Use your imagination. I'm happy to discuss possible ideas with you.
Implement one or more non-trivial algorithms, e.g. from the Introduction to Algorithms book. Some possibilities:
balanced binary trees (using AVL or red-black balancing)
graph algorithms: finding strongly connected components, finding minimum spanning trees, finding single-source or all-source shortest paths
linear algebra: solving linear systems, inverting matrices, LU decomposition, least squares approximation
number theory (primality testing, integer factorization)
computational geometry algorithms (finding intersections among a set of line segments, convex hull, closest set of points)
Implement arbitrary-precision floating point numbers.
Implement a computer player for a strategic board game. Some possibilities: chess, checkers, 3D tic tac toe, Pente, Quoridor, Gobblet. Here is a list of many more. Implement a text-based or even a graphical interface to the game.
Write a program that can solve Sudoku, Minesweeper, Klotski, the 15-puzzle, Rush Hour, or another puzzle.
Write a simple ray tracer that can render an image of a scene including several geometric objects.
Write a program that can read a sound file in MIDI format and generate an audio file that renders the musical notes using simple sound synthesis.
Implement a primitive computer algebra system that can simplify algebraic expressions and solve simple equations, perhaps even sets of equations.
Write a program that lets me make SQL-like queries on data in CSV files.
Write a program that answers simple natural-language queries about a filesystem or other fixed domain. For example, a filesystem query system might let me ask "which subdirectory of my home directory has the most files?" or "where is the file foo.txt"?
Implement a simple neural network that can learn to recognize handwritten digits.
Write a program that tests whether a formula of propositional logic is satisfiable using DPLL or a similar algorithm.
Write a program that can convert a non-deterministic finite automaton (NFA) to a deterministic finite automaton (DFA). Perhaps also implement a conversion from an arbitrary regular expression to a NFA.
Write a parser and interpreter for a simple programming language, e.g. a small subset of Pascal or Scheme.
Write a parser and interpreter for the untyped lambda calculus.
Write a simulator for a Turing machine, along with a compiler from some very simple language to the Turing machine.
General recursive functions, the lambda calculus and Turing machines all have the same computational power. Illustrate this by writing a translator between (at least) two of these formalisms.