一亩三分地论坛

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

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

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

[复制链接] |试试Instant~ |关注本帖
sanguine 发表于 2014-3-1 21:30:18 | 显示全部楼层 |阅读模式

[Coursera]Algorithms #5 - 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是可以的

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

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


Week 5


Can we guarantee fast search, insert, delete, min, max, floor, ceiling, rank, and select in a symbol table with Comparable keys? This week, you will learn that the answer to this question is a resounding Yes! and that a relatively compact implementation discovered just five years ago can do the job. Then, we consider applications and generalizations of binary search trees to problems in computational geometry.

Lecture: Balanced Search Trees. In this lecture, our goal is to develop a symbol table with guaranteed logarithmic performance for search and insert (and many other operations). We begin with 2-3 trees, which are easy to analyze but hard to implement. Next, we consider red-black binary search trees, which we view as a novel way to implement 2-3 trees as binary search trees. Finally, we introduce B-trees, a generalization of 2-3 trees that are widely used to implement file systems.

Lecture: Geometric Applications of BSTs. We start with 1d and 2d range searching, where the goal is to find all points in a given 1d or 2d interval. To accomplish this, we consider kd-trees, a natural generalization of BSTs when the keys are points in the plane (or higher dimensions). We also consider intersection problems, where the goal is to find all intersections among a set of line segments or rectangles.

Exercises. Drill exercises on the lecture material.

Programming Assignment: Kd-Trees. Your programming assignment is to implement kd-trees, which can form the basis for fast search/insert in geometric applications and in multidimensional databases.

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

Suggested readings. Section 3.3 in Algorithms, 4th edition.



rsun 发表于 2014-3-1 21:34:51 | 显示全部楼层
感觉开学后,各种忙,跟下来的人越来越少了。。。
这也是任何一门课程的趋势
回复 支持 反对

使用道具 举报

 楼主| sanguine 发表于 2014-3-1 21:41:10 | 显示全部楼层
回复 支持 反对

使用道具 举报

rsun 发表于 2014-3-1 21:49:58 | 显示全部楼层
sanguine 发表于 2014-3-1 21:41
我能说我还是弄week2么==被毕设逼死了。。。

我倒是到了week 4了,块week 5 了。
只是我跟的课比你少。
不过明天开始实习两周,,,就各种落下了
回复 支持 反对

使用道具 举报

jaly50 发表于 2014-3-21 14:49:15 | 显示全部楼层
判断题:
Consider two paths from the root to a null link in a red-black BST on N nodes. Then, the maximum difference in the length of the two paths is ~ lg N.
这个说法是对的。理由为:The extreme case occurs when the length of one path is ~ lg N and the length of the other path is ~ 2 lg N.

我不明白,哪位大神能给个例子么? 在哪种情况下2个path的距离会是lgN呐?
回复 支持 反对

使用道具 举报

jaly50 发表于 2014-3-21 17:53:21 | 显示全部楼层
花了一整天,做了10遍都没做到3分。快被我自己蠢哭了。

这两个选择题有什么区别么,为什么第一个是错的,第二个是对的?
Inserting a key into a 2-3 tree can make its height strictly decrease.
X:explain:        0.20        The height either remains the same (typical case) or increases by 1 (when the root node splits).


Inserting a key into a red-black BST can make its height strictly decrease.
YES, explain:        0.00        Consider inserting the sequence of keys { 6, 5, 4, 0, 1, 3, 2 } into an initially empty red-black BST. After key 3 is inserted, the BST has height 3. After key 2 is inserted, the tree is perfectly balanced has has height 2.       
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-3-23 22:59:52 | 显示全部楼层
今天把编程作业写了,但是Timing测试怎么也过去不,实在是想不出改进的余地了
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-3-24 00:24:44 | 显示全部楼层
经过1个多小时的debug,终于把Timing也过了,原来是开方消耗了太多的时间
回复 支持 反对

使用道具 举报

麦圈罐头 发表于 2014-4-3 01:00:57 | 显示全部楼层
jaly50 发表于 2014-3-21 17:53
花了一整天,做了10遍都没做到3分。快被我自己蠢哭了。

这两个选择题有什么区别么,为什么第一个是错的 ...

我做了8遍……
考虑两个树包含的操作,就知道2-3树不可能减少层数,红黑树的旋转操作可能使层数减少

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

麦圈罐头 发表于 2014-4-3 01:04:32 | 显示全部楼层
jaly50 发表于 2014-3-21 14:49
判断题:
Consider two paths from the root to a null link in a red-black BST on N nodes. Then, the m ...

不是两个path的距离,是根到叶的距离。课件里有,层数最大2lgN,最小lgN
回复 支持 反对

使用道具 举报

rushshi 发表于 2014-7-27 18:00:52 | 显示全部楼层
写递归真是遭罪, 有人有简便的方法写递归吗? 就像if的流程图一样,写出递归的逻辑,然后直接按图敲代码。
回复 支持 反对

使用道具 举报

rushshi 发表于 2014-7-27 18:02:01 | 显示全部楼层
pyemma 发表于 2014-3-24 00:24
经过1个多小时的debug,终于把Timing也过了,原来是开方消耗了太多的时间

大哥,写递归有简便的方法吗,调试递归太痛苦了? 有木有就像画if的流程图一样,写出递归的逻辑,然后直接按图敲代码。
回复 支持 反对

使用道具 举报

complete_46 发表于 2014-10-9 12:53:49 | 显示全部楼层

1.jpg

2.jpg

3.jpg


更多图片 小图 大图
组图打开中,请稍候......
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 02:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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