_index.org

minimum spanning tree

Last edited: December 12, 2025

constituents

an undirected, conected, weighted graph

requirements

  • a spanning tree is a tree that touches all of the vericies (i.e. a graph with no cycles)
  • minimum spanning tree is a tree that connects all of the vertices with minimum edge cost

algorithm

PrimKurskal
Grows a …treeforest
Runtime 1\(O\qty(m \log n)\) with a red-black tree\(O\qty(m \log n)\) with union-find
Runtime 2\(O\qty(m + \log\qty(n))\) for Fib heapOr \(O\qty(m)\) with radix sort

Kruskal’s Algorithm

“smallest edge that doesn’t make a cycle”

red-blak

Last edited: December 12, 2025

SU-CS161 TA Review

Last edited: December 12, 2025

TODO: create a table—algo, problem it solves, runtime, conditions. Prof lemmas?

Shortest-Path Algorithms

Dijikstra’s Algorithm

Intuition: subpaths of shortest paths are shortest paths. \(O\qty(n \log n + m)\)

Bellman-Ford Algorithm

Intuition: Dijkstra but k rounds across the whole graph

Floyd-Warshall Algorithm

All-pairs shortest path. Naive solution is \(O\qty(n)O\qty(nm) = O\qty(n^{2}m)\) by running bell

DP Problems

Greedy

SU-CS229 OCT272025

Last edited: December 12, 2025

neural network

Algorithms Index

Last edited: December 12, 2025

SU-CS161 Things to Review

SU-CS161 Embedded Ethics

Lectures

Divide and Conquer

Sorting

Data Structures

Graphs

DP

Greedy Algorithms

Closing