Divide and conquer (Chapter 4)

Divide-and-conquer - divide, conquer, combine. Often recursive. e.g. merge-sort.

recurrence: function which defines itself in terms of its value on smaller inputs.

maximum sub array problem: obviously only interesting if contains negative numbers (otherwise whole array is the max).

Strassen's algorithm for matrix multiplication

Solving recurrences; the master theorem.

General notes

Algorithm: a tool for solving a well-defined computational problem (the statement of the problem is the desired input/output relationship)

 NP-complete: no known way to determine most efficient algorithm. we settle for reasonable algorithms.

Loop invariant: help us see if an algorithm is correct. Must show that the state is correct at three times:
1. initialization: prior to loop
2. maintenance: at the start of each loop
3. termination: at the termination of the loop

Analyzing an algorithm = predicting the resources it will require

Rate of growth / order of growth = leading term of the running time. eg. insertion sort has an average cost of an2 + bn + c, so we say the running time is theta-n2.