Algorithms

Question 1

What is NP HARD and NP complete

Answer 1

NP complete will not be solved in polynominal time and there is no current solution example of this is TRAVELLING SALESMAN

Question 2

What is exhaustive search

Answer 2

Testing each possibility sequentially this is done in both NP hard and NP complete

Question 3

What is polynomiaml time

Answer 3

This is a reasonable amount of time

Question 4

What is faster oLogn or O(n)

Answer 4

O(LOGn)

Question 5

What is faster O(n^2) or O(2n)

Answer 5

O(2n)

Question 6

What is asymptotic notation

Answer 6

This is the notation that will allow us to measure the running time of an algorithm as the input increase

Question 7

What is binary search

Answer 7

This is a search method that will break an array in half each time when looking for a key value the array that is presented must be in order.

This has a running time of O(LogN)

Question 8

What is quick sort

Answer 8

This uses the pivoting algorithm that will split the arrays and sort them then place them back together

Question 9

What is the fastest sorting and searching algorithm

Answer 9

Binary Search and Radix Sort

Question 10

What is the time for bubble sort

Answer 10

O(n^2)

Question 11

What is the time for binary search

Answer 11

O(logn)

Question 12

What is the time for linear search

Answer 12

O(n)

Question 13

what is LIFO and where is it used

Answer 13

STACKS

Question 14

What is FIFO and where is it used

Answer 14

QUEUES

Question 15

What is a hash table and where is it used ?

Answer 15

This is used to identify objects that are similar that are grouped toghether but need to be uniquley identified

Question 16

What is a graph

Answer 16

A collection of nodes and edges that are relarted

Question 17

What are the uses for a graph

Answer 17

Satellite navigation, developing networks, developing routes, tube station maps and times

Question 18

What are the graph traversal algorithms ?

Answer 18

Breadth first search, Best first search, A*, Depth First search

Question 19

What is the worst case scenario for exhaustive search

Answer 19

O((n-1)!)

Question 20

What is depth first search ?

Answer 20

This is the process of exploring and back tracking until all nodes and paths on a graph have been visited

Question 21

What is a heuristic and why would we use them ?

Answer 21

This is a generic guideline that we need to follow that will increase our performance when exploring the solution space

Question 22

What is the fitness function >?

Answer 22

This is how good the current solution is within the solution space

Question 23

What is a maximization problem ?

Answer 23

This is a problem where the higher the fitness the better

Question 24

What are example of heuristics ?

Answer 24

Random mutation hill climbing

Question 25

What is the difference between global and local optima ?

Answer 25

The difference is that local optima is the optimal solution found in a subset of the a solution space, this may contain the global optima. Global optima is the best solution found in the given solution space

Question 26

What is parameter optimization

Answer 26

This is the process in which the best parameters will be found to obtain a good solution, these are a set of values that will help solve a problem

Question 27

What is combinatorial optimization

Answer 27

This is finding the best object within a finite set of objects

Question 28

What is the tabu search ?

Answer 28

This is a search method that will escape the local minima, this will keep a list of past moves and attempt to find the global optima

Question 29

What are the advantages of using tabu search ?

Answer 29

The use of a tabu list, the global optima may be found, better than some other methods in larger more difficult problems.

Question 30

What are the disadvantages of tabu search ?

Answer 30

Tabu List can become huge, CPU time run out, May not find the global optima if the parameters are wrong.

Question 31

What is crossover in genetic algorithms ?

Answer 31

The process of creating a child from a parent

Question 32

What is a generation ?

Answer 32

The amount of times that breeding has occurred

Question 33

What is the difference between genetic algorithms & evolutionary programming

Answer 33

Evolutionary programming uses tournament selection which is the comparison of one chromosome against a select amount of chromosomes, there is no crossovers only mutations, genetic algorithms will have crossovers mutation and use natural selection

Question 34

What is the difference between one point and uniform crossover

Answer 34

A child will obtain either 50% of one parent and the other child will get the other genes that the other child didn't get, there is a chance that they may get anything in one point (I THINK)