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

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是可以的

讨论帖(该贴仅为week6讨论帖，加分贴请点这里)

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


Week 6

We conclude the course by considering hash tables, a data structure that achieves constant-time performance for core symbol table operations, provided that search keys are standard data types or simply defined. Then we consider several fundamental (and useful) examples of symbol-table clients.

Lecture: Hash Tables. We begin by describing the desirable properties of hash function and how to implement them in Java, including a fundamental tenet known as theuniform hashing assumption that underlies the potential success of a hashing application. Then, we consider two strategies for implementing hash tables—separate chaining and linear probing. Both strategies yield constant-time performance for search and insert under the uniform hashing assumption. We conclude with applications of symbol tables including sets, dictionary clients, indexing clients, and sparse vectors.

Exercises. Drill exercises on the lecture material.

Final exam. The final exam is cumulative and designed to make sure you understand how each algorithm works and when it is effective. The final will not involve Java programming. You may take the final exam up to three times (and we will record your best score).

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

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

今天在下载Week6视频的时候发现“Completed Symbol Table Applications: Sets (5:04) (optional)“这个视频无法加载也无法下载。在论坛里有人给了youtube的视频链接，我已经把所有视频都下载了下来，并且已经把week6的视频都上传到了百度网盘上了，如果有不能上youtube的同学，可以到我的网盘中下载。http://pan.baidu.com/s/1o6ufavo

想请教一个问题：
Quiz里面有个seed=659960的问题里面：

priority queue里面一次性加入N个keys的算法复杂度，我选的是NlogN，答案给出的是N
想不明白，求大牛指点！

不太理解 insert a batch of N keys(given all at once) 这个given all at once会对算法复杂度产生影响吗？
given all at once 不也得一个一个insert，然后swim么？


原题摘抄：
Suppose that you have a piority queue containing N keys that is represented internally using a max-oriented binary heap (caching a minimum key), Assume that the data type is implemented in an efficient and natural manner given the specified representation.

Match up each of the following operation with their amorteized running times.

___ insert a batch of N keys (given all at once)

--------------------------------------------------------------------------------
刚刚在discussion forum'里面找到了答案https://class.coursera.org/algs4 ... read?thread_id=1355