[HomeWork] Algorithms, Part I (week 2)

发现地里木有交princeton Algorithms week2的programming assignment的，于是自发一贴。
作业完成截图如下：

PS：lz水平实在是太菜了，一个地方傻逼了，结果耗了我好久好久。

enirinth 发表于 2015-7-13 22:36
先贴作业：

1. dequeue()的效率为何是O(1)randomizedQueue用resizing array实现。每一次的dequeue()都会随机在[front, back)区间中generate一个随机数，然后删去这个数。
删去了之后，形成一个空位；但是此时不能移动元素把空填住：因为amortized running time的要求是O(1), 所以只在resizing这样的“稀疏”时刻允许大规模移动元素；不能每次都移动。
那么只能检查generate的这个数在不在以前的空里，如果不幸命中空位，只能再重新生成，那我得重新生成多少次呢？会不会次数太多不是O(1)了呢？
randomized analysis:
假设[front,back)区间长度是N，其中有M个空，那么命中空位的概率为p = M/N
只需要1次就成功删除的概率为: 1 - p
2次：(1 - p)p
3次：(1 - p)p^2
i次： (1 - p)p^(i-1)
那么每次dequeue()需要操作次数的期望就是S = 1*(1 - p) + 2*(1 - p)p+ 3*(1 - p)^2 + ... + i*(1 - p)p^(i-1) + ...
S = (1 - p) (1 + 2p + 3p^2 + 4p^3 + ... )
   = (n -> 无穷) (1 - p^n)/(1 - p) - np^n
   = 1/(1 - p)
由于randomizedQueue的array整体的size ≥ N(front,back这个区间的长度)；
一共有N - M个数，N - M ≤ 0.25 * size就会resize了，所以一定有
N － M ≥ 0.25 * size ≥ 0.25 * N
从而p ＝ M/N ≤ 0.75
故S = 1 / (1 - p) ≤ 4
也就是说，虽然我每次都有可能生成一个随机数数刚好命中空位，但数学期望是我在4次以内能命中一个非空位，使得dequeue()成功进行；
从而dequeue()期望上是O(1)的。

至于resizing，它只发生在一些稀疏的时刻，amortized analysis中的averaging method很容易得出连续M个dequeue()平均下来一定是O(1)的；
那么如果dequeue(),enqueue()交替混杂的进行，如何判断平均用时呢？
- accounting method; CS 61B这门课分析resizing hash table的时候详细讲了这个方法，此处从略；它依旧可以证明我随机的进行dequeue()和enqueue()操作时，最后得出的平均时间还是O(1)；

2. I/O
input stream最重要的特点就是你不能反复的读取它，读到了某个位置之后，再readString()就一定是在这个位置之后了；
这门课提供的StdIn实际上主要用的是java.util.Scanner；
作业不让用util里的类，让你用StdIn，其实后者也用到了util，多么讽刺....
用Scanner的好处是，我可以直接readAll()，存一个String（而不是String[], 因为数组长度是O(N)的，违反了bonus test的要求）；然后就是String的算法了，Scanner里面提供了很多很直白的函数；
既然不让用，那我们就免不了while (!StdIn.isEmpty()) 这个循环了

3. bonus point: randomizedQueue的最大长度始终≤k,而不是N

我最开始的想法是如果知道了k和N，那么读每个数的时候就知道他进randomizedQueue 的概率了；
但问题是input stream读完之前，我不可能知道N是多少；而input stream读完之后，每个数都按自己应有的概率enqueue了;
所以解决问题的方法就是：N是动态的；每读一个数，N++，然后对之前的概率分配进行调整；
以1,2,3,4,5 ; k = 3, N =5 为例：
在queue长度达到k之前，照单全收；所以queue长度达到k时里面的元素是:1, 2 ,3
这时候从input stream里面读到4，一共读了4个数，N变成了4;
由于queue的长度不能超过k，超过1个也不行，所以我要先从1，2，3里面随机洗出一张牌，再把4放进去；保证queue的长度一直是k；
由于dequeue()是随机的，所以(1,2,4),(1,3,4),(2,3,4)都是等概的；
问题是没有(1,2,3); 所以有一定概率我不要4从而得出(1,2,3)。这个概率是多少呢？
也就是从N个数里面挑k个数，没有某一个数的概率 = C_{N - 1}k / C_Nk = (N - k) / N
此时k = 3, N =  4，(1,2,3)的概率就是1/4了；
下一步，读到5，N = 5; 又要面临是否要把5弄进去的抉择，此时的(N - k) / N = 2/5; 也就是说不要5的概率是2/5.
由此保证了每个(a,b,c)的permutation一定是等概的。

