Week 7 Flashcards
Difference between computability and complexity
Computability is an understanding of which problems admit algorithmic solutions
Complexity talks about the complexity of the problems for which there do exist algorithms.
Explain computability vs feasibility
Of those problems which are computable (there are effective procedures) it is useful to distinguish those that are FEASIBLY COMPUTABLE
Name the 3 complexity classes
LIN - linear algorithms
P - polynomial algorithms
EXP - exponential algorithms
Explain LIN
Linear algoithm has asymptotic behaviour of form n, where n is the size of the input
As a first approximation, a linear algorithm is likely to be feasible for all data sizes.
Explain P
A polynomial algorithm has asymptotic behaviour of the form n^c where n is the size of the input.
As a first approximation, many are feasible for practical input data sizes, but unfortunately many are not.
Explain EXP
Exponential algorithms have asymptotic behaviour of the form c^n, where n is the size of the input
As a first approximation, an exponential algorithm is infeasible for all but the smallest data sizes.
What major computer resources are there
Time - elapsed period from start to finish
Space - an amount of storage space
Hardware - an amount of physical mechanism
What is the Big O notation
Indicating the quality of an algorithm in terms of asymptotic worst-case runtime.
What is the Extended Church-Turing thesis
All notions of computation can simulate each other up to a polynomial factor.
There is significant doubt about this because a highly parallel computer may be able to efficiently compute what a sequential computer cannot.
What is the Sequential Computation thesis
All notions of sequential computation can simulate each other up to a polynomial factor. All sequential computers have related execution times - any algorithm which runs in polynomial time of one computer can run in polynomial time on any other.
Difference between sequential and parallel computers
On a sequential computer, the time taken by an algorithm must be at least O(n), because the algorithm must look through all input data
On a parallel computer, the time taken can be O(log(n)) because many parts of the input can be considered simultaneously.
How are benchmarks often flawed?
Non-reproducibility
Failure to optimize
Apples vs oranges
Cold vs hot runs
What is non-reproducibility
All configuration parameters should be published so the experiment can be reproduced. In addition, source code should be available to allow others to reproduce the experiments
What is failure to optimize
The performance of an improperly configured system can be significantly worse than a normal one. Use the same configuration used in previous publications.
What is apples vs oranges
A performance comparison between two systems can only be fair if both systems do the same thing. Check that same functionality is measured - one system must provide the same results as another in all cases
What are hot vs cold runs
Initial cold runs will take significantly longer than subsequent hot runs as relevant data needs to be loaded from persistant storage into cached memory. Time 10 runs, drop the lowest two, drop the highest two, average the remaining 6.
What is the Cobham-Edmonds Thesis?
Feasible problems are exactly those in P
Examples of problems in P
FFT
Shortest path in a graph
Maximum flow in a graph
Primality
What is FFT?
Converts waves into a spectrum
The Cooley-Tukey algorithm FFT is an O(NlogN) algorithm, which operates by decomposing an N-point time domain signal into N single-point time domain signals and calculating frequency spectra corresponding to these time domain signals.
What is shortest path in a graph?
Find shortest path from one node to another in a weighted graph
O(N^3) by comparing all possible paths through a graph between each pair of vertices.
What is maximum flow in a graph?
Used to find the maximum flow through a network at a time, from source to sink, given the maximum capacities of the links
O(MXf) where M is the number of links and f is the max flow.
What is the primality test?
For a binary number of n digits is O(sqrt(2^n))
One version (AKS) algorithm is O(n^12), and can be greatly reduced.
Matrix multiplication naive vs Strassen
Naive O(N^3)
Strassen O(N^2.8074)
