一亩三分地论坛

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

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

[公开课] [Princeton] Algorithms, Part II (week 1)

[复制链接] |试试Instant~ |关注本帖
venomtian 发表于 2014-3-22 22:52:43 | 显示全部楼层 |阅读模式

[Coursera]Algorithms, Part II #1 - 2014-03-22@Princeton

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

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

x
本帖最后由 venomtian 于 2014-3-22 22:56 编辑

汇总贴:http://www.1point3acres.com/bbs/thread-89465-1-1.html

本周任务:
Exercises. Drill exercises on the lecture material.

Programming Assignment: WordNet. Determine the semantic relatedness of two nouns using the WordNet lexicon.

Job Interview Questions. Algorithmic interview questions based on the lecture material.

Suggested readings. Section 4.1 and 4.2 in Algorithms, 4th edition.



截图规范:

把本周的Exercises,Programming Assignment结果截图

会有版主给大家加分,每周1学分(50大米

glennq 发表于 2014-3-24 22:10:54 | 显示全部楼层
好像还没人发截图,我来当第一个吧
屏幕快照 2014-03-24 下午10.09.10.png
屏幕快照 2014-03-24 下午10.09.01.png
屏幕快照 2014-03-24 下午10.05.43.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-3-25 12:06:19 | 显示全部楼层
交作业 exercise1.png
exercise2.png
Program.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

dengfy 发表于 2014-3-25 17:32:30 | 显示全部楼层
回复 支持 反对

使用道具 举报

dengfy 发表于 2014-3-25 18:01:50 | 显示全部楼层
自己解决了,交作业~ QQ截图20140325180023.png QQ截图20140325125328.png QQ截图20140325125314.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| venomtian 发表于 2014-3-27 22:11:15 | 显示全部楼层
回复 支持 反对

使用道具 举报

wangfeng 发表于 2014-3-29 19:48:55 | 显示全部楼层
dengfy 发表于 2014-3-25 18:01
自己解决了,交作业~

你好,我现在正处于算法的初学阶段,你能把你编的这个程序发的我的邮箱里吗?我的邮箱是2327193734@qq.com
回复 支持 反对

使用道具 举报

wangfeng 发表于 2014-3-29 19:54:35 | 显示全部楼层
glennq 发表于 2014-3-24 22:10
好像还没人发截图,我来当第一个吧

你好,我现在正处于算法的初学阶段,你能把你编的这个程序发的我的邮箱里吗?我的邮箱是2327193734@qq.com
回复 支持 反对

使用道具 举报

glennq 发表于 2014-3-30 00:15:47 | 显示全部楼层
wangfeng 发表于 2014-3-29 19:54
你好,我现在正处于算法的初学阶段,你能把你编的这个程序发的我的邮箱里吗?我的邮箱是

我记得这课貌似有说不允许直接分享code...如果你有哪块具体的不明白的可以在这问,应该会有不少人愿意回答
回复 支持 反对

使用道具 举报

skenan 发表于 2014-3-31 12:03:16 | 显示全部楼层
回复 支持 反对

使用道具 举报

浅浅 发表于 2014-4-1 16:22:43 | 显示全部楼层
交下作业……感谢skenan给我的巨大帮助


algorithm2_pa1.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

landuostorm 发表于 2014-4-1 21:32:39 | 显示全部楼层
交作业 这style与我所学大不相同啊
algs_w1.jpg

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-4-6 11:28:09 | 显示全部楼层
交作业。。。
更多图片 小图 大图
组图打开中,请稍候......

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

rsun 发表于 2014-4-11 10:49:23 | 显示全部楼层
本帖最后由 rsun 于 2014-4-11 21:02 编辑

先交作业吧。。。
虽然还有个小bug

1.jpg
2.jpg

终于100分了

终于100分了

3.jpg






4.jpg

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

rsun 发表于 2014-4-11 14:46:56 | 显示全部楼层
本帖最后由 rsun 于 2014-4-11 15:08 编辑
landuostorm 发表于 2014-4-1 21:32
交作业 这style与我所学大不相同啊

请问一下你是用什么data structure存放synsets的?
我是用了一个ST<String, Bag<Integer>>存放noun 和对应的ids
然后再用了一个resizing array String[] 存放id和相应的nouns
这样就能从noun查找到ids,然后SAP里面的ancestors的id返回来也能找到nouns。
一个time test没过

我新手一个,感觉这样好麻烦。
所以想跟大家交流一下,你们用的是什么样的data structure

回复 支持 反对

使用道具 举报

landuostorm 发表于 2014-4-11 18:51:00 | 显示全部楼层
rsun 发表于 2014-4-11 14:46
请问一下你是用什么data structure存放synsets的?
我是用了一个ST存放noun 和对应的ids
然后再用了一个 ...

我的id to synsets 和 synsets to id 都是用了ST
回复 支持 反对

使用道具 举报

rsun 发表于 2014-4-11 19:18:15 | 显示全部楼层
本帖最后由 rsun 于 2014-4-11 19:20 编辑
landuostorm 发表于 2014-4-11 18:51
我的id to synsets 和 synsets to id 都是用了ST

这么说来我的time没过是其他的原因了。。。我再找找

不对,也有可能是rezising的时候超时了。。。我换ST试试

回复 支持 反对

使用道具 举报

landuostorm 发表于 2014-4-11 19:45:17 | 显示全部楼层
rsun 发表于 2014-4-11 19:18
这么说来我的time没过是其他的原因了。。。我再找找

不对,也有可能是rezising的时候超时了。。。我换 ...

嗯,有可能,resizing 和 searching 都是O(n)复杂度
回复 支持 反对

使用道具 举报

wsmjmiisme 发表于 2014-4-20 17:26:17 | 显示全部楼层
rsun 发表于 2014-4-11 19:18
这么说来我的time没过是其他的原因了。。。我再找找

不对,也有可能是rezising的时候超时了。。。我换 ...

全局变量声明一个Array[],大小未知

我在读文件的时候把<ID, nouns>放到了一个TreeMap<Integer,String>里面(临时的),
读完以后知道了V的大小,Array = new String[V],
然后for遍历临时的TreeMap,把string放到对应的Array里面,

这样以后查找的时候都是O(1)
回复 支持 反对

使用道具 举报

wsmjmiisme 发表于 2014-4-20 17:30:05 | 显示全部楼层

我最后一个timing 没过,想了半天也没有优化的办法了,请问大神们有没有针对outcast有什么优化?

我的思路就是暴力遍历:
d = dis[i,1]+dis[i,2]+...+dis[i,N]
dis的时间复杂度也是在SAP里面确定的,但是SAP的timing 我过了。。。

Timing Outcast
*-----------------------------------------------------------
Running 1 total tests.

3.34 seconds to build WordNet

Computing time to find outcasts. Total time must not exceed 5 seconds.


    filename       N     time
-----------------------------
   outcast4.txt    4     0.42
   outcast5.txt    5     0.17
  outcast5a.txt    5     0.10
   outcast5.txt    5     0.08
   outcast7.txt    7     0.16
   outcast8.txt    8     0.24
  outcast8a.txt    8     0.26
  outcast8b.txt    8     0.18
  outcast8c.txt    8     0.19
   outcast9.txt    9     0.24
  outcast9a.txt    9     0.28
  outcast10.txt   10     0.32
outcast10a.txt   10     0.22
  outcast11.txt   11     0.32
  outcast12.txt   12     0.31
outcast12a.txt   12     0.33
  outcast20.txt   20     0.95
  outcast29.txt   29     2.13
=> FAILED, total elapsed time: 6.87

Total: 0/1 tests passed!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 04:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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