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

• fib
• shortest path
• longest common subsequence
• knapsack of all kinds
• independent set

Greedy

• activity selection
• scheduling
• DO THIS ON REVIEW: Huffman Coding is Greedy
• minimum spanning tree

neural network

SU-CS161 Things to Review

SU-CS161 Embedded Ethics

Lectures

Divide and Conquer

• SU-CS161 SEP232025

Sorting

• merge sort: SU-CS161 SEP252025
• recurrence solving: SU-CS161 SEP302025
• median: SU-CS161 OCT022025
• randomized algos + quicksort: SU-CS161 OCT072025
• linear time sorting: SU-CS161 OCT092025

Data Structures

• red-black trees: SU-CS161 OCT142025
• hashing: SU-CS161 OCT212025

Graphs

• DFS/BFS: SU-CS161 OCT232025
• Strongly connected components: SU-CS161 OCT282025
• Dijikstra: SU-CS161 OCT302025

DP

• bellman-ford and Floyd-Warshall: SU-CS161 NOV112025
• more DP LCS, knapsack, independent set: SU-CS161 NOV132025

Greedy Algorithms

• greedy algorithms: SU-CS161 NOV182025
• MSTs: SU-CS161 NOV202025

Closing

• Max Flows, Min Cuts, and Ford-Fulkerson: SU-CS161 DEC022025

L = [[start_node]]+[[] for _ in 1 ... n]
start_node.visited = True

for i = 0 ... n-1:
    for u in L[i]:
        for v in neighbor(u):
            if not v.visited:
                v.visited = True
                L[i+1].append(v)

This uses \(O\qty(n+m)\). We can find the shortest paths in \(O\qty(m)\)