CSC263H1S 20231 (All Sections): Data Structures and Analysis

Jump to Today

↓ Contents ↓

Feeling Ill? Missed some work?

Course instructors cannot grant Special Consideration for Final Examinations! If you are unable to write the final exam, please contact your College Registrar for the next steps — the process is explained in more detail on the Sidney Smith Commons.

For all other situations, the Special Consideration section below explains what you must do to receive any form of special consideration (including extensions on problem sets). Please read it carefully and follow the instructions to submit your requests.

The Term Tests and Final Exam section below explains how we handle tests missed for unexpected reasons outside your control.

If you are sick, please complete a self-assessment before you show up to a class or test/​exam!

↓ Contents ↓

Got A Question?

Please do NOT use Quercus messaging!

  1. Before you ask your question, please take a few minutes to see if it might already be answered on this page (or pages linked from it). You will get an answer faster (no need to wait), and it will make the course better for everyone by leaving us more time to answer other questions.
  2. In particular, all course announcements will be posted here, on Quercus. You are responsible for reading all announcements made by the instructor or the TAs, and for being familiar with the entire content of this Syllabus — please take a few minutes at the beginning of the term to read through the entire Syllabus.
  3. If your question is NOT already answered within this document or other parts of the Quercus site, then either:
    • Start a new topic on Ed (the course discussion board), for all questions of general interest (whose answer could be useful to other students) that do not reveal any idea or part of a solution to an assessment. OR
    • Send email from your U of T email address to csc263-2023-01@cs.toronto.edu, for all questions that are personal (whose answer is useful only to you) or that you cannot ask without revealing part of your solution to a course assessment. Please include “CSC263” in the subject line, and your full name and UTORid in the body of your message.
  4. We aim to respond to all email and forum postings within 48 business hours (not counting weekends and holidays). However, it may take longer, especially near due dates. If you do not hear back after four days, please do not hesitate to send a follow-up email, or come in person during office hours.

Table of Contents

This page contains LOTS of information, all in one place (to make it easier to search)! The following links may help you find what you are looking for a little faster — but we strongly recommend that you read this entire syllabus at least once (during the first week of term would be ideal), to make yourself familiar with the course organization and expectations.

↑ Contents ↑

Overview

All readings refer to Chapters, Appendices, or Problems in the textbook.

Week-by-week overview of course activities
Dates & Topics Readings & Materials Assessments
Jan 09 – Jan 13
Runtime Analysis		 Ch. 5.1, 5.2 (review Ch. 2, 3, 4, App. C)
Slides: LEC0101 / LEC0201 / LEC0301 / LEC5101
Jan 16 – Jan 20
Priority Queues; Heaps
(Jan 22: last day to enrol)		 Ch. 6
Slides: Blank / LEC0101 / LEC0201 / LEC0301 / LEC5101		 Problem Set 1
(2% / Jan 20)*
Jan 23 – Jan 27
Dictionaries; Binary Search Trees		 Ch. 12.1, 12.2, 12.3
Slides: Blank / LEC0101 / LEC0201 / LEC0301 / LEC5101		 Term Test 1
(≈9% / Jan 27)†
Jan 30 – Feb 3
AVL Trees		 Ch. 13.2, Prob. 13-3
Slides: Blank / LEC0101 / LEC0201 / LEC0301 / LEC5101		 Problem Set 2
(2% / Feb 3)*
Feb 6 – Feb 10
Augmentation (Ordered Sets); Hashing		 Ch. 14.1, 14.2, 11
Slides: Blank / LEC0101 / LEC0201 / LEC0301 / LEC5101		 Term Test 2
(≈9% / Feb 10)†
Feb 13 – Feb 17
Hashing; Quicksort		 Ch. 11, 5, 7
Slides: Blank / LEC0101 / LEC0201 / LEC0301 / LEC5101		 Problem Set 3
(2% / Feb 17)*
Feb 20 – Feb 24 Reading Week: no lectures; no tutorials.
Feb 27 – Mar 3
Amortization; Dynamic Tables		 Ch. 17
Slides: Blank / LEC0101 / LEC0201 / LEC0301 / LEC5101		 Term Test 3
(≈9% / Mar 3)†
Mar 6 – Mar 10
Graphs; Breadth-First Search		 Ch. 22.1, 22.2
Slides: Blank / LEC0101 / LEC0201 / LEC0301 / LEC5101		 Problem Set 4
(2% / Mar 10)*
Mar 13 – Mar 17
Depth-First Search
(Mar 19: last day to drop)		 Ch. 22.3, 22.4
Slides: Blank / LEC0101 / LEC0201 / LEC0301 / LEC5101		 Term Test 4
(≈9% / Mar 17)†
Mar 20 – Mar 24
Minimum Spanning Trees		 Ch. 23
Slides: Blank / LEC0101 / LEC0201 / LEC0301 / LEC5101		 Problem Set 5
(2% / Mar 24)*
Mar 27 – Mar 31
Disjoint Sets		 Ch. 21
Slides: Blank / LEC0101 / LEC0201 / LEC0301 / LEC5101		 Term Test 5
(≈9% / Mar 31)†
Apr 3 – Apr 7
Lower Bounds
(Apr 7: U of T closed)		 Ch. 8.1, 9.1
Slides: Blank / LEC0101 / LEC0201 / LEC0301 / LEC5101		 Research Survey
(1% / Apr 7)*
Apr 10 Make-Up Day: tutorials for all sections. Problem Set 6
(2% / Apr 10)*
Apr 11 – Apr 28
(see the Exam Schedule)		 Final Exam
(45%)‡
  • * All Problem Sets are due before 21:00 on their due date. You may earn up to 13% in total for the problem sets and research survey, and this can be used to offset marks lost in other work; however, your final course mark cannot exceed 100%!
  • † All Term Tests take place during your regular tutorial time (and in your regular tutorial room). Your lowest term test mark will be worth only 5%; the others will each be worth 10%.
  • ‡ The Final Exam will be scheduled by the Faculty of Arts & Science. In order to pass the course, you must earn at least 25% on the final exam. In other words, if your final exam mark is strictly less than 25%, your final mark in the course will be reduced to no more than 45.

