Essential Algorithms, 2nd Edition

APPENDIX ASummary of Algorithmic Concepts

This appendix summarizes the key concepts covered in each of the book's chapters.

Chapter 1: Algorithm Basics

• Understanding algorithms: To understand an algorithm, you need to understand certain facts about it, such as the following:
  • Behavior: Does the algorithm always find the best solution?
  • Speed: How does speed vary with the number of inputs?
  • Memory requirements: Are they reasonable? How does memory use vary with the number of inputs?
  • Main techniques: Can you reuse those techniques?
• Algorithms and data structures: A data structure holds data in some sort of arrangement. An algorithm produces a result. You need an algorithm to build and use a data structure.
• Pseudocode: Pseudocode is text that looks a lot like code but not in any particular programming language. You need to translate it into an actual programming language such as Python or C# before you can execute it.
• Algorithmic goals: To be useful, an algorithm must be correct, maintainable, and efficient.
• Big O notation: Big O notation describes the relationship between the number of inputs and run time or memory requirements as the problem size grows large. Big O notation ignores constant multiples and considers only the fastest-growing function that describes performance.
• Run-time functions: Some common run-time functions in order of increasing speed of growth are 1 (constant), log N, sqrt(N), N, N log N, N², 2^N, and N!.

Chapter 2: Numeric Algorithms

• Randomization: ...