This is an old revision of the document!
Table of Contents
Chapter 2
2.1 Computational Tractability
- Comparison of algorithms makes necessary some measure of efficiency. This must be abstract for convenience in comparison, but should still be applicable to normal real-world cases. The best known general-purpose measure is the worst-case running time, as average case has its uses but is rarely well-defined. The natural comparison is brute-force search; since brute-force typically takes exponential time, efficiency can be defined as the next-smallest order of growth, polynomial running time. There may be cases in which great disparities in coefficients and small sample sizes can make exponential time attractive or polynomial time impractical, but polynomial time is useful in most circumstances.
- No insights.
- Is there always an easy brute-force algorithm? I was recently working on an algorithm for laying out nodes in relational graphs, and do not see any brute-force solution (I wound up using a force-directed technique). Finding a measure of goodness is somewhat straightforward, but how does one come up with candidates? (Although I suppose that one could say that the search space is the fantastically large set of layouts unique at the display resolution. But what about truly continuous problems?).
- I would have much preferred a direct approach; I only see as significant in this section the analysis of brute-force bounds and the definition of polynomial time as a standard of efficiency. That said, I have already seen this before, and I think that the authors did do a good job of leading readers toward the answer. 8/10.
2.2 Asymptotic Order of Growth
- Mere use of upper bounds is insufficiently granular, ensuring that the equivalency classes are each sparsely populated, and misleading, in counting individual steps makes efficiency analyses overly implementation-sensitive. Therefore, we ignore linear coefficients and slowly-growing terms, giving asymptotic bounds (upper, lower, and tight). These are transitive, but addition leaves only the greater order and multiplication by a constant is an identity.
- No insights.
- No questions.
- Well done; I think that the level of proof/explication was well chosen. 9/10.
