[TOC]

PQ又叫"堆"(heap), 但是可能优先队列这个名字更容易记忆它的用途: pq是一种队列, 不过不是先进先出(FIFO), 而是每次出队的元素永远是优先级最高的.

# logical structure of PQ

• 除了最后一层, 所有层都排满(没有非空节点)
• 最后一层的所有非空节点都排在左边

[TOC]

# 1. Introduction to substring search

"most ingenious algorithm we've seen so far"
pb. having two strings, `pattern` and `text`, len(pattern)=M << len(text)=N, try to find pattern in text.

ex. `indexOf` method of String in java.

# 2. Brute-Force Substring Search

function signature:
`public static int search(String …`

[TOC]

[Algo]

• 选择基准项(pivot element, 一般取第一个元素为pivot)
• 把数组里所有小于pivot的移动到pivot左边, 大于pivot的移动到右边 ⇒ 此时pivot已经位于最终排序时的正确位置
• 对pivot左右两个数组分别递归进行快速排序

## quick partition

[TOC]

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 …

[TOC]

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 …

[TOC]

# 0. Why TeXmacs?

## 0.0 LaTeX强迫症自测

⇒ 如果你不能容忍直接写成`\$A^T\$`, 而一定要写成类似`\$\textbf{A}^\intercal\$`的话... 请直接忽略本文 & 继续用LaTeX, 好走不送......
(另: 强迫症可以去这里看到底怎么打转置: http://tex.stackexchange.com/questions/30619/what-is-the-best-symbol-for-vector-matrix-transpose)

[TOC]

# 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 …`

[TOC]

# 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 …

[TOC]

# 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 …

[TOC]

# 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 …