Data Structures and Analysis
CSC263 Summer 2021
The course slides, worksheets, and modules
are based on the CSC263 Winter 2021
offering and were developed by Michelle Craig
(with some help from Samar Sabie)
Marking Scheme
Weekly Quercus
Modules (11)
22% Each worth 2%.
Completed
Individually
Problem Sets (3) 36%
PS1 (12%)
PS2 (12%)
PS3 (12%)
Completed
Individually or with
one partner
Term Tests (2) 42% Each worth 21%.
Completed
Individually
Weekly Quercus Modules
• 11 of these, each worth 2%
• Completed individually on Quercus
• Released Tuesday at 3pm
• Due Tuesday the following week at 2pm
• No late submissions accepted
• Unlimited attempts; no feedback/grades until after the deadline
• You may work individually or in pairs
• Submissions need to be typed into a PDF file and submitted to
MarkUS
• Due dates are Thursday @ 11am
• Late assignments: 0% penalty for the first hour, 5% for the next two
hours, 10% up to 3 hours late, etc… (check table on Quercus)
Problem Sets
Typing up Problem Sets
• LaTeX is strongly encouraged (but not required)
• You can generate LaTeX files using a web-based tool such as
https://www.overleaf.com/
• Many tutorials online, e.g.:
http://www.maths.tcd.ie/~dwilkins/LaTeXPrimer/
• 50-minute workshop recording posted on Quercus > Problem Sets page
https://www.overleaf.com/
http://www.maths.tcd.ie/~dwilkins/LaTeXPrimer/
Term Tests
• Test 1: during the June assessment period (date and time still tbd)
• Test 2: Tuesday August 10, window from 6:30pm-9:00 pm Toronto
time
• 120 minutes to complete the test during that time window
• Run on MarkUs
• Typed or photos of legible handwritten work
• “CLRS”
• Optional
• Available online at UofT library
• We will reference during lectures and
Quercus modules and you can find
appropriate chapters based on topics.
Textbook
Academic Integrity and Professionalism
• Honesty
• Proper Collaborations
• Respect
Communication and Getting Help
• Piazza – linked from the Quercus site
• csc263-2021- .edu
• Office Hours
• BB Collaborate
• Schedule on Quercus site
mailto://(null)csc263-2021- .edu
Online Learning
• Technical Issues
• Attendance
• Recordings
• Chat
• Cameras
Engagement is key!
Why are you taking CSC263?
Mentimeter Poll
www.menti.com
Enter Code 4482 1276
Why Study Data Structures?
http://www.menti.com/
LEC5101: A Section for Champions!
• 6-9pm (all lecture + breakout rooms + polls + worksheets)
• My Commitment to you
• Why join synchronously?
1. –
2. –
3. –
• Breaks at 7pm and 8pm are enforced (ask when we come back after the
break!)
Volunteer Note-taker Needed
To become a volunteer note-taker, please follow these 4 steps:
Register Online as a Volunteer Note-Taker at:
1. https://clockwork.studentlife.utoronto.ca/custom/misc/home.aspx
2. Click on Volunteer Notetakers, and sign in using your UTORid
3. Select classes you wish to be a volunteer for
4. Start uploading your notes right away
Email as. or call 416-946-5555 if you have questions
or require any assistance with uploading notes.
Administrative Questions?
Why are you taking CSC263?
Why Study Data Structures?
Abstract Data Type (ADT) = Set of objects together with operations
Data Structure = Implementation of an ADT
A way to represent objects and an algorithm for every operation
Chalk Talk Review of 148 What is a Data Structure Anyway?
Runtime Complexity Abstractions
Input Size
Number of
Basic
Operations
Chalk Talk Review of 165
Complexity =
Resource =
Input Size is problem dependent
Analyzing Runtime Complexity
Best case
Average case
Worst case
Big O
Big Omega
Big Theta
Runtime Cases >
Asymptotic Notation >
Asymptotic Notation (Mathematically)
O(g(n)) = {f(n): there exist positive constants c and n0 such that
0 d f(n) d cg(n) for all n t n0}
Ω(g(n)) = {f(n): there exist positive constants c and n0 such that
0 d cg(n) d f(n) for all n t n0}
Θ(g(n)) = {f(n): there exist positive constants c1, c2, and n0 such that
0 d c1 g(n) d f(n) d c2g(n) for all n t n0}
Asymptotic Notation (Intuitively)
Big-Oh: f(n) = O(g(n)) means that the function f(n) grows slower or
at the same rate as g(n)
Big-Omega: f(n) = Ω(g(n)) means that the function f(n) grows faster
or at the same rate as g(n)
Big-Theta: f(n) = Θ(g(n)) means that the function f(n) grows at the
same rate as g(n)
Chalk Talk Review of 165
Asymptotic Notation (Practically)
In practice:
Big-O (upper bound): argue that the algorithm executes no more than
cg(n) steps on every input of size n.
Big-Omega (lower bound): exhibit one input on which algorithm executes
at least cg(n) steps.
What about big-Theta?
• In Breakout Rooms
• Worksheets posted on Lectures page on Quercus
• Only do questions 1-3 now (fine to just get Q1 done if you get
talking today!)
Worksheet Activity
Worst-case Analysis
Asymptotic Notation: What is the running time of an algorithm for an
input size n?
Worst case analysis: What is the maximum possible running time of
an algorithm for an input size n?
T(n): max {t(x) : x is an input of size n }
def hasTwentyOne(L):
j = L.head
while j != None and j.key != 21:
j = j.next
return
1
2
3
4
Chalk Talk Worst-case Analysis
Chalk Talk Worst-case Analysis
• Give a pessimistic upper bound that could occur for any input of a
fixed size n as T(n) = O(f). Must be proved on all possible inputs
• Give a family of inputs (one for each input size) and a lower bound
on the number of basic operations that occurs for this particular
family of inputs as T(n) = Ω(f(n))
• If the two expressions involve the same function then T(n) = Θ(f(n))
Worst-case Analysis
Average-case Analysis
terrible
worst-case
good
average-case
Many Algorithms in Practice
def hasTwentyOne(L):
j = L.head
while j != None and j.key != 21:
j = j.next
return
1
2
3
4
Chalk Talk
Average-case Analysis
For algorithm A, define Sn = sample space of all inputs of size n
Let tn(x) = number of steps executed by A on input x (in Sn)
Let Tavg(n): the (weighted) average of the algorithm’s running time
for all inputs of size n
Average-case Running Time
Is the expectation of the running time as distributed over all possible
values of T:
Chalk Talk Continues
def hasTwentyOne(L):
j = L.head
while j != None and j.key != 21:
j = j.next
return
1
2
3
4
Handy Summation Formulas
More space Chalk Talk
Continues
def hasTwentyOne(L):
j = L.head
while j != None and j.key != 21:
j = j.next
return
1
2
3
4
More space Chalk Talk
Continues
def hasTwentyOne(L):
j = L.head
while j != None and j.key != 21:
j = j.next
return
1
2
3
4
Average-case Analysis (Meta) Lesson
1. Define the possible set of inputs (e.g. numbers between 1 and 10)
and a probability distribution over this set (e.g. uniform)
2. Define the “basic operations” being counted. This is often the
operation that happens the most frequently (such as list access
when searching one) or the most expensive operation
3. Define the random variable T over this probability space to
represent the running time of the algorithm.
4. Compute the expected value of T, using the chosen probability
distribution and formula for T.
5. Since the average number of steps is counted as an exact
expression, it can be written as a Theta expression.
Worksheet
Chalk Talk