COMP3602 - Theory of Computing

Announcements

Please sign up on the Slack channel by submitting your email address. I will mass email the invite link. Slack sign-up

Mark sheet

Assignments

Assignment 1 [Due: 24th October 2019]

Assignment 2 [Due: 21st November 2019]

Assignment 3 [Due: 28th November 2019]

Helper Code for A3

Syllabus

1. Review of Sets, Proofs
2. Intro to the concept of a language
3. Deterministic Finite Automata and Regular Languages
4. Closure properties of operators on Regular Languages
5. Nondeterministic Finite Automata
6. Pumping Lemma for Regular Languages
7. Chompsky Hierarchy and Non-Regular Languages
8. Context Free Langauges and Context Free Grammars
9. Pushdown Automata
10. Pumping Lemma for Context-Free Languages
11. Turing Machines

Course Textbooks

Introduction to the Theory of Computation - Michael Sipser - Third Edition

Formal Language: A Practical Introduction - Adam Webber

Supplementary Slides (pulled from various other sources such as Stanfords CS103)

1.DFAs and Regular Languages

2.NFAs and Closure Proof Sketches

3.Regular Expressions

1. Pumping Lemma

   Pumping Lemma #2

5.Non-Regular Languages

6.Context-Free Grammars

7.Turing Machines

Course Mark Breakdown

3 Assignments @ 10% each

2 CW Exams @ 10% each

1 Final Exam @ 50%

Course Work Exam Dates

CW Exam #1 - 17th October 2019

CW Exam #2 - 14th November 2019

Assignment Due Dates

A1 - 24th October 2019

A2 - 7th November 2019

A3 - 28th November 2019

Required Reading (and Viewing)

Video on Comptational Complexity Zoo - youtube video

Video on Godel’s Incompleteness Theorem

Video on Finite-State Machines in Vending Machines

Where Did GREP Come From? - Great video on a common usage of Regular Expressions

Basics of Lambda Calculus

Lectures

Tutorials

Tutorial #1

Tutorial #2

Tutorial #3

Tutorial #4

Tutorial #5

Extra Problem Sets

Extra PS1

Reading Material

Book of Proof Open Maths Textbooks