Preview

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.

  TRUE

  FALSE

 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 the best solution for a given problem

  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

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

  shortest path

  longest path

  correct path

  incorrect 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

  untractable

  computable

 7. All computational problems are computable

  FALSE

  TRUE

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

  considered time-bound

   in a practical sense, unsolvable

  considered non-time-bound

  considered solvable

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

  numeric complexity

  the number of prime numbers

  hardware

  human error

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

  optimisation

  time-bound

  tractable

  turbulent

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

  bent fallacy

  bound farraday

  brute force

  ballistic fathom

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

  exactly five possible routes

  5 x 5 = 25 possible routes

  None of these options are correct

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

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

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

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

  possible to solve as the number of cities increases

  impossible to solve within a reasonable time

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

  a sub-optimal algorithm

  an optimised algorithm

  an intractable problem

  a time-bound solution

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

  O(n x n)

   O(n!)

  O(n x O)

  O(1)

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

  oxy-time

  Big O time

  polynomial-time

  un-time-bound

 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”

  FALSE

  TRUE

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

  TRUE

  FALSE

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

  FALSE

  TRUE

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

  heuristic

  optimised

  Big O

  tractable

 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

  TRUE

  FALSE

 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

   Making an ‘educated guess’

  Creating an exact algorithm to solve the problem

  Making a list of all possible solutions

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

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

  heuristic algorithm

  breadh-first 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

  FALSE

  TRUE