University of Toronto, Department of Computer Science
CSC263H Data Structures and Analysis
Fall 2012


Announcements Assignments CourseInfo FAQ Forum TimeTable Links


Students should consult this page at least once a week and check for new announcements.

If you have a question, please check first the FAQ and the forum to see if your question is already answered. Please try to post non-personal questions like clarification requests about assignments on the forum so other students can also benefit from them. If you are sending an email to us please check this note.


Course Info

Instructor
Name: Kaveh Ghasemloo
Email: csc263f12
Office: SF4306B
Teaching Assistants:
Names: Michael Dzamba, Aziz Mezlini, Mohammad Norouzi, Chun Kong Yung
Email: csc263f12ta
Lectures
When: Thursdays 10AM-12PM
Where: LM161
Tutorials
When: Tuesdays 10AM-11AM
Where: LM161
Office Hours (by TAs)
When: Tuesdays 11AM-12PM
Where: BA2230
Office Hours (by Instructor)
When: Thursdays 12PM-1PM
Where: BA2230
or email the instructor for an appointment.
Course Website
http://www.cs.toronto.edu/~kaveh/csc263h/
http://j.mp/csc263h
Course Forum
Discussion/Bulletin Board for CSC263H
Teaching assistants will be monitoring the board regularly to answer your questions.
Textbook
T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, "Introduction to Algorithms", 3rd. ed., 2009.
Errata page for the book.
Online access to the 2nd edition is available to UofT students through the UofT library.
We will be using the 3rd edition of the book. Buying a copy is a good investment and is strongly encouraged.
Supplementary Book
Goodrich M.T. and Tamassia R., "Algorithm Design, Foundations, Analysis, and Internet Examples", 2001.
Course Goals
Data structures are ways of organizing the data involved in computation, suitable for representation in and manipulation by computers. Algorithms are precisely stated, general problem solving methods. Data structures and algorithms are central to computer science. They are also integrally related: neither can be studied fruitfully without knowledge of the other. This course has two goals: First, to survey several important data structures and algorithms; and second, to introduce the basic tools and techniques for the analysis of algorithms and data structures.
Course Description
Algorithm analysis: worst-case, average-case, and amortized complexity. Expected worst-case complexity, randomized quicksort and selection. 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 and comparison of data structures. Introduction to lower bounds.
(from undergraduate handbook)
Tentative Course Outline
Review of time complexity of algorithms and asymptotic notation; upper and lower bounds on algorithm complexity; Abstract data types; Priority queues; Dictionaries; Binary search trees; Balanced search trees; Augmenting data structures; Hashing; Disjoint sets; Amortized analysis; Dynamic tables; Graphs; BFS; DFS; MST; Randomized algorithms (QuickSort); Lower bounds (decision trees and lower- bounds for comparison based sorting).
Prerequisites
CSC207H1, CSC236H1/CSC238H1/CSC240H1, STA247H1/STA255H1/STA257H1,
CGPA 1.5/enrollment in a CSC subject POSt.
The prerequisite requirement is strictly enforced in this course.
Marking Scheme
Marking Scheme
Title Points Notes
Assignments 40

4 assignments, each worth 10 points.

Tests 20

Take Home 10

Optional, see the instructions below.

Final Exam 40

To pass this course you must get at least 40% in the final exam.

Total 110

Anyone with score above 100 points will get 100 points (the extra points are bonus).

Course Information Sheet
csc263f12info.pdf

FAQ and General Remarks

