General info

Doing a project is optional, it is a way to improve your grade if you did not do well on the exams, or just want to get some extra credit.

All projects will be due by the end of the semester. You will have to:

1. make a short (5-8 minutes) presentation in the last class, showing your work.
2. Also, you will have to write a 5-6 page report, describing the problem, your solution, and the results obtained.

Before you start working on the topic, I have to approve it. The topic should be chosen before the end of Spring Recess, April 18.

Report you progress regularly (for example, once a week), so I can guide you, and you don’t waste time.

How to choose a topic

Read Rosen’s book, in the end of each chapter, there is a section Computer Projects, where you can find some ideas. Also, you can look in the chapters we have not talked about yet (Graphs, Sets, Probability, for example).

Find something that is interesting and seems to be related to the course.

If you can write code, choose a project that requires programming. We can always find a project that matches your current proficiency in programming.

Try to find something you are interested in, and we will find a way to add some math to make a project out of it.

New possible topics

1. A simple propositional satisfiability solver. (A program that checks whether the given compound proposition is satisfiable or not).
2. Programming fractals, L-systems, etc.
3. Another fractal drawing topic: Context-free art program.
4. Analysis of social network data. (You will need a specific topic / research goal here).
5. Solving logical puzzles with SMT solvers or Prolog.
6. Experimental analysis of the running time complexity of various standard algorithms.

I will add more topics, but, maybe you already know something interesting you would like to work on.

To boost your imagination, the topics from previous semesters:

1. Sudoku solver.
2. Wolfram cellular automata.
3. Maze generation with Prim’s algorithm.
4. Maze path finding algorithm.
5. Fractals visualization with OpenGL.
6. RSA enctryption/decryption.
7. Procedural music generation using ChucK.
8. Logical paradoxes (essay).
9. Automatic summarization of texts.
10. Stochastic simulation of the Predator-Prey (Lotka-Volterra) model.
11. Generation of permutations and combinations (described in Rosen, for example).
12. Experimental analysis and Big-O time complexity of sorting algorithms.
13. Map coloring game.
14. Connectivity of random graphs. Giant connected component.
15. Generating large prime numbers.
16. A probabilistic strategy for solving the game Minesweeper.
17. Random graphs. Experimental comparison of Erdos-Renyi and Barabasi–Albert random graph models.
18. 2048: The best strategy to play the game.
19. Dijkstra’s shortest path algorithm.
20. Breaking the Substitution cipher using frequency analysis.
21. De Bruijn Graphs and Genome Assembly.
22. Shortest path algorithms (A-star and Dijkstra’s).
23. Optimality of Change in Currency Systems.
24. Friendship paradox. Its verification using real social network data.
25. Finding the optimal strategy in 5 card draw poker.
26. Catalan numbers and Gambler’s ruin problem.
27. Finding Euler cyles in Eulerian graphs.
28. Implementing Huffman coding.
29. Graph coloring.
30. Dynamic programming.
31. Prime numbers generation.
32. Random word generation with Markov chains.
33. Bioinformatics: Sequence alignment algorithm.
34. Solving the Graceful Tree conjecture with SMT solvers.