COMP10001 Lecture Notes - Lecture 11: Solution Set, Binary Search Algorithm, Weather Forecasting
25 May 2018
School
Department
Course
Professor
An algorithm is a set of steps for solving an instance of a particular problem type
-
An algorithm should terminate for every input with the correct output
○
Incorrect algorithms can either terminate with the wrong output or not terminate
○
Correctness
-
Runtime
-
run as fast as possible
○
Storage
-
require as little storage as possible
○
Efficiency
-
Algorithms:
Brute force
Divide and conquer
Exact
-
calculate the solution set with a guarantee of correctness
○
Simulation
Heuristic search
Approximate
-
estimate the solution set, ideally with an additional estimate of how close
this is to the exact solution set
○
Exact vs approximate methods
-
A candidate answer is easy to test
The set of candidate answers is ordered or can be generated exhaustively
Assumptions
○
Generate candidate answers and test them one by one until a solution is found
Strategy
○
Linear search
Test whether a number is prime
Examples
○
Brute force
-
Solve a smaller sub
-
problem
Extend the sub
-
solution to create the solution of the original problem
Can also be iterative
Strategy
○
Binary search
Many sorting algorithms
Examples
○
Storing the value for each element used to avoid having to recalculate it
Can lead to more efficient algorithms
Memoisation
○
Divide and conquer
-
Randomly generate a large amount of data to predict an overall trend
Use multiple runs to verify the stability of an answer
Used in applications where it is possible to describe individual properties of a
system but hard to capture the interactions between them
Strategy
○
Weather forecasting
Movement of planets
Prediction of share markets
Examples
○
Simulation
-
Search via a cheap, approximate solution which works reasonably well most of the
time
Strategy
○
Heuristic search
-
Algorithm families:
Week 11
Saturday, 19 May 2018 11:24 AM
Foundations of Computing Page 1
Document Summary
A(cid:374) algo(cid:396)ith(cid:373) is a set of steps fo(cid:396) sol(cid:448)i(cid:374)g a(cid:374) i(cid:374)sta(cid:374)(cid:272)e of a pa(cid:396)ti(cid:272)ula(cid:396) p(cid:396)o(cid:271)le(cid:373) t(cid:455)pe. A(cid:374) algo(cid:396)ith(cid:373) should te(cid:396)(cid:373)i(cid:374)ate fo(cid:396) e(cid:448)e(cid:396)(cid:455) i(cid:374)put (cid:449)ith the (cid:272)o(cid:396)(cid:396)e(cid:272)t output. I(cid:374)(cid:272)o(cid:396)(cid:396)e(cid:272)t algo(cid:396)ith(cid:373)s (cid:272)a(cid:374) eithe(cid:396) te(cid:396)(cid:373)i(cid:374)ate (cid:449)ith the (cid:449)(cid:396)o(cid:374)g output o(cid:396) (cid:374)ot te(cid:396)(cid:373)i(cid:374)ate. Sto(cid:396)age - (cid:396)e(cid:395)ui(cid:396)e as little sto(cid:396)age as possi(cid:271)le. E(cid:454)a(cid:272)t - (cid:272)al(cid:272)ulate the solutio(cid:374) set (cid:449)ith a gua(cid:396)a(cid:374)tee of (cid:272)o(cid:396)(cid:396)e(cid:272)t(cid:374)ess. App(cid:396)o(cid:454)i(cid:373)ate - esti(cid:373)ate the solutio(cid:374) set, ideall(cid:455) (cid:449)ith a(cid:374) additio(cid:374)al esti(cid:373)ate of ho(cid:449) (cid:272)lose this is to the e(cid:454)a(cid:272)t solutio(cid:374) set. The set of (cid:272)a(cid:374)didate a(cid:374)s(cid:449)e(cid:396)s is o(cid:396)de(cid:396)ed o(cid:396) (cid:272)a(cid:374) (cid:271)e ge(cid:374)e(cid:396)ated e(cid:454)hausti(cid:448)el(cid:455) Ge(cid:374)e(cid:396)ate (cid:272)a(cid:374)didate a(cid:374)s(cid:449)e(cid:396)s a(cid:374)d test the(cid:373) o(cid:374)e (cid:271)(cid:455) o(cid:374)e u(cid:374)til a solutio(cid:374) is fou(cid:374)d. E(cid:454)te(cid:374)d the su(cid:271)-solutio(cid:374) to (cid:272)(cid:396)eate the solutio(cid:374) of the o(cid:396)igi(cid:374)al p(cid:396)o(cid:271)le(cid:373) Sto(cid:396)i(cid:374)g the (cid:448)alue fo(cid:396) ea(cid:272)h ele(cid:373)e(cid:374)t used to a(cid:448)oid ha(cid:448)i(cid:374)g to (cid:396)e(cid:272)al(cid:272)ulate it. Ra(cid:374)do(cid:373)l(cid:455) ge(cid:374)e(cid:396)ate a la(cid:396)ge a(cid:373)ou(cid:374)t of data to p(cid:396)edi(cid:272)t a(cid:374) o(cid:448)e(cid:396)all t(cid:396)e(cid:374)d. Use (cid:373)ultiple (cid:396)u(cid:374)s to (cid:448)e(cid:396)if(cid:455) the sta(cid:271)ilit(cid:455) of a(cid:374) a(cid:374)s(cid:449)e(cid:396)
