This course is an introduction to the theoretical foundations of software engineering covering topics in automata theory, computability, and computational complexity.
As an aspiring software engineer, the goal of this course is to leave you with a deeper understanding of what we really mean when we talk about computers and computing. We'll delve into the essence of what a computer really is, which will then let us examine different kinds of computational problems. Some of these problems are easy to compute, some are hard to compute, and some cannot even be computed at all.
This course is not about circuits, CPUs, or any hardware in particular, nor is it about about any programming language or program in particular. Rather this course is about exploring the fundamental capabilities and limitations of any computer, and in turn, of the very software you will write through your career.
A digital computer may be explained by saying these machines are intended to carry out any operations which could be done by a human computer. A human computer follows some fixed set of rules which we may suppose are supplied in a book. This book is altered whenever s/he is put on a new job. S/he also has an unlimited supply of paper on which to perform calculations.
Alan Turing. Computing machinery and intelligence. Mind, 59, 433-460.
An algorithm must be seen to be believed.
Donald Knuth. Fundamental Algorithms (1968)
Please consult the course outline for policies relating to this course.
M |
Tu |
W |
Th |
F |
Tutorial:1:30pm-3:30pmUCC-37 |
Lecture:4:30pm-6:30pmSEB-2100 |
Lecture:12:30pm-1:30pmSEB-2202 |
Week | Subject | Readings | Lecture Slides |
---|---|---|---|
Jan 5th & 6th | Course introduction and background. Review of notation. Introduction to deterministic finite automata (DFA) | Preface, Chapter 0, 1.1 | |
Jan 12th & 13th | DFA's continued. Introduction to non-determinism and non-deterministic finite automata (NFA) | Chapter 1.2 | |
Jan 19th & 20th | NFA's continued. Equivalence of DFAs and NFAs. | Chapter 1.3 | |
Jan 26th & 27th | Closure properties of regular languages. Regular expressions. Pumping lemma for regular languages. | Chapter 1.3 and 1.4 | |
Feb 2nd & 3rd | Introduction to context-free grammars (CFG) | Chapter 2.1 | |
Feb 9th & 10th | Introduction to push-down automata (PDA). Pumping lemma for CFGs. | Chapter 2.2 | |
Feb 16th & 17th | Introduction to Turing machines (TM). TM examples. Turing's original paper. | Chapter 3 | |
Feb 23rd & 24th |
Reading week. Oh yea! |
||
Mar 2nd and 3rd | The Church-Turing Thesis. Decidable languages. | Chapter 4 | |
Mar 9th |
Midterm test (4:30-6:30pm. Location: 3M 3250) |
||
Mar 10th | Universal Turing machines. The halting problem and other undecidable languages. | Chapter 5 | |
Mar 16th & 17th | Computational complexity and running time. Complexity classes P and NP. | Chapter 7.1-7.3 | |
Mar 23rd & 24th | The class NP-Complete, the Cook-Levin Theorem, and the million dollar question: does P=NP? | Chapter 7.4-7.5 | |
Mar 30th & 31st | The class NP-Hard. Probabilistic Turing machines and the class BPP. Quantum computers and the class BQP. | Chapter 10.2 | |
Apr 6th | |||
Apr 7th |
Course Component | Weight | Date/Deadline | Location | |
---|---|---|---|---|
Assignment 1 | 5% | Online via OWL | ||
Assignment 2 | 5% | February 17th | Online via OWL | |
Assignment 3 | 5% | March 17th | Online via OWL | |
Assignment 4 | 5% | Online via OWL | ||
Midterm Test | 30% | 3M 3250 | ||
Final Examination | 50% | Wed. April 19th, 2:00pm-5:00pm | UCC 37 |