CSC265 (Fall 2019): Enriched Data Structures and Analysis

Overview

Welcome to the course webpage for the Fall 2019 term of CSC265, Enriched Data Structures and Analysis. Here is the course content description:

Algorithm analysis: worst-case, average-case, and amortized complexity. Standard abstract data types, such as graphs, dictionaries, priority queues, and disjoint sets. A variety of data structures for implementing these abstract data types, such as balanced search trees, hashing, heaps, and disjoint forests. Design, implementation, and comparison of data structures. Introduction to lower bounds.

This course is an "enriched" version of CSC263, Data Structures and Analysis. While we cover roughly the same topics, we will go at a faster pace, in greater depth and with more rigour, and with more challenging assignments. Greater emphasis will be placed on proofs, theoretical analysis, and creative problem-solving. Certain topics briefly mentioned in CSC263 may be covered in more detail in this course, and some additional topics may also be covered.

Make sure to read and understand the course information sheet. Check this website and Piazza frequently to make sure you receive any course announcements. Check the Lectures page for the required readings. Always attempt the exercises after the required reading!

Announcements

(Dec 10) If you want to meet once again before the exam, please come to office hours on Monday, December 16, 2pm-4pm.
(Dec 10) Assignment 6 has been updated with solutions. Moreover, some practice problems on MST have been posted. In addition to these, please also attempt the problems from CLRS and the problems from past exams.

Finally, here are some pointers to the sources of our homeworks:
- w-trees are called weak AVL trees, or wAVL trees for short. They come from this paper, and are covered in some data structures textbooks.
- The compression method from Q1 of A3 is based on the Count Min sketch.
- S-heaps are a mirror image of Skew Heaps. You can find plenty of information about them online. Here is the original paper.
- The colourful paths from Q1 of A6 are usually called alternating, or augmenting, paths, and are used in algorithms for finding a maximum matching (i.e., set of edges with disjoint vertices) in a bipartite graph. You can check these lecture notes.
- Q2 of A6 is an algorithmic proof of Robbins' theorem.
(Nov 28) Assignment 5 has been updated with solutions.
(Nov 22) The sixth homework assignment has been posted. Note that it is due on December 4.
(Nov 18) Assignment 4 has been updated with solutions. For tomorrow's class, please review Section 22.1 (Representations of Graphs) and the graph theory notions in Appendix B.4. in CLRS.
(Nov 10) There will be no in-class lecture on November 12. 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 November 14 you will solve problems related to proving problem complexity lower bounds.
(Nov 8) The fifth homework assignment has been posted.
(Nov 7) Assignment 3 has been updated with solutions.
(Nov 2) You can see the midterm exam solutions. Grades are posted on MarkUs, and the physical exams will be returned after reading week. Please check Piazza for some feedback. This is a good time to catch up with things that you may have missed so far in the course.
(Oct 25) The fourth homework assignment has been posted.
(Oct 22) This week office hours will be moved to Wednesday, 3pm-5pm. Feel free to email me if you want to meet outside this window.
(Oct 20) Assignment 2 has been updated with solutions.
(Oct 13) The CSC 265 midterms from Fall 2016 and Fall 2018 are posted for practice.
(Oct 10) The third homework assignment has been posted.
(Oct 1) Assignment 1 has been updated with solutions.
(Sept 27) The second homework assignment has been posted.
(Sept 24) In a week we will start talking about hashing, and with it also about probability. In two weeks we will start doing proofs which will require you to know basic facts about probability and about expected values. Please start looking at the Review of Probability Theory.
(Sept 24) Assignment 1 is due on September 27, not September 26, as the PDF mistakenly said. I am sorry for the typo! Also the assignment is now added to MarkUs.
(Sept 13) The first homework assignment has been posted.
(Sept 10) 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. There will be additional readings posted for select topics.

Contact information

Instructor/TA	Aleksandar Nikolov	Lily Li (TA)
Email	anikolov -at- cs.toronto.edu	xinyuan -at- cs.toronto.edu
Office	Sandford Fleming 2301B	N/A
Office Hours:	Wednesdays 10am-12 noon, or by appointment	N/A

Here are some guidelines for efficiently communicating with us:

Students are encouraged to use Piazza for any questions that may be of interest to other students. Your post may not contain a solution to a homework assignment problem, even a partial one. Students can expect a reply to their post within 1 business day.
Questions about specifics of coursework should be brought to office hours for in-person help.
Emails should be sent only for matters that impact individual students, such as applying for special consideration on coursework. Students can expect a reply to their email within two business days.

You are encouraged to attend office hours even if you do not have a question about the homework or the lectures. You could, for example, introduce yourself, ask questions about research or a career in computing, etc.

Where and When

Type	Lecture	Tutorial
Room	Wallberg Building 219	Wallberg Building 219
Time	Tuesday 2pm - 4pm	Thursday 3pm - 4pm

Grading Scheme

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

Homework assignemnts: 36%
Midterm exam: 18%
Final exam: 46%

The midterm exam will be one hour long, and will take place on October 22, during the second half of the regular lecture 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.

Piazza

The link to sign up for our Piazza forum is piazza.com/utoronto.ca/fall2019/csc265.
Piazza is a third-party software. It will be used in this class strictly as a discussion board. When posting, abide by the academic integrity policy. In particular, do not post solutions to homework problems. Make sure to read the Piazza terms of use before signing up, and if you have any concerns, contact the instructor directly. If you decide to participate in Piazza, only provide content that you are comfortable sharing under the terms of the Privacy Policy and Terms of Use.
When using Piazza, be respectful to your instructors and fellow students. Offensive language and threatening behavior will not be tolerated. Keep in mind that when posting "anonynomously", you are anonymous only to other students, but not to the instructors.