Algorithms in a Nutshell
Principle: Know Your Data
Dijkstra’s Algorithm will run forever if a cycle exists whose sum of all edge weights is negative.
Choose the most appropriate algorithm based upon your data as you become more familiar with the available options.
Principle: Decompose the Problem into Smaller Problems
Convex Hull Scan produces the final convex hull by constructing and merging together two partial hulls (the upper and lower).
Principle: Choose the Right Data Structure
a binary heap offers no ability to determine whether it contains a specific element.
Line Sweep can provide only O(n log n) performance because it uses an augmented binary tree to implement the priority queue and still provides O(log n) performance for removing the minimum element.
Principle: Make the Space versus Time Trade-off
Many of the computations carried out by the algorithms are optimized by storing information that reflects the results of past computations.
Principle: If No Solution Is Evident, Construct a Search
Principle: If No Solution Is Evident, Reduce Your Problem to Another Problem That Has a Solution
Principle: Accept Approximate Solution When Possible
The Knapsack unbounded problem provides such a scenario, since the approximation is no worse than 50% of the actual result.
Principle: Add Parallelism to Increase Performance
Principle: Know Your Data
Dijkstra’s Algorithm will run forever if a cycle exists whose sum of all edge weights is negative.
Choose the most appropriate algorithm based upon your data as you become more familiar with the available options.
Principle: Decompose the Problem into Smaller Problems
Convex Hull Scan produces the final convex hull by constructing and merging together two partial hulls (the upper and lower).
Principle: Choose the Right Data Structure
a binary heap offers no ability to determine whether it contains a specific element.
Line Sweep can provide only O(n log n) performance because it uses an augmented binary tree to implement the priority queue and still provides O(log n) performance for removing the minimum element.
Principle: Make the Space versus Time Trade-off
Many of the computations carried out by the algorithms are optimized by storing information that reflects the results of past computations.
Principle: If No Solution Is Evident, Construct a Search
Principle: If No Solution Is Evident, Reduce Your Problem to Another Problem That Has a Solution
Principle: Accept Approximate Solution When Possible
The Knapsack unbounded problem provides such a scenario, since the approximation is no worse than 50% of the actual result.
Principle: Add Parallelism to Increase Performance
