Announcements

• (Dec 14) Solutions to HW4 have been posted. Here are some pointers to the sources of our homeworks:
  • R-heaps are a mirror image of leftist heaps. S-heaps are a mirror image of skew heaps. You can find plenty of information about both online.
  • The closest pair of points algorithm in HW3 is due to Michael Rabin and was one of the early examples of the power of randomness in computation. You can read more about this algorithm in Section 13.7. of the book Algorithm Design by Kleinberg and Tardos.
  • Question 2 of HW3 and Question 2 of HW5 come from this paper by Seidel.
• (Dec 4) You do not need to complete question 1a on homework 6, since it is actually proved in theorem 22.10 in CLRS.
• (Dec 2) Homework Assignment 6 has been posted, and is due by midnight on December 6. This is an individual assignemnt.
• (Nov 28) Solutions to HW4 have been posted.
• (Nov 25) Marks for HW3 have been released. You have a week (until midnight on Friday, Dec 2) to submit a remark request through MarkUs.
• (Nov 24) Proof of the log-star amortized complexity of the forest implementation of the union-find data structure (with weighted union and path compression) was posted. Taken from the first edition of CLR (before S).
• (Nov 17) Homework assignment 5 is posted. You can also access it from the Homework page. The homework is due on December 1.
• (Nov 17) Embarrassingly, there was still a problem with question 2 on homework assignment 4: the hint was misleading in suggesting an actual cost which sometimes grossly overestimates the time complexity. The actual cost should just be the number of comparisons. The homework assignment has been updated and the deadline has been extended to midnight on Monday, Nov 21.
• (Nov 11) Counterexamples referred to in comments on your graded submissions in MarkUs have been posted. For example, a comment might say "Algorithm does not work --- simulate it on tree T[1]". Before you submit a remark request, check the corresponding tree in the counterexamples to understand what the issue is. Reminder: the deadline to make a remark request on HW2 is Monday, Nov 14 at midnight. Remark requests will not be accepted later than that. Submit your remark request through MarkUs.
• (Nov 11) Solutions to the midterm have been posted. The answers are more detailed than what was expected on the actual midterm. For example, justifications were given for every question.
• (Nov 11) HW4 has been updated. There was an issue with problem 2 which was corrected: the Union algorithm should always swap the left and right subtree after the recursive union. Some clarifications have been added to problem 1 as well. Also, all homework deadlines until the end of the semester have been pushed back by 2 days.
• (Nov 7) Solutions to HW3 have been posted. Also, Homework 2 has been graded and the deadline for remark requests is until midnight on Monday, November 14. Please send remarking requests through MarkUs.
• (Nov 1) Homework assignment 4 is posted. You can also access it from the Homework page. The homework is due on November 15.
• (Oct 31) Another small clarification added to Problem 1. This week office hours will be on Wednesday, November 2, from 10am to 12pm noon. Next week office hours will be on Friday, November 11, from 10am to 12pm noon. Email me for appointments outside these time frames.
• (Oct 29) A small change was made in HW3 to clarify an issue in Problem 1.
• (Oct 28) The deadline for HW3 has been extended to midnight on Thursday, Nov 3, since for most of you the last few weeks were surely very busy with midterms. HW4 is still coming out on Nov 1, and the other deadlines are not affected.
• (Oct 22) Solutions to HW2 have been posted. Also HW3 was updated: there was a mistake in the definition of IsCloser in Problem 1.
• (Oct 18) Homework assignment 3 is posted. You can also access it from the Homework page. The homework is due on November 1.
• (Oct 16) The marks for Homework 1 have been released. You have one week to submit a remark request (through MarkUs). Many of you wrote overly long answers. As a guideline you do not need more than 5-6 pages to describe the entire solution to both problems in sufficient detail. E.g. the solution I posted is 2 pages. This is also true for Homework 2 and the subsequent homeworks we will have. Please follow this guideline for Homework 2: try to keep your submissions below 6 pages. Starting from Homework 3, submissions will have page limits.
• (Oct 13) Several new resources posted in Lectures:
  • Lectures notes by Jeff Erickson on problem complexity lower bounds: Decision Trees; Adversary Arguments (ignore the section on connectedness).
  • Review of Modular Arithmetic. Also read Sections 31.1-31.4 in CLRS.
  • Review of Probability Theory. Also, you can review Appendix C in CLRS once again.
  Some clarifications were also added to problem 2 in Homework 2: elements with different keys can have the same color.
• (Oct 6) Solutions to Homework 1 posted.
• (Oct 5) Correction made to problem 2 in the homework assignment.
• (Oct 4) Homework assignment 2 is posted. You can also access it from the Homework page. The homework is due on October 18.
• (Oct 4) There will be no in-class lecture on October 11. Instead, you should watch all of the following videos:
  • Introduction to Lower Bounds and Comparison Trees
  • Information Theory Arguments
  • Adversary Arguments
  • Reductions
  In the tutorial on October 13 you will solve problems related to proving problem complexity lower bounds.
• (Sept 28) Due to a DCS faculty meeting, my office hours on Thursday, Sept 29, will be changed to 10-11am and 1:30pm-2:30pm. Apologies for the last minute notice! Also, the office hours on Thursday, Oct 6, will be moved to Wednesday Oct 5, 10am-12pm.
• (Sept 27) All students registered for the course have been added to MarkUs. Apologies for the delay: my original request to the IT support had fallen through the cracks. Please write to me if you have trouble logging in.
• (Sept 26) Handout for AVL trees posted. Added to reading assignment for the week: Chapter 18 on B-trees from CLRS. Focus on 2-3-4 trees. In tutorial this week we will cover the closely related 2-3 trees.
• (Sept 22) A correction was made to assignment 1: in part b. of problem 2, max was changed to min in the definition of the d-value.
• (Sept 20) Homework assignment 1 is posted. You can also access it from the Homework page. The homework is due on October 4. Make sure to read the guidelines on the first page! The password to access the homework was given in class.
• (Sept 18) Handout for binomial heaps uploaded. Taken from CLRS, 2nd edition. This is the reading for the week. Also, review BSTs (Chapter 12 from CLRS).
• (Sept 13) Make sure to sign up for Piazza, read this website thoroughly, and do the reading for the week (Chapter 6 from CRLS).

Text Book

Introduction to Algorithms, Third Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein is available online from the University of Toronto library. We will refer to this text as CLRS.

Contact information

Prof. Nikolov will attempt to respond to legitimate email inquiries from students within 48 hours. Please include "CSC265" in the subject line of the email.

Where and When

Grading Scheme

Your mark for the class will be based on the following components:

• Homework assignemnts: 42%
• Midterm exam: 15%
• Final exam: 43%

The midterm exam will be one hour long, and will take place on October 27, 2016, in the tutorial time slot. It will cover all the material in the first six weeks of the course.

You need to score at least 40\% on the final exam to pass the course.

Academic Integrity

Every student must abide by the University of Toronto academic integrity policy, and the Code of Student Conduct. Academic misconduct is taken very seriously! See the Homeworks page for information about what resources you are allowed to use when working on your assignments.