read more 
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.