一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1614|回复: 2
收起左侧

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

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

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

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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


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


评分

2

查看全部评分

回复 支持 反对

使用道具 举报

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

想请教一个问题:
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
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

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

custom counter

GMT+8, 2016-12-8 10:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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