↑ Contents ↑

Logistics

  • This is an in-person course, meaning that you must be available for in-person activities (lectures, tutorials, and office hours) and assessments (term tests and final exam).
  • All lectures, tutorials, and office hours begin ten minutes past the hour.
  • You are welcome to attend office hours held by any instructor or TA.
  • See the technical advice further below, for additional information about connecting to online office hours.
  • TA office hours will NOT follow a regular schedule. The details will be posted here, usually the week before the office hours take place.
  • Recordings will be generated automatically for each lecture, and can be accessed through the OCCS Student App. Remember that course videos and materials belong to your instructor and the University, and are protected by copyright. You are permitted to download videos and materials for your own personal academic use, but you may not copy, share, or otherwise distribute them without explicit permission from the instructor.

↑ Contents ↑

Exam Period Office Hours
Day and Time Instructor / TA Room or Zoom
Tue 11 Apr 14:00–15:00 Angela Zavaleta Zoom Link
Meeting ID: 850 5437 9130
Passcode: 2632023
Tue 11 Apr 16:00–20:00 Yunshun Zhong Room BA 2270
Wed 12 Apr 13:30–15:00 François Pitt Room BA 3289
Thu 13 Apr 10:00–11:00 Angela Zavaleta Zoom Link
Meeting ID: 850 5437 9130
Passcode: 2632023
Thu 13 Apr 16:00–20:00 Mohammad Mozaffari Room BA 2270
Fri 14 Apr 09:30–11:00 François Pitt Zoom Link
Meeting ID: 850 5437 9130
Passcode: 2632023
Fri 14 Apr 11:00–15:00 Vedic Sharma Room BA 2270
Mon 17 Apr 09:30–11:00 François Pitt CANCELLED

↑ Contents ↑

Course Staff & Office Hours (Jan 9 – Apr 7)
Who? (Role) When? Where?
François Pitt (Instructor)
(NO office hour on Feb 20
NO office hour on Apr 10)		 Mon 09:30–11:00 Zoom Link
Meeting ID: 850 5437 9130
Passcode: 2632023
Wed 13:30–15:00 BA 4290
Angela Zavaleta (Instructor) Tue 15:00–16:00
Thu 15:00–16:00		 BA 2283
Amin Gillani (Support Staff) (N/A) BA 4207

↑ Contents ↑

Lecture & Tutorial Schedule
What?
(Section)		 Who?
(Instructor/​TAs)		 When?
(Day & Time)		 Where?
(Room)
LEC 0101 François Pitt Tue 09:00–10:00 KP 108
Thu 09:00–10:00 KP 108
LEC 0201 François Pitt Tue 13:00–14:00 PB B150
Thu 13:00–14:00 MP 202
LEC 0301 Angela Zavaleta Tue 14:00–15:00 PB B150
Thu 14:00–15:00 MP 102
LEC 5101 Angela Zavaleta Thu 18:00–20:00 BA 1160
TUT 0101 Saba Ale Ebrahim & various* Fri 10:00–11:00 HA 403 on Apr 10
TUT 0102 Maryam Haghi Fam & Richard Hou Fri 10:00–11:00 AB 107
TUT 0103 Mohammad Mozaffari & various* Fri 10:00–11:00 BA 1130 on Apr 10
TUT 0104 Hossein Ghotbaddini & Vedic Sharma Fri 10:00–11:00 MC 252
TUT 0201 Yunshun Zhong & Maryam Haghi Fam Fri 11:00–12:00 AB 107
TUT 0202 Hossein Ghotbaddini & Vedic Sharma Fri 11:00–12:00 HA 403 on Apr 10
TUT 0203 Saba Ale Ebrahim & various* Fri 11:00–12:00 BA 1180 on Apr 10
TUT 0204 Mohammad Mozaffari & Bogdan Pikula Fri 11:00–12:00 BA 1190 on Apr 10
  • * The second TA for this section will vary from week to week.

