Algorithm Design Patterns

Algorithms can be classified based on their design paradigm, i.e. how they approach a given problem

Greedy Algorithms

Algorithms that try to find the immediate short-term solution are considered greedy. It makes the best local choice at a given stage:

Greedy Arguments can be used to prove the correctness and/or optimality of greedy algorithms

---

Link to source

---

Brute-force (Exhaustive)

Algorithms that will systematically go through every possible option, and then determine the optimal one

• Linear Search
• Bellman-Ford Algorithm
• Permutations & Combinations

Link to source

---

Divide-and-Conquer

Breaks down a main problem into multiple sub-problems. Then it makes use of all sub-problems to find the solution

• Binary Search (Technically, Binary search is a decrease-and-conquer algorithm, as it uses only one half while searching at every iteration. I put it here because I (think) VCAA classifies it as a divide and conquer*)
• Merge Sort
• Quick Sort

Link to source

---

Decrease-and-Conquer

Continually reduces the problem into a smaller sub-problem, until a ‘base problem’, i.e. a trivial problem is reached. Then solves this base problem and starts ‘adding the sub-problems back’. Most recursive algorithms use the decreases and conquer approach.

• Depth First Search (DFS): Starts by reducing the graph into a subgraph of just the start node and it’s neighbours. Then it builds on this subgraph
• Breadth First Search (BFS): Same idea as DFS
• Recursive Factorial Algorithm: $n!$ is reduced to $(n-1)!\to (n-2)!$ until the problem becomes $(n-n)!=0!=1$

Link to source

---

Dynamic Programming

Dynamic programming is an optimization of Divide-and-Conquer.

Similar to divide-and-conquer, dynamic programming algorithms split the problem into related sub-problems. Solutions to sub-problems can be used in other to sub-problems. In this way, the final solution is created by ‘building’ on to subproblems.

One method to do is known as Memoization, where results of subproblems are stored for future use, in case the subproblem recurs.

• Floyd-Warshall’s Algorithm
• Fibonacci Algorithm
• Bellman-Ford Algorithm
• Dijkstra’s Algorithm

Link to source

---

Backtracking

Backtracking is an optimization of Brute-force (Exhaustive). Backtracking attempts to find a solution, but discards searching it if there is no way it can achieve the solution requirements.

Pseudocode §

Algorithm BackTrack(attempt = [],possible_options = []):
	if attempt meets all requirements then:
		return attempt
	else if attempt could reach the goal:
		for each i in possible_options do:
			Append i to attempt
			solution = BackTrack(attempt,possible_options)
			if solution = True then:
				return solution
	Pop the last element from attempt
	return False

Link to source