University of Toronto Scarborough,
Department of Computer and Mathematical Sciences
CSCB63H Design and Analysis of Data Structures
Winter 2013


Announcements Assignments CourseInfo FAQ Forum TimeTable Links


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


If you have a question, please check first the frequently asked questions and the forum to see if your question is already answered. Please try to post non-personal questions like (e.g. clarification requests about assignments, explanation requests for topics covered in lectures, etc.) on the forum so other students can also benefit from them. If you are sending an email to us please read this note so we don't miss your email.


Course Info

Instructor
Name: Kaveh Ghasemloo
Email: cscb63
Office: IC467
Teaching Assistants:
Names: Bahar Aameri, Jan Gorzny, Anya Tafliovich
Lectures
When: Mondays 1PM-3PM Mondays 1PM-2PM and Wednesday 2PM-3PM
Where: SW128 IC220
Tutorials
When: Thursdays, 2PM-3PM
Where: IC208
When: Tuesdays, 4PM-5PM
Where: HW408
Office Hours (by Anya Tafliovich)
When: Mondays 2PM-3PM, Thursdays 3PM-5PM, Fridays 11AM-Noon, and 1PM-2:30PM
Where: IC495
Office Hours (by Kaveh Ghasemloo)
When: Mondays 3PM-4PM
Where: IC467
or email the instructor for an appointment.
Course Website
http://www.cs.toronto.edu/~kaveh/cscb63h/
http://j.mp/cscb63h
Course Forum
Discussion/Bulletin Board for CSCB63H
We will be monitoring the board regularly to answer your questions.
Textbook
Goodrich M.T. and Tamassia R., "Algorithm Design, Foundations, Analysis, and Internet Examples", 2001.
Supplementary Book
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.
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
Design, analysis, implementation and comparison of efficient data structures for common abstract data types. Priority queues: heaps and mergeable heaps. Dictionaries: balanced binary search trees, B-trees, hashing. Amortization: data structures for managing dynamic tables and disjoint sets. Data structures for representing graphs. Graph searches.
(from UTSC Calender)
Tentative Course Outline
Core: 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 and probabilistic algorithms (QuickSort);
Depending on time: Lower-bounds (decision trees and lower-bounds for comparison based sorting).
Prerequisites
CSCB07H3,
CSCB36H3,
CGPA 2.5 or enrolment in a CSC Subject POSt.
The prerequisite requirement is strictly enforced in this course.
Exclusion
STA263H1/STA265H1.
Breadth Requirement
Quantitative Reasoning.
Marking Scheme
Marking Scheme
Title Points Notes
Assignments 40

4 assignments, each assignment 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
cscb63w13info.pdf

Time Table

