cassiechen.com

宝贝说他国内一好哥们最近刚有了女儿，现在2个月大左右了，回国本说带点奶粉过去，毕竟国内的奶粉不是人喝的。。结果人家说他媳妇奶多的是，母奶都喝不完，别说奶粉了，放家也就是摆设罢了。然后，介于我每次路过童装店都有一种想住里面不回家了的欲望。。这次二话没说，拉着我宝贝就逛街去了。我看中了至少100样东西，好吧，确切的说，他们店里没有什么是我看不上的。=.= 我遇到小孩的东西就克制不住自己。。

哈哈，这些小衣服都留不下，虽然我特想全装箱子里留给我女儿以后穿。我说我第一天怀孕了，我就拿xx钱出来，不管男女，一顿乱买，宝贝头上无数滴汗下来了估计。。

这次买的那件小比基尼也太可爱了，还有小樱桃在上面，哈哈哈哈，太逗了。有的时候真想什么都不管了，直接要个娃娃算了，理智冷静下来，的确还不是时候=_=|| 烦啊。。。我想要小女儿啊，给她买无数的公主裙啊。。

跟宝贝的日子越过越开心了，我仔细的想了一想，过去的2年多时间里，我似乎没有一天不是笑着过的。我很满足。我要跟我宝贝好好过一辈子。

这个是在graph里，找到所有 s 到 t 的 path 必须全部经过特定的一个点。

Given:
$G=(V,E)$ be an $n$ vertex graph. Suppose $G$ has a pair of vertices $s$ and $t$ such that $dist(s,t)>\frac{n}{2}$ .

Want:
Argue that every path from $s$ to $t$ must go through a vertex $u \neq s,t$ . Find such vertex with linear time algorithm.

Solve:
We run a BFS starting from $s$ . Let $L_0,L_1,\dots,L_{k+1}$ be the layers discovered. Thus $L_0={s}$ and $L_(k+1)={t}$ , so there are $k$ layers between $s$ and $t$ .

By $dist(s,t)>\frac{n}{2}$ , it follows that $k> \frac{n}{2}$ . We claim that there is a layer $L_i$ for some $1<i<k$ that has a single node. Otherwise, if all layers between $L_0$ and $L_{k+1}$ had two or more vertices then if we count all vertices in the tree, we have 1 vertex $s$ + 1 vertex $t$ + 2 vertices for $k$ layers, so:
$\sum_{i=0}^{k+1}|L_i| \geq 2+2k>2+2 \frac{n}{2}=n+2$ .

This means $n \geq 2+n$ , but this cannot be.

然后现在找一个graph里，所有path都经过 u 或者 v点，当 $dist(s,t)>\frac{n}{3}$ 的时候。
Prove:
There are 2 vertices $u,v$ , if removing them will disconnects path $s,t$ .
Solve:
$dist(s,t)>\frac{n}{3}\Rightarrow k>\frac{n}{3}$ . Assume all layer has more than 2 vertices, then we get $n\geq 2+3k \Rightarrow n\geq2+n$ .
Running time: $O(m+n)$ for BFS.

Given an array $A$ consisting of $n$ integers, $A[1],A[2],\dots,A[n]$ . Want to compute the matrix $B[i,j]=\sum_{k=i}^{j}{A[k]=A[i]+A[i+1]+\dots+A[j]}$ for $1\leq i \leq j \leq n$ . Consider below for computing B:

Algorithm 1 SUMMING_UP(A)
1. for  do
2.   for  do
3.     add up array entries  through 
4.     store result in 
5. return B

i) First count how many times Lines 3 and 4 are executed. There are $n$ iterations for outer for loop, and inner loop ranges from $n$ iterations when $i=1$ to 1 iteration when $i=n$ . Thus Lines 3 and 4 are executed

$1+2+\dots+n=\sum_{k=1}^{n}{k}=\frac{n(n+1)}{2}$

times depending on how far apart $i$ and $j$ are. Line 3 and 4 take $\Theta (j-i+1)$ time. Means each iteration takes $O(n)$ time.

So overall running time $O(n^3)$ . And if each iteration takes $\Omega (1)$ , then running time is $\Omega (n^2)$ .

Now to show that the time complexity is in fact $\Theta (n^3)$ . For this, we need to argue only the algorithm runs in $\Omega (n^3)$ . Consider the iterations where $i \leq \frac{n}{3}$ and $j \geq \frac{2n}{3}$ . There are $\frac{n^2}{9}$ such iterations. In each of there iterations, $j-i \geq \frac{n}{3}$ . Therefore, even when only restricted to there iterations, we get a time complexity of $\Omega (n^3)$ .

今天在家没事做，也不想学习，就把空间给清理了。这么些年，竟然堆了这么多东西在这里。host公司肯定老郁闷了，我还真把他们象征性的无限空间给拿来无限用了。这个空间越来越慢，我总感觉这个公司是变相报复我。不过对于一个月3澳币的host来说，我也不能多说什么了。

这个学期就一门考试，其他的课都在学期中结束了，导致我最后2个星期过的跟鬼似的。现在感觉突然轻松了。虽然我剩下的那门考试，是挂掉了无数人的课。

我记得这个学期开学的时候，我在跟其他组员说这个课也太难了，真不想学啊。结果众人睁大了眼睛，问我：“这难道是你第一次上这个课吗?” 感情他们全是上学期挂掉的，弄的我很紧张。哈哈。

一堆quiz，assignment，test下来，我也就是个及格的货，唉，算啦算啦，我向来是追求50分整的人，51分都闲多，所以现在也就很轻松了，好几天没碰书了。

今天开始整理这个课的笔记，发现好多东西啊，怎么都不会啊。

空间的图片我给重新上传了，Flare好像还有好多link连着我空间的图片，其他的就不弄了先。每次换个主题，去换每个post的格式最费时间了。我应该没那个闲工夫来一个个更新了。

14-NOV-2011 宝宝衣服

Algorithms and Complexity No.2

New Start

Recent Posts