Unit 4 Notes Flashcards
1
Q
What is backtracking?
A
Backtracking involves finding a solution incrementally by recursively exploring all possible solutions and undoing them if they lead to a dead end.
2
Q
What algorithm design pattern does the graph colouring problem use?
A
Backtracking
3
Q
What are divide and conquer algorithms?
A
Breaks down the problem into sub-problems and then solves the individual problems recursively
4
Q
What is dynamic programming
A
Dynamic programming algorithms split the problem into related sub-problems which are only solved once.
5
Q
What are P class problems
A
problems that can be SOLVED in polynomial time
6
Q
What are NP Class problems
A
Problems that can be VERIFIED in polynomial time
