List of Semester Projects for CS 222: Theory of Computation

  1. The P=?NP Problem.
  2. Make a formally verified toy compiler
  3. Make a visual Turing machine.
  4. The Church-Turing thesis
  5. Infinite search in finite time.
  6. Randomized computation.
  7. Cryptography.
  8. Complexity studies on Natural Languge Processing.
  9. Basic computational learning theory.
  10. Advanced complexity theory: P vs. NP.
  11. Advanced complexity theory:PSPACE.
  12. Advanced complexity theory:NSPACE, L, and NL.
  13. Approximation algorithms.
  14. Greedy algorithms.
  15. The Mathematics of Social Networks
  16. Finite automata for speech recognition
  17. Modeling human languages using context-free languages and grammars
  18. Enumeration of finite automata
  19. Enumeration of PDA
  20. Enumeration of Turing machines
  21. Ambiguous grammars
  22. Disambiguation of Grammars
  23. Enumeration of Context-free langauges
  24. Enumration of Turing machines
  25. Universal Turing machines.
  26. Design of lexical analyser
  27. Theory and aplications of LBA
  28. Randomized Turing machines
  29. Fuzzy Turing machines
  30. PSPACE Algorihms
  31. NP Compleyte Algorithms
  32. Probablem solvability using Reduction
  33. Design of TM to emulate a finite automata
  34. Design of TM to emulate a PDA
  35. Complexity analysis of encryption algorithms using TM
  36. Design of TM to perform sorting
  37. Design TM to perform searching.
  38. Develop a tool to draw a transition diagram for any given DFA.
  39. Develop a tool to illustrate the algorithm for converting an arbitrary NFA to a DFA .
  40. Constrcut graphical representation of TM to solve simple problems.
  41. Simulate a very elementry micro-processor using TM
  42. Simulate sophsisticated elevator using TM
  43. Simulate harddisk reading writing mechanism using TM
  44. Simulate a cipher system using TM
  45. Simulate a TM using a TM
  46. Simulate a four function calculater using TM
  47. Simulate the Caeser Cipher using TM
  48. Simulate Tic-tac-toe using TM
  49. Simulate parallel processing using TM
  50. Simulate parity checking using TM
  51. Simulate CRC check algorithm using TM
  52. Simulate a clock using TM for hh:mm:ss