1
Q
Give examples of real-world applications of algorithms
A
- Analysis of Big Data (machine learning algorithms)
- Social media (algorithmic marketing)
- online shopping (recommendation systems)
- Stock market (high-frequency trading algorithms)
- Search engines
2
Q
Give the formal definition of an algorithm
A
An algorithm is a sequence of steps for performing a task in a finite amount of time
3
Q
What does it mean that an algorithm runs in a finite amount of time?
A
That when we run the algorithm with input data, it should always stop.
4
Q
What is the mathematical definition of an algorithm?
A
A Turing Machine
5
Q
What do we use data structures for in regards to computational algorithms?
A
We use data structures to store, access and manipulate data in computational algorithms
6
Q
What is the definition of a good algorithm?
A
Algorithms which:
- utilise efficient data structures
- are formally correct in terms of providing the correct solution according the problem spec
- efficient in terms of speed and resources
7
Q
What are our three interests in regards to algorithm analysis?
A
- Primary interest: Running time/time complexity
- Secondary interest: space (memory) usage
- third interest: optimality of the output solution
8
Q
What are the two types of analysis?
A
- Experimental
- Theoretical
9
Q
What is experimental analysis of algorithms?
A
Analysis where we’re interested in the dependency of the running time on the size of the input.
10
Q
What is the size of the input in experimental analysis?
A
The amount of memory you need to use in order to represent your data in the computer
11
Q
What does experimental analysis involve?
A
Running our algorithm on input data designed for the purpose of testing it.
- This requires a good choice of sample inputs and an appropriate number of tests for statistical certainty
12
Q
What does running time depend on in algorithms?
A
It depends on both the size and instance of input and the algorithm used as well as the software and hardware environment on which it runs.
13
Q
Why might 3 different instances of inputs with the same size run through the same algorithm have varying running times?
A
This could be because those instances might be of varying difficulty or structural appearance.
- for example a for loop might be used in the algorithm and some input may qualify to evoke the for loop but others may not, despite being the same size of input
14
Q
In experimental analysis what do we do when we have multiple instances of running time for the same input size?
A
We record the average running time of those instances (find the mean)
15
Q
What are the potential drawbacks of experimental analysis
A
- they are performed on a limited set of test inputs (some problems may have infinite possible inputs so it would be impossible to test them all) so we must choose representatives of the set of input instances
- it requires all tests to be performed using the same hardware and software which is time consuming
- it requires implementation and execution of algorithms which is time consuming
16
Q
What are the benefits of theoretical analysis?
A
- can take all possible inputs into account simultaneously (by abstracting from those objects). For example, we do analysis for all inputs of a fixed size n
- can compare efficiency of multiple algorithms independent of hardware/software environments
- No implementation is needed
17
Q
How do we characterise the running time of an algorithm in theoretical analysis?
A
We represent the algorithm’s run time with a function f(n) where n is the non negative input size
18
Q
List common run time functions and their names in order of slowest to fastest
A
n - linear
log(n) - logarithmic
n^2 - quadratic
n*log(n), - sorting runtime
n^5 - polynomial
2^n - exponential
19
Q
What type of run time is the most efficient to scale with input size
A
Polynomial run times are the most efficient to scale with input size
20
Q
What do we need to perform formal theoretical analysis
A
- A formal language to describe algorithms (so it can be acted upon in a certain way and used to implement a solution if)
- a computational model in which algorithms are executed
- a metric for measuring running time
- a way of characteristing running time
21
Q
What is pseudo code?
A
- a high level description language for defining algorithms
- it provides a more structured description of algorithms
- allows for high level analysis of algorithms to determine their running time and space requirements
22
Q
What are the steps for finding the minimum element of a set of numbers, stored in an array A
A
- set the minimum to the first element of array A
- loop through the elements of array A for j to the length of array A
- compare the current minimum to the element in the value of the current index in the list
- if this is smaller, store it in the variable holding the minimum
- once all elements in the list have been looped through, return the minimum value.
23
Q
describe pseudocode
A
- is a mixture of natural and high-level programming languages
- describes a generic implementation of data structures or algorithms
- include expressions, declarations, variables initialisation and assignments, conditionals, loops, arrays and method calls.
24
Q
Describe the computational model we’re abiding by
A
- typically found on a modern day computer
- CPU connected to a bank of memory cells, CPU can access memory
- each memory call can store a number, character or address
- we use random access machines which can address every single memory cell in the bank of memory in constant time
25
What is reaching a specific cell counted as in Random access machines
counted as one single primitive operation performed in constant time.
26
What is unit time?
An abstraction for saying how many seconds it takes
27
What are examples of primitive operations and an assumption about them?
- single addition, multiplication, comparison are all examples
- assumption is they require constant time to perform
28
How do we analyse run time of an algorithm in theoretical analysis?
We count the number of operations executed during the course of the algorithm
29
How many primitive operations take place in the finding the minimum algorithm?
3*(length[A] - 1) primitive operations since:
- there's 1 assignment to the minimum at the start + 1 assignment to the minimum during the loop = 2
- And there's 3 occurrences of length[A]-1, once are the start of the loop, and twice when comparing the current minimum and the indexed value.
30
What’s the motivation behind the assumption, every cell in the memory can be accessed in constant time, so addressing time of the cell in an array for example takes constant time?
- Every device has a fixed constant amount of memory, for example 250 gb
- if we have a fixed constant number of cells then addressing one cell (could be the first or the last) takes a fixed amount of time
31
why is it ideal that it in the random access machine it takes constant time to access any cell in memory?
It means abstraction is possible, greatly simplifying analysing algorithms (as we don't have to specify which cell we need)
32
What does average-case complexity refer to?
Running time of an algorithm as an average taken over all the inputs of the same size
33
What does worst-case complexity refer to?
Running time of an algorithm as the maximum taken over all the inputs of the same size (what we're most interested in)
34
What sort of input will give us the fastest run time of the finding the minimum algorithm?
A list that goes in increasing order as n-1 number of operations is never carried out since the minimum never needs to be re-assigned/declared
35
How can we find the average running time of an algorithm that can take instances of different sizes?
- In practice this would be done using a probability distribution over such inputs, then analysing what the expected performance is, to estimate average running time
36
What is asymptotic notation?
- Allows for characterisation of the main factors influencing running time of an algorithm
- we abstract by counting only asymptotically, this is so we can assume each primitive operation takes constant time
37
When and why do we use asymptotic notation?
- it lets us compare run time of several algorithms
- used in simplified analysis that estimates the number of primitive operations executed by an algorithm
38
What is big O notation
- most commonly used form of asymptotic notation
- given two positive functions f(n) and g(n) (which measure run times of algorithms), we says f(n) is O(g(n)) meaning f(n) belongs to the class big O of g(n) if there are constants c and n0 such that f(n) <= c * g(n) for all n >= n0
39
What does it mean that f(n) <= c * g(n) for all n >= n0
it means that at some point before n0 f(n) can be greater than c * g(n) but at the position of n0 f(n) is below g(n) then for all the time up to time infinity
40
Prove that for f(n) = 7n - 4, f(n) ∈ O(n)
1. must find constants c and n0 such that 7n - 4 <= c*n for all n >= n0
2. possible solution is c = 7 and n0 = 1 because this holds for all of n since 7n - 4 is always strictly < 7n
3. there's an infinite number of choices for n0 and c since any real number c ≥7 and any integer n0 ≥1 would satisfy this.
41
Why do we want to find the smallest possible values of c and n0
Because we want to show that this function f is c * some function g
42
Why is f(n) = 3n^2 + n + 16 ∈ O(n^2)?
- can prove n <= n^2 for any n >= 1, we just divide both sides by n to get n >= 1
- we can also prove n^2 >= 16 for any n >= 4, and if n = 4, then n >= 1 holds since 4 >= 1
- the compare each term with it's worst case:
3n^2 <= 3n^2, n <= n^2 (upper bounding n by n^2) and 16 <= n^2
- summing up the worst case scenario gives us 3n^2 + n^2 + n^2 = 5n^2
- 3n^2 + n + 16 <= c * g(n) - 5 * n^2, so c = 5 and g(n) = n^2, and n0 = 4
43
list the rules of big O notation upper bounds
- n >= 1
- n^2 >= n
- n >= log(n)
- log(n) >= log(log(n))
- for any polynomial, ak*n^k ∈ O(n^k)
- for any polynomial, ak*n^k ∈ O(n^k) ∈ O(n^j) where j > k
- n >= √n
- 2^70 ∈ O(1)
- 5/n ∈ 1/n ∈ 1/√n
44
Write in order of increases slowest (shorter) to increases fastest (longer) in runtime typical functions of asymptotic notation
- Logarithm O(log2(n))
- Linear O(n)
- Quadratic O(n^2)
- Polynomial O(n^k) where k > 0
- Exponential O(a^n) where a > 1
45
What are the three types of asymptotic notation?
- Big O
- Big Omega Ω
- Big Theta Θ
46
What is big Ω (omega) notation?
- The opposite to big O notation
- this is lower bounding
- so f(n) is Ω(g(n)) if there exists c and n0 such that f(n) >= c*g(n) for all n >= n0
47
What is big Θ (theta) notation?
- when f(n) satisfies both big O and big Ω
- f(n) is Θ(g(n)) if f(n) is O(g(n)) and f(n) is Ω(g(n))
48
Prove that 3log(n) + loglog(n) is big Ω(log(n))
- need to find c and n0
- so 3log(n) + log(log(n)) >= c*log(n)
- since log(log(n)) is positive we know 3log(n) + log(log(n)) will always be > log(n)
- so we can do 3log(n) + log(log(n)) >= c*log(n)
and then simplify to give 3log(n) = c*log(n), so c = 3 and n0 = 1
49
Why can big O notation big misleading in terms of running time?
- Since we ignore terms of lower order in big O notation, even if the constant factors are really large (so will take a long time to run), we ignore these if they are not the largest term asymptotically
- for example 10^100n is still O(n) when likely 10^100 is larger than n
50
What does tractable mean?
a problem is defined as tractable if an algorithm exists to solve it that can be executed in polynomial time or less.
51
What is an optimisation problem?
For a given instance, the objective of the problem is to find a solution that optimises (max or min) a given objective function
52
Give an example of a real life optimisation problem
Renter's Dilemma:
- alice wants to listen to some music. Every time she streams a song it costs x pounds to rent the song (also have to pay to replay a song)
- Suppose it costs y pounds to buy all the songs on an album, in which she can replay songs as many times as she likes, let y = 10 * x
Dilemma:
- when should alice buy the whole album instead of streaming a song, once at a time?
53
What is the dilemma in the renter's dilemma?
Dilemma: Decide when to buy the whole album instead of streaming songs one at a time?
-If she buys the album before streaming any song and then decides that she doesn’t like any, then she has spent 10 times more than she should.
-If she streams many times and never buys the album, then she will spend potentially even more than 10 times more than she should.
54
What is the issue in optimisation problems?
The issue is the future, as it's unknown, so we can't predict the suitability of certain variables
55
How can we best solve the renter's dilemma
- we can use the paradigm of online algorithms
56
What is an online algorithm?
An online algorithm A responds to a sequence of service requests, each service request is associated with a cost.
57
What is the difference between an online and offline setting of online algorithms?
Online setting:
- Service requests arrive sequentially one by one and algorithm A must completely finish serving that request before it receives the next request.
- So the algorithm must decide whether to serve a request or not before seeing future requests
Offline setting:
- The algorithm receives the entire sequence of requests in advance so it can/will do whatever is optimal
58
What is competitive analysis and OPT?
- Compare a given online algorithm A to an optimal offline algorithm, OPT.
- OPT is very powerful, as we assume it knows the future/everything in advance
59
What does cost(A,R) and OPT(A,R) mean?
- cost(A,R) is the cost the algorithm A pays for serving the whole request sequence R
- OPT(A,R) is the optimum cost for the whole request sequence R, assuming OPT knows the whole sequence in advance
60
When do we class an online algorithm A as c-competitive?
- an online algorithm is c-competitive for some constant >= 1 if the cost of serving sequence R is at most c * the optimum cost of serving r plus b (which is some constant independent of the input data)
- in most cases we forget about b and just have cost(A,R) <= c*cost(OPT, R)
61
What must be true to say that an algorithm is strictly c-competitive
a must be c-competitive and b must = 0
62
What does it mean if we've found a c-competitive algorithm?
That we've found an algorithm that is not much worse (only c times worse) than the offline strategy for online decision making without knowing the future.
- for example if c = 2 then it means our online algorithm is not worse than twice the running time of the optimal solution
(if c = 2, this is a c-competitive algorithm)
63
What is the analysis of the renter's dilemma
Strategy 1: If Alice streams songs n times (she has n such requests), this online algorithm of always “renting” will cause her to spend n/10 times more pounds than she would have just buying the album - x*m/10x = n/10 = competitive ratio which is a pretty bad competitive ratio because if n is large, for instance n = 1000, n/10 = 100
Strategy 2: buying the first time has a worst-case competitive ratio of 10 because she’ll pay 10*x instead of x, if she dislikes the first song and never listens to the album again - 10x/x = 10
2-competitive strategy: Rent for 10 times, and then buy the album. If there are 10 requests and they all want to listen to a song then rent it for the first 10 times, on the 11th request to listen to a song from an album, then we buy the album. Here we can only lose twice the cost of the optimum solution.
- The worst case is if she never listens to the album that she just bought. But then she has spent 10x + y = 2y pounds, when the optimal offline algorithm spends 10x , so the competitive ratio is 2.
64
Why are NP-complete problems equivalent in a formal computational sense?
Because if one of them can be solved, all of them can be solved due to polynomial time reduction
65
What are the 4 types of simple proof techniques we use to analyse algorithms
- proof by mathematical induction
- proof by contradiction
- proof by contrapositive argument
- disproof by counterexample
66
In these examples state what the induction base is for
1.n(n+1)/2 for all n > 1,
2. 2^n = n >= 5
1. induction base = 1
2. induction base = 5
67
Explain the steps of proof by induction:
- prove the base case holds (which is typically the smallest value of the parameter (n)), can do this by substituting this value into the statement
- assume the statement is true for some integer value k >= base case. This is called the induction hypothesis
- inductive step: prove the statement for k+1, by substituting in k+1 into the statement
- Manipulate the equation algebraically, using the induction hypothesis, until it matches the desired form
- conclude that the statement holds true for all positive integers n since the inductive step held.
68
How do we perform a proof by contradiction
- We consider the negation of a statement and try to prove that the negation leads to a contradiction and therefore the original statement must be true.
69
Explain how we perform a proof by contrapositive
- the contrapositive means p implies q
- we say if p is true then q must be true and if q is not true then p is not true.
70
How do we perform a proof by counter example?
- Usually there is a generic claim that 'element x in a set s has property p'
- we just need to produce an example that proves it's not
- for example if we have the statement that every number of the for 2^1 -1 is prime where i > 1
- we can counter prove this is incorrect by saying 2^4-1 = 15, which is not prime since 3*5 = 15
