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
  • Non-regular languages
  • 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
Lecture: Tuesday/Thursday 4:00 pm - 5:15 pm in Lawrence 209
Student Hours: Monday-Thursday form 12:30-2:30 pm in Sennott Square 6305 Or by appointment
  • I really cannot overemphasize this enough. If none of the listed student hours 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!

Teaching Assistant

Name: Siddharth Mahesh
Email: SVM22@pitt.edu
Student Hours:
  • Tuesday/Thursday 10:30 am - 12:00 am in Sennott Square 5806
  • Friday 4:30 pm - 6:00 pm via Zoom (link in Canvas, passcode CS1502)
Homework review session: Saturday 11:00 am - 12:30 pm via Zoom (link in Canvas, passcode CS1502)

Course Links

  • Canvas
    • All Zoom links can be found in the Zoom tab on Canvas (passcode: CS1502)
    • All lecture recordings can be found in the Panopto Video tab on Canvas
  • Discord
  • Top Hat (Join code 005734)