Transcript CS 130 A: Data Structures and Algorithms

Course Outline
Introduction and Algorithm Analysis (Ch. 2)
 Hash Tables: dictionary data structure (Ch. 5)
 Heaps: priority queue data structures (Ch. 6)
 Balanced Search Trees: general search structures (Ch. 4.1-4.5)
 Union-Find data structure (Ch. 8.1–8.5)
 Graphs: Representations and basic algorithms
 Topological Sort (Ch. 9.1-9.2)
 Minimum spanning trees (Ch. 9.5)
 Shortest-path algorithms (Ch. 9.3.2)
 B-Trees: External-Memory data structures (Ch. 4.7)
 kD-Trees: Multi-Dimensional data structures (Ch. 12.6)
 Misc.: Streaming data, randomization

0
Minimum spanning tree
2
2
4
1
10
3
5
2
7
2
8
4
1
1
4
6
6
1
weight of tree = 16
• Connected, undirected graph with weights on edges
• Spanning tree: connected, hits all nodes, has no cycles
• MST = spanning tree of minimum total edge weight
1
Cut theorem
2
2
4
1
10
3
5
2
7
2
8
4
1
1
4
6
6
1
• For any cut in the graph,
the lowest-weight edge crossing the cut is in a MST.
• (If ties, each lowest-weight edge is in some MST)
• “Greed works.”
2
Prim’s algorithm
2
2
4
1
10
3
5
2
7
2
8
4
1
1
4
6
1
T = one vertex, no edges
for i = 1 to n-1
add the cheapest edge joining T to another vertex



3
very similar to Dijkstra’s shortest-path algorithm
implementation: priority queue (binary heap)
of edges from known to unknown vertices
time: O( |E| log |V| )
6
Kruskal’s algorithm
2
2
4
1
10
3
5
2
7
2
8
4
1
4
6
1
6
1
for i = 1 to n-1
add the cheapest edge that doesn’t create a cycle
4

implementation: priority queue (binary heap) of all edges

disjoint set union to detect cycles

time: O( |E| log |V| )