> For the complete documentation index, see [llms.txt](https://2ood.gitbook.io/2ood-knowledge-base/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://2ood.gitbook.io/2ood-knowledge-base/lecture-notes/algorithms/2023-11-27.md).

# 2023-11-27

## Introduction

> **Summary**

> **keywords**

> **TODO**

> **HW**

> **Exercise**\*

> **Next time**

***

## Huffman Coding

Characters that are more frequent needs less code.

## Minimum Cost Spanning Tree

> finding the spanning tree that has minimum cost.

### Spanning Tree

* The tree that touches all the nodes with minimum number of edges
* Do not have any loops.

> **The # of edges = (# of nodes) -1**

### representation of a Graph

G = (V,E), where V = {1,2,3,4,5,6} , E = {(1,2),(2,3),(3,4),(4,5),(5,6),(6,1)}

* There is only one minimum cost spanning tree.
* There is only one minimum cost

### Prim's Minimum Cost Spanning Tree

1. select the minimum cost edge
2. Select the **next** minimum cost edge among already connected nodes.
3. repeat stage 2 until the number of edges become (# nodes -1)

### Kruskal's Minimum Cost Spanning Tree

> Select the next minimum, but not if you make up a cycle. In that case, take the next minimum instead.

time complexity $O(E\*E)$

If you take the heap, it can be reduced to $O(E \log{E})$

### Use case on Non-Connected Graphs

> Kruskals. The Prims will not able to discover the other isolated nodes.

## Dijkstra's Algorithm

> Single Source shortest path problem

The shortest path weight from a selected source node to the each other nodes.

* initialize the not-directly-connected paths with infinity.
* **Relaxation** : exchanging/taking the less costed path.