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 V2.
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(V2). 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: n2
Mergesort: nlog(n)
Heapsort: nlog(n)
Insertionsort: n2
Bubblesort: n2

Write Big-oh definitions.

Proof by induction:

  • State what you want to prove.
  • For which variable.
  • Base cases.
  • “I want to prove for greater than base”
  • Induction Hypothesis (for greater than base < k < n).
  • Want to prove for n.
  • Work —> break n into smaller cases.