Unit 8 - Algorithms

Question 1

What are factorials?

Answer 1

5! (spoken 5 factorial) is a shorthand way of expressing the product of numbers 1 to 5:
- 5! = 5 x 4 x 3 x 2 x 1
- 0! = 1

Question 2

What is a recursive subroutine?

Answer 2

A subroutine that contains itself.
A recursive subroutine has three essential characteristics:
- A stopping condition or base case must be included which when met means that the routine will not call itself and will start to “unwind”,
- For input values other than the stopping condition, the routine must call itself,
- The stopping condition must be reached after a finite number of calls.

Question 3

How do recursive subroutines work with the call stack?

Answer 3

• Every time a subroutine is called, the return address (the line after CALL statement) is put on the call stack,
• Even with a stopping condition, the recursive routine can only be called a limited number of times or the stack will overflow the maximum memory capacity.

Question 4

What is an example of a recursive algorithm?

Answer 4

Tree traversal algorithms.

Question 5

What are two ways to measure how efficient a program is?

Answer 5

• Length of code,
• Execution time .

Question 6

What is Big-O notation?

Answer 6

Big-O notation is a measure of the time complexity of an algorithm, it is a useful approximation of the time taken to execute an algorithm for a given number of items in a data set.
- There is no such thing as, for example, O(2n + 1),
- Only the dominant term counts, so it is O(n).

Question 7

What is a permutation?

Answer 7

A permutation of n items is the number of ways the n items can be arranged.

Question 8

What are the types of permutations?

Answer 8

• Repetition allowed; for example, a combination lock with 4 digits 0 to 9,
• No repetition allowed; for example, you have 4 differently coloured balls in a bag, and you draw them out one at a time.

Question 9

What are the two ways of traversing a graph?

Answer 9

• Depth-first,
• Breadth-first.

Question 10

What is depth-first traversal?

Answer 10

You go as far as you can down a path before backtracking and going down the next path.

Question 11

What is breadth-first traversal?

Answer 11

You explore all the neighbours of the current vertex, then the neighbours of each of those vertices and so on.

Question 12

What is Dijkstra’s shortest path algorithm?

Answer 12

The algorithm is designed to find the shortest path between a start node and every other node in a weighted graph.

• It works like a breadth-first search,
• It uses a priority queue as the supporting data structure to keep a record of which vertex to visit next,
• It starts by assigning a temporary distance value to each node,
• The temporary distance is 0 at the start node, and ∞ at every other node.

Question 13

What are computable problems?

Answer 13

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

Some problems may be theoretically soluble by computer but if they take millions of years to solve, they are, in a practical sense, insoluble.

Question 14

What imposes limits on computations?

Answer 14

• Algorithmic complexity,
• Hardware.

Question 15

What is The travelling salesman problem (TSP)?

Answer 15

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

Question 16

What are tractable problems?

Answer 16

A problem that has a polynomial-time solution or better is called a tractable problem.

Question 17

What are intractable problems?

Answer 17

An intractable problem is one that does not have a polynomial time solution.
Although the problem may have a theoretical solution, it is impossible to solve it within a reasonable time for values of n greater than something very small.

Question 18

What is a heuristic approach?

Answer 18

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

Question 19

What is the Halting problem?

Answer 19

This is the problem of determining for a given input, whether a program will finish running or continue for ever.