Algorithm Flashcards
Greedy algorithm
Always takes the best option that is immediately available (finds the optimal solution)
Picking the best option at face value at each step (Prim’s)
Prim’s algorithm
Easiest method to find minimal spanning tree, greedy algorithm
Minimal spanning tree
Subset of edges in a weighted, undirected graph to connect all nodes in the smallest distance possible
Recursive algorithm
Calls itself during runtime
* takes up lots of space in computer memory and can lead to exponential/polynomial time complexity
Iterative algorithm
Loops a process x times or until it satisfies a condition (for and while loops)
Dijkstra’s algorithm
Finds shortest path between one node and all other nodes in weighted and directed graph (positive edges only)
Bellman-Ford algorithm
Finds shortest path between one node and all other nodes in weighted and directed graph. Takes longer than Dijkstra’s. (positive and negative edges)
Brute force algorithm
Trying every single option until you find the solution, guaranteed solution eventually but can take very long
Divide and conquer algorithm
Dividing problem into several subproblems, which are solved and joined to find original problem’s solution (Merge sort)
Decrease and conquer
Shrinks main problem into smaller problem that can be solved more easily (Binary search)
Transform and conquer
Converting given problem into different problem that gives the same answer as required
Backtracking
Systematically generating possible solutions to a problem and then going back and regenerating a part of the solution when it reaches a dead end or solution is incorrecct
Floyd-Warshall Algorithm
Looks for transitive closure, solves all pairs shortest paths problem. The time complexity is Θ (V³).
i -> starting point
k -> midpoint
j -> endpoint
Algorithm design patterns
- Brute-force algorithm
- Greedy algorithm
- Decrease and conquer
- Divide and conquer
- Dynamic programming
- Backtracking
