2. Dynamic programing, Greedy algorithm
3. 排列， 组合
4. 设计模式
5. 读书列表
6. 接下来干什么
这两周都在看技术上的书， 所以记在这里。
1. Programming Pearls
<Programming Pearls>, 每天看一篇， 现在已经看了10篇了， 第一部分应该是提纲挈领的说， 使我对软件工程的工程这个概念有了进一步的认识, 我抄下了认为精彩的一段：
Roebling was a good engineer, and he built a good bridge by employing a huge safety factor to compensae for his ignorance(No ignorance, this is engineering).
We would design the way Jonh Roebling did, and not the way his contempararies did. So far as I know, none of the suspension bridges built by Roebling j's contempararies in the U.S still stands, and a quarter of all the bridges of any type built in the U.S in the 1870's collapsed within then years of their construction.
人生又何尝不是这样。
具体来说， 第一部分以排序为切入点， 讲到一个具体程序的问题分析， 算法， 数据结构， 程序验证， 调试， 编码， 到程序的优化。 给人的很多观念上的启发。 如果说我还记得什么的话， 我能想到这么一些关键字： don't rush into your first idea, bit map, hash map, approximate calculation, quick calculation, common sense, easy judgement, "everything should be made as simple as possible(Einstein)"
Binary search 的例子让人都不敢相信：
"A binary search is a notoriously tricky algorithm to program correctly. It took seventeen years after its invention until the first correct version of a binary search was published"
要认真啊。
2. Dynamic programing, Greedy algorithm
<the algorithm design manual>, <introduction to algorithms>两本一起， 回顾算法上的一些东西， 主要集中在Dynamic programming, greedy programming, tree上面. 看过线性代数以后， 终于明白了greedy algorithm的matroid. 我觉得DP, GP的关键就在那个optimal structure上面， 能实现问题的分治。Again, Don't rush into your first idea!Huffman 编码是GP的一个例子， 但是Huffman编码不能用那个matroid理论说明， 因为， 编码间并不是子问题的关系， 我觉得Huffman编码只是有那个Greedy的概念。
3. 排列， 组合
然后就是排列， 组合问题， 最直接的办法就是递归了。但学到了一个更高明的办法， 就是对所要表达的排列/组合编码， 比如， 生成{1,2,3}的所有子集： 把1,2,3分别用一个比特位表示，当一个数出现在一个子集中的时候， 对应的比特位就是0， 否则是1。 设定a, b, c 分别表示1,2,3, 二进制数abc就可以表示2^3种集合了(包括空集), 下面是一段java代码:
/*
* @param n, the size of the base set
*/
public void encodedPerm(int n){
//the number of the subsets
int setNum = (int)Math.pow(2, n);
int[] key = new int[n];
int op = -1;
//generate the base set and the key lookup table
HashMap<Integer, String> baseSet = new HashMap<Integer, String>();
baseSet.put(Integer.valueOf(0), "");
for(int i = 1; i <= n; i++){
key[i-1] = (int)Math.pow(2, i-1);
baseSet.put(Integer.valueOf(key[i-1]), Integer.toString(i));
}
for (int i = 0; i < setNum ; i++){
System.out.print("code "+i+" : ");
//generate a subset by examing bit by bit
for(int j = 0; j < n; j++){
op = key[j] & i;
System.out.print(baseSet.get(Integer.valueOf(op))+"/t");
//System.out.print(op);
}
System.out.println();
}
}
还有一个办法就是, 做递归处理， 每次增加一个元素， 假设给定的集合是一个数组， 那么新一轮增加的元素序号必须比上一轮大。 比如， 集合int[] A = {3,7,5}; 当空集新增了3(元素序号0)以后， 下轮可以增加7(元素序号1)； 但空集新增7以后， 下一轮不能增加3
base set A as a global value
D is initialized to -1
fun(sub set B, last index D){
if(D equals to A's length - 1)
return
for each element Elem with index > D in the set A
expand subset B by the A[D]
do anything you want with the subset
D = Elem's index
fun(A, D)
}
如果没有序号上的限制， 就可以做排列了。 说到排列， 也是可以编码的， 但是稍微复杂一些的编码。有些问题还没有弄明白， 再看看。
4. 设计模式
在图书馆没有找到传说中的经典， GoF, Head First。 开始看的是<design patterns in java>， 挺烂的书， 还不如维基百科讲的明白。 后来找到<design patterns explained>，好一些， 问题都讲清楚了。
经典的设计模式都过了一遍， 不敢说都记得， 但提到一个具体的模式我应该知道了。 这方面， 以后要积累的。
5. 读书列表
收集了一个40项的读书列表， 都是从看过的书里面摘录下来的书， 有机会可以再看。
6. 接下来干什么
我打算下周就要具体的练习一下编程了。TopCoder或者其他的题目。不然都生疏了。然后再做分形， 想了很久很久了。
还有就是Set partition 的编码问题。