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).
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.