一亩三分地论坛

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

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

2016 9月 Algorithm,Part1 week1 作业帖

[复制链接] |试试Instant~ |关注本帖
minchen57 发表于 2016-9-7 09:42:58 | 显示全部楼层 |阅读模式

[Coursera]Algorithms, Part I #1 - 2016-09-02@Princeton University

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

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

x
第一次作业,用Union−Find来实现Percolation  作业入口

先交作业,再谈感受:
week1.png

1. 对于一个同时在跟cs61b的人来说,这门课第一个作业就不太一样,不会像是cs61b那样大框架有了,只需要填空。整体的java source file都需要自己来写。
2. 第一条导致了checkstyle将我的code style 评为0分,错误百出。因为我是用notepad写,command line运行。格式上完全不怎么注意。
3. 作业入口链接开始 有个section Install a Java programming environment, 里面的链接讲述了如何用algs4.exe 安装 drjava,并且完成一些列的wrapper设置。楼主本来不想用,因为这个附带安装的java版本比较低。但是因为style实在错误太多,所以下决心想试试如何保留这些设置,但却使用新版本java。
4. 我是这样做的,如果有同学觉得有什么更好的办法请指教,我的办法挺蠢得:
    a. 先运行一遍algs4.exe,这样会把一批文件/夹,包括bin,java,checkstyle-6.9,findbugs-3.01,algs4.jar,drjava.jar 等安装到默认目录:C:\username\Min\algs4
    b. 删除java 文件夹,(相当于删除了低版本的java),如果已经安装了新版本,并且设置了path,那就没问题了,否则,去下载并安装新版本java jdk,设置好path
    c. 将path中指向 C:\username\Min\algs4\java\bin 的那一条删除,添加(如果没有的话)C:\username\Min\algs4\bin
    d. 删除桌面上algs4.exe为你建立好的drjava的快捷方式,因为已经失效,可以从C:\username\Min\algs4\drjava.jar 直接启动,或者建立快捷方式。
    e. c这一步保证了原来默认安装的一些wrapper依然可以使用,比如 checkstyle-algs4 HelloWorld.java      findbugs-algs4 HelloWorld.class   或者是javac-algs4 TestAlgs4.java。   好处是不用每次用-cp去设置使用 -algs4.jar。而且可以在提交前自己check style 和bug
啰嗦完了。。。。


这两天有时间会重新写一下第一次作业,用drjava,看看style能不能有些进步
nsc 发表于 2016-10-9 22:08:02 | 显示全部楼层
我参加的是10月份开的课。week 1作业贴这儿可以吧?
Untitled.png
回复 支持 1 反对 0

使用道具 举报

 楼主| minchen57 发表于 2016-9-7 09:49:23 | 显示全部楼层
第一次发作业帖,有些紧张,没有发总帖地址,以后一定注意
课程汇总 && 介绍:http://www.1point3acres.com/bbs/thread-200970-1-1.html
回复 支持 反对

使用道具 举报

windseason 发表于 2016-9-7 12:18:01 | 显示全部楼层
楼主为什么我看到的是10月1号开始呀
回复 支持 反对

使用道具 举报

farewell 发表于 2016-9-7 13:23:21 | 显示全部楼层
防止backwash要用两个UF,一个用于检查是否percolate,一个用于检查isfull
坚持!求加分!
Percolation.png
回复 支持 反对

使用道具 举报

youngyang 发表于 2016-9-7 22:15:18 | 显示全部楼层
1.我用Eclipse写的,然后加了package,传上去之后系统好像编译不了,所以最好还是不要package了。
2.判断percolation可以在top和bottom各加一个virtual node,在课的视频里教授有提到。
3.两个UF可以解决backwash问题,楼上已经提到了。
4.好像checkstyle不全过也可以拿满分。。。 捕获.PNG
回复 支持 反对

使用道具 举报

 楼主| minchen57 发表于 2016-9-7 22:39:43 | 显示全部楼层
折腾了好久,终于整到100分了。。。提交了20次了吧。除了backwash想清楚怎么解决之外,用新的method时候应该好好读读说明,后来得98分就是因为 uniform(int a, int b) Returns a random integer uniformly in [a, b)
这一条没有读清,不包含b,所以要用 uniform(1,n*n+1)。

week1_1.png week1_2.png


回复 支持 反对

使用道具 举报

Raymomd 发表于 2016-9-9 10:23:42 | 显示全部楼层
一开始把下标看错以为从0开始,结果后面大部分工作变成改index。。。 Screen Shot 2016-09-08 at 21.21.26.png

回复 支持 反对

使用道具 举报

nhqgoal 发表于 2016-9-9 10:44:54 | 显示全部楼层
backwash是什么意思?
回复 支持 反对

使用道具 举报

Raymomd 发表于 2016-9-9 10:50:09 | 显示全部楼层
nhqgoal 发表于 2016-9-9 10:44
backwash是什么意思?

当使用virtual node 会出现回流问题,可以维持两个Union find对象,一个有两个virtual node,另一个只有顶层的node
回复 支持 反对

使用道具 举报

nhqgoal 发表于 2016-9-9 14:45:07 | 显示全部楼层
Raymomd 发表于 2016-9-9 10:50
当使用virtual node 会出现回流问题,可以维持两个Union find对象,一个有两个virtual node,另一个只有 ...

那么我只使用一个top node,这样percolates()从N^2降到N,可行吗? 感觉这样也不会多慢
回复 支持 反对

使用道具 举报

Raymomd 发表于 2016-9-9 21:08:52 | 显示全部楼层
nhqgoal 发表于 2016-9-9 14:45
那么我只使用一个top node,这样percolates()从N^2降到N,可行吗? 感觉这样也不会多慢

要求:all methods should take constant time plus a constant number of calls to the union-find methods union(), find(), connected(), and count().
回复 支持 反对

使用道具 举报

magicbdy 发表于 2016-9-11 14:10:13 | 显示全部楼层
我用了两个Weighted Union Find,最后其他没啥问题,就是Percolation的memory test超标, 1.3x,请教各位大虾下一步可以怎么改进
回复 支持 反对

使用道具 举报

东南一个传说 发表于 2016-9-19 01:22:40 | 显示全部楼层
终于100,对于从来没有接触过java的我来说真是太难了,但感觉这样学习语法是最快的,需要用什么就去查用法。
没有用virtual top and bottom,用一个siteStatus数组来表示每个site的状态,通过位运算来改变状态,比如,这个site连接第一行则siteStatus |2(010),连接最后一行,则siteStatus|4(100),open则siteStatus|1(001).
这样只用一个UF就可以。
Screen Shot 2016-09-18 at 13.14.31.png
回复 支持 反对

使用道具 举报

MarcoLiang 发表于 2016-10-13 10:44:36 | 显示全部楼层

                               
登录/注册后可看大图
回复 支持 反对

使用道具 举报

des1994 发表于 前天 11:04 | 显示全部楼层
还在加分吗?交个作业
Princeton-1.jpeg
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 14:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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