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



查看: 1774|回复: 2

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

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

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


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

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 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.

baibai 发表于 2014-3-9 21:25:24 | 显示全部楼层
今天在下载Week6视频的时候发现“Completed Symbol Table Applications: Sets (5:04) (optional)“这个视频无法加载也无法下载。在论坛里有人给了youtube的视频链接,我已经把所有视频都下载了下来,并且已经把week6的视频都上传到了百度网盘上了,如果有不能上youtube的同学,可以到我的网盘中下载。




回复 支持 反对

使用道具 举报

wsmjmiisme 发表于 2014-4-13 14:21:20 | 显示全部楼层
本帖最后由 wsmjmiisme 于 2014-4-13 15:13 编辑


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'里面找到了答案 ... read?thread_id=1355
回复 支持 反对

使用道具 举报



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

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

custom counter

GMT+8, 2017-5-27 20:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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