Summary_Algo.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sort\n",
    "\n",
    "### Bubble Sort\n",
    "\n",
    "```\n",
    "for i = 1 to N-1:\n",
    "    for j = 1 to N-i:\n",
    "        if A[j] < A[j-1]:\n",
    "            swap(A[j], A[j-1])\n",
    "```\n",
    "\n",
    "* 证明正确性：每个j循环之后，A[N-i:N]都变为有序的\n",
    "* 复杂度：不管什么情况都需要$O(n^2)$次判断，最好情况可以不做交换，平均和最坏需要$O(n^2)$次交换\n",
    "\n",
    "###  Insertion Sort\n",
    "\n",
    "```\n",
    "for i = 2 to N:\n",
    "    tmp = A[i]\n",
    "    for j = i downto 2:\n",
    "        if tmp >= A[j-1]:\n",
    "            break\n",
    "        A[j] = A[j-1]\n",
    "    A[j] = tmp\n",
    "```\n",
    "\n",
    "* 证明正确性：每次j循环之后A[1:i]都变为有序的\n",
    "* 运行时间：$O(n^2)$\n",
    "\n",
    "### Heap Sort\n",
    "\n",
    "* 最大堆：一颗二叉树，每个父节点都比自己的子节点大\n",
    "* 一个最大堆，根节点i被修改了，通过max_heapify可以使得其在$O(\\log n)$时间内维护成最大堆\n",
    "\n",
    "```\n",
    "def max_heapify(A, i):\n",
    "    l = left(i)\n",
    "    r = right(i)\n",
    "    if l <= heapsize and A[l] > A[i]:\n",
    "        largest = l\n",
    "    else:\n",
    "        largest = i\n",
    "    if r <= heapsize and A[r] > A[largest]\n",
    "        largest = r\n",
    "    if largest != i\n",
    "        swap(A[i], A[largest])\n",
    "        max_heapify(A, largest)\n",
    "```\n",
    "\n",
    "* 思路：先建立一个堆，由最大堆的性质可以知道，堆的根是最大的元素，把根和最后一个叶子互换，然后把那个叶子从堆中取走，再维护成一个最大堆。如此重复，可以得到排序\n",
    "\n",
    "```\n",
    "def build_heap(A):\n",
    "    headsize(A) = len(A)\n",
    "    for i = floor(len(A) / 2) downto 1:\n",
    "        max_heapify(A, i)\n",
    "```\n",
    "\n",
    "```\n",
    "def heap_sort(A)\n",
    "    build_heap(A)\n",
    "    for i = N downto 2:\n",
    "        swap(A[1], A[i])\n",
    "        heapsize(A) -= 1\n",
    "        max_heapify(A, 1)\n",
    "```\n",
    "\n",
    "## Basic Graph\n",
    "\n",
    "### BFS\n",
    "\n",
    "```\n",
    "def BSF(G, s):\n",
    "    for each u in G:\n",
    "        color[u] = WHITE\n",
    "    color[s] = GRAY\n",
    "    Q = [s]\n",
    "    while Q:\n",
    "        u = Q.pop()\n",
    "        for each v adj to u:\n",
    "            if color[v] = WHITE:\n",
    "                color[v] = GRAY\n",
    "                Q.append(v)\n",
    "        color[u] = BLACK\n",
    "```\n",
    "\n",
    "### DFS\n",
    "\n",
    "```\n",
    "def DFS(G):\n",
    "    for each u in G:\n",
    "        color[u] = WHITE\n",
    "    for each u in G:\n",
    "        if color[u] == WHITE:\n",
    "            DFS_visit(u)\n",
    "            \n",
    "def DFS_visit(u):\n",
    "    color[u] = GRAY\n",
    "    for each v adj to u:\n",
    "        if color[v] == WHITE:\n",
    "            DFS_visit(v)\n",
    "    color[u] = BLACK\n",
    "```\n",
    "\n",
    "### Topological Order\n",
    "\n",
    "* 性质：在有向无环图中，存在一种排序使得每条边都往后指\n",
    "* 运行DFS，并且按照每个节点被标记为黑色的时间先后顺序排序就是拓扑排序；只有某个节点的后继都标黑了它才可能标黑，所以标黑时间靠后的排在前面。\n",
    "\n",
    "### Strongly Connected Components\n",
    "\n",
    "* 定义：一个图中的一个节点集合，任意两个节点都可以互通，就叫做强连通分支；问题是给定一个图，找出其强连通分支的分解\n",
    "* 图的转置：就是把边都翻过来 $G^T=(V, E^T)$，$E^T = \\{(u,v) | (v, u)\\in E\\}$\n",
    "\n",
    "```\n",
    "def strongly_connected_components(G):\n",
    "    DFS(G) record turn-black time f(u) for all u\n",
    "    DFS(G^T) in decreasing order of f(u) and record the forest\n",
    "        each tree in the forest is a strongly connected component\n",
    "```\n",
    "\n",
    "## Matching\n",
    "\n",
    "* 定义：图$G(V,E)$中的一个边集$M\\subseteq E$，每个结点都至多出现在M的一条边上。称M为匹配。如果每个结点恰好出现在M的一条边上，成为完全匹配。\n",
    "    * matching: 不共点的边集M\n",
    "    * matching number: 不共点边集的边的数量\n",
    "    * maximum matching: matching number最大的\n",
    "    * perfect matching: 能够覆盖所有点的\n",
    "    * M-alternating path: $G=(V, E)$中一条交替出现在$M$和$E\\setminus M$中的路径\n",
    "    * M-augmenting path: 路径中两端没有被覆盖\n",
    "    \n",
    "### Hungarian Algorithm\n",
    "\n",
    "```\n",
    "start from any matching M\n",
    "if M is a perfect matching:\n",
    "    return M\n",
    "x0 = a exposed vertex in X\n",
    "A = {x0} \n",
    "B = {}\n",
    "if N(A) == B:\n",
    "    return NO_PERFECT_MATCHING\n",
    "    # because |N(A)|=|B|=|A|-1<|A|, violate Hall's theorem\n",
    "else:\n",
    "    y1 = a vertex in N(A) but not in B\n",
    "    if y1 is covered by M:\n",
    "        B += {y1}\n",
    "        A += {x1: (y1,x1) in M}\n",
    "        goto 'if N(A) == B'\n",
    "    else:\n",
    "        P = path from x0 to y is an alternating path\n",
    "        replace M by new M'\n",
    "        goto 'if M is a perfect matching'\n",
    "```\n",
    "\n",
    "### Hall's Theorem\n",
    "\n",
    "* 动机：如何在不求出最大流的情况下，找出一个证据说某二分图不存在完美匹配，即最大流小于n。根据最大流最小割定理，如果能够找到一个割容量小于n，即可说明。ps. 当然如果直接求出最大流，也能知道是否存在完美匹配。\n",
    "* 描述：对于一个子集$A\\subseteq X$，用$\\Gamma(A)\\subseteq Y$表示邻接A中节点的集合，如果二部图$(X,Y)$有完美匹配，那么对于所有的$A\\subseteq X$，都有$|\\Gamma(A)|\\ge |A|$。\n",
    "\n",
    "\n",
    "## Linear Programming\n",
    "\n",
    "线性规划标准型表示：\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\max\\  {\\bf C}^T {\\bf x} \\\\\n",
    "& s.t. {\\bf Ax} \\le {\\bf b} \\\\\n",
    "& \\quad \\quad {\\bf x} \\ge 0\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "LP都可以转化为标准型。特别地，如果某元素$x_j$不满足$x_j \\ge 0$，可令$x'_j,x''_j \\ge 0$，代换$x_j = x'_j - x''_j$\n",
    "\n",
    "线性规划松弛型表示，相关的不等式约束都变成等式约束，只剩下关于单个元素的不等式约束：\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& \\max\\  z = v + \\sum_{j\\in N}c_j x_j \\\\\n",
    "& s.t. x_i = b_i - \\sum_{j \\in N} a_{ij}x_j, \\, \\forall i \\in B \\\\\n",
    "& \\quad \\quad x_i \\ge 0, \\, \\forall i \\in B\\cup N\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "\n",
    "### Simplex\n",
    "\n",
    "* 基本解：考虑松弛型表示，令第一个约束右边变量（非基本变量）都为0，得到的一组解\n",
    "* 基本可行解：如果基本解也满足第二个约束，则是基本可行解\n",
    "* 单纯形法思路：先找一个基本可行解，然后每次都考虑变化一个最优化表达式中的非基本变量，使其刚好不违反约束而使得目标最优，然后把这个非基本变量$x_e$代换成一个基本变量$x_l$（pivot），然后重复进行\n",
    "\n",
    "```\n",
    "def pivot(N, B, A, b, c, v, l, e):\n",
    "    b_new[e] = b[l] / a[l,e]\n",
    "    for each j in N-{e}:\n",
    "        a_new[e,j] = a[l,j] / a[l,e]\n",
    "    a_new[e,l] = 1/a[l,e]\n",
    "    \n",
    "    for each i in B-{l}:\n",
    "        b_new[i] = b[i] - a[i,e] * b_new[e]\n",
    "    for each j in N-{e}:\n",
    "        a_new[i,j] = a[i,j] - a[i,e] * a_new[e,j]\n",
    "    a_new[i,l] = - a[i,e] a_new[e,l]\n",
    "    \n",
    "    v_new = v + c[e] * b_new[e]\n",
    "    for each j in N-{e}:\n",
    "        c_new[j] = c[j] - c[e] * a_new[e,j]\n",
    "    c_new[l] = - c[e] * a_new[e,l]\n",
    "    \n",
    "    N_new = N - {e, l}\n",
    "    B_new = B - {e, l}\n",
    "    \n",
    "    return N_new, B_new, A_new, b_new, c_new, v_new\n",
    "```\n",
    "\n",
    "其中需要一个程序initialize_simplex来找到第一个基本可行解。\n",
    "\n",
    "```\n",
    "def simplex(A, b, c):\n",
    "    N, B, A, b, c, v = initialize_simplex(A, b, c)\n",
    "    while some index e in N that c[e] > 0:\n",
    "    for each i in B:\n",
    "        if a[i, e] > 0:\n",
    "            delta[i] = b[i] / a[i, e]\n",
    "        else:\n",
    "            delta[i] = inf\n",
    "        choose l in B that minimize delta[i]\n",
    "        if delta[l] == inf:\n",
    "            return UNBOUNDED\n",
    "        else:\n",
    "            N, B, A, b, c, v = pivot(N, B, A, b, c, v, l, e)\n",
    "            \n",
    "    for i = 1 to n:\n",
    "        if i in B:\n",
    "            x[i] = b[i]\n",
    "        else:\n",
    "            x[i] = 0\n",
    "    return x\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.4.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}