Tentative Time Table
Dates Topics GT CLRS Handouts Notes
Week 1
(Jan. 7   )
Course introduction
Review:
time complexity of algorithms
asymptotic notations
upper & lower bounds (on worst case complexity)
Abstract data types
1.1-3, 2.1-2 1, 2, 3 Bounds
Week 2
(Jan. 14)
Priority queues:
heaps
mergable heaps
2.4 6 Binomial heaps A1 out
Week 3
(Jan. 21)
Dictionaries
Binary search trees:
balanced search trees
2.3, 3.1 12.1-3
Week 4
(Jan. 28)
Binary search trees:
balanced search trees (cont'd)
Augmenting data structures
3.2 14
(using AVL
in place of RB)
AVL trees
A1 due,
A2 out
Week 5
(Feb. 4)
Hashing:
basic definitions
probabilistic analysis of hashing with chaining
2.5 11.1-3, (11.4?)
Week 6
(Feb. 11)
Amortized analysis
Dynamic tables
1.5 17 A2 due
Week 7
(Feb. 18)
Feb. 18: Family Day holiday, University is closed.
Reading Week: no classes.
Week 8
(Feb. 25)
Disjoint sets
4.2 21.1-3 Test,
A3 out
Week 9
(Mar. 4)
Graphs:
basic definitions and data structures
depth-first search (DFS) and applications
breadth-first search (BFS) and applications
6.1-3 22.1-2 BFS
Week 10
(Mar. 11)
Graphs:
depth-first search (DFS) and applications
breadth-first search (BFS) and applications
6.3 (6.4?) 22.3-4, (22.5?) A3 due,
A4 out
Week 11
(Mar. 18)
Graphs:
minimum spanning trees (MST) and applications
7.3 23, 35.2 MST
Week 12
(Mar. 25)
Deterministic algorithms with probabilistic inputs vs. randomized algorithms:
Quicksort
4.3 5.1-3 (5.4?),
7.1-3 (7.4?)
A4 due
Week 13
(Apr. 1)
Lower bounds:
decision trees
lower bounds for sorting
adversary arguments
lower bounds for the Min-Max problem
4.4 8.1, 9.1 Min-Max
Week 14
(Apr. 8)
Apr. 8: Classes end, no lecture scheduled.
Study Break.
TakeHome due
Apr. 15–
Apr. 30
Final examinations.

Announcements

Apr. 24, 2013:
The course has ended. We hope that you have enjoyed the course. Have a nice summer. :)
The marks are submitted and should appear on Rosi in a few days. Overall course marks information: Total.png, Grades.png, course average: 68%.
Jan. 16, 2013:
We will need knowledge of basic probability theory in some lectures. We will have a tutorial on probability theory, but it will not be a course on probability theory. You can check appendix C of CLRS. We will need most but not all of what is covered in this appendix for this course. In particular, the last section of the appendix about tails of distributions is not needed.
Jan. 13, 2013:
The course website is now online. We still need to update a few things (e.g. how to submit assignments, course time table, links to files, etc.), don't forget to check the website and the forum next week before the tutorial.
Prerequisite waiver: Please check the prerequisite waiver policy if you need one. We will check them over the next weekend and let you know the result.
Jan. 1, 2013:
Course starts on Jan. 7.
Students should check this page and the forum regularly for new announcements (at least once a week).
Please read the FAQ.

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 "CSCB63", e.g. "CSCB63 prerequisite waiver request" or "CSCB63 special consideration request for test". We may miss emails without subject line starting with "CSCB63".
Please send email only from your official University of Toronto email address when contacting us if you want to receive a reply, this is required by regulations, we cannot reply to any other email address.
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.
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 "cscb63h" and "winter2013" 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 to compute your mark for the missed homework.
If you are emailing the forms the subject line of your email must start with "CSCB63 special consideration request".
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. Please check the policy and information about Student Medical Certificate on UofT Health Services.
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.
If you are emailing the forms the subject line of your email must start with "CSCB63 special consideration request".
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.
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) after the papers are returned. 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.

Assignments

How to submit assignments:
Assignments must be typed and a PDF copy must be submitted for marking using MathLab's submit command . Programming assignments should be submitted in separate files. The filenames 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". For programming assignments, your python/java program submission must be "A1sol.py" or "A1sol.java".
Include you student number inside your files.
To submit your files, log on to mathlab, then use the following command to submit your files:
submit -c cscb63w13 -a A1 -f FILE
For example, for assignment A1 use the following commands.
submit -c cscb63w13 -a A1 -f A1sol.pdf
submit -c cscb63w13 -a A1 -f A1sol.tex
submit -c cscb63w13 -a A1 -f A1sol.py
submit -c cscb63w13 -a A1 -f A1sol.java


Two extra days for using LaTeX:
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. Wednesday in place of Monday). You have to submit both the PDF and TeX file to use the extension. Make sure you submit the right PDF file. We will mark only your submitted PDF file. TeX file will not be used for marking under any situation, it will be only used for checking that you have used LaTeX. 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.

Programming assignments:
Each programming assignment will describe an algorithmic task to be solved, the precise format of input and output. Make sure your program compiles and works correctly on MathLab machines. Any submission that:

  • does not compile,
  • produces a runtime error,
  • does not adhere to the precise input/output format,

