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

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.

zplxcxyc 发表于 2014-3-15 12:15
我现在写到第三个作业有点小疑问，不知道可不可以问问你。主要是Fast.java的思路问题，我用了Arrays.sort ...

用两个数组  第一个数组把那些点 从小到大排   
for (int i = 0; i < N; i++){
   Point p = points[i];  
第二个数组 再按斜率排
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 的  

wendaomumu 发表于 2017-1-1 21:42
当数组里重复元素很多时，很可能出现一个subarray全部是同一个元素，这时候如果你不停下来，会导致每次pa ...

我这儿还有一个问题。。就是用arrays.sort（）的时候如果参数里面只有一个数组名称，为何它还是可以排序的？我在point类中实现comparator接口的函数比较的是两个点和特定点的斜率啊。。

好心水教授说的那个Quicksort t-shirt
可是淘宝和凡客都没找到
你们知道在哪买吗

jaly50 发表于 2014-3-1 11:16
好心水教授说的那个Quicksort t-shirt
可是淘宝和凡客都没找到
你们知道在哪买吗

来美国再买吧。。
http://www.zazzle.com/quicksort_ ... -235914162256526017

jaly50 发表于 2014-3-2 00:16
好心水教授说的那个Quicksort t-shirt
可是淘宝和凡客都没找到
你们知道在哪买吗

Google一下可以发现几个网站~不过都不是国内的

sanguine 发表于 2014-3-1 13:21
Google一下可以发现几个网站~不过都不是国内的

于是week3讨论帖全是关于，嗯，T恤衫的。。

淘宝上 找一家定制衣服的  把 代码 截成图片 给卖家发过去 让他们印就好了   估计也就几十块钱的事儿

在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相同的元素时，要停下来坐等交换是不是......)
                               为什么呢，这不是很浪费么。。。教授都没解释。。

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.  是怎么用的。。
还是不理解怎么实现的

突然自己想明白了，编辑掉，刚才的问题好蠢

终于做完了，谢谢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