May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲



查看: 1959|回复: 12

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

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

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


您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

本帖最后由 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是可以的


课程汇总 && 介绍:

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

我倒是到了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 | 显示全部楼层

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 | 显示全部楼层
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-3-24 00:24:44 | 显示全部楼层
回复 支持 反对

使用道具 举报

麦圈罐头 发表于 2014-4-3 01:00:57 | 显示全部楼层
jaly50 发表于 2014-3-21 17:53

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





回复 支持 反对

使用道具 举报

麦圈罐头 发表于 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 ...

回复 支持 反对

使用道具 举报

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

使用道具 举报

rushshi 发表于 2014-7-27 18:02:01 | 显示全部楼层
pyemma 发表于 2014-3-24 00:24

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

使用道具 举报

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




更多图片 小图 大图
回复 支持 反对

使用道具 举报



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

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

custom counter

GMT+8, 2017-5-29 10:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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