SE 3310b • Theoretical Foundations of Software Engineering (Winter 2015)

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)

Course Outline

Please consult the course outline for policies relating to this course.

Personnel

Aleksander Essex
Course Instructor
Office: TEB 235
Email: aessex
Office Hour:
Thursdays, before class (i.e., 3:30-4:30)
TBD
Teaching Assistant
Email:
TBD
Teaching Assistant
Email:

Emailing Us

Email addresses are @uwo.ca. Please include "[SE 3310]" in the subject when emailing us, thanks!

Textbook

Michael Sipser. Introduction to the Theory of Computation, 3rd Edition, Cengage Learning, 2012.

Further Reading

Anil Maheshwari and Michiel Smid. Introduction to Theory of Computation. 2012.

Lecture Times and Locations

M

Tu

W

Th

F

Tutorial:

1:30pm-3:30pm

UCC-37


Lecture:

4:30pm-6:30pm

SEB-2100

Lecture:

12:30pm-1:30pm

SEB-2202


Apr 11th: Assignment 4 solutions posted (see below).
April 6: Exam review document has been posted.
March 26: Assignment 4 is available (See below).
March 22: Assignment 4 due date has been extended one week.
Mar 14th: The office hour has been updated to Thursdays before class (3:30-4:30pm)study guide.
Mar 6th: Check out the pumping lemma study guide.
Mar 6th: Assignment 3 available (see below).
Mar 5th: Assignment 2 solutions posted (see below).
Feb 13th: The midterm has been postponed by one week to March 9th. It will be held during our regular Thrusday class time in 3M 3250 (see below).
Feb 6th: Assignment 1 solutions and Assignment 2 are now available (see below). 17th.
Jan 19th: Assignment 1 available (See below). Deadline extended 1 week. 17th.
Jan 3rd: 2017 website has been posted. First tutorial will be held Tuesday Jan. 17th.
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 Shor's Quantum Factoring Algorithm Exam review
Apr 7th Exam review No lecture.
Course Component Weight Date/Deadline Location PDF
Assignment 1 5% January 27th Extended to February 3rd Online via OWL

Assignment 2 5% February 17th Online via OWL

Assignment 3 5% March 17th Online via OWL

Assignment 4 5% March 31st April 7th Online via OWL

Midterm Test 30% March 2nd March 9th 4:30-6:30pm 3M 3250
Final Examination 50% Wed. April 19th, 2:00pm-5:00pm UCC 37