Email
Email is the preferred way to contact the instructor and the teaching assistants for personal issues. For non-personal issues please try to post on the forum so other students can also benefit from them.
Feel free to email the instructor regarding any course related issues.
Please use only the email addresses provided in the course info section.
Please use informative subject lines for your emails and include "[CSC263]", e.g. "[CSC263] a question about asymptotic complexity" or "[CSC263] clarification request for assignment 1". We may miss emails without subject line starting with "[CSC263]".
Please send email only from your official University of Toronto email address when contacting us if you want to receive a reply.
We will try to answer your emails in 3 working days. Please do not rely on getting same-day answers.
How to ask questions outside lectures/tutorials
Please try to post your question on the forum as much as possible so other students can also benefit from them.
You can also ask questions by coming to an office hour or emailing the TAs or the instructor.
The Undergraduate Help Center (located in BA2230) is open from Monday-Thursday 4-6pm. You can drop by the Help Center to ask questions.
You can also post questions on online Q&A sites like Computer Science - StackExchange.
Accessing files in the restricted areas of this website
If needed use "csc263h" and "fall2012" to access the files on this website.
Late homework policy
No late homeworks will be accepted.
If you miss a homework deadline because of a medical or personal emergency, you must fill out the Special Consideration Form. In case of a medical emergency, you must also submit the U of T Student Medical Certificate, completed and signed by your physician. Please check the policy and information about Student Medical Certificate on UofT Health Services.
If we judge your reason for missing the deadline to be valid, we will use the average mark you achieved in other homeworks as your mark for the missed homework.
Missed test policy
If you miss the test due to a medical or other serious emergency, get in touch with your instructor immediately, and fill out the Special Consideration Form. In case of a medical emergency, you must also submit the U of T Student Medical Certificate, completed and signed by your physician. There will be no make-up test, but if we consider your reason for missing the test to be valid, we will use your final examination mark to compute your mark for the missed midterm test.
Tutorial attendance
Attendance in tutorials is as mandatory as attendance in lectures. A formal attendance is not taken in neither. However, there will be new material that is presented only in tutorials and not discussed in the lectures for which you are responsible and in which you may be tested in homeworks or exams.
Prerequisite
The prerequisite requirement is strictly enforced in this course.
If you do not satisfy it, you must contact the instructor and submit a petition for a waiver within the first week of class.
You must be already in the list of the students provided by the undergraduate office (UGO), we can only give a waiver to students on the list. If you are on the list and not satisfy prerequisite you should receive an email from them. If you haven't please contact the UGO directly.
Your petition should include the following information:
  • Your full name,
  • Your student number,
  • The specific prerequisite that you are requesting a waiver for,
  • The reason for requesting a waiver,
    i.e. explain why you need a waiver and why you have not completed the prerequisite,
  • Explain why you know the material covered by the prerequisite.
We will grant a waiver only in exceptional cases where we have enough confidence based on the information you have provided that you will not suffer in this course because of not completing the required prerequisite. In addition, you should provided good reasons for why you have not taken the prerequisites before taking this course. Please submit one email explaining all relevant information, the decisions are final, we will not consider any information provided later. Submitting a request doesn't mean that you will receive a waiver. If you are making any plans, you should do so assuming that your request is going to be rejected.
If you receive a waiver it will be your responsibility to learn any material needed from the prerequisite. Throughout the course the assumption will be that students are familiar with material from the prerequisite.
Accessibility
The University of Toronto is committed to accessibility. If you require accommodations or have any accessibility concerns, please visit Accessibility Services as soon as possible to make any required arrangements.
Remark request policy (for assignments/test)
You can ask for remarking if you believe there is a mistake in the marking. If your request concerns a simple addition error or similar kind of errors, see the instructor.
For any other kind of remarking request, you must submit your request in written form. To submit a remark request, please print and fill the remark request form, attach it to your paper, and give it to the instructor. In the explanation section of the form, specify the question and the part you are requesting a remarking, and explain briefly and clearly which part of marking you disagree with and why.
You should submit your remark request at most one week (7 days) before the final exam. Remark requests after this date will not be accepted.
We will look at all remark request, however please try to submit a remark request only when you believe the remarking will result in a significant increase your mark, e.g. please don't submit a remark request if the total increase that can result from your remark request is less than 1% of your final grade.

