一亩三分地论坛

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

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

Algorithm Princeton part II (week3)

[复制链接] |试试Instant~ |关注本帖
18258170717 发表于 2015-4-7 16:28:47 | 显示全部楼层 |阅读模式

[Coursera]Algorithm, part II #3 - 2015-3-20@Princeton

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

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

x
这次图论的课第一遍听得云里雾里,仔细看了讲义发现懂了不少,还是挺深奥的。。anyway,作业这次竟然一遍过了,直接吓尿了。。。

Week3

Week3

评分

1

查看全部评分

thomaschan 发表于 2015-4-8 19:09:36 | 显示全部楼层
这次作业编程的难度不高,但是问题非常抽象,得仔细琢磨才能想明白
2015-04-08 19:05:38 的屏幕截图.png
2015-04-08 19:06:23 的屏幕截图.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

dnalwqer 发表于 2015-4-12 20:04:50 | 显示全部楼层
LZ,我碰到一个问题,还望指点,那个subset R是怎么求出来的?我找了半天instruction也没发现,是将剩下的没有eliminated的加起来吗?
回复 支持 反对

使用道具 举报

 楼主| 18258170717 发表于 2015-4-12 21:58:57 | 显示全部楼层
dnalwqer 发表于 2015-4-12 20:04
LZ,我碰到一个问题,还望指点,那个subset R是怎么求出来的?我找了半天instruction也没发现,是将剩下的 ...

不是有FF里面的inCut方法么,就是判断与S相连的min-cut的,直接用就行了
回复 支持 反对

使用道具 举报

dnalwqer 发表于 2015-4-12 22:30:58 | 显示全部楼层
搞定~  交个作业。。。。。
98DF9610-6D4A-4F16-B96A-09D72050FCFC.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

gjxwin 发表于 2015-4-13 11:00:39 | 显示全部楼层
交作业
Screen Shot 2015-04-13 at 10.51.33.png

这次作业第一次一遍就100分,真是吃惊。这次作业感觉理解有点难,起码我感觉是这样。代码码起来也没有所说的很easy,但是只要把那几个test过了,基本就满分了。
另外发现了几个warning,求教各位,不懂啥问题:


3]QQU)8(M}{K]79$G(QOUSC.jpg

其中15行是str = in.readLine().trim().split("\\s+");
124行是FordFulkerson FF= new FordFulkerson(FN, 0, numberOfTeams() + (numOfTeams -1) * (numberOfTeams() - 2) / 2);
多谢!

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

czbnlzd920706 发表于 2015-4-23 19:41:18 | 显示全部楼层
最近进度比较慢,看到算法就心烦。这次又是讲的什么maxflow mincut,那一块听了好久。。后来问一个搞空间通信的同学,说这一块内容属于拓扑学的范畴。这次作业最大的难点,时间复杂度和空间度复杂度好像都没有了。所以代码可以随便写,只要能实现要求就可以了。
我觉得得搞清楚如何使用maxflow-mincut模型来解决这个问题。之前看人给的提示,说是,当右边全满时,如果左边的有未全满的,那么就一定eliminated的了。我也是照着这个写的。后来发现这样子是不全面的。
我的思路是,遍历左边的每条边,某条边没满时,查找到这条边to结点对应的那场比赛的双方,在右侧对应的两条边,看下这两条边是否已经满了。如果没满,那就一定eliminated的了。
如果右侧有边直接capacity < 0,那就直接退出这个方法了。这是我之前没想到的。我以为其他的仍然也需要验证,然后放进subset。但这里显然进行了简单处理。
另外,我觉得处理输入的字符串,构造多个数组,这一块儿,我并没能一次通过,因为有好多情况没考虑到。然后不断地换新的输入,不断地改进自己的constructor才搞好。是不是有一些模板式的处理方法我不知道?或者说有一些string类函数可以直接调用?但是中间可能有三个空格,两个空格,一个空格。结尾处可能是空格,也可能单纯的就是数字。我就是用一个头指针一个尾指针不停地扫描出来的。所以经常出错。
Anyway, 又熬过了一次作业。。
assignment8_Score.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

热情bruce的 发表于 2015-5-10 07:01:46 | 显示全部楼层
谢谢你们!谢谢coursera!
Screen Shot 2015-05-09 at 7.01.18 PM.png
回复 支持 反对

使用道具 举报

bluestarwing 发表于 2015-6-25 02:25:58 | 显示全部楼层
请问lz,跳过I的projects直接做II的OK吗?没有什么关联吧?
回复 支持 反对

使用道具 举报

 楼主| 18258170717 发表于 2015-6-25 10:20:02 | 显示全部楼层
bluestarwing 发表于 2015-6-25 02:25
请问lz,跳过I的projects直接做II的OK吗?没有什么关联吧?

我记忆中是没什么关联,基础好的话直接上吧
回复 支持 反对

使用道具 举报

zealot5209 发表于 2016-1-6 19:42:34 | 显示全部楼层
请问这门课的Slide去哪里可以找到?找了好久。 方便的话请哪位同学发到我邮箱,万分感谢! zealot5209@gmail.com
回复 支持 反对

使用道具 举报

aj931128 发表于 2016-1-17 12:30:54 | 显示全部楼层
这门课上完了怎么就关了呀...课程内容都看不到了
回复 支持 反对

使用道具 举报

L.r_yoga 发表于 2016-5-28 13:57:05 | 显示全部楼层
这周的作业比较方便~调用现成的FlowNetwork和FordFulkerson也不会挂Timing和memory~【偷懒专业户哈哈哈哈哈】
更多图片 小图 大图
组图打开中,请稍候......

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

elyn 发表于 2016-7-1 19:46:20 | 显示全部楼层
为什么我觉得这周的作业比之前的都难。。。
算法实现到是很简单,但是感觉maxflow-mincut的原理好抽象,虽然作业完成了,但感觉还需要再琢磨琢磨。。。
baseball.png
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 19:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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