CS 3530: Computational Theory

Resources


Introduction and Mathematical Preliminaries

August 22

[slides]

Topics

Resources:

To install LaTeX on Linux:

sudo apt-get install texlive-latex-recommended texlive-metapost texlive-fonts-recommended

To install on macOS, install MacTeX:

To install on Windows, install TeXLive:

To compile documents, make sure theory.mp is in the same directory, then run:

pdflatex -shell-escape inputfile
pdflatex -shell-escape inputfile

i.e., run it twice. Or you may modify and use this Makefile:

Just assign the list of input .tex files you want compiled to the SRC= line and run make. To make a specific file, even if it is not in the SRC line, use make file.pdf. When I will be working on a file for a while, I like to change the all rule to point to the file I am currently trying to create, then all I have to type is make to build it.


Finite Automata and Regular Languages

September 5

[slides]

Topics

Assignments


Context-free Languages

September 21

[slides]

Topics

Assignments


Midterm Exam


Computability

October 17

[slides]

Topics

Assignments


Uncomputability

October 31

[slides]

Topics

Assignments

Resources:


Computational Complexity

November 14

[slides]

Topics

Assignments

Resources:


Final Exam

Last Updated 09/06/2017