topic 3

Question 1

what does the phrase analysis of algorithms cover?

Answer 1

it covers the consideration of algorithms from the point of view of how ‘good’ they are (with respect to some resource).

Question 2

why do we focus on algorithms rather then the implementation of algorithms?

Answer 2

We work only with algorithms, and not their implementations, in the strong expectation that our analysis will be machine-independent but still closely related to and reflective of the time taken by any implementation of the algorithm on any given processor.

Question 3

what is one of the fundamental assumptions when defining the time taken by any algorithm which is described using our pseudo-code

Answer 3

that variables can be manipulated in a small, fixed number of units of time, as can basic operations involving variables. So, for example, an assignment of some basic value to a variable or a comparison of two variables can be done in at most c units of time, say, where c is some fixed integer.

Question 4

what is the assumption about the time taken for any basic algorithim operation?

Answer 4

Any basic algorithmic operation can be undertaken in at most c units of time.

Question 5

what determines whether an algorithm is basic?

Answer 5

any operation that can be undertaken by a processor in a small number of units of time (c units) is deemed to be basic and this is determined by what the algorithmic operation translates to when compiled and executed on a processor

Question 6

what is an assumption made about the size of numbers n in the selection sort?

Answer 6

the n numbers involved in the input to Selection-sort are all sufficiently small that they canbe dealt with by our processor in the fetch-decode-fetch-execute cycle. we always assume that our input objects are of managable size

Question 7

what is a fundamental assumption about worst case upper bounds and size?

Answer 7

The size of an input is the number of basic objects it contains, and in general the time taken by an algorithm is strongly influenced by the size of the input and increases as the size of the input increases.

Question 7

what is a fundamental assumption about worst case upper bounds and size?

Answer 7

The size of an input is the number of basic objects it contains, and in general the time taken by an algorithm is strongly influenced by the size of the input and increases as the size of the input increases.

Question 8

what is an assumption about the finite amount of inputs in a selection sort?

Answer 8

we only ever have a finite number of inputs of any size n. For although there are an infinite number of potential input numbers (forming elements of an input list to Selection-sort),at some point the size of these numbers will get so big so as to counteract our assumption that any such number can be ‘handled’ by our algorithm (and the underlying computer for which this algorithm is to be implemented) in our small number c of time units.

Question 9

what are two different resources used by an algorithm that we might measure?

Answer 9

time taken by an algorithm or the amount of memory used by an algorithm

Question 10

What is the worst-case time complexity of an algorithm? Why is it expressed as a function on the natural numbers?

Answer 10

the worst case upper bound b is a function that is a boundary above the algorithms’ runtime function, when that algorithm is given the inputs that maximize the algorithm’s run time. it is expressed as a function of natural numbers as we group the inputs together according to their size whivh is defined as a natural number reflecting their natural size of the input, and then to express our worst case upperbound as a function of these natural numbers so that any input of size n can be completed in at most f(n) units of time.

Question 11

why can the worst case upper bound of a selection sort not be completed in b units of time?

Answer 11

ideally you would want the worst case upper bound to be b units of time however this is not possible as if the list of atleast (b/c)+q numbers take atleast c[(b/c)+1) units of time which is greater than b

Question 12

what is the time complexity ?

Answer 12

Time complexity is defined as the amount of time taken by an algorithm to run, as a function of the length of the input. It measures the time taken to execute each statement of code in an algorithm. the worst case upper bound function is a time complexity

Question 13

what is the constant c meant to represent?

Answer 13

the unit of processor time that is needed to complete the basic instruction. each processor time will have a different constant c. it is some small fixed integer

Question 14

what is the cost of following the control flow?

Answer 14

the cost is zero

Question 15

how has the worst case upper bound reduced the problem?

Answer 15

the problem is now reduced to counting how many units of time the algorithm takes in the worse case when we restrict all inputs to be of size n.

Question 16

what is the main use of the time complexity?

Answer 16

the main use of the time complexity is to compare algorithms with one another. this can be used to decide which algorithm is best

Question 17

why does the c function become irrelevent when comparing the two algorithms?

Answer 17

as both algorithms will be in terms of c, the c will cancel out so as a result the final decision is independent from c

