Term Tests and Final Exam

Final Examination

The final examination is comprehensive (it covers all of the material of the course): Turing Machines, equivalence to other models, decidable and recognizable languages, diagonalization, proof of undecidability of ATM, undecidable and unrecognizable languages, mapping reductions (≤m); P, NP, coNP, polytime reductions (≤p), NP-completeness, self-reducibility, space complexity (PSPACE, L).

Important note about unauthorized aids

The Faculty of Arts and Science is very strict about unauthorized aids at final exams (an "unauthorized aid" is anything other than what you need to write the exam, except for aids that have been explicitly listed on the cover of the exam). This is a response to some innovative cheaters. The consequences have been significant: students don't only lose the aid, but they may lose the exam. This is the case whether or not they intended to use the unauthorized aid to cheat.

Note that for this purpose, all electronic devices (cell phone, pager, etc.) are considered unauthorized aids — except for calculators if they are listed on the front of the exam. In particular, cell phones and pagers are not allowed, even if they will be used just to tell the time.

There was a case a few years ago involving two friends who were communicating. They may just have been rolling their eyes as if to say "this exam is stupid/annoying, ha ha", but there was obviously communication going on and they got charged (as in, their exams were confiscated and they were accused of an academic offence). Unfortunately, it's completely untenable to have a rule which says that communication is allowed iff it's not on the topic of the exam! So people who can't help communicating should take care not to sit near each other.

Advice and cover page

Here is further advice on studying for the exam and writing the exam.

Here is the cover page for the final examination.

Please read it carefully. In particular, note that you will be allowed to bring one aid sheet but that it must be handwritten (we will be under obligation to confiscate printed or photocopied sheets during the examination).

Also, note the number of pages, the number of questions, and the number of marks (total and for each question). This will allow you to plan your time carefully: given that you have 3 hours = 180 minutes to write the exam, you can figure out right away how much time you have available for each page, each question, or each mark on the exam, including leaving yourself a bit of time at the end for reviewing your answers.

Term Test 2

Term Test 2 will take place on Monday 3 December 2007 from 2:10pm to 3:00pm in room SS 1083. The test will be closed book (no aid allowed).

The test will be on all of the complexity material: P, NP, coNP, polytime reductions (≤p), NP-completeness, self-reducibility, space complexity (PSPACE, L).

Term Test 1

Term Test 1 will take place on Monday 22 October 2007 from 2:10pm to 3:00pm in room SS 1083. The test will be closed book (no aid allowed).

The test will be on all of the computability material: Turing Machines, equivalence to other models, decidable and recognizable languages, diagonalization, proof of undecidability of ATM, undecidable and unrecognizable languages, mapping reductions.

General information

Check the general information on the main page for links to previous offerings of this course, where you can find term tests and assignments to practice on.

The term test(s) will last 50 minutes and will be held during regularly scheduled tutorials — see the important dates for the exact test date(s), and the course schedule for tutorial times.

If you have any serious conflict with the time or date of the test(s), please inform your instructor immediately to make alternative arrangements.

The term test(s) will be closed book (i.e., NO aids allowed), and should be written in pen (remarking requests for tests written in pencil will not be accepted) — the test paper will have lots of room for rough work.

The "20% rule"

We want to encourage you to be aware of (and honest about) what you know and what you do not know, because it's important to be aware of the level of your own knowledge. (Also, to be quite frank, this will spare you the trouble of writing — and us the trouble of reading — lots of random or irrelevant bits of information in the hopes of getting a few part marks.) For this reason, if you cannot answer a question (or part of a question) on a term test or on the final exam, you will receive 20% of the marks for that question (or part of a question) if you write

I don't know.

(or something similar) in the space reserved for your answer. You will NOT receive the 20% if you leave your answer completely blank, or if you write anything in addition to the sentence above, because neither of those cases show that you are aware of what you don't know. However, if you cross off an answer that you realized was wrong (so it will not be marked), and then write the sentence above, you will receive the 20%.

Note that it is certainly possible to get less than 20% on a question, if you write an answer that is mostly incorrect. Note also that this rule does not apply on assignments, where you have the time (and the responsibility) to ask questions and learn how to solve each problem.