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, more …

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 …

今天总结一下也许是搜索问题里最重要的算法: DFS !

由于树可以看成是一个graph, 这里还是只写对于graph的DFS算法. Graph类的定义还是用每一个节点保存邻居信息:

public class GraphNode{      
    int val;      
    List<GraphNode> neighbors …

今天总结一下广度优先搜索(BFS). BFS是树/图的遍历的常用算法之一, 对于没有边权重的图来说可以计算最短路径.
由于树的BFS只是图的BFS的一种特殊情况, 而 …