Hanniverse！

Definition

目的是在海量语料库/文章中发现固定窗口（如5词以内、一句话内甚至一段内）单词a和单词b共同出现的频率，并以此构建单词共现矩阵。（矩阵可对称也可不对称（强调顺序），取决于具体应用）.

Definition

二级排序的目的是实现key-value对对键排序之后继续按值排序的功能.

• 解决方案1： 思路完全为Java算法. 在Reducer内直接对给定key的所有值进行排序(例如: 把一个key对应的所有value放到一个Array或List中,再排序)，因此可能会出现数据量过大，Reducer内存溢出的情况.
• 解决方案2： 方案2通过MapReduce思路进行实现，因为在MapReduce程序中，Mapper输出的键值对会经过shuffle过程再交给Reducer，在 shuffle 阶段，Mapper 输出的键值对会经过 partition(分区)->sort(排序)->group(分组)三个阶段，在MapReduce中可以通过重写sort来实现，因此只需要对key的格式进行修改，加入需要二级考虑的值并修改key类的compareTo或Comparator class即可.

利用MapReduce并行化实现选择、投影、并、交、差及自然连接的关系代数操作。

Definition

任意矩阵$M$和$N$,若$M$列数等于$N$的列数，则记M和N的乘积$P=M \cdot N$,且乘积矩阵$P$中元素均可表示为：

$p_{ik} = (M\cdot N)_{ik} = \sum_j{m_{ij}n_{jk}}$

• 最终决定$p_{ik}$位置的元素为$i,k$，因此将其作为Reduce的输出key值；
• 为记录$m_{ij}$和$n_{jk}$，需要对矩阵名称及元素所在行列进行记录，这些属性将通过Mapper处理得到.

Problem Description

一个背包的总容量为W,现在有N个物品且物品不可分,第i个物品的重量为weight[i],价值为val[i]；
往该背包里装东西,怎样装才能使得最终包内物品的总价值最大。

记录完美解决虚拟机安装VM tools之后仅能实现屏幕自适应，无法进行物理机和虚拟机之间复制粘贴+文件拖拽功能的方法。

方法的重写(Overriding)和重载(Overloading)是java多态性的不同表现，重写是父类与子类之间多态性的一种表现，重载可以理解成多态的具体表现形式。

二叉排序树

定义： 二叉排序树或者是一棵空树；或是具有如下特性的二叉树：

• 若左子树不为空，则左子树上所有节点值均小于根节点；
• 若右子树不为空，则右子树上所有节点值均大于根节点；
• 左、右子树均为二叉排序树.

核心算法： 查找算法、插入算法、删除算法

相关名词

• 连通图(无向图)： 在无向图中，若任意两个顶点$V_i$与$V_j$都有路径相通，则称该无向图为连通图。
• 强连通图(有向图)： 有向图中，若任意两个顶点$V_i$与$V_j$都有路径相通，则称该有向图为强连通图。
• 生成树： 含有图中全部n个顶点的一个连通子图，只有足以构成一棵树的n-1条边。即若生成树中再添加一条边，则必定成环。
• 最小生成树： 在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

定义及名词解释

树

1.节点的度：

• 树的度是各节点度的最大值

• 节点的度是节点拥有的子树个数

  • 树中的叶子结点的个数计算方法：

    若一棵度为4的树中度为1、2、3、4的节点的个数分别为4、3、2、2，则该树叶子节点的个数是多少？总节点个数是多少？

    设树T中的结点个数为n，度为0的结点的个数为n0，度为1的结点的个数为n1，度为2的结点的个数为n2，度为3的结点的个数为n3，度为4的结点的个数为n4，则有：

    n = n0 + n1 + n2 + n3 + n4

    设树T中的总边数为e，则该树节点的总入度 = 总出度 = 总边数

    因为除了根节点的入度为0，其余各节点的入度都为1，则有：

    e = n0 + n1 + n2 + n3 + n4 - 1

    又因为，n0的出度为0，n1的出度为1，n2的出度为2，n3的出度为3，n4的出度为4，所以：

    e = n0 * 0 + n1 * 1+ n2 * 2 + n3 * 3 + n4 * 4

    代入即可得n0的值.

2. 树的深度： 树的层数