Theory of Computation

CSCI 48400

3

P: CSCI 36200


Fall
Spring


Introduction to formal languages and automata theory: finite automata, regular expressions, regular languages, context-free languages and pushdown automata, context sensitive languages, Turing machines, undecidability, P and NP. Design and analysis techniques for: divide-and-conquer algorithms, greedy algorithms, dynamic programming, amortized analysis.