注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
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.
|