Algorithms

Question 1

Algorithm Definition

Answer 1

• 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

Question 2

What do the different shapes mean in a flowchart?

Answer 2

• Long ovals (rectangles with curved edges) indicate the start of end of process
• Diamonds contain questions (decisions).
• Rectangle contains a process/instruction.

Question 3

Efficiency of an algorithm

Answer 3

• Measure of the ‘run-time’ of an algorithm and in most cases is proportional to the number of operations that must be carried out.

Question 4

Size of a problem

Answer 4

• A measure of its complexity and so in the case of sorting algorithm the number of elements in the list.

Question 5

Complexity of an algorithm

Answer 5

• 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.

Question 6

Full Bin Packing Strategy

Answer 6

• It is a strategy and not an algorithm because it is not deterministic.
• Using common sense sort boxes into bins yourself.

Question 7

First Fit + First Fit Decreasing

Answer 7

• Come as they serve bin packing, decreasing is just when you order the list from largest to smallest beforehand.H

Question 8

Heuristic Algorithms + Examples

Answer 8

• 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.

Question 9

Bubble Sort Complexity

Answer 9

• Quadratic

Question 10

Order for calculating the run time of an algorithm, given the complexity and times taken.

Answer 10

(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