# CS代考程序代写 data structure database assembly python deep learning algorithm COMP3027: Algorithm Design

COMP3027: Algorithm Design

Lecture 1a: Admin

William Umboh

School of Computer Science

The University of Sydney

1

Aims of this unit

This unit provides an introduction to the design and analysis of algorithms. We will learn about

– (i) how to reason about algorithms rigorously: Is it correct? Is it fast? Can we do better?

– (ii) how to develop algorithmic solutions to computational problems Assumes:

– basic knowledge of data structures (stacks, queues, binary trees) and programming at level of COMP2123

– discrete math (graphs, big O notation, proof techniques) at level of MATH1004/MATH1064

University of Sydney

2

Course Arrangements

Course page: Canvas and Ed

Lecturer:

William Umboh

Level 4, Room 410, School of Computer Science william.umboh@sydney.edu.au

Ph. 0286277122

Tutors:

Patrick Eades (TA) Alex Stephens (TA) Oliver Scarlet Madeleine Wagner Michael Lin Jongmin Lim

Joe Godbehere (online)

BH Cho

Jahanvi Khatkar Nick Cranch

Greg Mclellan Michael Zhao Alec Zhang

The University of Sydney

3

Course Arrangements

Course book:

J. Kleinberg and E. Tardos Algorithm Design

Additional Reference:

J. Erickson Algorithms

Available free online

Outline:

13 lectures (Thu 10-12 & Thu 4-5 (Adv)) 5 assignments

10 quizzes

Exam

Tutorials:

12 tutorials

University of Sydney

4

Assessment

Assessment:

Quizzes 15% (average of best 8 out of 10)

Each assignment 5% (5 assignments – total 25%) Exam 60% (minimum 40% required to pass)

Submissions:

Theory part – Gradescope (invites to be sent out later this week) Implementation – Ed (Assignments 1 and 3 only)

Collaboration:

General ideas – Yes! Formulation and writing – No!

Read Academic Dishonesty and Plagiarism.

The University of Sydney

5

Quizzes

10 assessed quizzes (and one self-review quiz)

Average of best 8 of the 10 quizzes will count

Worth 15% of final mark

Quizzes are due 23:59:00 AEDT on each Sunday – Late submissions will not be accepted

You get a single attempt at each quiz only

You have 20 minutes from the time you open the quiz

The University of Sydney 6

Assignments

There will be 5 homework assignments

The objective of these is to teach problem solving skills

Each assignment represents 5% of your final mark

Late submissions will be penalized by 20% of the total marks per day. Assignments > 2 days late get 0.

For example, say you get 80% on your assignment:

If submitted on time = 4.0

Late but within 24 hours = 4.0 – (20% * 5.0) = 4.0 – 1 = 3 Between 24 and 48 hours = 4.0 – (40% * 5.0) = 4.0 – 2 = 2

Theory part needs to be typed (LaTeX > GDocs, Word), no handwritten submissions accepted

Some assignments will involve programming (only Python allowed)

The simplicity of Python lets one focus on core algorithmic ideas

The University of Sydney 7

Assignment 1

Released: Week 2 (5 March)

Due: Week 3 (11 March 23:59:00 AEDT)

Submissions close: 13 March 23:59:00 AEDT (No submissions accepted after this)

Returned: Week 4 (19 March)

The University of Sydney 8

Academic Integrity (University policy)

– “The University of Sydney is unequivocally opposed to, and intolerant of, plagiarism and academic dishonesty.

– Academic dishonesty means seeking to obtain or obtaining academic advantage for oneself or for others (including in the assessment or publication of work) by dishonest or unfair means.

– Plagiarism means presenting another person’s work as one’s own work by presenting, copying or reproducing it without appropriate acknowledgement of the source.” [from site below]

– http://sydney.edu.au/elearning/student/EI/index.shtml

– Submitted work is compared against other work (from students, the

internet etc)

– Turnitin for textual tasks (through eLearning), other systems for code

– Penalties for academic dishonesty or plagiarism can be severe

– Complete self-education AHEM1001

The University of Sydney 9

Academic Integrity (University policy)

• The penalties are severe and include:

1) a permanent record of academic dishonesty, plagiarism and misconduct in

the University database and on your student file

2) mark deduction, ranging from 0 for the assignment to Fail for the course 3) expulsion from the University and cancelling of your student visa

• Do not confuse legitimate co-operation and cheating! You can discuss the assignment with another student, this is a legitimate collaboration, but you cannot complete the assignment together – everyone must write their own code or report, unless the assignment is group work.

• When there is copying between students, note that both students are penalised – the student who copies and the student who makes his/her work available for copying

The University of Sydney 10

Final exam

The final will be 2.5 hours long, consisting of 6 problems similar to those seen in the tutorials and assignments

The final will test your problem solving skills

There is a 40% exam barrier

The final exam represents 60% of your final mark

Our advice is that you work hard on the assignments throughout the semester. It’s the best preparation for the final

The University of Sydney 11

Tutorials

After the main lecture, we will post a tutorial sheet for the week on Ed

To get the most out of the tutorial, try to solve as many problems as you can before the tutorial. Your tutor is there to help you out if you get stuck, not to lecture

We will post solutions to tutorials on Ed

If you are unable to attend a tutorial, you may ask your questions on Ed

The University of Sydney 12

Contacting us

Unless you have a personal issue, do not send us direct email

Instead, post your question on Ed so that others can benefit from the answers.

Feel free to answer another student’s question. This will help you digest the material as well. The best way to learn is to teach others.

The staff will vet student answers.

The University of Sydney 13

Tips for success

This course emphasises creative problem-solving and being able to explain solution to others

Passively listening to lectures and tutorials, reading slides will not cut it

The only way to learn is by solving problems and explaining it Participate actively in tutorials and Ed

The University of Sydney 14

Special Consideration (University policy)

– Ifyourperformanceonassessmentsisaffectedbyillnessor misadventure

– Followproperbureaucraticprocedures

– HaveprofessionalpractitionersignspecialUSydform

– Submitapplicationforspecialconsiderationonline,uploadscans – Noteyouhaveonlyaquiteshortdeadlineforapplying

– http://sydney.edu.au/current_students/special_consideration/

– Also,notifycoordinatorbyemailassoonasanythingbeginsto go wrong

– Thereisasimilarprocessifyouneedspecialarrangementseg for religious observance, military service, representative sports

The University of Sydney 15

Assistance

– There are a wide range of support services available for students

– Please make contact, and get help

– You are not required to tell anyone else about this

– If you are willing to inform the unit coordinator, they may be able to work with other support to reduce the impact on this unit

– eg provide advice on which tasks are most significant

The University of Sydney 16

Do you have a disability?

You may not think of yourself as having a ‘disability’ but the definition under the Disability Discrimination Act (1992) is broad and includes temporary or chronic medical conditions, physical or sensory disabilities, psychological conditions and learning disabilities.

The types of disabilities we see include:

Anxiety // Arthritis // Asthma // Autism // ADHD Bipolar disorder // Broken bones // Cancer Cerebral palsy // Chronic fatigue syndrome

Crohn’s disease // Cystic fibrosis // Depression Diabetes // Dyslexia // Epilepsy // Hearing impairment // Learning disability // Mobility impairment // Multiple sclerosis // Post-traumatic stress // Schizophrenia // Vision impairment and much more.

Students needing assistance must register with Disability Services. It is advisable to do this as early as possible. Please contact us or review our website to find out more.

Disability Services Office
sydney.edu.au/disability
02-8627-8422

The University of Sydney

17

Other support

– Learning support

– http://sydney.edu.au/study/academic-support/learning-support.html

– International students

– http://sydney.edu.au/study/academic-support/support-for-international-students.html

– Aboriginal and Torres Strait Islanders

– http://sydney.edu.au/study/academic-support/aboriginal-and-torres-strait-islander-

support.html

– Student organization (can represent you in academic appeals etc)

– http://srcusyd.net.au/ or http://www.supra.net.au/

– Please make contact, and get help

– You are not required to tell anyone else about this

– If you are willing to inform the unit coordinator, they may be able to work with other support to reduce the impact on this unit

– eg provide advice on which tasks are most significant

The University of Sydney 18

WHS INDUCTION

School of Information Technologies

General Housekeeping – Use of Labs

– Keep work area clean and orderly

– Remove trip hazards around desk area

– No food and drink near machines

– No smoking permitted within University buildings

– Do not unplug or move equipment without permission

The University of Sydney 20

EMERGENCIES – Be prepared

www.sydney.edu.au/whs/emergency

The University of Sydney 21

EMERGENCIES

WHERE IS YOUR CLOSEST SAFE EXIT ?

The University of Sydney 22

EMERGENCIES

The University of Sydney

23

l

MEDICAL EMERGENCY

– If a person is seriously ill/injured:

1. call an ambulance 0-000

2. notify the closest Nominated First Aid Officer

If unconscious– send for Automated External Defibrillator (AED)

AED locations.

NEAREST to CS Building (J12)

– Electrical Engineering Building, L2 (ground) near lifts – Seymour Centre, left of box office

– Carried by all Security Patrol vehicles

3. call Security – 9351-3333

4. Facilitate the arrival of Ambulance Staff (via Security)

Nearest Medical Facility

University Health Service in Level 3, Wentworth Building

First Aid kit – SIT Building (J12) kitchen area adjacent to Lab 110

The University of Sydney 24

School of Computer Science Safety Contacts

CHIEF WARDEN
Greg Ryan

Level 1W 103

9351 4360

0411 406 322

Orally REPORT all INCIDENTS

& HAZARDS

to your SUPERVISOR

OR

Undergraduates: to Katie Yang 9351 4918

FIRST AID OFFICERS

Julia Ashworth Level 2E Reception

9351 3423

Will Calleja Level 1W 103

9036 9706 0422 001 964

Katie Yang Level 2E 237

9351 4918

Coursework Postgraduates:

to Cecille Faraizi 9351 6060

CS School Manager: Priyanka Magotra 8627 4295

The University of Sydney

25

SEmcheorogleonfcyCopmropceudteurreSscience Safety Contacts

CHIEF WARDEN

Greg Ryan

– In the unlikely event of an emergency we may need to

Level 1W 103

Orally REPORT all INCIDENTS

9351 4360

evacuate the building

0411 406 322

– If we need to evacuate, we will ask you to take your

& HAZARDS

FIRST AID OFFICERS

belongings and follow the green exit signs and proceed to the

assembly area.

to your SUPERVISOR

– In some circumstances, we might be asked to remain inside the

Julia Ashworth

Level 2E Reception

building for o9u3r51o3w42n3 saf
ety. We call this a lockdown or shelter-

in-place.

– Further information is available at

9351 4918

to Cecille Faraizi 9351 6060

9036 9706

Postgraduates:

0422 001 964

OR Undergraduates: to Katie Yang

Will Calleja Level 1W 103

Coursework

www.sydney.edu.au/emergency

Katie Yang Level 2E 237

9351 4918

CS School Manager: Priyanka Magotra 8627 4295

TThheeUUnniviveersristiytyooffSSyyddnneeyy

Page 236

SCcohronoal voifruCsom(CpOuVteIDr -S1c9ie) nce Safety Contacts

CHIEF WARDEN

Greg Ryan

– Allstaffandstudentswhohavecoldorflusymptoms

Level 1W 103

Orally REPORT all

9351 4360

should isolate themselves from others

0411 406 322

INCIDENTS & HAZARDS

FIRST AID OFFICERS

– If you have a non-infectious condition such as asthma or

to your SUPERVISOR

hayfever please let your teacher and classmates know

Julia Ashworth Level 2E Reception

OR

Undergraduates: to Katie Yang

9351 3423

– If you are otherwise unwell with cold or flu symptoms please

excuse yourself from this class and we will support you to

Will Calleja Level 1W 103

9351 4918

continue the work remotely

9036 9706 0422 001 964

Coursework Postgraduates:

to Cecille Faraizi 9351 6060

– Make sure you read the information on special consideration Katie Yang

in the unit outline.

Level 2E 237

9351 4918

CS School Manager: Priyanka Magotra 8627 4295

TThheeUUnniviveersristiytyooffSSyyddnneeyy

Page 257

SCcohronoal voifruCsom(CpOuVteIDr -S1c9ie) nce Safety Contacts

CHIEF WARDEN

Greg Ryan

– The University is following advice from the government and

Level 1W 103

Orally REPORT all INCIDENTS

9351 4360

related public health authorities

0411 406 322

–
For the latest information, see the advice on the

& HAZARDS

to your SUPERVISOR

FIRST AID OFFICERS

University website

– It’s important to remember that the University is a respectful Julia Ashworth

environment and that racism won’t be tolerated in the

Level 2E Reception classroom, on9li3n5e1 3o42r3on c
ampus

OR

– Student video Undergraduates: to Katie Yang

Will Calleja Level 1W 103

9351 4918

– Please take care of each other and yourselves and if you need

9036 9706

Coursework

support reach out to your unit coordinator or the health and

Postgraduates: to Cecille Faraizi wellbeing area of the Current Student webs9i3te51 6060

Katie Yang Level 2E 237

9351 4918

0422 001 964

CS School Manager: Priyanka Magotra 8627 4295

TThheeUUnniviveersristiytyooffSSyyddnneeyy

Page 268

COMP3027: Algorithm Design

Lecture 1b:

Introduction

William Umboh

School of Computer Science

The University of Sydney

29

Recall: aims of this unit

This unit provides an introduction to the design and analysis of algorithms. We will learn about

– (i) how to reason about algorithms rigorously: Is it correct? Is it fast? Can we do better?

– (ii) how to develop algorithmic solutions to computational problems

University of Sydney

30

Recall: aims of this unit

What’s in an algorithm?

This unit provides an introduction to the design and analysis of

l

Algorithms can have huge impact

algorithms. We will learn about

For example:

l

– (ii) how to develop algorithmic solutions to computational problems – Professor Martin Grotschel

l A benchmark production planning model solved using linear programming would have taken 82 years to solve in 1988, using the computers and the linear programming algorithms of the day.

l Fifteen years later, in 2003, this same model could be solved in roughly 1 minute, an improvement by a factor of roughly 43 million!

[Extreme case, but even the average factor is very high.]

– (i) how to reason about algorithms rigorously: Is it correct? Is it fast? CaAnrwepeordtotobethteteWr?hite House from 2010 includes the following.

University of Sydney

31

Recall: aims of this unit

What’s in an algorithm?

This unit provides an introduction to the design and analysis of

IAnlg2o0r0it3hmthserceanwheareveexhaumgepliemspoafctproblems that we can solve 43 million times algofarsitehrmtsh.anWien w19il8l8learn about

l

l

For example:

– (i) how to reason about algorithms rigorously: Is it correct? Is it fast? – This is because of better hardware and better algorithms

CaAnrwepeordtotobethteteWr?hite House from 2010 includes the following.

– (ii) how to develop algorithmic solutions to computational problems

– Professor Martin Grotschel

l A benchmark production planning model solved using linear programming would have taken 82 years to solve in 1988, using the computers and the linear programming algorithms of the day.

l Fifteen years later, in 2003, this same model could be solved in roughly 1 minute, an improvement by a factor of roughly 43 million!

[Extreme case, but even the average factor is very high.]

University of Sydney

32

Recall: aims of this unit

What’s in an algorithm?

This unit provides an introduction to the design and analysis of

IAnlg1o9r8it8hms can have huge impact

algorithms. We will learn about

In 2003

l

l

F-or eInxtaeml p3l8e6: and 386SX – Pentium M

– (i) how to reason about algorithms rigorously: Is it correct? Is it fast?

l

About 275,000 transistors

CaAnrwepeordtotobethteteWr?hite House from 2010 includes the following.

l

l

– (ii) how

– Professor Martin Grotschel

l

l

tcolodcekvsepleoepdsalogfo1r6itMhHmz,ic solutions to computational problems

20MHz, 25MHz, and 33MHz

A benchmark production planning model solved using linear

l

– MSDOS 4.0 and windows 2.0 –

programming would have taken 82 years to solve in 1988, using the

AMD Athlon 64

– VGAcomputers and the linear programmi-ngWalignodroitwhsmXsPof the day.

l Fifteen years later, in 2003, this same model could be solved in roughly 1 minute, an improvement by a factor of roughly 43 million!

[Extreme case, but even the average factor is very high.]

About 140 million transistors

Up to 2.2 GHz

University of Sydney

33

Recall: aims of this unit

What’s in an algorithm?

This unit provides an introduction to the design and analysis of

l

AInlgoarritehpmorstctaonthaevWe hiutgeeHiomupseacftrom 2010 includes the following.

algorithms. We will learn about

F-or ePxroafmepssleo:r Martin Grotschel:

– (i) how to reason about algorithms rigorously: Is it correct? Is it fast?

l

A benchmark production planning model solved using linear CaAnrwepeordtotobethteteWr?hite House from 2010 includes the following.

l

programming would have taken 82 years to solve in 1988, using the

– (ii) how to develop algorithmic solutions to computational problems – Professor Martin Grotschel

l

•

computers and the linear programming algorithms of the day.

A benchmark production planning model solved using linear Fifteen years later, in 2003, this same model could be solved in

programming would have taken 82 years to solve in 1988, using the roughly 1 minute, an improvement by a factor of roughly 43 millions

l l

roughly 1 minute, an improvement by a factor of roughly 43 million! Hardware: 1,000 times improvement

•

computers and the linear programming algorithms of the day. Fifteen years later, in 2003, this same model could be solved in

Observation:

[Extreme case, but even the average factor is very high.]

Algorithms: 43,000 times improvement

University of Sydney

34

Recall: aims of this unit

WhaEtf’fsicinieannt algorithms?

l Efficient algorithms produce results within available resource This unit provides an introduction to the design and analysis of

l

Algorlitmhimts can have huge impact

algorithms. We will learn about

l

In practice

For example:

– (i) how to reason about algorithms rigorously: Is it correct? Is it fast? CaAnrwepeordtotobethteteWr?hite House from 2010 includes the following.

l

– Low polynomial time algorithms behave well

– (ii) how to develop algorithmic solutions to computational problems

–

l

Professor Martin Grotschel

– Exponential running times are infeasible except for very small

l

l

l

A benchmark production planning model solved using linear instances, or carefully designed algorithms

programming would have taken 82 years to solve in 1988, using the Perfcoormpauntceersdaenpdetnhdeslionenamr parnoygroabmvmioinugs afalgcotroitrhsms of the day.

Fifteen years later, in 2003, this same model could be solved in – Hardware

– Algorithm

[Extreme case, but even the average factor is very high.]

– Implementation of the algorithm

This unit: Algorithms

roughly 1 minute, an improvement by a factor of roughly 43 million! – Software

University of Sydney

35

Recall: aims of this unit

WhaEtf’fsicinieannt algorithms?

l Efficient algorithms produce results within available resource This unit provides an introduction to the design and analysis of

l

EAflgfiocrliietmnhtimtaslgcoarnithamvse“hduogethiemjpoabc”t the way you want them to…

algorithms. We will learn about

l

l

Complex, highly sophisticated algorithms can improve For example:

In practice

– –

– (i) how to reason about algorithms rigorously: Is it correct? Is it fast? performance

l

– Do you need the exact solution?

CaAnrwepeordtotobethteteWr?hite House from 2010 includes the following.

– Low polynomial time algorithms behave well

– (ii)- hoAwretyooudedveealionpg awligtohrsiothmme iscpesocilaultcioanses atondcnoomt pwuithataiogneanlerparlopbrloebmlesm?

l

Profebsusot.r.M. artin Grotschel

– Exponential running times are infeasible except for very small Is it ok if you miss the right solution sometimes?

A benchmark production planning model solved using linear instances, or carefully designed algorithms

Fifteen years later, in 2003, this same model could be solved in – Hardware

– Algorithm

[Extreme case, but even the average factor is very high.]

– Implementation of the algorithm

This unit: Algorithms

l

l

l

programming would have taken 82 years to solve in 1988, using the Reasonably good algorithmic solutions that avoid simple,

