INTRODUCTION TO THEORY OF COMPUTING

COMPSCI 520

Course Description

Basics about the notion, capabilities, and limitations of computation: elements of finite automata and regular languages, computability theory, and computational complexity theory. Additional topics include context-free grammars and languages, and complexity-theoretic cryptography.

Prerequisties

(COMPSCI/MATH 240 or COMPSCI/MATH/STAT 475 ) and (COMP SCI 367 or COMPSCI 400 ), or graduate/professional standing, or declared in the Capstone Certificate in Computer Sciences for Professionals

Satisfies

This course does not satisfy any prerequisites.

Credits

Not Reported

Offered

Not Reported

Grade Point Average

3.04

1.62% from Historical

Completion Rate

95.12%

1.53% from Historical

A Rate

29.27%

20.66% from Historical

Class Size

6.56% from Historical

Instructors (2025 Fall)

Sorted by ratings from Rate My Professors

Similar Courses

TOPICS IN THEORETICAL COMPUTER SCIENCE

COMPSCI 880

Advanced topics in algorithms, complexity, and cryptography. The exact topic varies.

PRINCIPLES OF PROGRAMMING LANGUAGES

COMPSCI 704

Introduction to principles of advanced programming languages and programming-language theory. Topics include: lambda-calculus, functional languages, polymorphic functions, type inference, structural induction, lazy evaluation, operational semantics, denotational semantics, and axiomatic semantics. Students are strongly encouraged to have knowledge of programming languages, such as fromCOMP SCI 536.

COMPUTABILITY THEORY

MATH 773

Turing degree and jump, strong reducibilities, arithmetic hierarchy, index sets, simple and (hyper)hypersimple sets, easy forcing arguments in computability theory, finite and infinite injury, Friedberg-Muchnik and Sacks Splitting Theorem, Sacks Jump and Sacks Density Theorems, computable ordinals. Familiarity with the topics in a basic Foundations course such asMATH 770is strongly recommended.

COMPUTATIONAL COMPLEXITY

COMPSCI 710

Study of the capabilities and limitations of efficient computation. Relationships between models representing capabilities such as parallelism, randomness, quantum effects, and non-uniformity; and models based on the notions of nondeterminism, alternation, and counting, which capture the complexity of important problems. Knowledge of the theory of computation is strongly encouraged, such asCOMP SCI 520.

INTRODUCTION TO THE THEORY AND DESIGN OF PROGRAMMING LANGUAGES

COMPSCI 538

Design and theory of programming languages: procedural, object-oriented, functional and logic paradigms. Serial and concurrent programming. Execution models and formal specification techniques.