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), discrete math (graphs, big O notation, proof techniques) and programming.
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:
Joe Godbehere (TA) Patrick Eades Milutin Brankovic Shane Arora
Joel Gibson
Oliver Scarlet Madeleine Wagner Simon Koch
The University of Sydney
3
Course Arrangements
Course book:
J. Kleinberg and E. Tardos Algorithm Design Addison-Wesley
Outline:
13 lectures (Thu 10-12 & 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 – Canvas (checked by Turnitin) Implementation – Ed
Collaboration:
General ideas – Yes! Formulation and writing – No!
Read Academic Dishonesty and Plagiarism.
The University of Sydney
5
Quizzes
10 assessed quizzes (and one background quiz)
Average of best 8 of the 10 quizzes will count
Worth 15% of final mark
Quizzes are due before midnight each Wednesday – 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 5% of the total marks per day. Assignments > 10 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 – (5% * 5.0) = 4.0 – 0.25 = 3.75 Between 24 and 48 hours = 4.0 – (10% * 5.0) = 4.0 – 0.5 = 3.5
Theory part needs to be typed (LaTeX > GDocs, Word), no
handwritten submissions accepted
Some assignments will involve programming
The University of Sydney 7
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 8
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 9
Assignment 1
Released: Week 2 (March 7)
Due: Week 4 (March 20 23:59:00)
Solutions out: March 27 23:59:00 (No submissions accepted after this) Returned: Week 5 (March 28)
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 Canvas/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
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 University of Sydney 13
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 14
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 15
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
16
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 17
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 19
EMERGENCIES – Be prepared
www.sydney.edu.au/whs/emergency
The University of Sydney 20
EMERGENCIES
WHERE IS YOUR CLOSEST SAFE EXIT ?
The University of Sydney 21
EMERGENCIES
The University of Sydney
22
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 23
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: Shari Lee 9351 4158
The University of Sydney
24
COMP3027: Algorithm Design
Lecture 1b:
Algorithm Analysis
William Umboh
School of Computer Science
The University of Sydney
25
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
!26
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
!27
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
!28
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
!29
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
!30
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
!31
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
!32
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) )
University of Sydney
!33
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)
University of Sydney
!34
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
!35
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
!36
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
!37
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
!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
Θ(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
!39
Pre-processing
Speed up “evaluate”
subroutine by
pre-computing for all i:
B[i] = A[i] + … + A[n-1]
The rest is as before
evaluate(b+1,n-1)
def evaluate(a,b)
return B[a] – B[b+1]
n = size of A
B = array of size n+1
for i in 0 to n-1
B[i] = A[i] + … A[n-1]
B[n] = 0
⋮
evaluate(a,b)
evaluate(a,n-1)
def preprocessing(A):
Θ(1) time
Obs. preprocessing runs in Θ(n2) time University of Sydney
!40
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
!41
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
!42
This week
Tutorial Sheet 1: – posted tonight
– make sure you work on it before the tutorial
Quiz 0
– 15 minutes long
– It won’t count as assessment. It’s just to learn about your math background
Practice Quiz (optional)
– To familiarise yourself with the quiz interface
University of Sydney
!43