Solving Recurrences Advanced Algorithms & Data Structures
Solving Recurrences Advanced Algorithms & Data Structures
COMP4500/COMP7500
10/8/2020
Overview of today
Admin
Recap of last week
Recursive algorithms
Calculating computational complexity
Tutorials
Tutorials start this week.
Solutions to revision exercises will become available the week after the tutorial.
COVID-19 :
Please wear masks if you are attending In-person tutorials
Allow 1.5m social distancing, when possible
If you are feeling unwell then you must stay at home.
You are requested to practice good hand hygiene
Course Profile ECP
Should be available very soon
The examination will be in the form of a pdf file you can download from Blackboard.
You can print the exam and write on the exam paper, or write your answers on blank paper, or write electronically on a suitable device.
You will then scan or photograph your work if necessary and upload your answers as a single pdf file.
Recap of last week: analysing algorithms
We use functions of input size to describe the:
best-case,
worst-case and
average-case
efficiency (e.g. time, space) of algorithms.
Recap of last week: analysing algorithms
We describe and compare these functions using asymptotic notation:
focus on the rate of growth of these functions for large inputs
abstract away from constant factors, lower order terms to give a machine-independent comparison
We use:
asymptotic upper bounds (),
lower bounds () and
tight bounds ()
Recap of last week: analysing algorithms
We use summations to describe the amount of work involved in loops, recursion etc.
Need to remember some maths to help us solve these summations.
Overview of this week
Recusive procedures are hard to analyse
Express running time as a recurrence (instead of, for instance, a summation for a loop) Merge-sort:
Three strategies:
Substitution: Use experience to guess; then prove by induction
Iteration: (also called recursion-tree method) Expand out the recurrence, obtaining a summation, and solve
Master method: Generalises the above work into 3 cases; but does not cover every case
/docProps/thumbnail.jpeg