CS 3530: Computational Theory

Resources


Introduction and Mathematical Preliminaries

August 23

[slides]

Topics

Resources:

To install LaTeX on Linux:

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

To install on Mac or Windows, search for TeXLive and install it.

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 6

[slides]

Topics

Assignments


Context-free Languages

September 22

[slides]

Topics

Assignments


Midterm Exam


Computability

October 18

[slides]

Topics

Assignments


Uncomputability

November 1

[slides]

Topics

Assignments

Resources:


Computational Complexity

November 15

[slides]

Topics

Assignments

Resources:


Final Exam

Last Updated 11/22/2016