↑ Contents ↑

Marking Scheme

  • 10% for 6 Problem Sets (2% each) and one Research Survey (1%); you may earn up to 13% in total for this component, but your final course mark cannot exceed 100%!
  • 45% for 5 Term Tests (5% for your worst mark; 10% for all others)
  • 45% for the Final Exam (you must earn a minimum of 25% on the exam in order to pass the course)

See the Overview table for the exact due dates of Term Tests, Problem Sets, and the Research Survey.

Additional information about the Research Survey will be provided in an announcement a few weeks before it is due.

↑ Contents ↑

Preparation Activities

Quercus contains weekly Modules that you are expected to complete before lectures. Each Module will consist of some combination of the following elements.

  • Review: Short quizzes that mostly test prerequisite material (concepts that you are expected to know from previous courses). If you are not confident about your answers to a review quiz, please take the time to review the corresponding material from your prerequisite courses and then retake the quiz.
  • Discover: Readings or links to a video or simulation where new material is introduced. CSC263H1 is not completely “flipped”, unlike courses like CSC108H1 and CSC209H1. However, some of the easier concepts will be taught through Discover components. This allows lectures to go further by building on the content of the Discover modules, instead of having to spend lecture time going over the easiest concepts. Each Discover component will usually be paired with a Describe component.
  • Describe: Short quiz questions about new material from an associated Discover component. If you find that you cannot answer these questions, you should go back and redo the Discover activity more carefully, before trying the Describe quiz again. You may also find it helpful to consult the relevant chapters in the course textbook, for additional explanations and examples. And of course, you can (and should) ask question on Ed and/or during office hours if anything is unclear.
  • Demonstrate: Quiz questions that give the opportunity to demonstrate and exercise the main concepts from the previous week’s lectures and tutorial.

These prep activities are for your learning benefit: by moving some of the easiest material to modules, we free up lecture time to be able to tackle more difficult concepts. But this only works if everyone takes the time to understand the correct answers for all prep quizzes: it’s not enough to get the correct answer by trial-and-error (and there is NO benefit to doing so); we want you to have the opportunity to tackle this material and ask questions until it makes sense.

↑ Contents ↑

Problem Sets

  1. PS 1 Handout / PS 1 Solutions
  2. PS 2 Handout / PS 2 Solutions
  3. PS 3 Handout / PS 3 Solutions
  4. PS 4 Handout / PS 4 Solutions
  5. PS 5 Handout / PS 5 Solutions
  6. PS 6 Handout / PS 6 Solutions

Links to each problem set handout will be added here as the term progresses (usually two weeks before they are due). Sample solutions will usually be added on the Wednesday following the due date.

“Aren’t you worried students will just wait for the solutions, rewrite them, and send that in to MarkUs?” Not really… Anyone who does this would only receive partial credit anyway, and there are better ways to obtain partial credit (described below). More importantly, doing this completely negates the chance to train yourself on the problem set: anyone doing this would not know what they have trouble with, and would not be able to ask for help and improve, before the term test. Because it’s clearly not to anyone’s advantage to do this, it’s not something we plan to actively try to prevent. We already expect everyone to get mostly full marks on their problem set submissions anyway: this does not change that. You should plan to lose marks on the problem sets, so that you can learn and do better on the tests — not the other way around!

The purpose of the problem sets is to clarify what you should know at various points during the course, by reviewing what we covered in lectures and consolidating your understanding. For maximum learning benefit, these should be completed before your tutorial, but they must be submitted before 21:00 on Friday to receive full credit. This provides you with some flexibility for situations when you might be unable to complete them before your tutorial. Each problem set is also worth a small number of marks to help you stay on track with the course material. In other words, the main purpose of homework is for you to learn and understand the material well enough to be able to generate a correct solution for yourself.

Problem sets are an opportunity to practice what you have learned and apply your knowledge and skills to new and more complex problems. Treat every problem set like a “practice term test”: a chance to try out your understanding in a context where you cannot lose marks for making small mistakes; an opportunity to find out what you don’t know and correct it before the following term test. They are typically the most challenging part of this course. Start problem sets early! At any point in time, you should be able to read any problem set handout to figure out what you’re supposed to do, even if you have no clue how to do it (yet).