Question 18

what does the judgement on which algorithm to use based on?

Answer 18

the dominant term in the time complexity ie which has the largest power. this is due to the fact that the larger power will grow much faster then lower powers so when n gets large the larger power will be algorithmically better.

Question 19

what is the definition of big O notation?

Answer 19

For two functions f, g : N → N, we write f = O(g) if there exists some n0 ∈ N and some positive rational k ∈ Q such that f (n) ≤ kg(n)whenever n ≥ n0.

Question 20

why is there a requirement of f (n) ≤ kg(n)whenever n ≥ n0?

Answer 20

caters for when some algorithm might run quicker than another but only for a small number of inputs of a small size

Question 21

what is the role of the constant k?

Answer 21

we want a machine independent evaluation of the time taken by the algorithm. the Big O definition allows us to think of functions that are different only by a multiplicative constant as ‘essentially the same’.

Question 21

what is the role of the constant k?

Answer 21

we want a machine independent evaluation of the time taken by the algorithm. the Big O definition allows us to think of functions that are different only by a multiplicative constant as ‘essentially the same’.

Question 22

what is the pratical relevence of big O notation?

Answer 22

asymptotic time complexity is a reasonable pratical guide to which algorithm to use for a particular problem?

Question 23

what is the flaws with the big O notation that relate to hidden constants?

Answer 23

it can be the case that the constants hidden by the big-O notation are quite large (large enough to have a practical significance). On occasion,
an algorithm with good asymptotic time complexity can be practically unusable because of large hidden constants.

Question 24

what are the flaw with the big O notation that relates to realisim?

Answer 24

Often a worst-case analysis is not realistic, as the worst-case inputs are few and far between or do not arise very often in practice. For example, the sorting algorithm Quick-sort has worst-case time complexity O(n2) but average-case time complexity O(n log(n)).

Question 25

what is the flaw with the big O notation that relates to memory?

Answer 25

If memory is sparse then algorithms such as Selection-sort and Bubble-sort might be favoured over Merge-sort, despite their asymptotic time complexities being worse (O(n2) is comparison to Merge-sort’s O(n log(n))),as the first three algorithms are in-place sorting algorithms, in that the list is sorted without requiring substantial extra memory, beyond that storing the input list, whereas Merge-sort requires significant additional memory in order to do the merging

Question 26

what is a flaw with the big O notation that relates to the enviroment

Answer 26

the environment within which a sorting algorithm is used can have an impact on the choice of algorithm. Suppose that the input list of numbers is streamed over the Internet and so initially not all of the input is available. In this scenario, Bubble-sort might be the algorithm chosen as it can be easily modified to work within this setting.

Question 27

why is it important for repeated small improvements in algorithms such as matrix multiplication?

Answer 27

the naive matrix multiplication has a time complexity of O(n^3) whereas the most recent time complexity is now O(n^2.3727). it is not uncommon for computers to apply matrixes with millions of rows and coloumns. using the naive method of multiplication it would take 11,574 days to complete however using the newest improvement will only take 2.08 days. he real point is that even minute improvements such as that above results in significant real savings as nowadays the amount of input data we work with is huge.

Question 28

what is the definition of a problem that is efficently solvable?

Answer 28

We define that a problem is efficiently solvable (or tractable) if it can be solved by an algorithm of polynomial time complexity; that is, it can be solved by an algorithm of time complexity O(n^k), for some fixed integer k.

Question 29

what does the denotion P mean?

Answer 29

We denote the complexity class of all decision problems (infinitely many of them, note) that are efficiently solvable as P, read as ‘polynomial-time’.

Question 30

what does it mean for a decision problem to be efficiently checkable?

Answer 30

that given a potential witness that some instance is a yes-instance, we can check in polynomial-time whether the potential witness is indeed a witness.

Question 31

what are the two valid objections to the defintion of efficently solvable?

Answer 31

1) what about the hidden constants in the big O notation? how can you say an algorithm is efficently solvable in polynomial time when the hidden constants are massive
2) what about an algorithm where k is massive, surely the number will also be massive

Question 32

what are the thing in common with the decision version of the TSP, graph colouring and the independent set problem

Answer 32

they all have a witness which you can check if the solution is valid