will not get any marks. Marks are earned based on passing (producing correct answer for) 20 test cases. For each test case that your program produces the correct output in the allocated runtime you get 5% of the assignment's mark.
You are free to write your answers in Python, Java, but be warned that Python programs might be at a disadvantage in terms of speed.
The runtime limit of the problem is there to test if you have implemented the fastest algorithm for the problem and is designed to be tight. A suboptimal algorithm, or a particularly poor implementation is not supposed to pass all the tests. (But if you can't figure out or implement the fastest algorithm feel free to submit a slower implementation; you will get the marks from the easier test cases.)
Java submissions are run using the following two commands. First we run "javac A1sol.java" to compile your submission. Then we run "java A1sol" (in the linux shell) to run it. We will NOT run the submissions in the NetBeans shell or anything like that.
The input should be read from standard input. The output should be written to standard output. The output must have exactly the same structure as the example given. No extra output other than those described should be written.
No late assignments will be accepted.

Assignment 1 (10 points)
Due: Monday, Jan. 28, 10PM
Topic: Review, Heaps ()
Questions: A1.pdf
Solutions: A1Q4tester.zip, A1sol.pdf
Marker's Remarks: A1mr.pdf
Marks: A1.png, average: 63.4
Assignment 2 (10 points)
Due: Monday, Feb. 18, 10PM Monday, Feb. 11, 10PM
Topic: BST (), Augmentation ()
Questions: A2.pdf
Solutions: A2sol.pdf
Marker's Remarks: A2mr.pdf
Marks: A2.png, average: 59.25
Assignment 3 (10 points)
Due: Wednesday, Mar. 13, 10PM Monday, Mar. 11, 10PM
Topic: Hash (), Amortized Analysis ()
Questions: A3.pdf
Solutions: A3sol.pdf
Marker's Remarks: A3mr.pdf
Marks: A3.png, average: 55.9
Assignment 4 (10 points)
Due: Monday, Apr. 1, 10PM Monday, Mar. 25, 10PM
Topic: Disjoint Sets (), Graphs (), BFS ()
Questions: A4.pdf
Solutions: A4sol.pdf
Marker's Remarks: A4mr.pdf
Marks: A4.png, average: 70
Assignment 5 (0 points, sample questions for practice)
Due: NA
Topic: DFS (), MST (), Probabilistic ()/Randomized Algorithms()
Questions: A5.pdf
Solutions: TBA
Marker's Remarks: NA
More practice questions:
Check the homeworks for CSC263 Winter 2013 by Prof. Sam Toueg

Test

Test (20 points)
When: Feb. 25, 1PM-2PM
Where: SW128
Questions: T.pdf
Solutions: Tsol.pdf
Marker's Remarks: Tmr.pdf
Marks: Test.png, average: 58.46
Notes:
No aids permitted.

Take Home

Takehome (10 points)
Due: Monday, Apr. 8, 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 your topic and a link to your reference. Use the subject line "CSCB63 takehome topic" for your email and send it to the instructor's email address provided above. 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.) The takehome should be submitted similar to the assignment. Use "THsol.pdf" as your filename.
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 0
B-tree 4
B+ tree 4
Bloom filter 4
Fibonacci heap 4
Red–black tree 4
Scapegoat tree 4
Splay tree 4
Tango tree 1
Skip list 4
Fusion tree 0
Soft heap 1
Pairing heap 0
Treap 2
Trie 4
Radix tree 4
Suffix tree 1
Exponential tree 1
Other Topics... 1

Final Examination (40 points)

Final Examination (40 points)
When: Tuesday, Apr. 16, 2013, 9:00AM-12:00PM
Where:SW309
Questions: FE.pdf (slightly edited version)
Marks: FE.png, average: 55
Notes:
No aids permitted.
UTSC 2013 April Examination Schedule


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 April 24, 2013.

Valid HTML 4.01 Strict Valid CSS!