一亩三分地论坛

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

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

[HomeWork] Algorithms, Part I (week 1)

  [复制链接] |试试Instant~ |关注本帖
18258170717 发表于 2015-1-25 18:10:07 | 显示全部楼层 |阅读模式

[Coursera]Algorithms, Part I #1 - 2015.1.23@Princeton

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

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

x
本帖最后由 18258170717 于 2015-1-25 18:11 编辑

第一周的作业Percolation。难点在于“backwash”也就是在percolate的时候,不能有“孤立”的virtual bottom与virtual top连在连在一起(变蓝),注意一下isFull。大家可以自己想明白的,可以多多讨论~顺便求米求学分~
Ps:coursera的评价系统好屌,各种style错误,还有一些小问题,不过既然是算法,大头对了就差不多了,不是完美主义者~
Screen Shot 2015-01-25 at 下午5.56.29.png

评分

2

查看全部评分

enirinth 发表于 2015-7-5 11:28:26 | 显示全部楼层
rilegoule.....终于过了bonus test....
111.png


222.png



解决backwash的两种方法:
1. 一个UF object 控制percolate(),另一个UF object控制isFull()
前者有virtual bottom和virtual top, 后者只有virtual top;
fields:UF object1 (N * N + 2); UF object2 (N * N + 1); boolean array (N * N) 控制isOpen()
2. 一个UF object控制isFull(), percolates()是每次open()的最后做一个DFS找所有unfilled sites,(找到一个fill一个),如果找到深度为N的的说明percolates了.
只有virtual top;
fields: UF obejct (N * N + 1)控制isFull(); boolean array1 (N * N) 控制isOpen(); boolean array2 (N * N)作为isFull的矩阵标记; boolean percolates单一布尔值做percolates与否的标记

只有方法2可以避免backwash的同时通过bonus memory test

为什么方法2可以通过timing test?
因为虽然对某个site来说, open它之后做的DFS最坏需要O(N^2)的时间,但是amortized running time一定是O(1) 的:
证明:
从sites全部blocked开始,进行M次open;每个open()最后都有一个DFS,所以一共是M次DFS;
DFS的时间取决于它经过的sites的个数;
每个DFS经过的sites都会fill掉;
设第i个open()中的DFS,经过了T(i)个sites,那么它一定也fill了T(i)个sites;
DFS只找unfilled sites,所以任意两次DFS fill的sites是没有重叠的,因而前M次fill的总数是它们直接相加: 一共fill了 T(1) + T(2) + ... + T(M)个site
而filled sites的总数不会超过当前open sites的总数,每次只open一个sites,所以第M次open()的最后open sites总数为M; 从而T(1) + T(2) + ... + T(M) ≤ M
这是M次DFS的总和,那平均每次DFS就 ≤ M/M = 1了


故平均每次open花的时间为O(1) (除了union()等UF操作之外)

评分

3

查看全部评分

回复 支持 4 反对 0

使用道具 举报

zj45499 发表于 2015-1-25 21:14:32 | 显示全部楼层
Screen Shot 2015-01-25 at 9.13.25 PM.jpg

Style还是挂了....不过好像不算分

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 18258170717 发表于 2015-1-25 21:30:30 | 显示全部楼层
zj45499 发表于 2015-1-25 21:14
Style还是挂了....不过好像不算分

哈哈,一开始Style出来吓了我一跳,不过移动format就好了。。
回复 支持 反对

使用道具 举报

birdor 发表于 2015-1-26 06:27:28 | 显示全部楼层
本帖最后由 birdor 于 2015-1-26 07:01 编辑

Screenshot 2015-01-25 15.01.06.png
要避免 backwash,还不能用自己写的 Union-Find,还不能用多个 Union-Find Object,真是纠结了好一会儿。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

凛冬将至 发表于 2015-1-26 10:50:14 | 显示全部楼层
还是那个老问题,怎么添加那几个jar啊?我的市Mac OX搞半天,按照去年的讨论贴看了,放到default,eclipse还是显示"WeightedQuickUnionUF can not be resolved to a type".难道是我理解错了放到哪一个default里?或者我还缺少别的操作?
回复 支持 反对

