More efficient version of symbol-table where the keys are strings.

# 1. R-way Tries

Two implementations of symbol tables that we've seen:

when keys are strings:
(`L`=string length, `N`=number of strings, `R`=radix)

for string keys ⇒ do better by avoiding examing the entire key.

goal: faster than hashtable ...

This week: string sort.

# 1. Strings in Java

### char data type

• char in C

8-bit integer, 256 characters, 7-bit ASCII code

• char in Java

16-bit Unicode

### String data type

`String`: immutable sequence of characters
operations: lengthe, ith char, substring, concatenate

implementation: using a `char[]`, maintain a `length` and an `offset ...`

# 1. Introduction to Maxflow

### Min-cut pb

• input: edge-weighted digraph G, each edge `e` has weight("capacity") `c[e]`>=0, a source vertex `s`, a target vertex `t`.
• def. an st-cut `(A,B)` is a partition of vertices into 2 disjoint sets A and B, with `s` in set `A` and ...

# 1. Shortest Paths APIs

context: directe, weighted graphs.

### shortest path variants

in terms of vertices:

• source-sink: form one vertex to another
• single source: from one vertex to all others (considered in this lecture)
• all pairs

constraints on edge weights:

• nonnegative weights
• arbitary weights
• eculidean

cycles:

• no directed cycles
• no negative ...

# 1. Introduction to MSTs

Given: undirected connecte graph `G` with positive edge weights.
def. Spanning tree `T`
is a subgraph of `G`, that is both tree (connected, acyclic) and spanning(all vertices are included).

⇒ Goal: find a spanning tree with minimum weight sum.

# 2. Greedy Algorithm

assumptions for simplification:

• edge ...

# 1. Intro to digraphs

Has profound differences wrt undirected graphs.

def: digraph
edges: have directions
vertex: distinguish indeg and outdeg

digraph pbs:

• path/shortest path
• topological sort: Can you draw a digraph so that all edges point upwards?
• strong connectivity: Is there a directed path between all pairs of vertices ...

# 1. Intro to graphs

Graph: vertices connected by edges.

terminology:

• path: sequence of vertices connected by edges
• cycle: path with same starting and ending vertex
• two vertices are connected: if there is a path between

ex of graph problems:

• path: or connectivity
• shortest path
• cycle
• Euler tour (ouii..)
• Hamilton tour ...

weighted graph的最短路径问题有三个非常有名的算法, 分别以三个大牛的名字命名, 今天用尽量简洁的篇幅一一介绍.

• node index = `{1,2,...,n}`
• `e[u,v]` = distance of edge(u,v); if (u,v) is not an edge, `e[u,v]=INF`
• 令N=点的数量, M=边的数量

# 任意两点最短路径: Floyd-Warshall

Floyd算法解决的问题是: 对于任意两个节点`s`(source)和`t`(target), 求s到达t的最短路径.

Floyd算法的思想是动态规划:

• 定义`d ...`

```public class GraphNode{
int val;
List<GraphNode> neighbors;
}
```

`HasheSet<GraphNode> visited = new HasheSet<GraphNode>();`

## Recursive DFS

```public void DFS(GraphNode nd){
System.out.println(nd.val);
for(GraphNode next: nd.neighbors){
if ...```

```public class GraphNode{
int val;
List<GraphNode> neighbors;
}
```

## BFS for trees/graphs

```public void BFS(GraphNode start){