Studying for Algorithms:
Time complexities and invariants for basic graph algorithms.
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:
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.