Keep in mind that even if you are unable to solve a problem by the time you submit your answers, it is still your responsibility to understand how to solve every problem (except those labelled “Extra”). In other words, you will be expected to solve similar problems on the term tests, so if there are problems you don’t know how to solve, it’s not enough to just explain what you don’t understand — you might receive partial credit for doing this, but it’s not enough for your learning. This should be only the starting point for you to work on figuring out what you are having trouble with (by discussing with other students, your TA and instructor, on Ed and/or during office hours), so that you can be confident that you can solve similar problems on your own.

Completion requirements

Each problem set will be marked for correctness, to provide you with valuable feedback about the level of understanding you have demonstrated. But because the purpose of the problems is primarily to help you self-assess your understanding of the relevant course material, your submission must meet the following conditions to receive credit.

  • A complete and mostly correct solution is required for all problem — except those marked “Extra”. What matters is that you have written a solution that addresses all the elements we would expect, even if it contains small errors or omissions. Solutions that contain many errors or omissions (or major ones) may receive less credit, of course.
  • “What if I don’t know how to solve a problem?” Then you have a responsibility to do the necessary readings, to use office hours and Ed, and to do the work required to figure out how to arrive at a solution. Even if you are uncertain about your answer, you can (and should) submit a partial solution. If you have a solution but you are unsure about its completeness, include a brief description of what you are unsure about, together with your partial solution.
  • “What if I’m not able to figure it out before the deadline?” For half the marks, you can submit a description of what you understand about the problem and the related course material (relevant sections from the lecture slides, page numbers from the textbook, etc.), to show that you are at least aware of the relevant material. Then write a clear statement of at least one question or confusion about this material that is making it difficult for you to get started. You may submit more than just one question/​concern (and under this condition, you really should for your own benefit), but it will not be required. Important: just writing “I don’t know how to do this” is not enough! Your responsibility to your own learning requires you to figure out more precisely what you understand and what you do not, so that you are able to formulate at least one concrete question about the material.

Submission instructions

  • You must submit all problem sets individually. More precisely, you may freely discuss the problems and their answers with your classmates, and with TAs and instructors, but you MUST write up and submit your own unique document. See the section on Academic Integrity for details of exactly what is allowed and what is not.
  • On weeks when there is a tutorial, your TAs will answer questions about the problem sets for current and previous weeks. Attempting the problem set before your tutorial will help you self-assess your level of understanding of the course concepts, so that you can be best prepared for the following week’s term test.
  • Problem sets must be submitted online through MarkUs before the due date. If you haven’t used MarkUs before, give yourself plenty of time to figure it out, and ask for help if you need it! The following Documentation for Students may also be useful if you have never used MarkUs before.
  • The link to connect to MarkUs is included directly in the navigation menu for the course. When you click on it, you will be taken to a login page where you can use your UTOR username and password OR your Teaching Lab username and password (both will work) — you can find your Teaching Lab account name and set or reset your password at https://www.teach.cs.toronto.edu/account. Once you have logged in, you will see a page with one tile for each course from this term that is using MarkUs — just click on the tile for csc263.
  • You may type your answers or hand-write them legibly, on paper or using a tablet and stylus. We encourage you to use LATEX if you have the time (it’s a good opportunity to practice), but this is NOT required.
  • You may write your answer directly on the question paper (if there is room), or on another piece of paper/​document.
  • [NEW for PS4, PS5, PS6.] You must submit your answers in a separate document for each problem, using the exact file name specified on MarkUs. Each document must be in PDF. Other formats (e.g., photos, Word documents, LaTeX source files, ZIP files) are NOT accepted — you must export, compile, convert and/or combine documents into ONE file in an accepted format, for each individual problem.
  • Each file you submit must be no larger than 47.5MB (this was increased on Jan 19). This may happen if you combine multiple photos into one PDF without any sort of compression, or when exporting longer documents from OneNote; if it does, you should use a PDF compression tool to make your PDF smaller, although please make sure that your PDF is still legible before submitting it. (PDFSAM is a good tool for this; it is free, open source, and runs on multiple platforms.)
  • You can submit your work more than once — and are encouraged to do so! — the most recent version submitted within the deadline is the version marked. However, your final submission should always contain exactly one file per question. In other words, please never submit multiple files with different names, for the same answers (or make sure you remove all files except the correct one). In general, you can (and should) simply overwrite your last submission with the next one — in other words, submit every file under the same name. MarkUs will replace your old submission with the new one, but keep a record of the previous versions so that we can roll back to them if necessary. You can never lose information this way.
  • The easiest way to know that your submission is okay is to try to view it afterwards: if MarkUs can display your submission directly (NOT by downloading it and opening it on your device), then everything worked fine; if you are unable to view your submission directly on MarkUs, then there was a problem that you must fix.
  • All problem sets are due by 21:00:00 on their due date. We recognize that unexpected issues sometimes make it difficult to submit problem sets on time, including technical issues. For this reason, problem set submissions will be accepted up to one week late with a penalty of −10% for each weekday late — except for the last problem set, which CANNOT be submitted once the final exam period begins on Apr 11. In other words, penalties begin at 21:00:00 on the Sunday after the due date (it’s like having an automatic built-in 2-day extension for every problem set), and increase at 21:00:00 each day thereafter. Submissions later than one week will receive no credit, so the very last time when you can submit (for a −50% penalty) is 20:59:59 on the Friday following the due date.
  • Note that this means at any point in time there will be multiple problem sets to which you can submit files. Double-check and triple-check before you submit to make sure you are submitting your work to the correct problem set!

