Week 7

Question 1

Difference between computability and complexity

Answer 1

Computability is an understanding of which problems admit algorithmic solutions

Complexity talks about the complexity of the problems for which there do exist algorithms.

Question 2

Explain computability vs feasibility

Answer 2

Of those problems which are computable (there are effective procedures) it is useful to distinguish those that are FEASIBLY COMPUTABLE

Question 3

Name the 3 complexity classes

Answer 3

LIN - linear algorithms
P - polynomial algorithms
EXP - exponential algorithms

Question 4

Explain LIN

Answer 4

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.

Question 5

Explain P

Answer 5

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.

Question 6

Explain EXP

Answer 6

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.

Question 7

What major computer resources are there

Answer 7

Time - elapsed period from start to finish
Space - an amount of storage space
Hardware - an amount of physical mechanism

Question 8

What is the Big O notation

Answer 8

Indicating the quality of an algorithm in terms of asymptotic worst-case runtime.

Question 9

What is the Extended Church-Turing thesis

Answer 9

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.

Question 10

What is the Sequential Computation thesis

Answer 10

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.

Question 11

Difference between sequential and parallel computers

Answer 11

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.

Question 12

How are benchmarks often flawed?

Answer 12

Non-reproducibility
Failure to optimize
Apples vs oranges
Cold vs hot runs

Question 13

What is non-reproducibility

Answer 13

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

Question 14

What is failure to optimize

Answer 14

The performance of an improperly configured system can be significantly worse than a normal one. Use the same configuration used in previous publications.

Question 15

What is apples vs oranges

Answer 15

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

Question 16

What are hot vs cold runs

Answer 16

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.

Question 17

What is the Cobham-Edmonds Thesis?

Answer 17

Feasible problems are exactly those in P

Question 18

Examples of problems in P

Answer 18

FFT
Shortest path in a graph
Maximum flow in a graph
Primality

Question 19

What is FFT?

Answer 19

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.

Question 20

What is shortest path in a graph?

Answer 20

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.

Question 21

What is maximum flow in a graph?

Answer 21

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.

Question 22

What is the primality test?

Answer 22

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.

Question 23

Matrix multiplication naive vs Strassen

Answer 23

Naive O(N^3)
Strassen O(N^2.8074)