Algorithms and Complexity

Question 1

Define an algorithm

Answer 1

A finite set of computational steps that transform input into output

Question 2

Why do we use algorithms?

Answer 2

Algorithms are effective methods for solving a class of problems

Question 3

What are common properties of algorithms?

Answer 3

1. The inputs to an algorithm must be finite
2. The inputs to an algorithm represent instances of the problem
3. An algorithm should produce the correct outcome
4. An algorithm should terminate

Question 4

Give examples of algorithm formats

Answer 4

Text, pseudocode, flowcharts, and computer code

Question 5

What makes an algorithm better than another?

Answer 5

We evaluate algorithms based on their space and time complexity

Question 6

Define space complexity

Answer 6

The amount of memory required by an algorithm to run to completion

Question 7

What are the two types of the memory that is required by an algorithm?

Answer 7

The fixed and the variable memory

Question 8

Define the fixed part of memory needed by an algorithm

Answer 8

The amount of memory required to store certain data/variables whose size is independent of the input to the algorithm

Question 9

Define the variable part of memory needed by an algorithm

Answer 9

The amount of memory required to store variables whose size is dependent on the input to the program

Question 10

Define time complexity

Answer 10

The theoretical relationship between the time an algorithm will take to run and the size of its input expressed as a function of the size of the inputs

Question 11

What factors effect runtime?

Answer 11

The size of inputs, the organisation of the inputs, the optimal operating temperature and the number of processor cores

Question 12

What case do we consider when evaluating the runtime of an algorithm?

Answer 12

The worst case scenario

Question 13

Why is it rare to have an algorithm with the best time and space complexity?

Answer 13

Often in decreasing the time or space complexity we increase the other meaning that we either need to work out whether our program should prioritise speed or memory or we need to balance the two equally

Question 14

Why would we not focus on the worst case scenario with regards to runtime?

Answer 14

If the worst case scenario is very rare there is little point in considering it in which case we would consider the average case

Question 15

Describe an experimental method of determining the runtime of a program

Answer 15

Running the program for a range of inputs and plotting the runtime

Question 16

Why do we rarely use an experimental approach to determine the runtime of a program?

Answer 16

You need to implement the algorithm for every input and also ensure that the running conditions are exactly the same for every test

Question 17

What is an alternative methods to determining how long an algorithm will take to run that is not experimental?

Answer 17

Operation counting

Question 18

What problem do we face with operation counting?

Answer 18

We need to determine what counts as one operation independent of which programming language it is in because there are differences between programming languages

Question 19

What does operation counting mean?

Answer 19

Counting how many operations are in an algorithm by tracing it through and working out how many will be executed for different inputs

Question 20

Why do we have different cases when analysing runtime using operation counting?

Answer 20

The runtime is not just dependent on the number of operations but also on the organisation of the input

Question 21

What does the notation T(n) mean?

Answer 21

The overall program time as a function of n

Question 22

How do we determine the average case for the runtime of a program if we cannot determine the runtime for every instance of inputs?

Answer 22

We work out the average number of times an instruction will be executed using the Nth partial sum equation and then use this to determine the average runtime

Question 23

What is the worst case time complexity for a linear search?

Answer 23

T(N) = 3N + 3

Question 24

How does a sentinel search work?

Answer 24

It checks to see whether the desired element is at the end of the list, if it is then it’s returned, if not then it sets the last item in the list equal to the desired element. This means that you do not have to perform the check to see whether you are out of bounds.

Question 25

What is the worst case time complexity for a sentinel search?

Answer 25

T(N) = 2N + 3

Question 26

What is the worst case time complexity for a binary search?

Answer 26

T(N) = C1 + C2log(N)

Question 27

What does the growth of functions describe?

Answer 27

How the runtime for a function increases as the number of input elements increases

Question 28

What does Big-Ohm represent?

Answer 28

The best case time complexity

Question 29

What does Big-O represent?

Answer 29

The worst case time complexity

Question 30

What does Big-Theta represent?

Answer 30

The average time complexity

Question 31

What is an intractable problem?

Answer 31

A problem which does not have a solution with a time complexity that is less than polynomial time

Question 32

What is a super polynomial function?

Answer 32

