| Test | Weight | Date |
|---|---|---|
| Term Test 1 | 15% | Wednesday, February 8 |
| Term Test 2 | 15% | Wednesday, March 22 |
| Final Exam | 40% | Exam period |
Check the past course offerings section for links to previous offerings of this course, where you can find term tests and assignments to practice on.
The term tests will last 50 minutes and will be held during regularly scheduled lecture time.
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 midterm test 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.
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.
Some previous offerings of this course: Fall 2005; Summer 2005; Winter 2005; Fall 2004.
The final exam will be written at the time set by the Final Exam Timetable. Make sure you note the date, time and room carefully.
The exam is set for three hours in length. The exam is closed-book but a handwritten notes-sheet is permitted as your only aid. It must be a US letter-sized sheet of paper (8.5" by 11") and must contain only hand-written notes on both sides. You must make your notes-sheet available to the exam presiding officers for inspection at any time. Make sure you have only handwritten notes on the sheet: otherwise is will be confiscated and you may face penalties and sanctions as specified by the Registrar's Office.
The final exam will consist of 5-6 questions. Each will consist of a problem (or series of related problems) for which you will give an efficient algorithm to solve or approximate, prove that an algorithm solves or approximates the problem, or both.
The exam will cover the following topics: greedy algorithms and their proofs, dynamic programming algorithms, divide-and-conquer algorithms, expressing problems using network flow, expressing problems as linear programs, and approximation algorithms.
The textbook exercises and past exams are good sources of study questions. In the back of each chapter there are solved exercises you can try and check, and many problems you can try solving. The Past Course Offerings section contains links to some of these exams. The Faculty of Arts and Science on St. George campus also has a website containing many of the past final exams for their courses.
Sample solutions to term test 2: PDF and PS
The second term test will be 50 minutes long, and written in the first hour of lecture on March 22. The test will take place in the regular lecture room. No aids will be allowed (closed book, no calculators, etc.).
Coverage and test format was decided in class prior to the test. The test will cover divide-and-conquer algorithms and network flow. I will provide to you the Master Theorem, so you don't need to memorize it -- concentrate instead on how to use it (or better yet, on how to come up with and analyze divide-and-conquer algorithms). I expect you to know:
Sample solutions to Assignment 3 will not be available online before the test, though the TA went through them in tutorial. There is a chance marks might be available prior to the test, so watch the Announcements page.
The term test 2 from last year might be a useful practice tool: Winter 2005.
The first term test will be 50 minutes long, and written in the first hour of lecture on February 8. The test will take place in the regular lecture room.
The test will cover greedy algorithms and dynamic programming algorithms. Questions will typically ask for to come up with an efficient algorithm to solve some problem, prove that an algorithm is correct, or both. Problems will be similar to homework problems (except easier). Often test problems are related to or similar in nature to problems you have seen in lecture, tutorial, or in the assigned readings from the textbook. I will try to return Assignment 1 prior to the test, so you can get feedback from the TA.
The format of the test is four problems, do three. Read over the entire test first, then choose which problems you would like to solve. Only three problems will be marked, so don't try to finish all four... you won't get any extra credit.
|
|