Chapter 1 (Algorithms) Flashcards
Prim’s algorithm, order?
Cubic
Kruskal’s algorithm, order?
Cubic
Bubble sort, order?
Quadratic
What’s an algorithm
A set of specific set of finite instructions for carrying out a procedure or solving a problem (usually terminate at one point).
Curved rectangular box meaning?
Start/ End
Rectangle box meaning?
Process (an instruction)
Diamond meaning?
Decision
How can you tell when a quick sort list of numbers are in order
Once every number has become a pivot (no more changes are made)
What do you do if the lower bound is not an integer?
Round up to the next whole number
First fit algorithm:
Take the items in the order they’re given, place each item in the first available bin that can take it. Start with bin one each time
Advantages and Disadvantages of the first fit bin algorithm:
Quick
Not likely to lead to a good solution
First fit decreasing algorithm:
Record the items so they’re in decreasing order
Apply the first fit algorithm to this recorded list
Advantages and disadvantages of the first fit decreasing algorithm:
Usually get fairly good solutions
Easy to do
You may not get the optimum solution
Full bin packing:
Use observation to find combinations of items that will fill a bin. Any remaining is packed using first fit algorithm.
Advantages and Disadvantages of Full bin packaging:
Good solution
Takes a long time
What can the order of an algorithm be described as?
As a function of its size
If an algorithm has an order of f(n) then increasing the size of the problem from n to m will increase the run time by a factor of what?
f(m)/f(n)
What number is definitely at the correct position after the first pass (list ascending order), in bubble sort?
The largest value
What’s the max number of comparisons needed for a list of 10 numbers?
n-1
=9 comparisons
