[Udacity CS 215] Algorithms (Week #2)

prviously:
第一个unit  http://www.1point3acres.com/bbs/thread-37390-1-1.html


这个unit重点讲了以下几个知识点：

1. chain, ring, grid, planar graph, hypercube
chain :
线段（中间有若干点）
ring:
把chain首尾相连
grid:
棋盘
planar graph:
平面图是可以画在在平面上并且使得不同的边可以互不交叠的图。说一个图是平面图，其实等价于说存在一个从空间到平面的连续的单射，能够将这个图投射到平面上。planar graph满足欧拉公式 vertices - edges + faces = 2
hypercube:
用通俗的递归说法,1个N阶的hypercube是将2个相同的N-1阶的hypercube对应点连接起来。1阶hypercube就是1个点。

2. big-theta reflexive
--GIVEN:
f(n) <= O(g(n))   注意：因为打字问题，"O不是O，而是Theta。下同。
--DEDUCTION:
EXISTS c1, c2>0, such that 0 <= c1*g(n) <= f(n) <= c2*g(n) for ANY n>n0
EXISTS c1, c2>0, such that 0 <= g(n) <= (1/c1)*f(n) <= (c2/c1)*g(n) for ANY n >n0
EXISTS c1, c2>0, such that 0 <= (1/c2)*g(n) <= (1/c2)*f(n) <= g(n) for ANY n>n0
=>
EXISTS c1, c2>0, such that 0 <= (1/c2)*f(n) <= g(n) <= (1/c1)*f(n) for ANY n>n0
--CONCLUSION:
g(n) <= O(f(n))

3. 用递归的方式构造图

输入的空格老是被系统吃掉，如果对齐错误就凑合着看吧 --! 你懂的
def makeG(n):
  if n == 1: return a single node
  G1 = makeG(n/2)
  G2 = makeG(n/2)
  list1 = random nodes from G1
  list2 = random nodes from G2
  make_link(G, list1, list2)

编程作业题：

---

Make a combination lock (本章唯一的编程题)

# Generate a combination lock graph given a list of nodes

a "combination lock" graph on n nodes consists of edges in a chain and edges in a star, with the left end of the chain as the center of the star.



  

use [ code] [/code ]写code，去掉空格，你懂得。。。。

小K 发表于 2012-8-9 06:24
use [ code] [/code ]写code，去掉空格，你懂得。。。。

好的 下次试试<code>标签。 python代码真是伤不起呀 还必须要保留每行前面空格。。。。   臣妾一直以为标签<code>标签是在帖子里直接插入html代码用的。   囧

have to be [], not <>......

小K 发表于 2012-8-9 07:42
have to be [], not ......

嗯 明白 刚才是因为我的那句话里用了两次[code]。 所以如果是[]的话，他们之间的文字就真的被装在code框框里了

lesson 2: