一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2646|回复: 50
收起左侧

[HomeWork] Algorithms, Part I (week 2)

[复制链接] |试试Instant~ |关注本帖
gjxwin 发表于 2015-2-3 18:14:55 | 显示全部楼层 |阅读模式

[Coursera]Algorithms #2 - 2015-01-23@Princeton

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x

发现地里木有交princeton Algorithms week2的programming assignment的,于是自发一贴。
作业完成截图如下:
Screen Shot 2015-02-03 at 18.05.34.png


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

评分

1

查看全部评分

enirinth 发表于 2015-7-14 12:05:37 | 显示全部楼层
本帖最后由 enirinth 于 2015-7-14 12:18 编辑

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个数,没有某一个数的概率 = CN - 1k / CNk = (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.   }
复制代码

评分

2

查看全部评分

回复 支持 5 反对 1

使用道具 举报

billb 发表于 2015-2-3 22:04:43 | 显示全部楼层
我能不能说连第一个percolation还没搞定。。。哎,,,苦逼转专业
回复 支持 反对

使用道具 举报

 楼主| gjxwin 发表于 2015-2-4 00:02:18 | 显示全部楼层
billb 发表于 2015-2-3 22:04
我能不能说连第一个percolation还没搞定。。。哎,,,苦逼转专业

我也是转专业,码代码好无力,智商不够用啊
回复 支持 反对

使用道具 举报

vancexu 发表于 2015-2-5 08:02:40 | 显示全部楼层
本帖最后由 vancexu 于 2015-2-5 08:04 编辑

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


Screen Shot 2015-02-04 at 4.03.41 PM.png



评分

1

查看全部评分

回复 支持 反对

使用道具 举报

zj45499 发表于 2015-2-6 17:28:39 | 显示全部楼层
总体难度不大 各种细节都搞定还是不容易的
Screen Shot 2015-02-06 at 5.24.15 PM.jpg



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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

czbnlzd920706 发表于 2015-2-6 18:22:05 | 显示全部楼层
感觉第二次作业比第一次要简单一些。难可能就难在生成随机队列的地方。需要用 knuth shuffle。 感觉自己这样只看视频写编程作业而丝毫不看书的模式不太好。等空了就得开始看书了。
1.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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

同感。。我也是看了视频就开始写代码了
回复 支持 反对

使用道具 举报

birdor 发表于 2015-2-7 07:16:35 | 显示全部楼层
回复 支持 反对

使用道具 举报

18258170717 发表于 2015-2-7 20:47:55 | 显示全部楼层
交作业咯,求分

week2

week2

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

New613Life 发表于 2015-2-11 22:17:00 | 显示全部楼层
基本搞定,但是有个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
更多图片 小图 大图
组图打开中,请稍候......

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

knight0clk 发表于 2015-2-12 03:11:44 | 显示全部楼层
New613Life 发表于 2015-2-11 22:17
基本搞定,但是有个bonus报错,求指导
Test 3 (bonus): Check that maximum size of any or Deque or Rand ...

据说用到了这个

http://en.wikipedia.org/wiki/Reservoir_sampling

可我别的地方还没搞定。。
那两个队列你是用arraylist和linkedlist做的吗?
我报了好多内存过大的错。。
回复 支持 反对

使用道具 举报

gqjapply 发表于 2015-2-12 07:10:48 | 显示全部楼层
knight0clk 发表于 2015-2-12 03:11
据说用到了这个

http://en.wikipedia.org/wiki/Reservoir_sampling

deque可以用双向链表做,可以过。Randomized Queue的话可以用resizing array做。这样时间内存什么的应该问题不大
回复 支持 反对

使用道具 举报

New613Life 发表于 2015-2-12 19:15:10 | 显示全部楼层
knight0clk 发表于 2015-2-12 03:11
据说用到了这个

http://en.wikipedia.org/wiki/Reservoir_sampling

嗯嗯,谢谢。
我就是按照12楼讲的做的,你可以参考一下
回复 支持 反对

使用道具 举报

wbwmartin 发表于 2015-2-16 11:06:27 | 显示全部楼层
交作业了,各种细节太麻烦了,调了半天style发现不算分。。
QQ20150215-1@2x.png QQ20150215-2@2x.png QQ20150215-3@2x.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

凛冬将至 发表于 2015-2-18 22:42:31 | 显示全部楼层
Week 2,加学分咧
hw2.jpg

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Howie 发表于 2015-2-26 21:33:47 | 显示全部楼层
做的有那么一点无力。。不想改了
QQ截圖20150226213215.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

tianqing705 发表于 2015-3-8 10:59:12 | 显示全部楼层
提交了8次才刷到一百分。好多小问题。每次debug要死要活完发现问题后真想扇自己几巴掌。。。
Screen Shot 2015-03-07 at 9.56.30 PM.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

zhoutaiyanghua1 发表于 2015-3-9 22:49:34 | 显示全部楼层
把之前的都补上
求学分~

                               
登录/注册后可看大图

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

热情bruce的 发表于 2015-3-16 07:43:56 | 显示全部楼层
之前week 2的:
Screen Shot 2015-03-15 at 7.41.11 PM.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

christy.zhang 发表于 2015-3-23 18:20:17 | 显示全部楼层
弱弱的问一句,为什么我的传上去编译不过呀?
Subset.java:7: error: cannot find symbol
                   String input = StdIn.readString();
                                  ^
  symbol:   variable StdIn
  location: class Subset
Subset.java:9: error: cannot find symbol
                   RandomizedQueue rq = new RandomizedQueue();
                   ^
  symbol:   class RandomizedQueue
  location: class Subset
Subset.java:9: error: cannot find symbol
                   RandomizedQueue rq = new RandomizedQueue();
                                            ^
  symbol:   class RandomizedQueue
  location: class Subset
3 errors
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 02:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表