Perfcoormpauntceersdaenpdetnhdeslionenamr parnoygroabmvmioinugs afalgcotroitrhsms of the day. or “lazy” mistakes, can have a much bigger impact!

l

roughly 1 minute, an improvement by a factor of roughly 43 million! – Software

University of Sydney

36

Three abstractions

Problem statement:

– defines a computational task

– specifies what the input is and what the output should be

Algorithm:

– a step-by-step recipe to go from input to output – different from implementation

Correctness and complexity analysis:

– a formal proof that the algorithm solves the problem

– analytical bound on the resources (e.g., time and space) it uses

University of Sydney

37

A computational problem

Motivation

-We are a cryptocurrency trading firm and have just developed a fancy deep learning algorithm to predict future price fluctuations of Bitcoin

– Given these predictions, we want to find the best investment time window Input:

– An array with n integer values A[0], A[1],… , A[n-1] (can be +ve or -ve) Task:

-Find indices 0 ≤ i ≤ j < n maximizing
A[i] + A[i+1] + ... + A[j]
University of Sydney
38
Naive algorithm
def naive(A):
def evaluate(a,b)
return A[a] + ... + A[b]
n = size of A
answer = (0,0)
for i = 0 to n-1
for j = i to n-1
if evaluate(i,j) > evaluate(answer[0],answer[1])

answer = (i,j)

return answer

Questions:

– how efficient is this algorithm?

– is this the best algorithm for this task?

University of Sydney

39

Efficiency

Def. 1: An algorithm is efficient if it runs quickly on real input instances

Not a good definition because it depends on – how big our instances are

– how restricted/general our instance are

– implementation details

– hardware it runs on

A better definition would be implementation independent: – count number of “steps”

– bound the algorithm’s worst-case performance

University of Sydney

40

Efficiency

Def. 2: An algorithm is efficient if it achieves (analytically) qualitatively better worst-case performance than a brute-force approach.

This is better but still has some issues: – brute-force approach is ill-defined

– qualitatively better is ill-defined

University of Sydney

41

Efficiency

Def. 3: An algorithm is efficient if it runs in polynomial time; that is, on an instance of size n, it performs p(n) steps for some polynomial p(x)=ad xd +ad-1 xd-1 +⋯+a0

Notice that if we double the size of the input, then the running time would roughly increase by a factor of 2d.

This gives us some information about the expected behavior of the algorithm and is useful for making predictions.

University of Sydney

42

Asymptotic growth analysis

Let T(n) be the worst-case number of steps of our algorithm on an instance of “size” n. We say that T(n) = O( f(n) ) if

thereexistn0 andc>0suchthatT(n)≤cf(n)foralln>n0 Also, we say that T(n) = Ω( f(n) ) if

thereexistn0 andc>0suchthatT(n)>cf(n)foralln>n0 Finally, we say that T(n) = Θ( f(n) ) if

T(n) = O( f(n) ) and T(n) = Ω( f(n) ) Note: c is a constant independent of n.

University of Sydney

43

Properties of asymptotic growth

Transitivity:

– If f = O(g) and g = O(h), then f = O(h)

– If f = Ω(g) and g = Ω(h), then f = Ω(h) – If f = Θ(g) and g = Θ(h), then f = Θ(h)

Sums of functions

– If f = O(h) and g = O(h), then f + g = O(h)

– If f = Ω(h) and g = Ω(h) , then f + g = Ω(h)

– If f = Θ(h) and g = Θ(h) , then f + g = Θ(h)

– BEWARE: If we have n functions f1, f2, … fn = O(h), then their sum is not O(h) but O(nh).

University of Sydney

44

Properties of asymptotic growth

LetT(n)=ad nd +⋯+a0beapoly.withad >0,thenT(n)=Θ(nd) Let T(n) = loga n for constant a > 1, then T(n) = Θ(log n) Foreveryb>1andd>0,wehavend =O(bn)

The reason we use asymptotic analysis is that allows us to ignore unimportant details and focus on what’s important, on what dominates the running time of an algorithm.

University of Sydney

45

Survey of common running times

Let n be the size of the input, and let T(n) be the running time of our algorithm.

We say T(n) is…

if…

