Computer Science 3719 -- Theory of Computation and Algorithms, Winter 2019
- 25/4/2019 The grades are a bit delayed, sorry for that. You should get them by the end of the week.
- 14/4/2019 An updated study guide with a diagram of complexity classes is now posted.
- 13/4/2019 The pre-exam office hours will be on Wednesday April 17th, 11:30am-1:30pm.
- 5/4/2019 A study guide for the exam is now
posted.
- 26/3/2019 As agreed in class, since assignment 4 overlaps with projects in other classes, I will take the maximum of the original marking scheme (with 2a and 2b counted at 5% each, and assignment 4 to be posted today at 10%), and a variant excluding assignment 4 and counting assignments 2a and 2b at 10% each.
- 27/3/2019 Assignment 4 is now posted. Due Wednesday, April 3rd.
- 26/3/2019 Assignment 4 deadline has been moved to Thursday, March 28th.
- 13/3/2019 I will be away all of next week. The lecture on Thursday, March 21 will be a guest lecture by Manrique Mata-Montero. There will be no lecture Tuesday, March 19th.
- 13/3/2019 Assignment 3 is now posted. Due Tuesday March 26.
- 7/3/2019 Thank you so much everybody who filled in the doodle poll! It looks like there is no time that would work for more than 2/3 of the people who responded, though... Luckily, Manrique Mata-Montero agreed to to give a guest lecture in our class on Thursday March 21st. That is, there is no make-up class, no class on Tuesday March 19th, and class as normal on Thursday March 21st taught by Manrique Mata-Montero.
- 5/3/2019 I will be away from March 16th to March 24th, and I am trying to arrange a make-up lecture sometime between this Friday and the end of next week. Could you fill in the times when you are available at this doodle poll by 1pm tomorrow (Wednesday)? Thank you! (I can get a room with lecture capture for this Friday at 4:30-6:30pm, but if we can find the time when less people are unavailable that would be better).
- 5/3/2019 Assignment 2b is postponed till Thursday 10pm (that is, you have extra 48 hours to work on it).
- 27/2/2019 The office hours on Thursday, Feb 28 will move to 3:30-4:40pm (I need to be at a departmental event 2:30-3:30pm).
- 25/2/2019 The second part of assignment 2 is now posted. Due Tuesday March 5th.
- 25/2/2019 The campus is closing at 1pm today (Monday), so there will be no office hours today. Sorry for that! Please email me if you have any questions. The midterm is still scheduled for tomorrow, Feb 26th.
- 20/2/2019 There will be office hours on Monday Feb 25th from 2:10pm to 3pm.
- 11/2/2019 Here is the study sheet for the Feb 26th midterm. Note that you are not allowed to use it (or any other aids) during the midterm, this is for preparation only.
- 8/2/2019 As discussed in class, we are implementing the following 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. After this 12-hour period, no assignments will be accepted. If there are several submissions, only the latest will be considered.
That is, if the deadline is at 10pm on Wednesday evening, you can submit with no penalty until this time. Assignments submitted between 10pm Wednesday and 10am Thursday morning will have the mark decreased by 10% of the total mark, e.g. by 10 points on a 100-point assignment. After 10am Thursday, we would not accept any assignments. So an assignment that would get 80/100 points when submitted at 9pm Wednesday, if submitted at 9am Thursday would get 70/100, and get 0 (not accepted) if not submitted by 10am Thursday.
- 6/2/2019 The notes on Turing machines are now posted. This should be all you need to do assignment 2, part 1 .
- 4/2/2019 The first half of assignment 2 is posted. Due Feb 13th, 10pm, typed up on D2L.
- 24/1/2019 Partial notes on pushdown automata and context-free grammars are now posted. They should have all the material you need to do your assignment 1.
- 17/1/2019 As discussed in class, the midterm will be on Feb 26th (Tuesday after the break).
- 16/1/2019 Assignment 1 is now posted. Due Jan 31st at 10pm. Please typeset it (here is the LaTeX source) and upload both the resulting pdf and the source to D2L.
- 8/1/2019 Office hours will be Tuesdays and Thursdays 2:30pm-3:30pm.
- 2/1/2019 There will be no class on Thursday, January 3rd (flights to St. John's cancelled due to weather).
Lectures: 10:30am-11:45am Tuesdays and Thursdays in EN-2040
Instructor: 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.
- M. Sipser: Introduction to the Theory of Computation (2nd edition).
- Cormen, Leiserson, Rivest, and Stein: Introduction to Algorithms (3rd Edition).
- Kleinberg and Tardos: Algorithm design.
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.
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.
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.