Overview

Communication

Description: Clearly and unambiguously communicate computational ideas using appropriate formalism. Translate across levels of abstraction.

Classify languages: Classify the computational complexity of a set of strings by determining whether it is regular, context-free, decidable, or undecidable.; Give examples of sets that are regular, context-free, decidable, or undecidable languages (and prove them).

Decision problems

Translate a decision problem to a set of strings coding the problem.

Classify computational complexity of a decision problem.

Automata

Use precise notation to formally define the state diagram of DFA, NFA, PDA, TM.

Use clear English to describe computations of DFA, NFA, PDA, TM informally.

Other Models of Computation

Use regular expressions and relate them to languages and automata.

Use context-free grammars and relate them to languages and pushdown automata.

Problem Solving

Description: Know, select and apply appropriate computing knowledge and problem-solving techniques. Reason about computation and systems. Use mathematical techniques to solve problems. Determine appropriate conceptual tools to apply to new situations. Know when tools do not apply and try different approaches. Critically analyze and evaluate candidate solutions.

Computability techniques: Use the pumping lemma to prove that a given language is not regular.; Use diagonalization to prove that there are 'hard' languages relative to certain models of computation.; Use appropriate reduction (e.g. mapping, Turing, polynomial-time) to deduce the complexity of a language by comparing to the complexity of another.

Modeling and Impact

Description: Understand, guide, shape impact of computing on society/the world. Connect the role of Theory CS classes to other applications (in undergraduate CS curriculum and beyond). Model problems using appropriate mathematical concepts.

Calibrate difficulty: Explain nondeterminism and describe tools for simulating it with deterministic computation.; Explain the Church-Turing thesis and use it to operationalize the notion of algorithm.