2016 9月 Algorithm，Part1 week1 作业帖

第一次作业，用Union−Find来实现Percolation  作业入口；

先交作业，再谈感受：

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能不能有些进步

我参加的是10月份开的课。week 1作业贴这儿可以吧？

折腾了好久，终于整到100分了。。。提交了20次了吧。除了backwash想清楚怎么解决之外，用新的method时候应该好好读读说明，后来得98分就是因为 uniform(int a, int b) Returns a random integer uniformly in [a, b)
这一条没有读清，不包含b，所以要用 uniform（1，n*n+1）。

防止backwash要用两个UF，一个用于检查是否percolate，一个用于检查isfull
坚持！求加分！

第一次发作业帖，有些紧张，没有发总帖地址，以后一定注意
课程汇总 && 介绍：http://www.1point3acres.com/bbs/thread-200970-1-1.html

楼主为什么我看到的是10月1号开始呀

1.我用Eclipse写的，然后加了package，传上去之后系统好像编译不了，所以最好还是不要package了。
2.判断percolation可以在top和bottom各加一个virtual node，在课的视频里教授有提到。
3.两个UF可以解决backwash问题，楼上已经提到了。
4.好像checkstyle不全过也可以拿满分。。。

一开始把下标看错以为从0开始，结果后面大部分工作变成改index。。。

backwash是什么意思？

nhqgoal 发表于 2016-9-9 10:44
backwash是什么意思？

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

Raymomd 发表于 2016-9-9 10:50
当使用virtual node 会出现回流问题，可以维持两个Union find对象，一个有两个virtual node，另一个只有 ...

那么我只使用一个top node，这样percolates（）从N^2降到N,可行吗？ 感觉这样也不会多慢