↑ Contents ↑

Term Tests and Final Exam

Feeling ill? Complete a self-assessment before you show up!

Keep in mind that course instructors cannot grant Special Consideration for Final Examinations! If you are unable to write the final exam, please contact your College Registrar for the next steps — the process is explained in more detail on the Sidney Smith Commons.

What if you miss a test for unexpected reasons outside your control? Please follow the instructions in the Special Consideration section. If you miss one or two tests for approved reasons, we will calculate a mark for the test you missed, based on your performance on the other tests and on the final exam, taking into account the class averages on every test and exam. This ensures that you are not unfairly penalized if the test you missed was easier, but also that you do not gain an unfair advantage if you missed a harder test. If you miss more than two tests, we will require you to make an appointment with your College Registrar to put in place a concrete plan for the rest of the term, before we approve any exception. This ensures that you are realistic about your ability to succeed in the course and that you have thought about how you will manage the risk: after all, missing more than two tests would put you in a situation where you would be taking the final exam with NO feedback on your performance for MORE than half the material of the course. To ensure you do not engage in “magical thinking” (that everything will work out fine, but without a concrete plan), we will require confirmation from your College Registrar that you have met with them and that your approach to the rest of the term is realistic. Once we receive this, we can easily put in place appropriate accommodations for your all your missed work.

Test & Exam Information
(see the Overview for dates, times, and location)
Test Coverage Aids Allowed Practice Papers & Solutions
TT1 Priority Queues and Heaps; NO average-case analysis None paper / solutions
(ignore questions 1c and 3 for now)		 TT1 paper / TT1 solutions
TT2 Dictionaries; BSTs; AVL trees None paper / solutions
(ONLY question 3 is relevant; also question 3 from the TT1 practice test)		 TT2 paper / TT2 solutions
TT3 Augmentation (Ordered Sets); Hashing; Quicksort (just the algorithm, NOT the average-case analysis) None paper / solutions
(questions 3–5)		 TT3 paper / TT3 solutions
TT4 Average-case analysis (including Quicksort); Amortized analysis None paper / solutions
(questions 2 and 3; also Q1c from the TT1 practice test, Q1b from the TT2 practice test, Q3 from the TT3 practice test)		 TT4 paper / TT4 solutions
TT5 Graph data structures; Breadth-first search; Depth-first search None paper (only question 2; unfortunately, we do NOT have solutions ready: ask on Ed or during office hours; also look at Q4 from the TT4 practice test) TT5 paper / TT5 solutions
Exam Comprehensive: you are expected to be familiar with all the material covered in the course. One 8.5"×11" aid sheet, handwritten on both sides. Old Exams Collection Cover Page

What to expect (in general terms)

Term Tests will generally contain 3–4 questions, at least one of which is meant to be easy (a more-or-less direct application of course material), and at least one of which is meant to be a little challenging (require some creativity in applying the course material).

We know tests are time-limited; we won’t ask questions that require a lot of time to figure things out! For example, we are not likely to ask you to solve a “Challenge”-level problem from a Problem Set, because that might require you to spend too long thinking about various possibilities to find one that works. But we could give you a problem similar to a Challenge-level question from a problem set, one where the key insight from the problem set can be applied fairly directly. This would then be considered an reasonably easy question, because you wouldn’t need to come up with any new ideas to solve it, just show that you can apply something you have already learned.

How to Prepare

First review the materials listed above. Start with the Problem Sets, make sure you understand how to solve them, and use this to decide what to review next — focus on the topics and problems that you have more difficulty with. Don’t forget to compare your answers against sample solutions (when these are available).

