Advanced Algorithm Design Flashcards
Dynamic programming
using arrays or old dictionaries to store values before performing operations, saves answers for later and returning them to create new answers
- prioritises time complexity over space complexity
Randomised heuristics
Used in NP-Complete and NP-Hard problems, does not give the best solution (impossible to know what the best solution is), but gives a solution that is good enough which can be faster than brute force methods to find the best solution
Simulated annealing
Randomised heuristics example, uses randomness and probability to make a given solution better. Assigns a temperature value to each solution and decreases the temperature value with each new better solution. The cooler the temperature, the less likely to allow for a worse solution.
Minimax
Provides the best move a player should pick at any stage if the game to result in the maximum possible score.
Graph colouring
With a graph, is there a way to colour all nodes so that no two adjacent nodes have the same colour? (NP-Complete)
Travelling salesperson optimal
Given a graph, find the shortest possible path to visit all nodes in the graph and return to the start node (brute force, NP-Hard)
Knapsack problem
When items have values and weights, what items should be taken within the knapsack’s weight limit with the highest value? (subset sum, NP Complete)
Mergesort
Repeatedly dividing array into two halves until there are multiple arrays with just two items. Each two-item array are sorted and then merged into a single array (recursive, divide and conquer)
Quicksort
Splits array in two using a pivot point, with two arrays of one with values lower than the pivot, and one with values higher than the pivot. (recursive, divide and conquer)
Mergesort time complexity
T(n)= 2T(n/2)+n
Quicksort time complexity first or last element pivot
Worst case, T(n)=T(n-1)+n
Quicksort time complexity random or median pivot
Best case, T(n)=2T(n/2)+n
