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.
In addition to the ideas below, you might want to look at the extensive list of project ideas from Martin Mareš, who also teaches at our faculty. His list is in Czech, but here is an automatic translation of it into English which is quite readable.
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
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 the 15-puzzle, Klotski, 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.