Next, you can try questions from previous years’ term tests — see above for some links, but please read the rest of this paragraph first! Keep in mind that questions on our test are more likely to be related to problems you have already worked on this term than to questions from previous tests. At the same time, these past test problems are a good way to practice your understanding. For maximum benefit, we strongly suggest the following approach: try these questions only after you have finished reviewing the rest of the materials from this term; time yourself to get the benefit of a real “test experience”, as a way to verify not only your understanding, but also your ability to answer questions quickly (this will matter for the actual tests); and finally, don’t look at the solutions until you have finished working on the questions as if it were a real test.

Make good use of the Sidney Smith Commons' Exam Toolkit. This contains many general resources to help you prepare for term tests and the final exams, including sections on “what to expect”, “how to study”, and “strategies”.

“How should I prepare my aid sheet for the final exam?”

  • Most importantly, do not rely on your aid sheet as a “shortcut” to studying! The exam will ask you to apply course material to new problems and/or under new situations. We will expect you to have already understood this material: you will not have time during the exam to read lots of notes in order to understand something from the beginning.
  • Putting together your aid sheet is a good way to structure your review of every course topic. The simple mechanical act of writing down information helps your brain make stronger connections, so that the information becomes easier to remember and understand. But as you review and put together your aid sheet, focus on understanding what you are studying (what it means, how it connects to other topics, how to use it to solve porblems), NOT on memorizing it — that’s what the aid sheet is for!
  • You can write anything you want on your aid sheet, but you will not have a lot of time to read it during the exam. We recommend you write down only key definitions and concepts and examples. Focus on those elements of the course that contain many easy-to-forget details, or those that you know you struggle with. Do this as you review: every problem that gave you some difficulty (on a problem set or a test) is a good candidate for information you can add to your aid sheet to help you remember how to solve similar problems.
  • If you are going to use past tests and exams to practice, how about putting everything away and trying to answer those questions using only your aid sheet? This will help you find new elements to add to your aid sheet, or increase your confidence that it is ready.

How to write tests

Read the questions! If you answer the wrong question, even if it’s because you were nervous and you misread it, there is nothing that we can do. If something is unclear, don’t be afraid to ask.

Manage your time! Be disciplined, to leave most of your time free for solving problems. In particular, it’s fine to give point-form answers with the key elements, instead of spending time writing long, complete sentences.

Show what you know! Your strategy during the test should be:

  • identify the questions that you know how to answer (this means that you must read EVERY question before you start answering any of them);
  • answer those questions right away;
  • go back to the questions you’re not sure about, and work on them;
  • if you get stuck on a question, move on to the next one and come back later (don’t waste your time) — you can figure out ahead of time how much time to devote to each question (based on how much it’s worth), and stick to that estimate as much as possible.

If you have an idea how to solve a question but no time to do it in detail, then of course you should write down your idea. You will get part marks for any question where you have the correct structure (i.e., clearly showing that you know what you are supposed to do), even if you cannot fill in the details. So it always pays off to take a minute to write down a correct outline for your answer — it’s worth marks, even if you are unable to do more.

Explain what you’re doing! When you give an answer, make sure that you give at least a short statement of what you’re doing before giving us the answer: if your answer is incorrect, this can make the difference between getting NO mark (because we can’t tell if you understand what you’re doing) or getting part marks (if we see that you have the right idea but simply made a small error, or that you have the wrong idea but wrote it up correctly).

Don’t ramble! Write concise, to-the-point answers. If you ramble, or if you write an answer for a related (but different) problem with no adjustment or explanation, the feeling it gives us is that you don’t know the correct answer. Also, be aware that if you give us a correct answer followed by explanations that are clearly wrong or irrelevant, you will lose marks! So only write down what you know is correct: if you’re not sure, either say so explicitly or don’t say anything.

On the other hand, if you start writing down an answer and you realize that it’s wrong, SAY SO! You’ll get more part marks for showing that you understand your mistake, even if you’re not sure how to fix it, than if you simply leave it like that (which gives the impression that you don’t even realize that what you did was wrong).

On a related note, don’t feel like you must fill all the available space: it is quite possible that a correct answer will require only part of the space for some questions.

Take care of yourself! You’ll function much better if you are well-rested and relaxed than if you are tired or tense. Take some time to exercise (moderately), to burn off some of your body’s stress, leaving you better able to manage your stress levels and better able to perform. Eat a nutritious meal (but not too much) so you’re not hungry during the test. And get a good night’s sleep the night before.

A related tip I learned from a student: trying to “force yourself to be calm” may not work well, or even backfire, because you’re trying to suppress your body’s natural response to stress. Instead, trick your brain into thinking that what you’re feeling is not stress — it’s excitement! The two feelings are similar enough, you can think of it as looking forward to the challenge — the way a trained athlete is primed for a competition, and turning their nervousness into positive stress.

