Show Menu
Cheatography
  1. Home >
  2. Programming >

Algorithm choosing techniques Cheat Sheet (DRAFT) by

Choosing the right technique or algorithm to solve a problem often depends on recognizing certain patterns or key characteristics in the problem statement.

This is a draft cheat sheet. It is a work in progress and is not finished yet.

Greedy Algorithms

Indicator
Making locally optimal choices to find a global optimum, problems involving finding minimu­m/m­aximum values.
Tips
Prove the greedy choice property and ensure it leads to an optimal solution.
Common Patterns
Interval schedu­ling, activity selection, minimum spanning trees.
Examples
Activity Selection Huffman Coding Dijkstra's Algorithm

Dynamic Progra­mming (DP)

Indicators
Optimal substr­ucture, overla­pping subpro­blems, constr­aints involving maximu­m/m­inimum values, finding number of ways to achieve a target.
Tips
Use memoiz­ation or tabulation to store results of subpro­blems, break the problem into smaller subpro­blems.
Common Patterns
Subset sums, longest subseq­uences, edit distance.
Examples
Longest Common Subseq­uence ,Knapsack Problem, Coin Change Problem