Algorithm Design and Analysis
Aho, Hopcroft, and Ullman, The design and Analysis of Computer Algorithms 1974:
"Perhaps the most import principle for the good algorithm designer is to refuse to be content"
This means always ask
"Can we do better?"
- Basically it's a set of well defined rules, a recipe in effect for solving some problem.
- In many areas performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speeds.
- The design and analysis of algorithms is simply fun. It's an endeavor that requires a rare blend of precision and creativity. It can certainly be frustrating at times, but it's also highly addictive.
- It is a modeling choice with which we measure a performance metric like the running time of an algorithm.
Divide and conquer algorithm paradigm
- Its a paradigm in which the idea is to first break the problem into smaller problems which then gets solved recursively, and then to somehow quickly combine the solutions to the sub problems into one for the original problem that you actually care about
- its an algorithm flips coins
- it has different execution paths if you run it over and over again on a fixed input
data structure is responsible of organizing data in a way that supports fast queries