logarithmic

T(n) = Θ(log n)

linear

T(n) = Θ(n)

“almost” linear

T(n) = Θ(n log n)

quadratic

T(n) = Θ(n2)

cubic

T(n) = Θ(n3)

exponential

T(n) = Θ(cn) for some c > 1

University of Sydney

46

Comparison of running times

Assume machine can run a million “steps” per second

size

n

n log n

n2

n3

2n

n!

10

<1 s
<1 s
<1 s
<1 s
<1 s
3s
30
<1 s
<1 s
<1 s
<1 s
17 m
WTL
50
<1 s
<1 s
<1 s
<1 s
35 y
WTL
100
<1 s
<1 s
<1 s
1s
WTL
WTL
1000
<1 s
<1 s
1s
15 m
WTL
WTL
10,000
<1 s
<1 s
2m
11 d
WTL
WTL
100,000
<1 s
1s
2h
31 y
WTL
WTL
1,000,000
1s
10 s
4d
WTL
WTL
WTL
WTL = way too long
University of Sydney
47
Recap: Asymptotic analysis
Establish the asymptotic number of “steps” our algorithm performs in the worst case
Each “step” represents constant amount of real computation Asymptotic analysis provides the right level of detail Efficiency = polynomial running time
Keep in mind hidden constants inside your O-notation
University of Sydney
48
Naive algorithm
def naive(A):
def evaluate(a,b)
return A[a] + ... + A[b]
n = size of A
answer = (0,0)
for i = 0 to n-1
Θ(n) time
Θ(n2) calls to evaluate
for j = i to n-1
if evaluate(i,j) > evaluate(answer[0],answer[1])

answer = (i,j)

return answer

Obs. naive runs in Θ(n3) time University of Sydney

49

Pre-processing

evaluate(a,n-1)

def preprocessing(A):

evaluate(b+1,n-1)

Speed up “evaluate”
subroutine by
pre-computing for all i:
B[i] = A[i] + … + A[n-1]

The rest is as before

def evaluate(a,b)

return B[a] – B[b+1]

n = size of A

B = array of size n+1

B[n] = 0

for i in 0 to n-1

B[i] = A[i] + … A[n-1]

answer = (0,0)

for i = 0 to n-1

for j = i to n-1

if evaluate(i,j) >

evaluate(answer[0],answer[1])
answer = (i,j)

return answer

evaluate(a,b)

Θ(1) time

Θ(n2) time

Θ(n2) time

University of Sydney

50

Pre-processing

evaluate(a,n-1)

def preprocessing(A):

Speed up “evaluate”
subroutine by
pre-computing for all i:
B[i] = A[i] + … + A[n-1]

The rest is as before

def evaluate(a,b)

return B[a] – B[b+1]

n = size of A

B = array of size n+1

B[n] = 0

for i in 0 to n-1

Θ(1) time

Obs.

preprocessing runs in Θ(n2) time

evaluate(a,b)

B[i] = A[i] + … A[n-1]

⋮

evaluate(b+1,n-1)

University of Sydney

51

Reuse computation

Imagine trying to find the best window ending at a fixed index j:
OPT[j] = maxi ≤ j B[i] – B[j]

But we can also express OPT[j] recursively in a way that allows us to compute, in O(n) time, OPT[j] for all j

Finally, in O(n) time, find j maximizing OPT[j]

There is an Θ(n) time algorithm for finding the optimal investment window

Obs.

University of Sydney

52

Recap: Algorithm analysis

naive runs in Θ(n3) time

preprocessing runs in Θ(n2) time

With a bit of ingenuity we can solve the problem in Θ(n) time

Why we separate problem, algorithm, and analysis?

– somebody can design a better algorithm to solves a given problem – somebody can give a tighter analysis of an old algorithm

University of Sydney

53

This week

Tutorial Sheet 1: – Posted tonight

– Review of asymptotic analysis and graphs

– Make sure you work on it before the tutorial

Quiz 0

– 15 minutes long

– It won’t count as assessment. It’s just to review your knowledge of graphs – Relevant materials on graphs uploaded as “Self-Review – Graphs” on Ed

University of Sydney

54