Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algorithms & their Applications > Algorithms > Flashcards

Algorithms Flashcards

1
Q

What is NP HARD and NP complete

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is exhaustive search

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is polynomiaml time

A

This is a reasonable amount of time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is faster oLogn or O(n)

A

O(LOGn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

O(2n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is asymptotic notation

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is binary search

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is quick sort

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the fastest sorting and searching algorithm

A

Binary Search and Radix Sort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the time for bubble sort

A

O(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the time for binary search

A

O(logn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the time for linear search

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

what is LIFO and where is it used

A

STACKS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is FIFO and where is it used

A

QUEUES

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a hash table and where is it used ?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is a graph

A

A collection of nodes and edges that are relarted

17
Q

What are the uses for a graph

A

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

18
Q

What are the graph traversal algorithms ?

A

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

19
Q

What is the worst case scenario for exhaustive search

A

O((n-1)!)

20
Q

What is depth first search ?

A

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

21
Q

What is a heuristic and why would we use them ?

A

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

22
Q

What is the fitness function >?

A

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

23
Q

What is a maximization problem ?

A

This is a problem where the higher the fitness the better

24
Q

What are example of heuristics ?

A

Random mutation hill climbing

25
Q

What is the difference between global and local optima ?

A

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

26
Q

What is parameter optimization

A

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

27
Q

What is combinatorial optimization

A

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

28
Q

What is the tabu search ?

A

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

29
Q

What are the advantages of using tabu search ?

A

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

30
Q

What are the disadvantages of tabu search ?

A

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

31
Q

What is crossover in genetic algorithms ?

A

The process of creating a child from a parent

32
Q

What is a generation ?

A

The amount of times that breeding has occurred

33
Q

What is the difference between genetic algorithms & evolutionary programming

A

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

34
Q

What is the difference between one point and uniform crossover

A

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)

Algorithms & their Applications (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions