Make the best or greedy choice at any given step.

Solves an optimization problem piece-by-piece by making choices that are:

1. Feasible
2. Locally Optimal: Make choices based on less expensive, short-term criteria
3. Irrevocable: Choices cannot be undone!

Why — Approximations can be wildly faster than precise ones.

Applies to Problems with:

• Optimal Substructures: Optimal solutions have optimal sub-solutions
• Greedy Choice Property: ???

Overview

Optimal Solutions:

• TODO

Approximations:

• TODO

Minimum Spanning Tree

Spanning Tree: A spanning tree of G is a connected acyclic subgraph that has all of G’s vertices.

Minimum Spanning Tree: A weighted version of the above.

• The “minimum” means this is an optimization problem (visit all vertices with minimum cost).
• Satisfies optimal substructure property.

Prim’s

Grow a MST by repeatedly adding the least-cost edge that connects a vertex in a the existing tree to a vertex not in the existing subtree.

TODO Describe algorithm in more detail.

Kruskal’s

Grow a MST by repeatedly adding the last-cost edge that doesn’t introduce a cycle among the edge included so far.

Key Question: How do you determine if its acyclic still?

If the two nodes being connected:

• belong to the same connected component, it’ll generate a cycle!
• don’t belong to the same connected component, it’s safe!

Union-Find Problem

??? TODO this is a requirement for Kruskal’s? (to find cycles?)

I have no freaking clue I wanna go home and eat.

Example: ???

Let S = \{ 1,2,3,4,5,6 \}

Applying MakeSet() six times, we initialize the structure of a selection of 6 singletons.

TODO ????

TODO Describe algorithm in more detail.

Okay so we make every node a singleton, sort it, and go smallest edge first and start growing the union efficiently in a way that doesn’t create a cycle.

Analysis

Sorting is the main thing O(m log m). MakeSet O(n), FindSet O(m), and Union O(n) got nothing on it..

Single Source Shortest Path Problem

Remember — Do not mismatch this problem with a problem in the last chapter (Floyd’s algortihm). This problem is about one node’s relationship to everyr other node! Floyd’s was about every node!

Problem: Given a weighted connected graph G, find shortest paths for soruce vertex s to each of the other vertices.

Dijkstra’s Algorithm

Actually pretty similar to Prim’s MST.

Among vertices not already in the tree, finds vertex u with the smallest sum.

d_v + w(v,u)

where:

• v: vertex for which shortest path has already been found (on preceding iterations)
• d: length of the shortest path from source to v
• w(v,u): length (weight) of edge between v and u

Aside — A* is an extended version of this.

TODO Example with airports.

BWI(-,0)

• JFK(BWI, 184)
• MIA(BWI, 946)
• ORD(BWI, 621)

JFK(BWI, 184)

• ORD(JFK, 740 + 184)
• BOS(JFK, 187 + 184)
• PVD(JFK, 144 + 184)
• MIA(JFK, 946 + 184)
• ??? (more remaining, actually)

…

…

ORD(BWI, 621)

• DFW(ORD, 1542)
• MIA(BWI,946)
• SFO(ORD,2462)

MIA(BWI,946)

• LAX(MIA, 2343 + 946 = 3289)
• LAX(DFW, 1235 + 1542 = 2777)
• LAX(SFO, 337 + 2462 = 2799)

Basically we find “what is the shortest path to this node?” and then build the shortest path by gradually extending and building paths out of these optimal little legos.

Aside: Notes

• Doesn’t work for negative weights
• Works on directed and undirected.
• Efficiency: O(|V|^2) for graphs represented by weight matrix and array implementation of priority queue.
• O(E|log|v|) for graphs represented by adj. lists and minhea.
• Don’t get it twisted with Prim’s nor Floyd’s! Prim’s doesn’t consider ???.

Coding Problem

Coding: Assignment of bit strings to alphabet characters

Codewords: Bit strings assigned for characters of alphebet.

Two Types of Codes:

• Fixed-length encoding (e.g., ASCII)
• Variable-length encoding (e.g., Morse)

Problem: If the frequencies of the character occurence are know (e.g., Standard American English), what’s the best binary prefix-free code?

Definition — Prefix-free codes: No codeword is a prefix of another codeword.

Huffman Codes

TODO Explanation

TODO Basically, it’s an optimal prefix code generated by creating a binary tree using the frequency of the character as like a weight or something.