使用道具 举报

gjxwin 发表于 2015-1-27 17:05:21 | 显示全部楼层
交作业了 Screen Shot 2015-01-27 at 17.04.51.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

凛冬将至 发表于 2015-1-28 09:08:32 | 显示全部楼层
有加学分么?没有完美...
搜狗截图15年01月27日2008_1.jpg

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

New613Life 发表于 2015-1-30 00:17:41 | 显示全部楼层
birdor 发表于 2015-1-26 06:27
要避免 backwash,还不能用自己写的 Union-Find,还不能用多个 Union-Find Object,真是纠结了好一会儿。 ...

你用一个Union-Find Object是怎么实现的?我只能用两个么
回复 支持 反对

使用道具 举报

 楼主| 18258170717 发表于 2015-1-30 19:58:41 | 显示全部楼层
New613Life 发表于 2015-1-30 00:17
你用一个Union-Find Object是怎么实现的?我只能用两个么

我也是用两个~请教大神
回复 支持 反对

使用道具 举报

Josh 发表于 2015-1-31 19:49:45 | 显示全部楼层
很久之前就做好了,补交一发
9~KWZ7R4T${924}LJ[TG)_S.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

czbnlzd920706 发表于 2015-2-1 06:21:50 | 显示全部楼层
惭愧,只有88。但是还是花了八个小时才写出来,还参考了网上的许多信息。。。累死了。。
评分系统说,我的Memory过大了,可能多引用了一个对象。我的确用了两个对象,一个对象有virtual top和virtual bottom,还有一个对象有virtual top 但没有 virtual bottom,以此来防止backwash现象。想不出还有什么更好的方法了,也想不动了。anyway,坚持就好!一定要跟完!
assignment1_score.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 18258170717 发表于 2015-2-1 14:56:38 | 显示全部楼层
czbnlzd920706 发表于 2015-2-1 06:21
惭愧,只有88。但是还是花了八个小时才写出来,还参考了网上的许多信息。。。累死了。。
评分系统说,我的 ...

没事的,坚持下来就是好事,水平会慢慢提高的
回复 支持 反对

使用道具 举报

宝贵费 发表于 2015-2-1 15:45:09 | 显示全部楼层
各路大神 我压根没看懂作业让我做什么。。。那个PercolationVisualizer是用来干嘛的。?
回复 支持 反对

使用道具 举报

vancexu 发表于 2015-2-1 16:31:28 | 显示全部楼层
才写完,求学分。 Screen Shot 2015-02-01 at 12.10.52 AM.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

vancexu 发表于 2015-2-1 16:32:36 | 显示全部楼层
birdor 发表于 2015-1-26 06:27
要避免 backwash,还不能用自己写的 Union-Find,还不能用多个 Union-Find Object,真是纠结了好一会儿。 ...

请教如何只用一个UF?
回复 支持 反对

使用道具 举报

czbnlzd920706 发表于 2015-2-1 19:07:37 | 显示全部楼层
宝贵费 发表于 2015-2-1 15:45
各路大神 我压根没看懂作业让我做什么。。。那个PercolationVisualizer是用来干嘛的。?

你可以谷歌一下这个作业,会有好多人的建议的。我也是初学者,Java都写不好。看着他们的提示一步步做就能做出来。主要就是用他API给的那些方法来实现这个percolate模型。并且为了提高时间效率,设置一个虚顶部和一个虚底部。也就是有两个数组,一个负责connect,另一个是标志位数组,表明是否open。具体你上网查吧,好多呢。
回复 支持 反对

使用道具 举报

titer1 发表于 2015-2-2 19:48:55 | 显示全部楼层
很高兴找到这个根据地,大家都很牛啊。一会把我第一章给贴出来
回复 支持 反对

使用道具 举报

youling_tong 发表于 2015-2-3 14:31:13 | 显示全部楼层
各种没考虑清楚,提交了四次才达到97分……
最终还是又一个corner case没考虑到..

UF-Percolation

UF-Percolation

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Howie 发表于 2015-2-9 01:12:35 | 显示全部楼层
还是没有拿到bonus 求问怎么用一个wuf做出来啊? mooc algs4.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 06:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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