| # |
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: Context-Free Languages and Grammars |
Context-Free Grammars
[Slides 7]
|
A context-free 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 context-free languages, which are those that can be generated by context-free grammars.
Is there some way to build an automaton that can recognize the context-free languages?
|
Any CFG can be converted into a PDA with just three states, meaning that the full power
of the context-free languages can be expressed by three-state 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 single-tape 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.
|
