Algorithms Flashcards
What is NP HARD and NP complete
NP complete will not be solved in polynominal time and there is no current solution example of this is TRAVELLING SALESMAN
What is exhaustive search
Testing each possibility sequentially this is done in both NP hard and NP complete
What is polynomiaml time
This is a reasonable amount of time
What is faster oLogn or O(n)
O(LOGn)
What is faster O(n^2) or O(2n)
O(2n)
What is asymptotic notation
This is the notation that will allow us to measure the running time of an algorithm as the input increase
What is binary search
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)
What is quick sort
This uses the pivoting algorithm that will split the arrays and sort them then place them back together
What is the fastest sorting and searching algorithm
Binary Search and Radix Sort
What is the time for bubble sort
O(n^2)
What is the time for binary search
O(logn)
What is the time for linear search
O(n)
what is LIFO and where is it used
STACKS
What is FIFO and where is it used
QUEUES
What is a hash table and where is it used ?
This is used to identify objects that are similar that are grouped toghether but need to be uniquley identified
What is a graph
A collection of nodes and edges that are relarted
What are the uses for a graph
Satellite navigation, developing networks, developing routes, tube station maps and times
What are the graph traversal algorithms ?
Breadth first search, Best first search, A*, Depth First search
What is the worst case scenario for exhaustive search
O((n-1)!)
What is depth first search ?
This is the process of exploring and back tracking until all nodes and paths on a graph have been visited
What is a heuristic and why would we use them ?
This is a generic guideline that we need to follow that will increase our performance when exploring the solution space
What is the fitness function >?
This is how good the current solution is within the solution space
What is a maximization problem ?
This is a problem where the higher the fitness the better
What are example of heuristics ?
Random mutation hill climbing
What is the difference between global and local optima ?
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
What is parameter optimization
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
What is combinatorial optimization
This is finding the best object within a finite set of objects
What is the tabu search ?
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
What are the advantages of using tabu search ?
The use of a tabu list, the global optima may be found, better than some other methods in larger more difficult problems.
What are the disadvantages of tabu search ?
Tabu List can become huge, CPU time run out, May not find the global optima if the parameters are wrong.
What is crossover in genetic algorithms ?
The process of creating a child from a parent
What is a generation ?
The amount of times that breeding has occurred
What is the difference between genetic algorithms & evolutionary programming
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
What is the difference between one point and uniform crossover
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)
