Course overview

Welcome to CSC 54-304! 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
This list is neither exhaustive nor set in stone.

Instructor

Name: Arjun Chandrasekhar
Email: chandrasa@southwestern.edu
Lecture: Tuesday/Thursday 11:30 am - 12:45 pm in FJS 304
Student Hours: All student hours will take place in FJS 310 (the Math/CS common room).
  • Mondays from 11:00 am - 12:00 pm
  • Tuesdays from 2:30 pm - 4:00 pm
  • Wednesdays from 11:00 am - 12:00 pm
  • Thursdays from 2:30 pm - 4:00 pm
  • I help organize Computer Science Lunch every other Friday from 12:30 pm - 1:30 pm in Mabee Commons. If you come to CS lunch I am happy to help you out.
  • If these times do not work for you AND you cannot make tutoring hours, then email me to set up student hours by appointment.

Course Links

Here is a tentative calendar for the course.