# 01 - Optimisation algorithms introduction

1. The question “What can be (efficiently) automated?” is one of the most inspiring philosophical and practical questions. The goal of optimisation is to make all algorithms equal.

FALSE

TRUE

2. Optimization is the process of finding the most efficient algorithm for a given task. A good algorithm is one that produces _______________________

the wrong answer but is computationally efficient and fast

the correct answer, but is computationally slow (which equates to stability)

the correct answer and is computationally efficient.

any answer (wrong or right) and is efficient (as fast as possible)

3. An algorithm could be described as a series of steps for a computer uses to carry out a particular task

FALSE

TRUE

4. Optimisation Algorithms examine large volumes of data and look _________________________

for all possible correct solutions in order to sort them numerically

for the least efficient solution, as this is usually the correct and most stable route to pursue

for all possible incorrect solutions in order to eliminate them

for the best solution for a given problem

5. Djikstra’s shortest path algorithm is designed to find the______________ between a start node and every other node in a weighted graph

incorrect path

correct path

shortest path

longest path

6. A problem is defined as being ________________ if there is an algorithm that can solve every instance of it in a finite number of steps

algorithmic

mutable

computable

untractable

7. All computational problems are computable

TRUE

FALSE

8. Some problems may be theoretically solvable by a computer but if they take millions of years to solve, they are, __________________________

considered solvable

considered time-bound

considered non-time-bound

in a practical sense, unsolvable

9. There are limits to computation. These limits are imposed by algorithmic complexity and _________________

numeric complexity

hardware

human error

the number of prime numbers

10. The following excerpt describes the famous 'travelling salesman problem'. The TSP is a well known _________________ problem.
`Given a list of towns and the distances between each pair of towns, what is the shortest possible route that the salesman can use to visit each town exactly once and return to the starting point?” `

tractable

turbulent

optimisation

time-bound

11. In the TSP it is possible to use the b_____ f______ method to solve the problem. ballistic fathom

bent fallacy

brute force

12. To solve the TSP, we can use a solution where all possible routes are tested. With five cities, there would be _____________________________ 5 x 5 = 25 possible routes

exactly 5 x 2 (as we always deal in binary) giving us 10 possible routes

None of these options are correct

exactly five possible routes

13. The TSP problem quickly becomes __________________________. Even with only 10 cities, there are more than three million possible routes

possible to solve as the number of cities increases

impossible to solve as the number of cities decreases to below five

impossible to solve within a reasonable time

more interesting as the time factor doesn't affect the solution

14. In the TSP, with 50 cities, the number of possible routes becomes a whopping 65-digit number. This is an example of _________________________

a time-bound solution

a sub-optimal algorithm

an optimised algorithm

an intractable problem

15. The TSP is said to have a time complexity of:

O(n x n)

O(1)

O(n!)

O(n x O)

16. A problem that has a ____________________ solution or better is called a tractable problem

oxy-time

polynomial-time

un-time-bound

Big O time

17. Algorithms with time complexities O(n), O(n2), O(nk) are all considered very ‘inefficient’ algorithms for solving problems

TRUE

FALSE

18. An example of a tractable problem is “Sort n numbers into ascending numerical sequence”

TRUE

FALSE

19. An intractable problem is one that does not have a polynomial time solution

FALSE

TRUE

20. Algorithms of time complexity O(2n) and O(n!) are examples of highly efficient and easy to calculate algorithms

TRUE

FALSE

21. A ___________ approach is one which tries to find a solution which may not be perfect but which is adequate for its purpose

tractable

optimised

heuristic

Big O

22. Decide whether the following excerpt is true or false
```A large number of heuristic solutions have been developed for the
Travelling Salesman Problem (TSP). These can find a solution within
2 - 3% of an optimal solution for up to 85,000 ‘cities’ or nodes

Virus scanners often use heuristic rules```

FALSE

TRUE

23. Can you fill in the blanks for number 2 in the following excerpt
```A heuristic approach is often used in decision-making

Examples
---------
1. Using a ‘rule of thumb’
2. _______________________
3. Using common sense

Researchers have found that ignoring some of the relevant
information can lead to better decisions```

Creating an exact algorithm to solve the problem

Creating a similar problem and using an incomplete and incorrect or inefficient algorithm

Making a list of all possible solutions

Making an ‘educated guess’

24. Dijkstra’s algorithm is a special case of a more general path-finding algorithm called the __________________

heuristic algorithm

A* algorithm

stack algorithm

25. Decide whether the following excerpt is true or false
```The Djikstra's algorithm focusses only on reaching the goal node,
unlike the A* algorithm which finds the lowest cost or shortest path
to every node.

It is used, for example, in computer games to enable characters to
navigate the world```

TRUE

FALSE