📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 4041| 回复: 12
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:
公开课
学校名称: princeton
Unit号: 5
开课时间: 2014-01-31
课程全名: Algorithms
平台: Coursera

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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 [i]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.[/i]

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.




上一篇:[Coursera] Algorithms (princeton) (week5) 加分贴
下一篇:[Stanford] Convex Optimization WK#6 作业讨论帖
推荐
rushshi 2014-7-27 18:02:01 | 只看该作者
全局:
pyemma 发表于 2014-3-24 00:24
经过1个多小时的debug,终于把Timing也过了,原来是开方消耗了太多的时间

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

使用道具 举报

推荐
rushshi 2014-7-27 18:00:52 | 只看该作者
全局:
写递归真是遭罪, 有人有简便的方法写递归吗? 就像if的流程图一样,写出递归的逻辑,然后直接按图敲代码。
回复

使用道具 举报

推荐
complete_46 2014-10-9 12:53:49 | 只看该作者
全局:







。
更多图片 小图 大图
组图打开中,请稍候......
回复

使用道具 举报

🔗
jby1797 2014-3-1 21:34:51 | 只看该作者
全局:
感觉开学后,各种忙,跟下来的人越来越少了。。。
这也是任何一门课程的趋势
回复

使用道具 举报

🔗
 楼主| sanguine 2014-3-1 21:41:10 | 只看该作者
全局:
rsun 发表于 2014-3-1 21:34
感觉开学后,各种忙,跟下来的人越来越少了。。。
这也是任何一门课程的趋势

我能说我还是弄week2么==被毕设逼死了。。。
回复

使用道具 举报

🔗
jby1797 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大米 +3 收起 理由
jaly50 + 3 Thanks!

查看全部评分

回复

使用道具 举报

🔗
麦圈罐头 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
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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