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.



 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



 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





 7. All computational problems are computable



 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


  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?” 





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

  ballistic fathom

  bound farraday

  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(n x O)

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




  Big O time

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



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



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



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



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




  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



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

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 __________________

  breadh-first algorithm

  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