Algorithms Flashcards
1
Q
Algorithm Definition
A
- An algorithm is a set of instructions
- It must have a finite number of steps
- It must work for any input
- It must have an end
2
Q
What do the different shapes mean in a flowchart?
A
- Long ovals (rectangles with curved edges) indicate the start of end of process
- Diamonds contain questions (decisions).
- Rectangle contains a process/instruction.
3
Q
Efficiency of an algorithm
A
- Measure of the ‘run-time’ of an algorithm and in most cases is proportional to the number of operations that must be carried out.
4
Q
Size of a problem
A
- A measure of its complexity and so in the case of sorting algorithm the number of elements in the list.
5
Q
Complexity of an algorithm
A
- A measure of its efficiency as a function of the size of the problem.
- We refer to the order of the algorithm to give an indication of its complexity.
6
Q
Full Bin Packing Strategy
A
- It is a strategy and not an algorithm because it is not deterministic.
- Using common sense sort boxes into bins yourself.
7
Q
First Fit + First Fit Decreasing
A
- Come as they serve bin packing, decreasing is just when you order the list from largest to smallest beforehand.H
8
Q
Heuristic Algorithms + Examples
A
- An algorithm that will find a good solution.
- Although it may not necessarily find an optimal solution, not to say it’s impossible, just not guaranteed.
- Both first fit and first fit decreasing algorithms fall under this category.
9
Q
Bubble Sort Complexity
A
- Quadratic
10
Q
Order for calculating the run time of an algorithm, given the complexity and times taken.
A
(New N / Old N) ^ Power of Complexity x Old Time = New Time
e.g. n^2, n=200, 0.03s, now n = 20000
(20,000/200)^2 x 0.03 = 300 seconds
