Here are some basics for algorithm analysis which we might not have enough time to cover in details but you can read if needed.

Concerning proofs:

The order of magnitude (e.g., the big Oh notation):

Chapter 1 Section 1.1 (pp. 5-10) of Algorithms and Complexity by Herbert Wilf (free download).
Leeann Bent's Order Notation Summary Sheet
A table of growth of functions.

Introduction to graph theory

Greedy Algorithm: Some links of explanations and examples.

NP-complete problems:

Recursive algorithms are nicely explained in Wilf's book (section 1.3 and 1.4, pp. 14-23).

Sorting:

Trees
- Breadth First Search tree, text by NIST, demo
- Deepth First Search tree, text by NIST, demo
- Minimum Spanning Trees
  - Kruskal Algorithm
  - Prim Algorithm
- Tutte's Theorem for perfect matching Page 39-41 in Distel's book.
Back to CSE202 page.