一亩三分地论坛

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

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

[Coursera] Algorithms (princeton) (week3) 讨论帖

[复制链接] |试试Instant~ |关注本帖
sanguine 发表于 2014-2-15 15:16:35 | 显示全部楼层 |阅读模式

[Coursera]Algorithms #3 - 2014-01-31@princeton

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

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

x
本帖最后由 sanguine 于 2014-3-19 17:06 编辑

Honor code.   All students in the course must agree to abide by the Coursera honor code. In particular, do not post solutions or partial solutions to programming assignments; however, you are permitted to discuss general ideas and problem-solving approaches. You are also permitted to discuss solutions to exercises and job interview questions.
assignments不可以share code,但是exercise和job interview questions是可以的

讨论帖(该贴仅为week3讨论帖,加分贴请点这里)

课程汇总 && 介绍:http://www.1point3acres.com/bbs/thread-78774-1-1.html

Schedule

Each Friday at 12:01pm EDT, we will release the course materials for the week: two lectures, two sets of exercises, a programming assignment, and two sets of job interview questions.


  • Exercises: due two weeks after they are released.
  • Programming assignments: due two weeks after they are released.
  • Job interview questions: for your own enrichment and not assessed.

Week 3

Our lectures this week are based on two classic algorithms that were invented over 50 years ago, but are still important and relevant today, as implementations of one or both of them are found in virtually every software system and research on new variants of these classic methods is ongoing. Our treatment ranges from the mathematical models that explain why these methods are efficient to the details of adapting them to real-world applications on modern systems.

Lecture: Mergesort. We study the mergesort algorithm and show that it guarantees to sort any array of N items with at most NlgNcompares. We also consider a nonrecursive, bottom-up version. We prove that any compare-based sorting algorithm must make at least ~NlgN compares in the worst case. We discuss using different orderings for the objects that we are sorting and the related concept of stability.

Lecture: Quicksort. We introduce and implement the randomized quicksort algorithm and analyze its performance. We also consider randomized quickselect, a quicksort variant which finds the kth largest item in linear time. Finally, consider 3-way quicksort, a variant of quicksort that works especially well in the presence of duplicate keys.

Exercises. Drill exercises on the lecture material.

Programming Assignment: Collinear Points. Your programming assignment is a typical example of a problem that could not be solved without a fast sorting algorithm, properly applied. It is a classic problem in computational geometry: Given a set of points in the plane, design an algorithm to find all line segments that contain 4 or more points.

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

Suggested readings. Section 2.2 and 2.3 in Algorithms, 4th edition.


jaly50 发表于 2014-3-15 21:17:43 | 显示全部楼层

