[TOC]

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 …

[TOC]

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算法的思想是动态规划:

• 定义 …

[TOC]

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

simHash

simHash的方法听上去比minHash还要简单:

1. 对一个文档d中的每一个term(ngram, shingle) t, 计算其hashcode(比如用java内建的`Object.hashCode()`函数) hash(t).
2. 把d中所有term的hash(t)合成为一个hashcode作为d的hashcode simHash(d): simHash(d)的长度与hash(t)相同, simHash(d)的第k个bit的取值为所有hash(t)第k个bit的众数.

[TOC]

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

BFS for trees/graphs

```public void BFS(GraphNode start){
HasheSet<GraphNode> visited = new HasheSet<GraphNode>();
q.push(start …```

[TOC]

Here is a mindmap of the common algorithms and data structures, it can give an overview of the algorithmic terms.

I shall update its content later on. And maybe write some blog entries on some of the items.

This mindmap is drawn using xmind.

approximate retrieval(相似搜索)这个问题之前实习的时候就经常遇到: 如何快速在大量数据中如何找出相近的数据.

step2. 编辑fstab

```\$ sudo blkid
/dev/sda1: LABEL="FILES" UUID="ddefc0a7-30a1-42fb-a71a-0aebb55cb0b3" TYPE="ext2 …```

assumptions in Bayes viewpoint

(btw, 对一个随机变量建模, 一般来说, 连续随机变量就用高斯 …

python科学计算包的基础是numpy, 里面的array类型经常遇到. 一开始可能把这个array和python内建的列表(list)混淆, 这里简单总结一下列表(list), 多维数组(np.ndarray)和矩阵(np.matrix)的区别.

list列表

list和java里的数组不同之处在于, python的list可以包含任意类型的对象, 一个list里可以包含int, string或者其他任何对象, 另外list是可变长度的(list有`append`, `extend``pop`等方法).

ndarray多维数组

ndarray是numpy的基石, 其实它更像一个java里面的标准数组: 所有元素有一个相同数据类型(dtype), 不过大小不是固定的.

ndarray对于大计算量的性能非常好, 所以list要做运算的时候一定要先转为array(`np.array(_a_list_ …`