algorithms and complexity

Question 1

what is an algorithm

Answer 1

set of computational steps that transforms an input into an output

Question 2

why do we study algorithms

Answer 2

to check performance correctness robustness and simplicity

Question 3

space complexity

Answer 3

the amount of memory required for an algorithm to run to completion

Question 4

fixed part

Answer 4

the size required to store certain variables that are independent to the size of the problem

Question 5

variable part

Answer 5

the space needed by variables with their size dependent on the size of the problem

Question 6

what is the experimental approach of calculating the run time

Answer 6

you can implement the program and input different values to accurately measure the running time them plot a graph from your findings

Question 7

what are some limitations to the experimental approach

Answer 7

the algorithm must be implemented which can take a long time and can be difficult
to compare two algorithms the same hardware and software must be used which may be difficult

Question 8

what is an alternative to the experimental approach

Answer 8

operation counting

Question 9

what does sigma notation do

Answer 9

expresses sums where each term is in the same form

Question 10

what is the sigma formation for a for loop

Answer 10

b
∑ 1 = b - a + 1
i = a

Question 11

how do you calculate the average case

Answer 11

sum up all the inputs and divide by the total number of inputs

Question 12

what is big o notation used for

Answer 12

calculating the growth of functions

Question 13

what is the order of function growth

Answer 13

constant - log n - n^c (o < c < 1) - n - nlog n - n^2 - n^3 - 2^n - 3^n - n!

Question 14

what is the formal definition of big o

Answer 14

f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k
big o establishes an upper bound for the growth of functions when numbers start to get very large
upper bound

Question 15

what is the formal definition for big omega (Ω)

Answer 15

provides a lower bound
f(n) is said to be Ω(g (n)) if there exists positive constant C and (n0) such that 0 <= Cg(n) <= f(n) for all n >= n0

Question 16

what is the formal definiton for big theta(Θ)

Answer 16

f(n) is said to be Θ(g(n)) if f(n) is O(g(n)) and f(n) is Ω(g(n))
0 <= C2g(n) <= f(n) <= C1g(n) for n >= n0
average bound

Question 17

how do you find the time complexity of a recursive algorithm

Answer 17

you identify two properties of t(n); base case (1) and n > 1
then use either back substitution a recursion tree or master theorem to solve the recurrence relation

Question 18

why can we not rely on faster computers to speed up an inefficient algorithm

Answer 18

the less efficient the algorithm is the less quickly the computer can reduce the problem size

Question 19

np

Answer 19

non deterministic polynomial time; decision problems that can be checked in polynomial time | a set of all decision problems solvable in polynomial time with a non-deterministic algorithm

Question 20

p vs np

Answer 20

if its easy to check in polynomial time then would it be easy to solve

Question 21

what can we do when we have intractable problems

Answer 21

use heuristics; a good enough solution
solve the problem approximately
us the exponential time algorithm anyways

Question 22

what is the factoring problem

Answer 22

when given the answer what two prime numbers can be multiplied together to make it

Question 23

decision problems

Answer 23

with yes or no answers

Question 24

decidable

Answer 24

a decision problem that can be solved with an algorithm

Question 25

optimisation problems

Answer 25

require a value to be minimised or maximised

Question 26

how do we convert an optimisation problem into a decision problem

Answer 26

by asking is there a solution that has a value lower or higher than the given value

Question 27

clique

Answer 27

a complete subgraph of the graph; all vertices and nodes are are connected to each other

Question 28

non-determinism

Answer 28

the idea of trying everything and if any of them work they return yes; evaluates all branches of a decision trees simultaneously

Question 29

certifier

Answer 29

given an input (problem instance) and a candidate solution (the certifier) checks whether the candidate solution satisfies the problems requirements
checks if its correct within polynomial time

Question 30

what is an np complete problem

Answer 30

it is in np
it is as hard as any np problem
decision problems that contains he hardest problems in np

Question 31

how can we show that one problem is as hard as another

Answer 31

using polynomial time reductions

Question 32

what is a reduction

Answer 32

a method of solving a problem using another

Question 33

how do you carry out a polynomial time reduction

Answer 33

define the source problem and the target problem
design a function that transforms an instance of a into b that is computable in polynomial time and ensure its correct (yes for a is a yes for b)
prove the polynomial time complexity
combine the algorithm to solve function b with the reduction algorithm

Question 34

𝑌 ≤p 𝑋

Answer 34

y is no harder than x

Question 35

np hard

Answer 35

problems that are at least as hard as the hardest problems in np; do not have to be elements of np

Question 36

how do we show np completeness

Answer 36

show that b is in np
choose an np complete problem and prove that x is no harder than b (𝑋 ≤p 𝐵) (reducing x to b in polynomial time)