# 
Week starting 
Content 
Lecture & Tutorial 
Activities 
Evidence 
1  7  11 Sept 2020  00: Set Theory 
Introduction to Set Theory
The Limits of Computation
[Slides 1]

This first problem set is designed to help you gain a familiarity with set theory and basic proof
techniques. By the time you're done, you should have a much stronger sense of how to rigorously
establish mathematical results.

Written reports and documentation source code.
Exercises for develop skills in set theory.

2  14  18 Sept 2020  01: Direct Proofs 
Induction and Deduction
[Slides 2]

In the sciences, much reasoning is done inductively.
In mathematics, reasoning is done deductively.

This second problem set is designed to help you master inductive proofs. It begins with some
simpler problems intended to help you adjust to induction, then concludes with applications to infinite series, recursive functions, and contests.

3  21  25 Sept 2020  02: Finite Automata I 
Finite automata
[Slides 3]

Finite automata are an abstraction of computers with finite resource constraints.
Provide upper bounds for the computing machines that we can actually build.

For each of the following languages over the indicated alphabets, construct a DFA that
accepts precisely those strings that are in the indicated language and begin with programing in python 3.

4  28  30 Sept 2020  03: Finite Automata II 
Non Finite Automata
[Slides 4]

An NFA is a Nondeterministic Finite Automaton

For each of the following languages over the indicated alphabets,
construct an NFA that accepts precisely those strings that are in the indicated language and
begin with programing in python 3.

5  05  09 Oct 2020  04: Regular Languages 
Regular Expressions and The Limits of Regular Languages
[Slides 5]

The regular expressions begin with three simple building blocks.

This fifth problem set explores the regular languages, their properties, and their limits.

6  12  16 Oct 2020  05: Programming Regular Languages 
Programming Regular Expressions
[Slides 6]

The regular expressions begin with programing in python 3.

This problem set explores the programming regular languages, their properties, and their limits.

7  19  23 Oct 2020  06: ContextFree Languages and Grammars 
ContextFree Grammars
[Slides 7]

A contextfree grammar (or CFG) is an entirely different formalism for defining certain languages. 
Below are a list of alphabets and languages over those alphabets.
For each language, design a contextfree grammar that generates that language.

8  26  30 Oct 2020  07: Pushdown Automata 
Regular Expressions and the Limits of Regular Languages
[Slides 8]

the contextfree languages, which are those that can be generated by contextfree grammars.
Is there some way to build an automaton that can recognize the contextfree languages?

Any CFG can be converted into a PDA with just three states, meaning that the full power
of the contextfree languages can be expressed by threestate PDAs.>

9  02  06 Nov 2020  08: Defining Computability 
The standard automaton for this job is the Turing machine.
[Slides 9]

A Turing machine is a finite automaton equipped with an infinite tape as its memory.

This problem explores Turing machines, nondeterministic computation, properties of the R and RE languages.

10  09  13 Nov 2020  09: Programming Turing Machines 
Design a simple programming language that “compiles” down to Turing machines.
[Slides 10]

Keep extending our language to see just how powerful the Turing machine is.

Let's define the language Python to be other language with the introduction of a finite number of counters,
variables that can hold arbitrary natural numbers. Initially, each counter holds the value 0.

11  16  20 Nov 2020  10: The Complexity Class P 
The complexity class P (polynomial time) contains all problems that can be solved in polynomial time.
[Slides 11]

What problems do we believe are computationally intractable?

Given an undirected graph G = (V, E), a simple path in a G is a path between two nodes u, v ∈ V
such that no node is repeated on the path.

12  23  27 Nov 2020  11: A nondeterministic Turing machine. 
An NTM may have multiple transitions defined for a given state/symbol combination.
[Slides 12]

If we add nondeterminism to the DFA, we get the NFA.

For each statement below, decide whether the statement would definitely prove P = NP, definitely
prove P ≠ NP, or would do neither.

13  01  04 Dec 2020  12: The Complexity Class NP. 
The complexity class NP (nondeterministic polynomial time) contains all problems
that can be solved in polynomial time by a singletape NTM.
[Slides 13]

Nondeterministically guess how to fill in all the squares.

A graph coloring is a way of assigning colors to nodes in an undirected graph such that
no two nodes joined by an edge have the same color.
