# Algorithms -- Greedy algorithms

## Minimum spanning trees

Here are some property:

- Removing a cycle edge cannot disconnect a graph
- A tree on n nodes has n-1 edges
- Any connected, undirected graph with |E| = |V| -1 is a tree
- An undirected graph is a tree iff. there is a unique path between any pair of edges

And *cut property*: Suppose edges X are part of a MST of G=(V,E). Pick any subset of nodes S for which X does not cross between S and V-S, and let *e* be the lightest edge across this partition. Then X \cup {e} is part of some MST

### Kruskal's MST algorithm

```
procedure kruskal(G, w){
// Input: A connected graph with weights w
// Output: A MST defined by edges X
for all u \in V:
makeset(u);
X={};
sort the Edges E by weight;
for all edges (u,v) \in E. in increasing order of weight:
if find(u) != find(v):
add edge (u,v) to X;
union(u,v)
```

}

So we need a kind of data structure to support such operations. It is *disjoint sets*

```
procedure makeset(x){
pa[x] = x;
rank[x] = 0;
}
function find(x){
while x != pa[x]:
x = pa[x];
return x;
procedure union(x,y){
rx = find(x)
ry = find(y)
if rx == ry: return
if rank[rx] > rank[ry]:
pa[ry] = rx;
else:
pa[rx] = ry;
if rank[rx] = rank[ry]:
rank[ry] = rank[ry] +1;
```

### Path Compression

```
function find(x):
if x != pa[x]:
pa[x] = find(pa[x])
return pa[x]
```

### Prim's algorithm

```
x ={ }
repeat until |X| = |V| - 1:
pick a set S \subset V for which X has no edges between S and V-S
let e \in E be the minimum-weight edge between S and V-S
X = X \cup {e}
```

## Huffman encoding

The goal is find a method to encode the message as compressive as possible. And in fact here is

```
cost of tree = \sum_{1}^{n} f[i] * (depth of ith symbol in tree)
```

And we can also express the sum as *frequencies of all leaves and internal nodes, except the root*

So we can construct the whole tree *from bottom by combining two nodes which are least frequent*

```
procedure Huffman(f){
// Input: An array f[1..n] of frequencies
// Output: An encoding tree with n leaves
let H be a priority queue of integers, ordered by f
for i = 1 .. n: insert(H,i)
for k = n+1 .. 2n-1:
i = deletemin(H), j = deletemin(H)
create a node numbered k with children i,j
f[k] = f[i] + f[j]
insert(H,k)
```

## Horn formulas

This topic is actually about logic. But how we test a satisfying assignment is related to Greedy Method.

## Set Cover

This is about **approximation factor** i.e. even greedy method doesn't behave well, but we'd like to know how far is it from