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
- Complexity theory and NP-completeness
This list is neither exhaustive nor set in stone.
Here is a tentative calendar
for the course.
: Arjun Chandrasekhar
Tuesday/Thursday 4:00 pm - 5:15 pm in Lawrence 209
: 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!
: Siddharth Mahesh
Homework review session:
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)
Saturday 11:00 am - 12:30 pm via Zoom (link in Canvas, passcode CS1502)
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
- Top Hat (Join code 005734)