Version: 0.3.38

Foundations

Here we lay the foundations: Defining algorithms and data structures from a Computer Science perspective, and understanding how a machine executes our algorithms. From there, we then look at what make an algorithm efficient, and how we can measure that efficiency.

Contents

• 1. Computations
  • 1.1. Computation
  • 1.2. Algorithms
  • 1.3. Data Structures
  • 1.4. How to Describe an Algorithm?
  • 1.5. Conclusions
• 2. Computer
  • 2.1. Random Access Machines
  • 2.2. Programming Languages
  • 2.3. Conclusion
• 3. Correctness
  • 3.1. Functional Correctness?
  • 3.2. Formal Proofs
  • 3.3. Testing
  • 3.4. Conclusion
• 4. Efficiency
  • 4.1. Running Example
  • 4.2. Benchmarking Performance
  • 4.3. Computational Complexity
  • 4.4. Conclusion
• 5. Algorithm Analysis
  • 5.1. Modeling Algorithm Efficiency
  • 5.2. Best, Worst, and Average Cases
  • 5.3. Conclusions
• 6. The Big-O Notation
  • 6.1. Comparing Efficiencies
  • 6.2. Asymptotic Analysis
  • 6.3. Orders of Growth
  • 6.4. Conclusions