用两个数组  第一个数组把那些点 从小到大排   
for (int i = 0; i < N; i++){
   Point p = points;  
第二个数组 再按斜率排
for (int j = 0; j < N; j++)
    temp[j] = points[j]; //copy the array to order by slope
   Arrays.sort(temp, p.SLOPE_ORDER);
draw的时候,只draw点大于p 的  
回复 支持 1 反对 0

使用道具 举报

jaly50 发表于 2014-3-2 00:16:20 | 显示全部楼层
好心水教授说的那个Quicksort t-shirt
可是淘宝和凡客都没找到
你们知道在哪买吗
回复 支持 反对

使用道具 举报

ifso 发表于 2014-3-2 01:32:41 | 显示全部楼层
jaly50 发表于 2014-3-1 11:16
好心水教授说的那个Quicksort t-shirt
可是淘宝和凡客都没找到
你们知道在哪买吗

来美国再买吧。。
http://www.zazzle.com/quicksort_ ... -235914162256526017
回复 支持 反对

使用道具 举报

 楼主| sanguine 发表于 2014-3-2 02:21:19 | 显示全部楼层
jaly50 发表于 2014-3-2 00:16
好心水教授说的那个Quicksort t-shirt
可是淘宝和凡客都没找到
你们知道在哪买吗

Google一下可以发现几个网站~不过都不是国内的
回复 支持 反对

使用道具 举报

ifso 发表于 2014-3-2 02:52:02 | 显示全部楼层
sanguine 发表于 2014-3-1 13:21
Google一下可以发现几个网站~不过都不是国内的

于是week3讨论帖全是关于,嗯,T恤衫的。。
回复 支持 反对

使用道具 举报

liuzhihaoabc 发表于 2014-3-2 05:00:26 | 显示全部楼层
淘宝上 找一家定制衣服的  把 代码 截成图片 给卖家发过去 让他们印就好了   估计也就几十块钱的事儿
回复 支持 反对

使用道具 举报

jaly50 发表于 2014-3-2 10:35:11 | 显示全部楼层
在MergeSort里,教授讲: 一个stable的sort是:Equal items never move past each other.  就是不动 相等的元素 是吧?
然后在QuickSort里又说:When duplicates are present, it is (counter-intuitively) better to stop on keys equal to the partitioning item's key.
                                   当相同元素出现时, 尽管这是有悖直觉的,对于和partitioning item相同的元素,最好停下来。  (就是说i(or i)在遇到和lo相同的元素时,要停下来坐等交换是不是......)
                               为什么呢,这不是很浪费么。。。教授都没解释。。
回复 支持 反对

使用道具 举报

jaly50 发表于 2014-3-2 11:31:41 | 显示全部楼层
It is straightforward to *stably* quicksort an array of N items using an auxiliary array of length N.
(To implement the partitioning step: copy the items to the auxiliary array; count the number of keys { less than, equal to, greater than } the partitioning key; scan through the array from left-to-right, and copy the items back to the original array using the counts to identify their locations.)
用一个辅助数组可以实现快排的稳定性?
怎么做的?:在partition里,复制原数组,然后记(大于,等于,小于)的数。从左到右遍历该数组,再把这个辅助数组拷回原来的数组。。
这个using the counts to identify their locations.  是怎么用的。。
还是不理解怎么实现的
回复 支持 反对

使用道具 举报

vesalius 发表于 2014-3-2 14:36:55 | 显示全部楼层
本帖最后由 vesalius 于 2014-3-2 14:52 编辑

突然自己想明白了,编辑掉,刚才的问题好蠢
回复 支持 反对

使用道具 举报

jaly50 发表于 2014-3-4 21:45:34 | 显示全部楼层
本帖最后由 jaly50 于 2014-3-4 21:54 编辑

终于做完了,谢谢readman大神的不吝指导。
哪怕这次比较简单还是折腾了好久。
><英语+java渣,老师的视频很多没看懂,或者没有自己推算清楚就草草过了。
在做exercise和assignment的时候就吃到了苦果。
mergesort attempt 5次,quicksort attempt 8次。 就花了一整天了。
都是很多概念和流程没有真的搞清楚。

然后assignment也写了好几天。
几个点吧(也许你们不像我那么粗心和英语渣,不会有这样的问题)
  要好好看作业说明和checklist.
1.Point.java 说明里已经给我们提供部分代码,我们只需要写其中三个方法即可。
2.文件不知道怎么输入,应参考Checklist的PointPlotter.java。
3.而在eclipse里怎么导进input呢?A.把input.txt放在和程序一起的默认文件夹。 B. run configuration里找到我们这个程序,在它的argument里直接输入input.txt(即输入你要输入的文件名)
4.Fast.java要求要N*NlogN的时间复杂度,怎么样才能达到呢?一定要用mergesort和quicksort了吧?不过不用自己写。在Checklist里有提到,使用Arrays.sort() 要注意看其用法。
5.sort完顺序会变,为了有序输出,还应再排序一次。6.Fast的要求是按顺序输出一条线上的所有点!!!----没认真看题目,我以为要求和brute一样是输出四个点=。=就花了好长时候在考虑其他问题TAT

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

jaly50 发表于 2014-3-4 21:51:02 | 显示全部楼层
% java Fast input6.txt

[testing standard output]
(14000, 10000) -> (18000, 10000) -> (19000, 10000) -> (21000, 10000) -> (32000, 10000)

[testing standard drawing]
      -  student   solution has 4 non-null entries
      -  reference solution has 1 non-null entries
      -  3 extra entries in student solution, including: (14000, 10000) -> (32000, 10000)


我当时明明Fast输出对的,却提示错误。

原因在于,我把p.drawto(最大点)放在循环内,所以画了好多条重合的线。(重合的线当然自己检查不出来)
=。=愚蠢的自己一是犯了愚蠢的错误
二是这个错误声明居然看不懂!!!


以及,用draw的时候,有人一开始调可能会发现,那个draw板上怎么什么都没有(好吧这就是缺心眼的我)
那是因为 作业说明里要求我们把坐标调到x和Y都是(0,三万多)
如果我们只自己自己选两个(0-10,0-10)的点输出的话。。
点和线都太小太短了。。所以看不见!=。=
回复 支持 反对

使用道具 举报

 楼主| sanguine 发表于 2014-3-4 21:51:18 | 显示全部楼层
jaly50 发表于 2014-3-4 21:45
终于做完了,谢谢readman大神的不吝指导。
哪怕这次比较简单还是折腾了好久。
>

明天中期答辩完我也要赶快写了%>_<%我真TM能拖。。。
回复 支持 反对

使用道具 举报

jaly50 发表于 2014-3-4 21:58:24 | 显示全部楼层
sanguine 发表于 2014-3-4 21:51
明天中期答辩完我也要赶快写了%>_

加油加油 快点来写作业指导我
我week4可能也要放一放了
下周一跟老师讨论毕业论文
一周以前布置的任务还没开始做...
现在做完week3,我要开始动毕业论文了
回复 支持 反对

使用道具 举报

 楼主| sanguine 发表于 2014-3-4 22:02:25 | 显示全部楼层
jaly50 发表于 2014-3-4 21:58
加油加油 快点来写作业指导我
我week4可能也要放一放了
下周一跟老师讨论毕业论文

我的毕设简直苦逼,搞得我想实习都没时间……

PS!你的签名是不是看了Stanford春晚-=。=
回复 支持 反对

使用道具 举报

zplxcxyc 发表于 2014-3-15 12:15:15 | 显示全部楼层
jaly50 发表于 2014-3-4 21:45
终于做完了,谢谢readman大神的不吝指导。
哪怕这次比较简单还是折腾了好久。
>

我现在写到第三个作业有点小疑问,不知道可不可以问问你。主要是Fast.java的思路问题,我用了Arrays.sort(points, p.SLOPE_ORDER),剩下的怎么也解决不了。。。怎么样才能避免重复draw呢?要用partition来找duplicate吗?
回复 支持 反对

使用道具 举报

zplxcxyc 发表于 2014-3-16 00:22:15 | 显示全部楼层
jaly50 发表于 2014-3-15 21:17
用两个数组  第一个数组把那些点 从小到大排   
for (int i = 0; i < N; i++){
   Point p = points;  ...

draw的时候只draw在哪里大于p的点??
回复 支持 反对

使用道具 举报

jaly50 发表于 2014-3-16 00:36:46 | 显示全部楼层
zplxcxyc 发表于 2014-3-16 00:22
draw的时候只draw在哪里大于p的点??

第一个数组按大小排了序了 在第一个循环 每个点设为p
所以后来draw的时候,除了确保slope一致外,只draw 比P大的点 保证 temp[first].compareTo(p) > 0

这样子就不会重复啦!
回复 支持 反对

使用道具 举报

majiamajia 发表于 2014-4-10 03:18:15 | 显示全部楼层
不好意思各位 我最近做第三次作业
最后出来其他都没问题
只有一个错误Test 7 (stdraw): Check that each point is drawn exactly once 没有通过,有人知道这是啥意思嘛??
FAST和BRUTE都没通过这个测试!
回复 支持 反对

使用道具 举报

ifso 发表于 2014-4-11 09:21:36 | 显示全部楼层
majiamajia 发表于 2014-4-9 14:18
不好意思各位 我最近做第三次作业
最后出来其他都没问题
只有一个错误Test 7 (stdraw): Check that each  ...

Also, draw the points using draw() and draw the line segments using drawTo(). Your programs should call draw() once for each point in the input file and it should call drawTo() once for each line segment discovered. Before drawing, use StdDraw.setXscale(0, 32768) and StdDraw.setYscale(0, 32768) to rescale the coordinate system.

你看看你的程序是不是哪里没有满足这段要求~每个点都要画并且只能画一次。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 18:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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