↑ Contents ↑

Academic Integrity

All work you submit must be your own. It is an academic offence to copy the work of someone else — even if the other person is not a student — unless you explicitly and clearly attribute the work to its original source. This includes files, words, and even ideas. Whether you copy or let someone else copy, it is an offence. Academic offences are taken very seriously.

At the same time, we want you to benefit from working with other students. For this course, you must write up your own individual submission to every problem set — you cannot submit the same document as another student — but you are allowed to discuss how to solve the problems with anyone you wish. The purpose of the problem sets is to ensure that you understand how to solve the problems. Even if you did not generate a solution yourself, you can still receive full credit for writing up a solution in your own words, together with a list of the sources (textbooks, web pages) and other students with whom you discussed the problem. (See the Problem Sets section for detailed description of what each submission must contain to receive full credit.)

You are also welcome to freely discuss course material and technology (such as LATEX) related to assignments, and we encourage you to do so. For example, you may work through examples that help you understand course material or a new technology, or help each other configure your system to run a supporting piece of software.

Any collaboration on, or sharing of, term test solutions or questions is strictly forbidden!

Please take a few minutes to consult the Academic Integrity at U of T website: it contains good information and concrete strategies to help support your learning in ways that follow the principles of academic integrity, in addition to references to formal policies and procedures.

↑ Contents ↑

Special Consideration

Feeling ill? Complete a self-assessment before you show up to a class or test!

If you are unable to complete course work or if you miss a test due to major illness or other circumstances outside of your control, please get in touch with us as soon as possible. Special consideration will be evaluated on a case-by-case basis and is not given automatically — we may be unable to grant you exactly the special consideration you seek, so please ensure we have time to discuss your situation.

In order to receive special consideration, you must fill out a Request for Special Consideration Form. Simply complete and submit the form online as soon as you can, together with any supporting documentation.

For illness or injury, including cold or flu-like symptoms and self-isolation, please self-declare your absence through the Absence Declaration tool on ACORN (the tool can be found in the Profile and Settings menu). You should record each day of your absence as soon as it begins, up until the day before you return to classes or other academic activities. You are NOT required to complete the U of T’s Verification of Student Illness or Injury (“VOI”) form as supporting documentation. To learn more, you may access relevant information on the U of T’s Verification of Illness or Injury page.

IMPORTANT: If you know that you will NOT be able to write a term test, just submit the request form as soon as you are able to (and have obtained appropriate documentation, like screenshots of your absence declaration). It is NOT necessary to send email for “simple” requests due to illness or injury or family emergencies — just the form is sufficient. However, if your situation is particularly unusual or complex, please contact us (by email using csc263-2023-01@cs.toronto.edu) to discuss the details. In that case, don’t hesitate to reach out as soon as you can: it is always easier to resolve situations earlier rather than later.

If you face a situation that is particularly disruptive (especially if it is likely to affect more than one course), please also contact your College Registrar — they are best equipped to provide you with general advice and support that goes beyond a single course. They can also help you document your situation and contact each of your course instructors on your behalf, to simplify the process of requesting accommodations.

↑ Contents ↑

Remark Requests

If you believe there was an error in the marking of a problem set or test — or if you just have questions about how your work was marked — you may request that it be remarked. Please complete and submit a Remark Request directly on MarkUs (no separate form or email message required). You must give a specific reason for the request, referring to possible errors or omissions by the marker, or asking specific questions about the feedback (or lack of feedback) you received.

Remark requests must be received within two weeks of when the item was returned.

Please note that when we receive a remark request, we may regrade the entire submission, though we will generally focus on the questions that are the subject of your request. Your mark may go up or down as a result of the remark. This is not meant to discourage you from submitting remarking requests! Just to acknowledge the reality that errors can be made in both directions in the initial marking: it’s possible that TAs misunderstand your solution and penalize it more than appropriate, but it’s also possible that TAs forget or miss some mistakes in your solution and do not apply appropriate penalties. When we remark, we correct both types of marking errors.

↑ Contents ↑

Creating a Positive Learning Environment

We are committed to creating a respectful learning environment in computer science courses for all students and expect that you will adhere to the University of Toronto’s Code of Student Conduct. Please be mindful of how your behaviour influences the atmosphere in our learning community, not just in classes, but also in computer labs, in online forums, and anywhere that you interact with other students and members of the department.

About Masks

As a courtesy to all your classmates (some of whom may live with immunocompromised individuals), we kindly ask that you wear a mask during lectures, tutorials, and in-person office hours. Wearing a mask is a simple, non-invasive way to be considerate to your community by reducing the risks of transmission of COVID-19 (and other illnesses), especially in indoor spaces where distancing is not possible.

