Course overview

Welcome to CS 1502! The course is an introduction to the theory of information and computation as a physical phenomenon. The course covers standard formalizations of computational concepts and proofs of noteworthy implications of these formalizations. We will be defining what a "computer" is, and exploring what are some of the fundamental limits of different types of computers. In this course we will study the following topics:

  • Formal languages and decision problems
  • Deterministic and nondeterministic finite automata
  • Regular expressions
  • Context free grammars
  • Pushdown automata
  • Turing machines
  • Turing completeness
  • Turing (un)decidabile and (un)recognizable languages
  • Reducibility
  • Complexity theory and NP-completeness
This list is neither exhaustive nor set in stone.

Here is a tentative calendar for the course.

Instructor

Name: Arjun Chandrasekhar
Email: arjunc@pitt.edu
Student Hours:
  • Monday-Thursday 11-12:30 in Sennot Square 6203
  • Or by appointment
    • I really cannot overemphasize this enough. If none of the listed studenthours work for you then email me to set up something else. Please don't give up on getting the help you need because you reasonably but mistakenly interpreted the listed student hours to be set in stone!

Course Links

UTAs and Graders