Decision C1 - Algorithms Flashcards
Define algorithm
A finite sequence of step-by-step instructions carried out to solve a problem
What does an oval mean in a flow chart?
Start / End
What does a rectangle mean in a flow chart?
Instruction
What does a diamond mean in a flow chart?
Decision
What type of sorting algorithms are there for unordered lists?
Bubble sort and quick sort
Describe the steps to carry out a bubble sort
Compare adjacent items in a list
If they’re in order, leave them
If they aren’t in order, swap them
The list is ordered when a pass in completed without any swaps
Describe the steps to carry out a quick sort
Select a pivot (the middle) then split the items into 2 sub lists
One sub list contains items less than the pivot
The other sub list contains items greater than the pivot
Select further pivots from within each sub list and repeat the process
What are all of the bin packing methods and how do they work?
First-fit:
Take items in order given
Place in first bin available that can take it
Start from bin 1 each time
First-fit decreasing:
Sort into descending order
Take items in order given
Place in first bin available that can take it
Start from bin 1 each time
Full-bin packing:
Use observation to find combinations of items that will fill a bin. Pack these items first
Take items in order given
Place in first bin available that can take it
Start from bin 1 each time
How do you calculate the lower bound of a bin?
Sum up all the item sizes and divide by the bin size. Then round up
What are the advantages and disadvantages of the first-fit algorithm?
+: Quick to implement
-: Not likely to lead to a good solution
What are the advantages and disadvantages of the first-fit decreasing algorithm?
+: Usually a good solution
+: Easy to implement
-: May not get an optimal solution
What are the advantages and disadvantages of the full-bin algorithm?
+: Usually a good solution
-: Difficult to do, especially when the numbers are plentiful and awkward
if an algorithm has an order f(n), then increasing the size of the problem from n to m will increase the run time of the algorithm by a factor of approximately…
f(m) / f(n)
How do you calculate the run time of an algorithm?
Original run time * Scale Factor^Order of the algorithm = Run time
o.e
OT * k^x = NT
