本帖最后由 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是可以的
课程汇总 && 介绍：http://www.1point3acres.com/bbs/thread-78774-1-1.html
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.