CS 3530: Computational Theory

Resources


Introduction and Mathematical Preliminaries

August 21, 23, 28, 30

[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

September 4, 6, 11, 13, 18

[slides]

Topics

Assignments


Context-free Languages

September 20, 25, 27, October 2

[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 12/04/2018