List of Semester Projects for CS 222: Theory of Computation
-
The P=?NP Problem.
-
Make a formally verified toy compiler
-
Make a visual Turing machine.
-
The Church-Turing thesis
-
Infinite search in finite time.
-
Randomized computation.
-
Cryptography.
-
Complexity studies on Natural Languge Processing.
-
Basic computational learning theory.
-
Advanced complexity theory: P vs. NP.
-
Advanced complexity theory:PSPACE.
-
Advanced complexity theory:NSPACE, L, and NL.
-
Approximation algorithms.
-
Greedy algorithms.
-
The Mathematics of Social Networks
-
Finite automata for speech recognition
-
Modeling human languages using context-free languages and grammars
-
Enumeration of finite automata
-
Enumeration of PDA
-
Enumeration of Turing machines
-
Ambiguous grammars
-
Disambiguation of Grammars
-
Enumeration of Context-free langauges
-
Enumration of Turing machines
-
Universal Turing machines.
-
Design of lexical analyser
-
Theory and aplications of LBA
-
Randomized Turing machines
-
Fuzzy Turing machines
-
PSPACE Algorihms
-
NP Compleyte Algorithms
-
Probablem solvability using Reduction
-
Design of TM to emulate a finite automata
-
Design of TM to emulate a PDA
-
Complexity analysis of encryption algorithms using TM
-
Design of TM to perform sorting
-
Design TM to perform searching.
-
Develop a tool to draw a transition diagram for any given DFA.
-
Develop a tool to illustrate the algorithm for converting an arbitrary NFA to a DFA .
-
Constrcut graphical representation of TM to solve simple problems.
-
Simulate a very elementry micro-processor using TM
-
Simulate sophsisticated elevator using TM
-
Simulate harddisk reading writing mechanism using TM
-
Simulate a cipher system using TM
-
Simulate a TM using a TM
-
Simulate a four function calculater using TM
-
Simulate the Caeser Cipher using TM
-
Simulate Tic-tac-toe using TM
-
Simulate parallel processing using TM
-
Simulate parity checking using TM
-
Simulate CRC check algorithm using TM
-
Simulate a clock using TM for hh:mm:ss