Algorithms

Question 1

Sum of triangular numbers complexity

Answer 1

1/2n(n-1)

Therefore quadratic

Question 2

First fit

Answer 2

Pack each box in turn into first available bin into which it will fit
- complexity = quadratic.

Question 3

First fit decreasing

Answer 3

• reorder largest to smallest
• apply first fit
• complexity = quadratic

Question 4

Full bin

Answer 4

• look for combos yourself
• not an algorithms because it is ambiguous - is heuristic

Question 5

quick sort

Answer 5

Pivot number compared to every number, slide all numbers less than it to the left of it, in the same order they were
- quadratic complexity in worst case

Question 6

Algorithms are

Answer 6

• unambiguous
• deterministic
• finite

Question 7

Heuristic algorithm definition

Answer 7

• will usually find a good solution although not necessarily an optimal solution

Question 8

Bubble sort shuttle sort complexity

Answer 8

Quadratic

Question 9

Put values less than or equal to the pivot

Answer 9

to the left of the pivot