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.

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

  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

  correct path

  longest path

  incorrect path

  shortest 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

  computable

  mutable

  untractable

 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 non-time-bound

  considered time-bound

  considered solvable

   in a practical sense, unsolvable

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

  hardware

  human error

  numeric complexity

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

  time-bound

  tractable

  turbulent

  optimisation

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

  bound farraday

  ballistic fathom

  brute force

  bent fallacy

 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

  None of these options are correct

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

  exactly five possible routes

  5 x 5 = 25 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

  possible to solve as the number of cities increases

  impossible to solve within a reasonable time

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

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

  an intractable problem

  a time-bound solution

  a sub-optimal algorithm

  an optimised algorithm

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

   O(n!)

  O(n x O)

  O(1)

  O(n x n)

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

  polynomial-time

  un-time-bound

  Big O time

  oxy-time

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

  FALSE

  TRUE

 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

  optimised

  tractable

  Big O

  heuristic

 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 a list of all possible solutions

   Making an ‘educated guess’

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

  Creating an exact algorithm to solve the problem

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

   A* algorithm

  breadh-first algorithm

  stack algorithm

  heuristic 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


Report an error