MATH 4L03 home page

Announcements:

December 14: Term scores for each student have been calculated and posted on the Avenue To Learn site for this course. The formula used to calculate the term score is: (Average of 5 best assignments) + (Project score) + (Test score)*(25/20). The maximum term score is 55. Your final grade will be the sum of your term score and exam score.

December 14: The course project has been graded. You can find your grade and feedback on the Avenue To Learn site for this course.

December 07: Solutions to assignment #6 have been posted here. The LaTeX source for this file can be found here.

December 02: The final exam for this course will be held on Thursday, December 11 from 9:00am to 11:30am in Hamilton Hall Room 104. Details on the final exam can be found here.

December 01: An excerpt from Sipser's book that contains a proof of the Cook-Levin Theorem can be found on the Avenue To Learn site for this course.

November 30: Skip question #2 from assignment #6. It was mistakenly included in the assignment.

November 25: Solutions to assignment #5 have been posted here. The LaTeX source for this file can be found here.

November 24: Assignment #6 has been posted here. It is due on Monday, December 1 by 11:59pm. The LaTeX source for this assignment can be found here.

November 14: Solutions to assignment #4 have been posted here. The LaTeX source for this file can be found here.

November 11: Please submit your project topic to Dr. Valeriote by Friday, 14 November.

November 11: Assignment #5 has been posted here. It is due on Friday, November 21 by 11:59pm. The LaTeX source for this assignment can be found here.

