Algorithms

For the most part, the theory and study of Algorithms deals with runtime and size complexity. That is "how fast does this code run, and/or how much space does it take up while running?"

More often than not, we only care about the the computational time (speed) of the algorithm. However, depending on data size and hardware limitations, memory, communication, or other space-related resources are the focus as well. To be more precise, we can define a few key terms:

• Algorithm - Any well defined, step-by-step procedure for performing some task in a finite amount of time.
  • Generally takes some value as input and produces some value as output.
• Algorithm Correctness:
  • An algorithm is "correct" if, for every input instance, the algorithm halts/ends with the correct output.
  • An algorithm is "incorrect" if for some input instances:
    • The algorithm does not halt.
    • The algorithm halts/ends, but provides incorrect output.
• Pseudo Code - Code written in whatever expressive method is most clear and concise.
  • Generally, pseudo code meant for human reading rather than machine reading, and thus does not worry about "issues of software engineering", such as error checking, abstraction, modularity, etc.
• Data Structure - A way to store and organize data in order to facilitate access and modification.
• Running time - The number of "Primitive Operations" a piece of code needs to execute to finish running.

Algorithms Topics

• Pseudocode
• Primitive Operations
• Runtime Analysis