Essential Algorithms: A Practical Approach to Computer Algorithms

APPENDIX A

Summary of Algorithmic Concepts

Chapter 1: Algorithm Basics

Understanding algorithms—To understand an algorithm, you need to understand certain facts about it:

• 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 number of inputs?
• Main techniques—Can you reuse those techniques?

Algorithms and data structures—A data structure holds data in some arrangement. An algorithm produces a result. You need an algorithm to build and use a data structure.

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 before you can execute it.

Algorithmic goals—To be useful, an algorithm must be correct, maintainable, and efficient.

Big O notation describes the relationship between the number of inputs and runtime 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.

Runtime functions—Some common runtime 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—A program can randomize a collection of objects. It can then pick the first items in the randomized collection to make a random selection. For example, to select five cards from a deck of cards, ...