November 2: Dr. Valeriote will not be on campus on Monday, 3 November and so the lecture scheduled for that day (#24) will be presented via a pre-recorded video. The video is available for download on macdrive and the link for it can be found on the front page of the Avenue To Learn site for this course. Please view this video in advance of the lecture on Wednesday, 5 November. Dr. Valeriote will be on campus then to present Lecture #25 in person. If you have any problems in accessing or viewing the video, please contact Dr. Valeriote.

October 29: The midterm test has been graded and solutions have been posted here. If you have any questions about how your test was graded, please consult the solutions and then contact Dr. Valeriote.

October 27: Assignment #4 has been posted here. It is due on Monday, November 10 by 11:59pm. The LaTeX source for this assignment can be found here.

October 22: Solutions to assignment #3 have been posted here. The LaTeX source for this file can be found here.

October 22: Details on the course project can be found here. You will need to submit your project topic to Dr. Valeriote by Friday, 14 November and submit your video presentation by Wednesday, 3 December.

October 22: The final exam for this course will be held on Thursday, December 11 from 9:00am to 11:30am. Details will be posted on the course website as they become available.

October 9: The MATH 4LT3/6LT3 midterm test will be held on Friday, October 24 from 4:30 to 5:20pm in the usual lecture room for this course. Details on the test can be found here.

October 6: Assignment #3 has been posted here. It is due on Tuesday, October 21 by 11:59pm. The LaTeX source for this assignment can be found here.

October 6: Solutions to assignment #2 have been posted here. The LaTeX source for this file can be found here.

September 24: Assignment #1 has been graded; you can find a copy of your graded assignment on the Avenue to Learn site for this course. Please read over the feedback that has been provided for your assignment and let Dr. Valeriote know if you have any questions about how it was graded. Solutions for the assignment have been posted; you should carefully read them over and compare them to the solutions that you provided.

September 22: Assignment #2 has been posted here. It is due on Friday, October 3 by 11:59pm. The LaTeX source for this assignment can be found here.

September 22: Solutions to assignment #1 have been posted here. The LaTeX source for this file can be found here.

September 17: Change to Assignment #1: Do not submit a solution to question #3 (b). This question will be added to Assignment #2. Please submit solutions to all other problems before the assignment deadline, Friday, 19 September, 11:59pm.

September 16: Another useful tool for dealing with automata can be found here. You may use it while working through any of the homework assignments in this course, especially assignment #1. Thanks to Pesara for bringing this to my attention.

September 5: The following two books can be used as additional resources for this course. The first is "Concise Guide to Computation Theory" by Akira Maruoka. This book is available as a (free) ebook through the McMaster Library. Here is a link to the library entry:

https://mcmaster.primo.exlibrisgroup.com/permalink/01OCUL_MU/deno1h/alma991003873789707371. The second is the book "Introduction to the theory of computation" by Michael Sipser. A copy of the 2nd edition of this book is available through the McMaster Library system. The library entry for this book is: https://mcmaster.primo.exlibrisgroup.com/permalink/01OCUL_MU/deno1h/alma991003175549707371. There are many other good books on this subject that can be found by exploring the library's catalog.

August 29: Assignment #1 has been posted here. It is due on Friday, September 19 by 11:59pm. The LaTeX source for this assignment can be found here.

August 29: Some useful, free software for dealing with automata and Turing machines can be found at www.jflap.org. You may use it while working through any of the homework assignments in this course, especially assignment #1.

August 29: Prior to the first class, students are encouraged to read the introductory sections of the textbook as well as Section 1.1.

The Avenue to Learn site for this course will be used to upload homework assignments and to provide grades for students. All other course information will be posted on this website.

Dr. Valeriote's office hours will be held from 3:30pm to 4:30 on Wednesdays. He is also available by appointment.

The course announcement can be found here.

The first class will be held on Wednesday, September 3 at 2:30pm; the location can be found on Mosaic or on the Avenue to Learn site for this course.

Assignments, Tests, and Solutions:

Test Dates:

There will be one 50-minute test held on Friday, October 24 during the scheduled class time. Further details on the test can be found here.

Final Exam Information:

The final exam for this course will be held on Thursday, December 11 from 9:00am to 11:30pm in Hamilton Hall Room 104. Details can be found here.

Lecture Schedule:

Detailed information on the lecture schedule will be posted here. The aim is to cover the first three chapters of the course textbook.

Lecture #

Date

topics covered

reading/resources/comments

03/09/25

introduction

05/09/25

alphabets, languages, DFAs

Agreements section, section 1.1 from the textbook

08/09/25

DFAs

1.1

10/09/25

continued, regular languages, closure under complementation

1.1, 1.2.1

12/09/25

clorsure under intersection, union

1.2.2

15/09/25

non determinism

1.3

17/09/25

continued, epsilon-NFAs

1.3.2

19/09/25

equivalence of epsilon-NFAs and DFAs

1.3.3

22/09/25

continued, more closure properties

1.4

24/09/25

non-regularity, the pumping lemma

1.6

26/09/25

continued

1.6

29/09/25

Deterministic Turing Machines, examples

2.1

01/10/25

acceptance, rejection, halting, the language of a DTM

2.1

03/10/25

computable, computably enumerable languages

2.1

06/10/25

examples of computable languages, functions

2.1

08/10/25

encoding of objects and DTMs

2.2

10/10/25

universal Turing Machines

2.3

20/10/25

continued, a non-CE language

2.3, 2.4

22/10/25

closure properties of computable and CE languages

2.5

24/10/25

midterm test

27/10/25

closure properties, nondeterministic Turing Machines

2.5, 2.6

29/10/25

NTMs

2.6

31/10/25

continued, multi-tape DTMs

2.6, 2.7

03/11/25

Reductions (presented via a video recording)

2.8

5/11/25

Reductions, examples

2.8

7/11/25

Rice's Theorem

2.9

10/11/25

Computational Complexity introduction, examples

3.1

12/11/25

PTIME languages

3.2

14/11/25

continued

3.2

17/11/25

NP languages

3.2

19/11/25

verifiers

3.2

21/11/25

verifiers, continued

3.2

24/11/25

polynomial-time many-one reducibility, NP-completeness

3.4, 3.5

26/11/25

the Cook-Levin Theorem

Sipser, third edition, section 7.4

28/11/25

continued

01/12/25

continued, 3SAT

03/12/25

3SAT, CLIQUE, INDEP-SET

MATH 4LT3/6LT3
Topics in Logic: Foundations of Computing
Fall 2025

Announcements:

Course Information:

Test Dates:

Final Exam Information:

MATH 4LT3/6LT3 Topics in Logic: Foundations of Computing Fall 2025

Announcements:

Course Information:

Test Dates:

Final Exam Information:

MATH 4LT3/6LT3
Topics in Logic: Foundations of Computing
Fall 2025