COURSE CONTENTS AND STRUCTURE

The first part of the course will provide some basic elements of Formal Language Theory, including Finite State Machines (fsm) and Recursive Function Theory. Note that fsm is part of your required background, so we view this part as training in writing rigorous proofs. We will use Sipser's book for the first part.

The second half will introduce the basic concepts complexity theory, and treat some important topics such as alternation and randomness. Most of the second part will use my own notes.