```Studying for Algorithms:

Dynamic programming
Greedy algorithms
Time complexities and invariants for basic graph algorithms.
Old stuff
Will use graphs as a basis for dynamic programming or greedy algorithms.

Basic Graph Algorithms:

If vertex is connected, there is a path between every pair of vertices. |E| \geq |V| -1.

If |E| = |V| -1, then it’s a tree.

A forrest is a collection of trees.

Adjacency lists just stores a linked list of all vertices connected to a given vertex. So max size would be V^2.
Adjacency list requires O(V+E) storage for directed and undirected.
Adjacency is best for sparse, matrix is best for dense.

•	Breath first:
⁃	Run-time: O(V+E).
⁃	Essentially, you start at some position and go uniformly out, in a layered fashion.
•	Invariant: Queue contains all (discovered) adjacent vertices in discovered/increasing distance order from source
⁃	Depth first:
⁃	Run-time: O(V+E).
⁃	Invariant: Vertex’s discovered time is > that of all previously discovered vertices and finishing time> all finishing times of vertices adjacent.

Minimum Spanning Trees:

Kruskals: look at every edge, from smallest weight to greatest, and add them to the minimal spanning tree and if you hit a cycle, don’t add that 		edge, and continue until you have all of the vertices. Runtime O(E log V).

Primm’s: start with a node, look at all connected nodes and chooses the one that has the smallest edge. Runtime O(|E| log |V|).

Finding shortest past between two nodes:

Dijikstra: O(V^2). It picks the unvisited vertex with the lowest-distance, calculates the distance through it to each unvisited 		neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.

Bellman Ford: time complexity O(V*E). Space: O(V). The Bellman-Ford algorithm is one of the classic solutions to this problem. It calculates 		the shortest path to all nodes in the graph from a single source.

Sorting time complexities:

Quicksort: n^2
Mergesort: nlog(n)
Heapsort: nlog(n)
Insertionsort: n^2
Bubblesort: n^2

Write Big-oh definitions.

Proof by induction:

1. State what you want to prove.

2. For which variable.

3. Base cases.

4. “I want to prove for greater than base”

5. Induction Hypothesis (for greater than base < k < n).

6. Want to prove for n.

7. Work —> break n into smaller cases.

```