Chapter 2: Getting Started

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms, Second Edition. The MIT Press, 2001

A brief overview of algorithms and how to think about them.

2.2 Analyzing Algorithms

You can use a loop invariant to inductively prove that an algorithm is correct:

Initialization: It is true prior to the first iteration of the loop.
Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

Introduction to Algorithms uses a single-processor single-threaded random-access machine (RAM) model when analyzing algorithms:

• Arithmetic (add, subtract, multiply, divide, remainder, floor, ceiling)
• Data Movement (load, store, copy)
• Control (conditional and unconditional branch, subroutine call and return)
• Bit Operations (e.g. $2^k$ can be done with a bitwise shift when k is a small enough positive integer)

2.3 Designing Algorithms

One way to design an algorithm is with an incremental approach. Insertion sort is an example of this.

Another approach is divide and conquer. It's usually recursive and has three steps:

Divide the problem into a number of subproblems.
Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
Combine the solutions to the subproblems into the solution for the original problem.

[Recursive algorithms] can often be described by a recurrence equation or recurrence.

Recurrence relations are often defined as $T(n)$, with constant runtimes noted as $c$.