Reminder: A remarking request can cause the overall mark to stay the same, increase or decrease: we may re-examine every question in the paper and if new mistakes are found they can also change the marking up or down accordingly. Please submit a remarking request only if: (a) you have read and completely understood our posted solution set, and (b) you still think that your solution is correct and was mistakenly marked as incorrect. We rarely if ever accept remarking requests of the type ``yes, my solution is not correct, but I think you took off too many marks for this mistake'': The marking scheme was decided and applied as uniformly as possible to all students. If you believe a marking scheme is too harsh, it is still fair as long as it is consistently applied, we will adjust the marks (by adding points to everyone) if the marks are unexpectedly low because of marking scheme being harsh.

Time Table

Tentative Time Table
Dates Topics Relevant Chapters Handouts Notes
Week 1
(Sept. 11, 13)
Course introduction
Review:
time complexity of algorithms
asymptotic notations
upper & lower bounds (worst case complexity)
Abstract data types
1, 2, 3 Bounds
Week 2
(Sept. 18, 20)
Priority queues:
heaps
mergable heaps
6 Binomial heaps A1 out
Week 3
(Sept. 25, 27)
Dictionaries
Binary search trees:
balanced search trees
12.1-3
Week 4
(Oct. 2, 4)
Binary search trees:
balanced search trees (cont'd)
Augmenting data structures
14 (using AVL in place of RB) AVL trees A1 due,
A2 out
Week 5
(Oct. 9, 11)
Hashing:
basic definitions
probabilistic analysis of hashing with chaining
11.1-3, (11.4?)
Week 6
(Oct. 16, 18)
Disjoint sets
21.1-3 A2 due
Week 7
(Oct. 23, 25)
Amortized analysis
Dynamic tables
17
Week 8
(Oct. 30, Nov. 1)
Graphs:
basic definitions and data structures
breadth-first search (BFS) and applications
22.1-2 BFS Test,
A3 out
Week 9
(Nov. 6, 8)
Graphs:
depth-first search (DFS) and applications
22.3-4, (22.5?)
Week 10
(Nov. 13, 15)
Graphs:
minimum spanning trees (MST) and applications
23, 35.2 MST A3 due,
A4 out
Week 11
(Nov. 20, 22)
Deterministic algorithms with probabilistic inputs
vs. randomized algorithms:
Quicksort
5.1-3 (5.4?), 7.1-3 (7.4?)
Week 12
(Nov. 27, 29)
Lower bounds:
decision trees
lower bounds for sorting
adversary arguments
lower bounds for the Min-Max problem
8.1, 9.1 Min-Max A4 due
Week 13
(Dec. 4)
4 short lectures on lower bounds
by Professor Faith Ellen for CSC265H1
1. Introduction and Comparison Trees
2. Information Theory
3. Adversary Arguments
4. Reductions
Guessing Game mentioned at the end of Part 2
TakeHome due

Announcements

The course is finished. I hope that you have enjoyed the course. Have a great holiday.
Dec. 14, 2012
Concerns about the final exam:
I know that some of you are concerned about the final exam and feel that you haven't done well. I haven't looked at the papers yet, however I expect that in general the marks for final exam to be considerably better than those for the midterm. However, as I said before if I see that the marks for the final exam are lower than I am expecting, I will adjust the marks by adding points to everyone to make sure the marks are reasonable, so don't worry too much about the marks.
Takehome:
I will post the marks for takehome by next weekend to CDF.
Picking up assignments/tests:
If you haven't picked up your assignments/test papers, you can do so on next Tuesday. I will be in my office from 1PM-3PM.
Dec. 12, 2012:
Office hour
Due to conflicts we have to move the office hour. The office hour will be held 12PM-3PM in the help center if it is possible. If we can't use the room then we will move to my office (SF4306B).
Picking up assignment/test
If you haven't pick up your papers you can drop by during the office hour to pick up your assignments.
Remark requests
The time for submitting remark requests for A3, A4 is extended till next Tuesday. Please follow the instructions for asking a remark request.
Marks on CDF
Marks posted on CDF are raw marks. In other words, if you have submitted a remark request or special consideration request they are not applied to the marks posted there.
Exam
Don't forget the final exam is Friday 9AM-12PM .
Lower-bounds
If you have missed the tutorial on lower-bounds, you can find the example here.
Dec. 4, 2012:
Course evaluations

Online course evaluations are in process! And in response to student requests, we have extended the deadline for your responses to Sunday, December 9th.

To complete your course evaluations, please check the email account associated with your UTORid/ROSI account (the email account from which you receive official university communications) for a direct link to your course evaluations. This email will have arrived on Friday, November 23 from “Course Evaluations” (course.evaluations@utoronto.ca).

If you have not received this email and have your utoronto.ca or mail.utoronto.ca email address set to forward your emails to a Gmail (or similar) account, please log in directly to your utoronto.ca or mail.utoronto.ca email account to check for an email from “Course Evaluations” (course.evaluations AT utoronto.ca).

Course evaluations are very important. They are used in the tenure and promotion process for your instructors, and instructors use the results to change and improve courses. The Faculty of Arts & Science also has a long history of sharing evaluation results with students, to help them in making course selections. Make sure that you provide your input on teaching at the UofT!

Nov. 30, 2012:
Lower-bounds:
There will be a tutorial next week. The topic of the tutorial will be lower-bounds. This tutorial is important, there will be a question about lower-bounds in the final exam, so you should attend this tutorial. I have also posted 4 video lectures by Professor Faith Ellen about lower-bounds that she has prepared for CSC265, around 25min in total, I strongly recommend watching them, however keep in mind they are more advanced than what we need, they are designed for the enriched version of this course.
Final Exam:
There are going to be 9 questions in the final exam, the questions will be similar to questions from exams from previous years and assignments (there won't be a question similar to question 1 in the test), the exam is going to be 3 hours long, you can bring an aid sheet similar to the one for the test (details), there will be roughly one question from each topic.
Office Hours:
The weekly office hours by the instructor will continue during the study and exam period, there will be one on Dec. 6 and another one on Dec. 13.
Remarking:
Remarking request form is available.
Nov. 29, 2012:
If you haven't picked up your test paper or assignments A1, A2, A3, you can pick them up today from my office until 3PM or next week during the tutorial or office hours.
Oct. 25, 2012:
Test:
The test is next week. There will be 3 questions. The duration of the test will be one hour. Please be on time. The difficulty of the questions will be similar to the questions you have solved in the assignments. For sample questions please check the links section.
I will be holding an extra office hour next week on Monday afternoon 2PM-3PM. The location will be the same as usual (Help Center, 2nd floor of Bahen Center). Feel free to drop by to ask questions.
Picking up your assignments:
If you haven't picked up yout first assignment yet, you can do so after the lecture or during my office hour.
The second assignment is being marked and hopefully I can return it to you on Monday.
Oct. 14, 2012:
Seeking online help in doing assignments is forbidden:
I have seen a student has posted an assignment question online. Remember that you are not allowed to seek help in written form. That means you are not permitted to post assignment questions online and/or seek help over the Internet in solving them.
The goal of the assignments is to make sure you understand the course material and learn problem solving skills. You should spend some time thinking about assignments alone and try to do the assignment on yourself before seeking help from any other resource.
If you don't spend time thinking about assignments yourself it is very likely that you will not learn these problem solving skills. As a result you will have trouble in the test/final exam. Note that to pass this course you have to get at least 40 out of 100 in the final independent of how you have done in the assignments.
Moreover if I see that academic dishonesty is endemic I will have to take measures to make sure the final grades faithfully reflect the knowledge and skills of students. For example, I may need to make the questions on the test/final more difficult.
Additionally, violating the course's policy is an academic offense. Any case that I will become aware of will be dealt with according to university's academic offense policy. That means I have to report it to the dean (and they will decide about what disciplinary action will be taken, and punishment can go as far as being expelled from university, see Advice About Academic Offences for more information about the process).
I strongly advice you to read the Policy Regarding Plagiarism and Academic Offense and make sure you follow it. If you are in doubt about what is permitted and what is not permitted feel free to ask them on the forum or by email.
Oct. 4, 2012:
Accessibility Services has asked me to post the following request:

There is a student in this class who requires a volunteer notetaker as an accommodation for a disability. By signing up and posting your notes, you can make a significant difference for this individual’s capacity to fully participate in this course. To sign up go to: http://www.studentlife.utoronto.ca/accessibility/pcourselist.aspx or come in person to Accessibility Services 215 Huron St. Suite 939.

Many students notice the quality of their notetaking improves through volunteering.

You will also receive a certificate of recognition.

Please also check Note-Taking Services: Online.
Sept. 19, 2012:
Background information for the course: Please skim through the appendices of the book to make sure you know the background we will need in this course and can follow the lectures. You should know almost all of the topics in the appendices from previous courses you have taken and it shouldn't take you much time to remind them to yourself. Feel free to ask questions about them on the course forum if you have trouble or some part is not clear.
Sept. 17, 2012:
Tentative course time table is now available.
Prerequisite waiver: I have gone over the list of students requiring a prerequisite waiver provided to me by the undergraduate office (UGO) and have informed them about my decisions. You can contact the office to check if you have got a waiver. You should have received an email from UGO if you were on the list. Note that I cannot provide a waiver for people who are not on the list provided to me by UGO. Please contact UGO.
Sept. 13, 2012:
The course website is now online. I still need to update a few things (e.g. how to submit assignments, course time table), don't forget to check the website next week before the tutorial.
Prerequisite waiver: If you have emailed me to get a prerequisite waiver, I will check them over the weekend. I will let you know if receive a waiver by next week. I will grant a waiver only in exceptional cases where I have enough confidence based on evidence you have provided that you will not suffer in this course because of not having the required prerequisites. In addition, you should have provided good reasons for why you have not taken the prerequisites before taking this course.
Note: AFAIK, the course will be available in the next semester (Spring 2013) (you should check with the undergraduate office to be sure).
Sept. 11, 2012:
Today's tutorial will be an introductory session to the course. I will explain logistics (marking scheme, etc.).
We will also review chapters 1, 2, and 3 from the textbook (CLRS). Please go over the chapters to make sure you understand them. Feel free to ask question if something is not clear for you or have trouble understanding any part.
Sept. 10, 2012:
Course starts on Sept. 11.
Students should check this page regularly (at least once a week) for new announcements.

Assignments

Assignments must be typed and a PDF copy must be submitted for marking using CDF's submit command or website. The filename must be the assignment's name followed by "sol", e.g. your submission for the assignment "A1" must be "A1sol.pdf". (Similarly the filename for your TeX file must be "A1sol.tex".)
Using LaTeX is strongly encouraged. If you use LaTeX (use sample.tex and csc_assignment.cls) then you will have two extra days to submit your assignment (i.e. Thursday in place of Tuesday). You have to submit both the PDF and TeX file to use the extension. Check also the LaTeX links section. If you are using another program to write your assignment, the output must be similar to the following sample: sample.pdf.
No late assignments will be accepted.

Assignment 1 (10 points)
Due: Tuesday, Oct. 2, 10PM
Topic: Review, Heaps (6)
Questions: A1.pdf
Solutions: A1sol.pdf
Marker's Remarks: A1mr.pdf
Assignment 2 (10 points)
Due: Tuesday, Oct. 16, 10PM
Topic: BST (12, AVL), Augmentation (14)
Questions: A2.pdf
Solutions: A2sol.pdf
Marker's Remarks: A2mr.pdf
Assignment 3 (10 points)
Due: Tuesday, Nov. 13, 10PM
Topic: Hash (11), Disjoint Sets (21), Amortized Analysis (17)
Questions: A3.pdf
Solutions: A3sol.pdf
Marker's Remarks: A3mr.pdf
Assignment 4 (10 points)
Due: Tuesday, Nov. 27, 10PM
Topic: Graphs (22.1), BFS (22.2), DFS (22.3), MST (23.1)
Questions: A4.pdf
Solutions: A4sol.pdf
Marker's Remarks: A4mr.pdf
Assignment 5 (0 points, sample questions for practice)
Due: None
Topic: MST (23.2), Probabilistic (5)/Randomized Algorithms(7), Lower-Bounds (8.1, 9.1)
Questions: A5.pdf
Solutions: A5sol.pdf
Marker's Remarks: NA

Test

Test (20 points)
When: Tuesday, Oct. 30, 10AM-11AM
Where: LM161
Questions: T.pdf
Solutions: Tsol.pdf
Marker's Remarks: Tmr.pdf
Notes:
You are permitted to bring a 8.5"x11" aid sheet, handwritten on both sides.

Take Home

Take Home (10 points)
Due: Tuesday, Dec. 4, 10PM
Questions: See the instructions below.
Sample file: THsample.tex, THsample.pdf
Instructions:
For takehome you have to write a short (2 pages long) brief high-level essay (no need for details) about an advanced data structure. The main goal is to get you familiar with some advanced data structure. You should explain the ADT, the running time of operations, comparison with other similar data structures (advantages and disadvantages), an application, and a high-level idea of how the data structure is implemented. Select an advanced data structure as your topic (something which we will not cover in this course) from the references listed below and send an email to the instructor about our topic and a link to your reference. Each topic can be selected a limited number of times. You should get a confirmation email form the instructor before starting working on a topic. (Other references might also be acceptable.)
Resources
WikiBook: Fundamental Data Structures by David Eppstein
Advanced Data Structures by Erik Demaine and André Schulz
Advanced Data Structures by Jeff Erickson
Takehome Topics
Topic Reference Selected by
van Emde Boas tree 1
B-tree 4
B+ tree 4
Bloom filter 4
Fibonacci heap 4
Red–black tree 4
Scapegoat tree 4
Splay tree 4
Tango tree 4
Skip list 4
Fusion tree 3
Soft heap 4
Pairing heap 1
Treap 3
Trie 4
Radix tree 1
Suffix tree 4
Exponential tree
Other Topics...

Final Examination (40 points)

Final Examination (40 points)
When: Friday, Dec. 14, 9AM-12PM
Where: SS1083 & SS1085, Examination Locations
Questions: FE.pdf
Notes:
You are permitted to bring a 8.5"x11" aid sheet, handwritten on both sides.
Faculty of Arts and Sciences 2012 December Examination Schedule
Faculty of Arts and Sciences 2012 Examination Schedule
Faculty of Arts and Sciences Examination Reminders
Faculty of Arts and Sciences Examination Rules


Policy Regarding Plagiarism and Academic Offense

University of Toronto has strict rules against plagiarism. You must not submit work belonging to others as yours. It is considered an academic offense and will be dealt with accordingly. The work you submit must be your own, if you are going to get help from any resource (books, online resources, people including other students, ...) other than the course material (textbook, course lecture notes) you must acknowledge them explicitly and give proper credit to them in your work.

For this course, you have the permission to discuss and work on assignments together with other students, but you must prepare the written solutions alone. It is fine to get help to understand, but the work you submit must represent your understanding in your words. You must be able to explain what you have submitted to the instructor orally without any previous preparation or notice during the semester. To make sure that you are writing what you have understood in your own words, don't take any notes from your discussions, wait a few hours before writing any notes related to them, and do not show your written answers to other students before due dates. Copying assignments and allowing others to copy your assignment are strictly forbidden.

For more information see Advice About Academic Offences by Jim Clarke


This page was last updated on Dec. 14, 2012.

Valid HTML 4.01 Strict Valid CSS!