CS计算机代考程序代写 scheme data structure algorithm Data Structures and Analysis

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