A function which has a time complexity greater than polynomial

Question 33

Define tractable

Answer 33

A problem which has an algorithmic solution with a polynomial time complexity or better

Question 34

What are P problems?

Answer 34

Problems for which there is a polynomial time algorithm

Question 35

What are EXP problems?

Answer 35

Problems for which there is an exponential time algorithm

Question 36

What are R problems?

Answer 36

Problems solvable in finite time

Question 37

T/F: Even if a problem is intractable, checking a solution to the problem is tractable

Answer 37

True

Question 38

What is an exhaustive search?

Answer 38

Often the process for many naive algorithms which involves checking all possible answers

Question 39

Downsides to exhaustive search

Answer 39

It can lead to combinatorial explosion and an exponential running time

Question 40

NP problems definitions

Answer 40

Non deterministic polynomial time = decision problems that can be checked in polynomial time

Question 41

What would happen if we proved that NP != P?

Answer 41

1. Prove that for some questions there is no clever shortcut to find the right answer 2. Prove there is a way to obscure information 3. Understand a lot more about computation

Question 42

What would happen if we could prove that P = NP?

Answer 42

1. We can decrypt all current internet communication 2. It will be useful for logistics and delivery (TSP) 3. Revolutionise AI leading to faster computation and enhanced optimisation algorithms 4. Possibly lead to a cure for cancer because protein folding is an NP-complete problem

Question 43

What are heuristics?

Answer 43

Conditions applied to develop a suboptimal but good enough solution

Question 44

What is a decision problem?

Answer 44

A problem with a yes or no answer

Question 45

What is a decidable problem?

Answer 45

A decision problem that can be solved by an algorithm

Question 46

How do we define a decision problem in terms of algorithms?

Answer 46

X is a binary relation mapping an instance to a solution. Decision problems are a variant of X which maps an instance to {0, 1}

Question 47

Define non determinism

Answer 47

To try everything and if one attempt works then return yes

Question 48

T/F: A deterministic algorithm will return a different value every time for a specific set of input values

Answer 48

False, it will always give the same output for the same input

Question 49

What is an equivalent set of problems to NP problems?

Answer 49

The set of decision problems with a polynomial time certifier

Question 50

What is the purpose of a certifier?

Answer 50

A certifier verifies that the solution to a problem can be executed in a certain time complexity .e.g. polynomial time

Question 51

How do we check the efficiency of a solution using a certifier?

Answer 51

We check the length of the certifier and check the runtime of the certifier

Question 52

What does NP-completeness focus on?

Answer 52

The hardest problems in NP

Question 53

How do we determine which problems are NP-complete?

Answer 53

We can compare the relative difficulty of problems using polynomial time reductions which provide a formal means of showing that one problem is at least as hard as another to within a polynomial time factor

Question 54

Explain how a reduction works

Answer 54

Let X1 and X2 be decision problems. Suppose A2 solve X2. The idea is to find a function f such that A2 can be part of an algorithm A1 to solve X1.

Question 55

When can we say that problem X1 is polynomial time reducible relative to a problem X2?

Answer 55

If there is a function f, computable in polynomial time, that takes input x to X1 and transforms it to an input f(x) of X2, such that the solution to X2 on f(x) is the solution to X1 on x.

Question 56

What does X1 <=p X2 mean?

Answer 56

X1 is polynomial time reducible relative to X2

Question 57

If we know the Y <=p X and X is a member of P what does that mean for Y?

Answer 57

Y is also a member of P

Question 58

How does polynomial time reduction help us determine the hardness of a problem?

Answer 58

If we know that Y is polynomial time reducible relative to X then we know that Y is no more hard than X is (and vice versa)

Question 59

When is a decision problem NP-complete?

Answer 59

1. B is a member of NP 2. A <=p B for A where A is a member of NP (for all problems A in NP, A reduces to B in polynomial time proving B is just as hard as every other NP problem)

Question 60

What NP-hard mean?

Answer 60

That a problem may not be NP but it is just as hard as any other problem in NP

Question 61

What is the relationship between NP-complete and NP-hard?

Answer 61

For a problem to be NP-complete it must be NP and NP-hard

Question 62

Give an example of an NP-complete problem

Answer 62

SAT