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