↑ Contents ↑

Accessibility

The University of Toronto is committed to accessibility. If you require accommodations for an ongoing disability or an acute issue such as an injury, you should register with Accessibility Services (AS). The process of accommodation is both confidential and private. AS provides the information necessary to implement an accommodation and no more, e.g., what is listed in a Letter of Accommodation. Your instructors and other university staff will not reveal that you are registered with AS.

Students who require accommodations for term tests (or the final exam) must register with Accommodated Testing Services (ATS). We will only be providing test accommodations sent to us through that official channel. This helps to guarantee that accommodations are provided in a fair and consistent manner for everyone.

When you register for test accommodations with ATS, please register based on your tutorial section (NOT your lecture section). This allows us to provide the correct regular starting time for your test, something we cannot do if we know only your lecture section (because there is no connection between lecture and tutorial sections).

↑ Contents ↑

Calendar Information

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.

Prerequisites: CSC236H1/​CSC240H1/​CSC236H5/​CSCB36H3/​APS105H1/​APS106H1/​ESC180H1; STA237H1/​STA247H1/​STA255H1/​STA257H1/​STAB57H3/​STAB52H3/​ECE302H1/​STA286H1/​CHE223H1/​CME263H1/​MIE231H1/​MIE236H1/​MSE238H1/​ECE286H1.

Exclusions: CSC265H1, CSC263H5, CSCB63H3.

↑ Contents ↑

Prerequisites

Each year, many students ask if they can take CSC263H1 at the same time as STA237H1/​247H1/​… Unfortunately, this is not possible — if it made sense, we would have long ago changed the course prerequisites to make it easier for everyone! The issue is simple: CSC263H1 relies on students being comfortable computing expected values and using techniques such as indicator random variables right from the first week of the course.

The other prerequisite (CSC236H1/​…) is similarly essential: we rely on your familiarity with the algorithm correctness proof format taught in CSC236H1, and the analysis techniques for the running time of divide-and-conquer algorithms. These skills are required right from the start in CSC263H1, so you really do need to have completed the prerequisites first.

If this is your situation, and you have no prior experience with the material from STA237H1/​247H1/​… or CSC236H1/​…, then I am sorry to inform you that your best course of action is to wait until you are ready to take CSC263H1. Remember that course prerequisites are not arbitrary; rather, they are a distillation of our years of experience with thousands of students. Far from being obstacles in a student’s way, they provide signposts to support student success. More concretely, they represent the knowledge and skills that students require to get the best possible learning experience from a course. Don’t shortchange your own learning for the sake of convenience or “speed”!

↑ Contents ↑

Learning Outcomes

By the end of CSC263H1, you will be familiar with a variety of standard, complex data structures and abstract data types (graphs, dictionaries, balanced search trees, hash tables, heaps, disjoint sets), and with standard, more advanced complexity measures (average-case, amortized). More specifically, you will be able to:

  • recognize algorithms that employ each data structure,
  • write algorithms that employ each data structure,
  • recognize when each complexity measure is most appropriate,
  • analyze the efficiency of algorithms using each complexity measure,
  • choose and/or modify data structures appropriately to solve various problems.

↑ Contents ↑

Textbooks

↑ Contents ↑

Technical Requirements

Some course activities (office hours) may be offered online, through Zoom.

  • To join online office hours, you must be signed in to your U of T Zoom account (see the Student Onboarding Guide provided by the Faculty of Arts & Science Information Commons).
  • “What U of T Zoom account?” Glad you asked: simply log on to utoronto.zoom.us with your UTORid and password to activate your free U of T Zoom account.
  • Already have a Zoom account? You can use it, but you may not have access to all the same functionality.
  • You will have a much better experience if you use the most recent version of the desktop client for Zoom, instead of accessing it through a web browser.
  • More generally, to fully participate in all course activities, you require reliable access to a full computer (not just a smartphone) on which you can browse web pages, read lecture slides, and type and submit problem sets.
  • To attend online office hours, this computer must have a microphone, optionally a webcam, as well as a reliable, high-speed internet connection.

↑ Contents ↑

LATEX help

LATEX is a standard typesetting program used in computer science, and we encourage you to learn how to use LATEX as part of your work — though this is not necessary to submit work in this course. The important thing is that you submit documents only in one of the approved formats, no matter how you generated them. In this section, we provide some resources to help you get started with LATEX.

Note that there is no “course template” for LATEX documents. Time permitting, I may try to post samples here if people run into difficulties generating certain types of content (e.g., graph pictures). Also, you can always ask questions on Ed, where I (and others) will be happy to help.

↑ Contents ↑

Course Summary:

Date Details Due