# CS代考程序代写 data structure database 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), 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