CPSC 313: Introduction to Computability (Fall 2019)

Announcements | General Information | Assignments | Tutorials | Lectures


Announcements


General information

Instructor: Joel Reardon, ICT 642, e-mail joel.reardon [at] ucalgary [dot] ca
Lectures: MWF 11:00--11:50, Room: EEEL 161
Office hours: MW 13:30--14:30 Room: ICT 642
Syllabus: [pdf]
Midterm: Thursday, October 17, 2019 at 6:00 pm in ENA 201 Statistics from midterm here.
Academic Misconduct Reference: available here
Notes from lectures: available here
Link to gradescope for submissions here


Practice Material

Assignments

assignment due date
Assignment 1[source] Sept 18th at 23:00 [solutions]
Assignment 2[source] Sept 27th at 23:00 [solutions]
Assignment 3[source] Oct 7th at 23:00 [solutions]
Assignment 4[source] Oct 23th at 23:00 [solutions]
Assignment 5[source] Nov 1st at 23:00 [solutions]
Assignment 6[source] Nov 20st at 23:00


Tutorials

T01 M 12:00--12:50 ST 057 Mohamad Elzohbi
R 18:00--18:50 ICT 102
T02 M 17:00--17:50 ST 057 Mohamad Elzohbi
R 18:00--18:50 ICT 102
T03 W 12:00--12:50 ST 057 Mohamad Elzohbi
R 18:00--18:50 ICT 102
T04 W 17:00--17:50 ST 057 Mohamad Elzohbi
R 18:00--18:50 ICT 102
T05 F 12:00--12:50 ST 063 Cooper Davies
R 18:00--18:50 ICT 102

There are two tutorials. One is divided into groups of about 25, the other is a full class. The small-class sized tutoral runs every week. They begin on the week of the 9th of September and they will consist of time to work through the exercises and ask questions about the material.

The full class tutorial is used for quizzes and other content and will not run every week! Here is the schedule for the full class tutorial:

Date Topic
Sep 12 [no tutorial]
Sep 19 Quiz Number 1
Sep 26 [no tutorial]
Oct 3 [no tutorial]
Oct 10 Quiz Number 2
Oct 17 Midterm
Oct 24 [no tutorial]
Oct 31 Quiz Number 3
Nov 7 [no tutorial]
Nov 14 [reading week]
Nov 21 [no tutorial]
Nov 28 Quiz Number 4
Dec 5 Review


Tools

I'll try to have some tools to play around with these concepts.
Note that the use of these tools is not required and they are being provided AS-IS without any guarantee on their correctness.
If you find problems please let me know!

Lecture Content

Lecture Date Topic Readings Exercises Exercise Lab (Week of)
2019/09/06 Introduction Wat 1.1, 1.2 Exercises 1 2019/09/09
2019/09/13 Alphabets, Strings, Languages HMU 1.5; Sud 2.1, 2.2; Wat 1.3; Eri 1 Exercises 2 2019/09/16
2019/09/20 Review of Proof Techniques HMU 1.2, 1.3, 1.4; Sip 0.4; MS 1.3
2019/09/20 Regular Expressions HMU 3.1, 3.3; Sud 2.3; Eri 2; MS 2.7 Exercises 3 2019/09/23
2019/09/25 Finite Automata MS 2.1, 2.2; Eri 3.1 Exercises 4 2019/09/30
2019/09/27 Extended Transition Function Eri 3.2 Exercises 4 2019/09/30
2019/10/02 Non-deterministic Finite Automata MS 2.4, 2.5 Exercises 5 2019/10/07
2019/10/04 Epsilon Transitions Wat 3.1 Exercises 5 2019/10/07
2019/10/07 Minimization of Automata HMU 4.4 Exercises 6 2019/10/14
2019/10/11 Kleene Theorem MS 2.6, 2.8 Exercises 6 2019/10/21
2019/10/21 Pumping Lemma for Regular Languages MS 2.9; Sip 1.4; Wat 5 Exercises 7 2019/10/28
2019/10/23 Context-Free Grammars Sip 2.1; Wat 7; MS 3.1, 3.2; HMU 5.1 Exercises 7 2019/10/28
2019/10/30 Context-Free Parsing Wat 8.1, 8.2; HMU 5.2, 5.4 Exercises 8 2019/11/4
2019/11/1 Chomsky Normal Form MS 3.4; Wat 8.3; HMU 7.1 Exercises 9 2019/11/18
2019/11/6 Using CNF Exercises 9 2019/11/18
2019/11/8 CFL Closure Properties HMU 7.3 Exercises 9 2019/11/18
Turing Machines Wat 12; Sip 3.1; HMU 8.2
Varients of Turing Machines Wat 13.1; Sip 3.2; HMU 8.4
Encodings of Automata Wat 13.2
Universal Turing Machines Sip 4.2; HMU 9.2.3
Computability and the Halting Problem Sip 4.2; HMU 9.2.4
Undecidable Languages and Reductions HMU 9.3; 9.5
Recursive and Recusively Enumerable Closures
Decidable Languages Wat 14; Sip 4.1
Busy-Beaver Numbers and Computability Aar

References

There are a number of references available. The code in brackets, e.g., [Wat], is how the references are identified for readings. Here are two recommended books that are on hold at the library: Also good but not on reserve:
There are also other free lecture notes available, which are as comprehensive as a textbook:

LaTeX resources for typing homework

Last updated: