CS 3530: Computational Theory

Resources


Introduction and Mathematical Preliminaries

August 20, 22, 27

[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.

Assignments


Finite Automata and Regular Languages

August 29, September 3, 5, 10, 12

[slides]

Topics

Assignments


Context-free Languages

September 17, 19, 24, 26, October 1

[slides]

Topics

Assignments


Midterm Exam


Computability

October 16, 18, 23, 25

[slides]

Topics

Assignments


Uncomputability

October 30, November 1, 6, 8

[slides]

Topics

Assignments

Resources:


Computational Complexity

November 13, 15, 20, 27, 29, 4

[slides]

Topics

Assignments

Resources:


Final Exam

Last Updated 11/19/2019