Algorithm Design, Analysis & Complexity, Fall 2017
Instructor: | Allan Borodin and Rabia Bakhteri |
Email: | bor at cs dot toronto dot edu | and rabia dot bakhteri at gmail.com
Office hours: | Wed., 4:30pm-5:30pm, SF2303B, or by appointment |
Lectures: | L0101, M,W 10:00-11:00, LM 161, F 10:00-11:00 WI 1016; Wed, 18:00-21:00, Bahen BA 1190 |
Tutorials: | Thur., 14:00-15:00 and 17:00-18:00. Starts on September 14, 2017. Tutorial rooms to be announced in lecture. |
Course Info Sheet: | course info sheet |
Standard algorithm design techniques: divide-and-conquer, greedy strategies, dynamic programming, linear programming, randomization, network flows, approximation algorithms. Brief introduction to NP-completeness: polynomial time reductions, examples of various NP-complete problems, self-reducibility. Additional topics may include approximation and randomized algorithms. Students will be expected to show good design principles and adequate skills at reasoning about the correctness and complexity of algorithms.
Required: | T. H. Cormen; C. E. Leiserson; R. L. Rivest; C. Stein, Introduction to Algorithms, 3rd Edition, 2009. Available online from the University of Toronto library. | codename: CLRS |
Supplementary: | S. Dasgupta; C. H. Papadimitriou; U. Vazirani, Algorithms, 2006. | codename: DPV |
Supplementary: | J. Kleinberg; E. Tardos,, Algorithm Design, 2005. | codename: KT |
Assignments: | 3 worth 5% each; Due dates: October 5, November 15, December 4 |
Term Tests: | 2 worth 20% each; tentative dates: October 12, November 16 |
Final (3 hours): | worth 45% |
Term tests will be held during tutorial slots.
You will receive 20% of the points for any (sub)problem for which you write "I do not know how to answer this question." You will receive 10% if you leave a question blank. If instead you submit irrelevant or erroneous answers you will receive 0 points. You may receive partial credit for the work that is clearly "on the right track." The 20% rule applies to all term work: assignments, term tests, and even the final.
Assignments will be submitted electronically on MarkUs (instructions will follow later). Late assignments will not be accepted.
If you believe that there was a significant mistake in how any question was graded, you may submit a one or two paragraph explanation (along with the original grading) as to why you believe the grade you received was a mistake. That explanation will be then re-considered by the grader. Please do not abuse this policy with minor complaints. Grading is subjective to some extent but we are trying to be as generous as possible. Clerical errors (i.e. grades not properly added or entered on Matrkus) can be rectified by the instructors.
You are allowed to discuss assignment questions with other students. You are allowed to consult additional materials, e.g., books, papers, websites. Nonetheless, the writeup of your solutions should be your own and should be done in isolation from other students and resources. In addition, you must clearly identify the names of students you collaborated with (if any) and provide a clear description of additional materials you consulted (if any).
The following rule of thumb might help you ensure that you are writing down your own understanding of a solution: (1) do not take notes during discussions with other students, (2) after solving a question, take a one-hour break before writing down the solution, (3) while writing down the solution do not consult any materials.
Copying or allowing other students to copy solutions is a serious academic offense and will be reported. You might find the Arts and Science website on academic honesty (and references therein) helpful.
I read email regularly, but I do NOT promise to reply to all emails. In particular, if your question is of general interest, I will not respond to it via email. Instead, I will address your question during the following lecture, so that everyone can benefit. Similarly, if your question requires a technical answer it is better to ask it during a lecture, or a tutorial, or office hours.
The course bulletin board can be found here. This bulletin board will NOT be monitored by the instructor or TAs. Course announcements will be made either during lectures or on the course website.
Students with diverse learning styles and needs are welcome in this course. In particular, if you have a disability/health consideration that may require accommodations, please feel free to approach me and/or Accessibility Services at 416-978-8060; http://accessibility.utoronto.ca.