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 nonpersonal 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:
 Office: IC467
 Teaching Assistants:
 Names: Bahar Aameri, Jan Gorzny, Anya Tafliovich
 Lectures
 When: Mondays 1PM3PM
Mondays 1PM2PM and Wednesday 2PM3PM  Where: SW128
IC220  Tutorials
 When: Thursdays, 2PM3PM
 Where: IC208
 When: Tuesdays, 4PM5PM
 Where: HW408
 Office Hours (by Anya Tafliovich)
 When: Mondays 2PM3PM, Thursdays 3PM5PM, Fridays 11AMNoon, and 1PM2:30PM
 Where: IC495
 Office Hours (by Kaveh Ghasemloo)
 When: Mondays 3PM4PM
 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, Btrees, 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: Lowerbounds (decision trees and lowerbounds 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
Dates  Topics  GT  CLRS  Handouts  Notes 

Week 1 (Jan. 7 ) 

1.13, 2.12  1, 2, 3  Bounds  
Week 2 (Jan. 14) 

2.4  6  Binomial heaps  A1 out 
Week 3 (Jan. 21) 

2.3, 3.1  12.13  
Week 4 (Jan. 28) 

3.2  14 (using AVL in place of RB) 
AVL trees 
A1 due, A2 out 
Week 5 (Feb. 4) 

2.5  11.13, (11.4?)  
Week 6 (Feb. 11) 

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) 

4.2  21.13  Test, A3 out 

Week 9 (Mar. 4) 

6.13  22.12  BFS  
Week 10 (Mar. 11) 

6.3 (6.4?)  22.34, (22.5?)  A3 due, A4 out 

Week 11 (Mar. 18) 

7.3  23, 35.2  MST  
Week 12 (Mar. 25) 

4.3  5.13 (5.4?), 7.13 (7.4?) 
A4 due  
Week 13 (Apr. 1) 

4.4  8.1, 9.1  MinMax  
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 is the preferred way to contact the instructor and the teaching assistants for personal issues. For nonpersonal 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 sameday 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 makeup 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 reexamine 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
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 highlevel 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 highlevel 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 Btree 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:00AM12:00PM
 Where:SW309
 Questions: FE.pdf (slightly edited version)
 Marks: FE.png, average: 55
 Notes:
 No aids permitted.
 UTSC 2013 April Examination Schedule
Links
 UTSC Resources
 UTSC Important Dates
 Course Websites from Previous Years
 CSC263H1 Fall 2012: Data Structures and Analysis by Kaveh Ghasemloo
 CSC263H1 Spring 2012: Data Structures and Analysis by Prof. Sam Toueg
 CSC263H1 Fall 2011: Data Structures by Prof. Toniann Pitassi and Prof. Faith Ellen
 CSC265H1 Fall 2011: Enriched Data Structures by Prof. Toniann Pitassi and Prof. Faith Ellen
 CSC263H1 at UTM Spring 2010 : Data Structures and Analysis by Prof. Avner Magen
 Sample Questions/Solutions
 Previous CSC263H Final Exam Questions from UofT Library
 Previous CSC265H Final Exam Questions from UofT Library
 Selected Solutions for Exercises/Problems from CLRS website
 TrueShelf
 LaTeX Resources
 TeXLive, a cross platform TeX/LaTeX distribution
 LEd, editor for Windows
 Kile, editor for Linux/Unix
 TeXShop, editor for Mac
 TeXMaker, cross platform editor
 TeX.SX, Q&A site for TeX/LaTeX
 A (Not So) Short Introduction to LaTeX2e
 Symbols accessible from LaTeX
 LaTeX Wikibook
 Comprehensive TeX Archive Network
 Misc
 Computer Science StackExchange, a Q&A site for Computer Science
 WikiBook: Data Structures
 WikiBook: Algorithms
 WikiBook: Fundamental Data Structures by David Eppstein
 Advanced Data Structures by Erik Demaine and André Schulz
 Advanced Data Structures by Jeff Erickson
 NIST Dictionary of Algorithms and Data Structures
 Encyclopedia of Algorithms
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