Section 8 - Algorithms Flashcards
1
Q
what is the point of depth first search and breadth first search algorithms
A
to traverse a graph so every node is visited
2
Q
what is depth first traversal
A
- go as far down one route before backtracking and taking the next
- uses a stack to record the nodes visited in the path currently gone down
3
Q
what is breadth first traversal
A
- starting at A visit all the nodes ajacent to A before visiting all the nodes ajacent to B
- uses a queue to keep track of all the nodes still to visit
4
Q
what is a tractable problem
A
one with polynomial or better time complexity
5
Q
what is a heuristic approach
A
- using knowledge about the problem
- can be used to find a good but not optimal solution
- can reduce the size of a problem
5
Q
what does computable mean
A
a problem is computable if there is an algorithm that can solve every instance of it in a finite number of steps
5
Q
what is the halting problem
A
- the problem of determining for a given input wether a program will finish running or continue further
- Alan Turing proved that a machine to solve the halting problem cannot exist
- the halting problem shows there are some problems that cannot be solved by a computer
6
Q
what is binary search
A
- items must be sorted
- compare the middle item to the sought item
- if the middle item is the sought item then end the search, if its bigger then remove the second half or if its smaller then remove the first half
- repeat this process, halving the list each time until the item is found
- O(logn)
7
Q
what is linear search
A
- search the items in the list one by one until the required item is found, or the end of the list is reached
- O(n)
8
Q
what is merge sort
A
- divide the unsorted list into n sublists, each containing one element
- repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining
- O(nlogn)