Question 33

how is the complexity class NP defined?

Answer 33

We define the complexity class NP, read as ‘non-deterministic polynomial-time’, as those decision problems that are efficiently checkable.

Question 34

why is P a subset of NP?

Answer 34

suppose that X ∈ P. In order for this problem X to be in NP, we need to show that it is efficiently checkable; that is, if given some potential witness, we can ascertain in polynomial-time whether the witness verifies that a given instance is a yes-instance. Suppose that the witness we provide for any instance of X is empty; that is, we provide no witness! Even without any witness, because X ∈ P we can decide in polynomial-time whether any instance is a yes-instance. the fact that P is efficiently solvable implies that it is efficiently checkable

Question 35

what is the most fundamental open problem in computer science?

Answer 35

is P=NP. this is equivelent to the question deciding whether there are problems in NP that are not in P that is whether there are problems which are efficently checkable but not efficently solvable

Question 36

what is a polynomial time reduction or polynomial time transfrormation of X to Y?

Answer 36

it is an algorithm which essentially converts a decision problem X into a decision problem Y and does this in polynomial time

Question 37

what is the essential qualitys of a polynomial time reduction?

Answer 37

it takes an instance I of X as input and provides an instance a(I) of Y as output and the instance I of X is a yes instance if and only if a(I) is a yes instance of a(I) of Y is a yes instance and vice versa for no instances

Question 38

what is the theorem related to polynomial time reductions?

Answer 38

If X →poly Y and Y ∈ P then X ∈ P.

Question 39

what does it mean for a problem to be NP complete?

Answer 39

if there exists a problem Y which is a part of NP which has the property that for any problem X which is a part of NP can be tranformed into Y through a polynomial time reduction. this is called a NP complete problem

Question 40

how can you prove P=NP?

Answer 40

if Y is an NP complete problem then P=NP if and only if Y is a part of P as if every problem X which is a part of NP can be transformed into Y which can be solved in polynomial time then this means that every problem X can be solved in polynomial time also

Question 41

what proved NP complete in 1971?

Answer 41

boolean satisfiability which was proved by

Question 42

what is a NP hard problem?

Answer 42

we call a search or optimisation problem NP hard if its solution in polynomial time would imply that P = NP

Question 43

what is the easiest way to deal with NP hardness?

Answer 43

you could ignore the fact that it is a NP hard question and just launch a brute force attack where we generate all possible witnesses to an instance of the problem and pick the best .

Question 44

what is the issue with using the brute force method when dealing with NP hardness?

Answer 44

the number of witnesses needing to be generated is exponential in the size of the input instance. for example in the travelling sales person there are (n-1)! tours which means when we reach 29! this is greater than the number of instructions executed by an intel core i7 processor started at the beginning of time

Question 45

what is a genetic algorithm and how is it used to solve optimisation problems?

Answer 45

an algorithm that is inspired by nature. there is a population of individuals which represent solutions to the problem and each of these individuals have some fitness score( representing the quality of the solution) . this population is intially randomly generated. a new population is formed by breeding individuals with the fitter individuals being more likely to be selected and the breeding occurs through crossover and mutation. this process goes on until a new population has been generated of the same size as previous. this process is the interated until some termination condition is met

Question 46

what is ant colony optimisation?

Answer 46

a set of software agents called artificial ants search for good solutions to a given optimisation problem. to apply ACO the problem must be transformed into the problem of finding the best path in a weighted graph ( each edge has a numeric weight and these weights change continuosly) from start to finish. they build solutions by moving in the graph with the solution construction method being stochastic(random) but biased by a pheromone model. as ants move along paths they will increase the weights which in turn attracts more ants to take that path. edges that are not being used will have their pheromone evaporate. this hopefully will lead to an optimal path emerging.

Question 47

what is the cross over breeding method?

Answer 47

two parent strings are chosen from the current population and are both split at the same randomly-generated point. The prefix of the first parent string is conjoined with the suffix of the second, and the prefix of the second parent string is con-joined with the suffix of the first. The fittest of the two offspring is retained as the child.

Question 48

what is the mutation breeding method?

Answer 48

a position in the child string is chosen at random and the digit is randomly changed with some probability.