Course overview

Welcome to CSC 54-844! 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
  • Context free grammars
  • Pushdown automata
  • Non-context-free 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.

Instructor

Name: Arjun Chandrasekhar
Email: chandrasa@southwestern.edu
Lecture: Tuesday/Thursday 10:00 am - 11:15 pm in Fondren-Jones 151
Student Hours:
  • Monday/Wednesday from 11:00 am - 12:00 pm in Fondren-Jones 301
  • Tuesday/Thursday from 1:00 pm - 3:00 pm in Fondren-Jones 301
  • By appointment
  • I really cannot emphasize the part in bold strongly enough. The above hours are when I am guaranteed to be in my office - but not the only times. If none of the listed student hours work for you then feel free to drop by my office at a different time, and/or email me to set up an appointment. 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

Here is a tentative calendar for the course.