Algorithms

Question 1

Define: Graph - Depth First Traversal

Answer 1

Explores down an entire branch before moving on. Uses a stack.

Question 2

Define: Graph - Breadth First Traversal

Answer 2

Explores a whole level before moving down instead of using branches. Uses a queue.

Question 3

Define: Recursive algorithm

Answer 3

A function which calls itself

Question 4

What are the three essential characteristics of a recursive routine?

Answer 4

1) A base case must be included, when met means that the routine will not call itself and will start to “unwind”.
2) The stopping condition must be reached after a finite number of calls.
3) The algorithm must modify something that moves it towards the base case.

Question 5

Define: Big-O Notation

Answer 5

Is a measure of the time complexity of an algorithm. It is a useful approximation to the actual number of steps in a computation

Question 6

Define: Linear Search

Answer 6

Starts at beginning and continues until found or end. O(n).

Question 7

Define: Binary Search

Answer 7

Goes to middle, then keeps splitting list in half until found/not found. Only works on ordered list. O(log2n).

Question 8

Define: Tractable Problems

Answer 8

Problems that have a polynomial (or less) time solution are called tractable problems.

Question 9

Define: Intractable Problems

Answer 9

Problems that have no polynomial (or less) time solution are called intractable problems.

Question 10

Define: Heuristic Approach

Answer 10

Is one which tries to find a solution which may not be perfect but which is adequate for its purpose. A heuristic approach makes an ‘educated guess’ and uses common sense.

Question 11

Define: Halting problem

Answer 11

Provides a definition for a non-computable problem.