What are the conditions for an algorithm
It must be finite and deterministic
What does finite mean
It must terminate, algorithms can’t loop infinitely
What does deterministic mean
A single input must result in the same output every time. No randomness
What does recursive mean
Processes that loop
What is a stopping condition
The conditions under which which an algorithm will stop
What does a counter do
It will increment each loop
What is a heuristic method
A heuristic method is quick and solves problems reasonably well, but not optimally
What is a greedy method
It is short sighted, making the best choice at any given time which may not provide the best solution overall
What is an ad hoc method
It is made up on the spot and specific to the exact problem being solved
What is the maximum run time represented as
T(n)
What is the order of an algorithm
The dominant term in the run-time for a large scale problem, denoted O(n)
Do the bubble sort of 7,10,201,98,2
DRAW IT
Do the quick sort of 7,10,201,98,2
DRAW IT
Do the shuttle sort of 7,10,201,98,2
DRAW IT
What is the order of a bubble sort
O(n^2)
What is the order of a shuttle sort
O(n^2)
What is the order of quick sort in its worst case
O(n^2)
What is the next fit algorithm
Take them in the order they’re listed and put each in the first bin that can fit them, starting each time with the bin that was most recently used
What is the first fit algorithm
Take the items in the order listed and pack each in the first bin that they can fit in, starting with the first bin each time
What is a first fit decreasing algorithm
Order the items from largest to smallest, then apply the first fit method
What is the full bin method
Look for combinations of items that will fill bins and pack them together. Pack the other items together to result in bins as close to full as possible.
What is an offline problem
A problem where all the items and weights are known from the outset
What is an online problem
A problem where the items/weights are released one at a time
