Algorithm Design, Analysis & Complexity, Winter 2017
See the official UofT Examination Timetable for time and place.
Aids allowed: one double-sided handwritten 8.5x11 aid sheet.
Material covered: the exam will be cumulative -- it will cover the entire material of the course up to and including approximation algorithms.
Exam structure: the exam will last 3 hours, and it will consist of 8 problems (each with subproblems). Questions will be similar in structure to homework questions and midterm-style questions. You will be asked to write descriptions of algorithms in plain English, as well as in pseudocode. You will be asked to prove correctness, analyze and justify running time. You can expect to be asked TRUE/FALSE questions with justification. You should know all the algorithms covered in this course (name, pseudocode, runtime, analysis of correctness), and you should practice solving problems (the more the better). In addition to questions on material covered up to and including the second term test, the exam will contain questions on complexity theory and approximation algorithms. You can expect to be asked to give reductions and prove languages NP-complete, and/or self-reducible. You can expect to be asked to prove approximation ratios.
Estimated exam difficulty: should be more difficult than term test 2, and not more difficult than term test 1.
Past exams: see this webpage of Allan Jepson (password: algor373)
Took place on March 13, 2017 during regularly scheduled tutorial hours 4:00PM-5:00PM.
Test problems: here
The grades are up on MarkUs.
If you have a legitimate regrade request then you should submit it through MarkUs no later than April 1, 2017 by 8PM.
| Section | Location |
|---|---|
| L0101 | Ramsay Wright, RW 110 |
| L0201 | Lash Miller, LM 161 |
Aids allowed: one single-sided handwritten 8.5x11 aid sheet.
Material covered: graph algorithms, network flow, linear programming (including Simplex with positive b).
Test structure: questions will be similar in structure to homework questions. You can expect short answer TRUE/FALSE questions. You can expect to be asked to design an algorithm and explain it in plain English, as well as pseudocode. You will be asked to analyze and justify running time. You should be comfortable with solving small LPs using Simplex by hand.
Took place on February 6, 2017 during regularly scheduled tutorial hours 4:00PM-5:00PM.
Test problems: here
The grades are up on MarkUs.
If you have a legitimate regrade request then you should submit it through MarkUs no later than March 4, 2017 by 11am.
| Section | Location |
|---|---|
| L0101 | Ramsay Wright, RW 110 |
| L0201 | Lash Miller, LM 161 |
Aids allowed: one single-sided handwritten 8.5x11 aid sheet.
Material covered: divide and conquer, greedy, dynamic programming, i.e., everything up to, but not including, graph algorithms.
Test structure: questions will be similar in structure to homework questions. You will be asked to write descriptions of algorithms in plain English, as well as pseudocode. You will be asked to prove correctness, analyze and justify running time.