Computer Science 3719 -- Theory of Computation and Algorithms, Winter 2019

Announcements | Course information | Assignments and tests | Lecture notes


older announcements...


Course information

Lectures: 10:30am-11:45am Tuesdays and Thursdays in EN-2040
Antonina Kolokolova , email: [Your browser cannot view this email address] , office ER-6033.
Instructor office hours: Tuesdays and Thursdays at 2:30-3:30pm, or by appointment.
Textbook: There will be no required textbook for this course; some course notes will be posted online.
There will be three reference books. The main reference book will be Sipser: intro to the theory of computation.

Marking scheme ( tentative! ): 4 assignments of 10% each, one midterm test 20% and a final exam 40%. Note that the last assignment may be due during the last week of the semester (to provide an adequate preparation for the final exam).

CS 3179 Tentative course outline
What is an algorithm? What does it mean for a problem to be computationally easy, hard or unsolvable? What can be solved by a computer with only small finite memory or in limited time? This course is an introduction to the theory of computation, an area which studies these types of questions. We will talk about what is known (and what is open) about the power of computation.


Assignments and tests

Assignment 1. ( LaTeX Source). Due Jan 31, 2019.
Assignment 2, part 1. ( LaTeX Source). Due Feb 13, 2019. Assignment 2, part 2. ( LaTeX Source). Due March 5, 2019.
Assignment 3. ( LaTeX Source). Due Mar 26, 2019.
Assignment 4. ( LaTeX Source, picture ) Due April 3, 2019

Please typeset your assignment and upload it to D2L, both your source file and in pdf format. You are encouraged to use LaTeX, and just edit the source files for assignments (linked above). Overleaf is a good online LaTeX editor, if you don't have your favourite yet. You don't need to know LaTeX, just open the source file and start filling the blanks, using the text in the file for reference.

Late assignment policy: For every assignment there will be 12 hours after the deadline when assignments would still be accepted, but the marks will be decreased by 10% of the total mark (e.g. a 100-point assignment will receive 10 points less if submitted within 12 hours after the deadline). After this 12-hour period, no assignments will be accepted. If there are several submissions, only the latest will be considered.

Policy on collaboration: The work you submit must be your own. You may discuss problems from assignments with each other; however, you should prepare written solutions alone. Plagiarism is a serious academic offense and will be dealt with accordingly.


Lecture notes

I will be posting lecture notes as we go; you are welcome to check the lecture notes from the previous run of this course.

A study guide for the midterm test. A study guide for the final exam.