Term Tests and Final Exam

Final Examination

The final examination is comprehensive (it covers all of the material of the course): greedy algorithms, dynamic programming, divide-and-conquer, network flows, linear programming, approximation algorithms.

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.

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 takes place on Tuesday 2 December 2008, from 6:10pm to 7:00pm, in room BA 2175. The test will be closed book (no aid allowed).

The test will be on all of the material covered since Test 2 up until now: network flows, linear programming, and approximation algorithms. Besides the lecture notes, pay particular attention to the material from homework exercises 5 and 6, and homework assignment 3 (including their sample solutions).

Term Test 2

Term Test 2 takes place on Tuesday 4 November 2008, from 6:10pm to 7:00pm, in room WB 342. 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: dynamic programming, divide-and-conquer, maybe a little bit of network flows. Besides the lecture notes, pay particular attention to the material from homework exercises 3 and 4, and homework assignment 2 (including their sample solutions).

Term Test 1

Term Test 1 takes place on Tuesday 7 October 2008, from 6:10pm to 7:00pm, in room BA 2175. The test will be closed book (no aid allowed).

The test will be on all of the material covered up until now: greedy algorithms (including proofs of correctness) and dynamic programming. Besides the lecture notes, pay particular attention to the material from homework exercises 1 and 2, and homework assignment 1 (including their sample solutions).

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 class time — see the important dates for the exact test date(s), and the course schedule for class 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.