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:
graph algorithms (e.g. finding a minimum spanning tree or shortest paths)
linear algebra: solving linear systems, inverting matrices, LU decomposition, least squares approximation
linear programming: implement the simplex algorithm
string matching: implement string matching with finite automata and/or the Knuth-Morris-Pratt algorithm
computational geometry algorithms (finding intersections among a set of line segments, convex hull, closest set of points)
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 interface to the game.
Write a program that can solve Sudoku, Klotski, the 15-puzzle, Rush Hour, or another puzzle.
Implement a primitive computer algebra system that can simplify algebraic expressions and solve simple equations, perhaps even sets of equations.
Implement the RSA public-key encryption system.
Write a program that lets the user 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"?
Write a program that can parse a sentence in English or another natural language, generate a parse tree annotated with grammatical categories, and output it in a format that can be rendered by a graph layout program such as Graphviz.
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.