Unit 8 Flashcards
What are the three characteristics of a recursive routine?
- A stopping condition or base case must be included
- The routine must call itself for all values other than the base case
- The stopping condition must be reached after a finite number of calls
T/F: The stopping condition and the base case are the same thing
True
Define base case
A value that stops a recursive routine from calling itself again and causes the call stack to ‘unwind’
How is stack overflow linked to recursive routines?
Recursive routines require a lot of memory space and when the call stack exceeds the designated memory space the program will crash
Define stack overflow
When the memory required for the call stack has exceeded that designated to the sub program
Give an example of where recursive routines are used and why
They can be used in tree traversal as they perform the traversal of either the right or left side of the tree multiple times
What is Big O notation a measure of?
Time complexity
Define Big O notation
A method used by computer scientists to describe the time complexity of an algorithm
What are the 5 time complexities we need to know (in order from least to most complex)?
- Constant time
- Logarithmic time
- Linear time
- Polynomial time
- Exponential time
What type of statement do we use to work out the time complexity of an algorithm?
Assignment statements
How do we simplify the time complexity of an algorithm from multiple terms to just one?
We focus on the most significant term only
What is the time complexity of a binary tree search?
Logarithmic
What is the time complexity of a bubble sort?
O(n ** 2)
What is the time complexity of a linear search?
Linear
Define permutation
The number of ways to arrange a set of items
What are the two types of permutation?
With repetition and with no repetition
What is the difference between the two types of permutation?
Permutations with repetition are were there are the same number of options for each choice (.e.g. numbers on a padlock) where as the number of option reduces with each choice in non repetition permutations (.e.g. removing balls from a bag)
What is the time complexity of permutations with repetition?
O(x ^ n) where x represents the number of options and n represents the number of choices
What is the time complexity of traversing a balanced binary tree?
O(log(n))
What is the worst case scenario for the time complexity of an unbalanced tree?
O(n)
What is the time complexity of a merge sort?
O(n log(n)), with a base of 2
What are the two methods of graph traversal?
Depth first and breadth first
Describe depth first graph traversal
You go as far down the route of one neighbour of the current vertex until you can’t go any further and have to back track
Describe breadth first traversal
Exploring all of the neighbours of the current vertex and then the neighbours of each of thsoe vertices in turn
What ADTs does depth first traversal use and why?
It uses a list to keep track of nodes visited and a stack to keep track of the last node visited, this is so that the previously visited nodes can be popped from the stack in order to revisited when backtracking
If a node has multiple neighbours how do we decide which one to traverse first?
Based on the position in the dictionary
What ADTs does breadth first traversal use and why?
It uses a list to keep track of the nods already visited and uses a queue rather than a stack to store the order of the recently visited nodes, this is because the first item in the queue will be the neighbour that has to be traversed next
What is the time complexity of DFS and BFS in a sparse graph?
O(n)
What is the time complexity of DFS and BFS in complex graphs?
O(n**2)
Which is more time efficient, DFS or BFS?
They are both the same!
What does Dijkstra’s shortest path algorithm do?
It is designed to find the shortest path between two nodes in a weighted graph
Describe how Dijkstra’s shortest path algorithm works
- The start node is assigned a temporary value of 0 and all other nodes are assigned a temporary value of infinity
- The start node is removed from the queue and each of its neighbours are visited
- The temporary distances of the start node’s neighbours are updated based on the weight of the edge used to get between the two nodes
- The process of visiting neighbouring nodes is then repeated with the first item in the priority queue until the queue is empty
- The shortest path can then be worked out by tracing the algorithm back
What ADT does Dijkstra’s shortest path algorithm use?
A priority queue
What is a heuristic?
A solution that is not perfect but will suit the situation it’s required for
Define a computable problem
A problem that has a corresponding algorithm that can solve every instance of it in a finite number of steps
Define soluble
A computable problem
Define insoluble
An incomputable problem
Define tractable
A problem that has a solution with a polynomial time complexity or better
Define intractable
A problem that has no solution with a polynomial time complexity or better
Why are some problems in theory soluble but in practice insoluble?
This is because they may take an excessive amount of time to solve that far exceeds the lifespan of one person
What are the two major limitations of computers?
Algorithm complexity and hardware availability
What is the travelling salesman problem?
TSP is a classic intractable problem where it is theoretically possible to work out the most efficient way of visiting the nodes but the brute force process to do this has a factorial time complexity which means it is practically insoluble
Define heuristic approach
An approach that attempts to find a solution that is not perfect but adequate for the situation
How came up with the Halting Problem?
Alan Turing
What is the Halting Problem?
This is a thought problem that proves that it is impossible for a machine (H) to determine whether a program (P) will always stop running or continue running forever for any given input
Why is the machine H in the Halting Problem impossible?
It is impossible to tell whether program (P) would halt for input (I) because the Machine (H) would have to run the code infinitely
Why was the Halting Problem significant?
It was proved that there are some problems which just can’t be solved by computers