这个算法的思路在于：
每次决定要不要一个新数加进来的时候，我都可以保证：如果加进来，然后我可以把包含它的所有组合洗的等概；那么我只要保证不加他进来的总概率（或加他进来的总概率）是对的即可；
这个不加进来的概率就是(N - k) / N （加进来的概率是k / N）

1. public static void main(String[] args) {
   
2.   int k = Integer.parseInt(args[0]);
   
3.   RandomizedQueue<String> randomStrQue = new RandomizedQueue<String>();
   
4.   double N = 1.0;
   
5.   while (!StdIn.isEmpty()) {
   
6.      String s = StdIn.readString();
   
7.      if (k == 0) {
   
8.         break;
   
9.      } else if (randomStrQue.size() < k) {   //  长度到k之前照单全收
   
10.          randomStrQue.enqueue(s);
    
11.      } else if (StdRandom.uniform() > ((N - k) / N)) {  //  按(N - k)/N的概率决定要这个新数之后，才先洗出来一张，然后把他加进去
    
12.          randomStrQue.dequeue();
    
13.          randomStrQue.enqueue(s);
    
14.      }
    
15.      N++;
    
16.   }
    
17.   while (!randomStrQue.isEmpty()) {
    
18.      System.out.println(randomStrQue.dequeue());
    
19.   }

复制代码

求问第三个subset.java该怎么读入数据呀？我用的eclipse，代码按照视频里用while(!StdIn.isEmpty())读入，但console一直显示在等待输入，没法进行下一步指令，我都纠结了半天了。谁能给下怎么写代码才对呀？多谢啦！

我能不能说连第一个percolation还没搞定。。。哎，，，苦逼转专业

billb 发表于 2015-2-3 22:04
我能不能说连第一个percolation还没搞定。。。哎，，，苦逼转专业

我也是转专业，码代码好无力，智商不够用啊

借楼报作业，也是交了几次才把bug都扫清。PS楼上的朋友加油！ass1要多用两个virtual node，一上一下，这样percolate能满足时间了。

总体难度不大 各种细节都搞定还是不容易的

另外CS61B有个作业没有帖子 我开了一个  版主看看能不能加分呀~ http://www.1point3acres.com/bbs/thread-115561-1-1.html

感觉第二次作业比第一次要简单一些。难可能就难在生成随机队列的地方。需要用 knuth shuffle。 感觉自己这样只看视频写编程作业而丝毫不看书的模式不太好。等空了就得开始看书了。

czbnlzd920706 发表于 2015-2-6 18:22
感觉第二次作业比第一次要简单一些。难可能就难在生成随机队列的地方。需要用 knuth shuffle。 感觉自己这 ...

同感。。我也是看了视频就开始写代码了

交作业咯，求分

基本搞定，但是有个bonus报错，求指导
Test 3 (bonus): Check that maximum size of any or Deque or RandomizedQueue object
                created is <= k
  * filename = tale.txt, N = 138653, k = 5
    - max size of RandomizedQueue object = 138653
  * filename = tale.txt, N = 138653, k = 50
    - max size of RandomizedQueue object = 138653
  * filename = tale.txt, N = 138653, k = 500
    - max size of RandomizedQueue object = 138653
  * filename = tale.txt, N = 138653, k = 5000
    - max size of RandomizedQueue object = 138653
  * filename = tale.txt, N = 138653, k = 50000
    - max size of RandomizedQueue object = 138653
==> FAILED