Term Tests and Final Exam

Final Examination

The final examination is comprehensive (it covers all of the material of the course): induction (simple, complete, well ordering), recurrence relations (setting up, solving, proving), recursive correctness, iterative correctness (loop invariants, partial correctness, termination), regular languages (RE's, FSA: DFA/NFA), non-regular languages, context-free languages (CFG's, PDA).

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.

Past exams

You can find copies of previous exams, for practice, on the Exams and Course Collections of the University of Toronto Libraries.

Last term's exam is not yet available from that site, but luckily I have my own copy: Fall 2007 Exam.

Warning! It is unlikely that any of the questions on our exam will be very similar to a question from a past exam — after all, we have access to those old exams just as you do! Past exams are a great source of problems to practice on, but only after you have carefully reviewed this term's materials (lecture notes, solutions to homeworks and tests): it is almost certain that some questions on our exam will be closely related to problems you have seen before on homework or tests (or even during lectures).

Term Test 3

Term Test 3 will take place on Thursday 10 April 2008 from 10:10am to 11:00am in room BA 2195. The test will be closed book (no aid allowed).

The test will be on all of the material covered from Test 2 up until now: loop invariants and correctness of iterative code, formal language definitions, regular expressions, finite-state automata, non-deterministic finite automata, regular languages and their properties, non-regular languages, maybe a little bit of context-free grammars.

Besides the lecture notes, pay particular attention to the material from homework exercises 5 and 6, and homework assignment 3.

Term Test 2

Term Test 2 will take place on Thursday 13 March 2008 from 10:10am to 11:00am in room BA 2195. The test will be closed book (no aid allowed).

The test will be on all of the material covered since Test 1 up until now, except for using loop invariants to design code: algorithm complexity, i.e., recurrence relations (deriving them from algorithms, solving them with Master Theorem or repeated substitution, proving bounds on them inductively), and algorithm correctness (pre/post conditions, proving correctness of recursive algorithms by induction on the input size, loop invariants, proving partial correctness and termination of iterative algorithms).

Besides the lecture notes, pay particular attention to the material from homework exercises 3 and 4, and homework assignment 2.

Term Test 1

Term Test 1 will take place on Thursday 7 February 2008 from 10:10am to 11:00am in room SS 2106 (rather than your usual tutorial room). The test will be closed book (no aid allowed).

The test will be on all of the material covered up until now, except the material on recurrence relations: induction (simple, complete, and well ordering) — besides the lecture notes, pay particular attention to the material from homework exercises 1 and 2, and homework assignment 1.

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).

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 you will always get at least 20% for any correct solution element (e.g., part of the main idea of a correct solution, or part of the correct structure for a solution). However, 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 homework, where you have the time (and the responsibility) to ask questions and learn how to solve each problem.