strategies-and-writing-algorithms.md

← Return to Index

Strategies and Writing Algorithms

1. Look for good invariants to exploit
2. Attempt to balance your work as much as possible
3. Do not repeat work (store, and re-use!)
4. Use appropriate data representations
5. Try well-known problem solving strategies
6. Sometimes greed is good

Invariants to Exploit

• Binary Search
• Sorting
• Shortest Paths and Connectivity
• Minimum Spanning Tree Algorithms

Balance Your Work

• Divide and Conquer strategy
• Merge Sort
• Quick Sort
• Hirschberg's Algorithm

Choose Data Structures with Care

• Certain data representations can be more efficient for certain problems
• Priority Queue in Dijkstra's algorithm
• Union-Find data structure in Kruskal's algorithm
• Efficient Search and Data Retrieval

Don't Repeat Work

• Do not compute anything more than once
• Use Dynamic Programming
  • Edit Distance
  • Largest Common Subsequence Problem
  • Dijkstra's Algorithm

Sometimes greed is good

• Dijkstra's Algorithm
• Prim's Algorithm
• Kruskal's Algorithm
• Green can give a good solution, even if not guaranteed optimal