Sorting

Insertion sort: most efficient for a small number of elements. take one element in the list at a time, and put it into the correct place in the list (No need to test the first)

Merge-sort: divide-and-conquer recursive algorithm.
1. Divide the list into 1/2.
2. Merge sort each half.
  a. if we have a 1 element list, it is already sorted.
  b. merge lists = take two already sorted lists, and put the lowest of each top element into a new list. (option - add a sentinel item at the end of each input list, with a value of max+1, to save testing for empty. loop will iterate for total number of cards).
The sequential access to already sorted lists makes merge-sort a good choice for linked lists.

Coarsening the leaves: insertion sort is quicker than merge-sort for small n, because of lower constant cost. Therefore it is even more efficient to swap to insertion sort in merge-sort when the divided lists become small enough.

Bubble sort: repeatable swap adjacent elements.

Probabilistic analysis and randomized algorithms (Chapter 5)

The hiring problem

Indicator random variables

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.