一亩三分地论坛

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

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

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

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

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

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

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

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

讨论帖(该贴仅为week2讨论帖,加分贴请点这里)

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

Schedule

Each Friday at 12:01pm EDT, we will release the course materials for the week: two lectures, two sets of exercises, a programming assignment, and two sets of job interview questions.


  • Exercises: due two weeks after they are released.
  • Programming assignments: due two weeks after they are released.
  • Job interview questions: for your own enrichment and not assessed.

Week 2

You may be familiar with several of the algorithms and data structures that we consider this week, but perhaps not with our approach to data abstraction and Java language mechanisms for implementing them, so it's worthwhile to pay close attention. In the week's first lecture, we consider robust implementations for stacks and queues. In the week's second lecture, we begin our study of sorting algorithms. In both cases, we consider applications that illustrate the efficacy of careful modular programming when implementing algorithms.

Lecture: Stacks and Queues. We consider two fundamental data types for storing collections of objects: the stack and the queue. We implement each using either a singly-linked list or a resizing array. We introduce two advanced Java features—generics and iterators—that simplify client code. Finally, we consider various applications of stacks and queues ranging from parsing arithmetic expressions to simulating queueing systems.

Lecture: Elementary Sorts. We introduce the sorting problem and Java's Comparable interface. We study two elementary sorting methods (selection sort and insertion sort) and a variation of one of them (shellsort). We also consider two algorithms for uniformly shuffling an array. We conclude with an application of sorting to computing the convex hull via the Graham scan algorithm.

Exercises. Drill exercises on the lecture material.

Programming Assignment: Deques and Randomized Queues. Your programming assignment will involve developing implementations of two conceptually simple "collection" data types—the deque and the randomized queue---which are quite useful in practice. Properly implementing these data types will require using a linked data structure for one and a resizing array for the other.

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

Suggested readings. Section 1.3 and 2.1 in Algorithms, 4th edition.




nibuxing 发表于 2014-2-11 10:22:35 | 显示全部楼层
Lecture的Stacks(16:24)第14分钟S[N++]=item;  return s[--N];
s[N++]和s[--N]第一次见到,这语句是什么意思啊。
回复 支持 反对

使用道具 举报

ifso 发表于 2014-2-11 10:46:01 | 显示全部楼层

S[N++] = item; assign the value of item to S[N], then N = N + 1.
return S[--N]; N = N - 1, then return S[N].
回复 支持 反对

使用道具 举报

rsun 发表于 2014-2-11 11:11:03 | 显示全部楼层
唉,这个老教授讲话吞吞吐吐的,本来听力就不好,感觉听起来费劲啊。不知道大家是否有同感
回复 支持 反对

使用道具 举报

nibuxing 发表于 2014-2-11 11:32:15 | 显示全部楼层
rsun 发表于 2014-2-11 11:11
唉,这个老教授讲话吞吞吐吐的,本来听力就不好,感觉听起来费劲啊。不知道大家是否有同感

上学校数据库课的时候,听着印度老师的云里雾里,默默地打开了Algorithms的lecture。
话说我倒很喜欢他这种吞吞吐吐啊,感觉很有节奏,能基本听懂,觉得是MOOCs里面比较好的一个了。
不过有时候人家能听懂的老师我会听不懂,我觉得我这人控发音。说不定你比较控节奏。
回复 支持 反对

使用道具 举报

 楼主| sanguine 发表于 2014-2-11 11:34:24 | 显示全部楼层
rsun 发表于 2014-2-11 11:11
唉,这个老教授讲话吞吞吐吐的,本来听力就不好,感觉听起来费劲啊。不知道大家是否有同感

+1==配了字幕学习
回复 支持 反对

使用道具 举报

nibuxing 发表于 2014-2-11 11:34:29 | 显示全部楼层
ifso 发表于 2014-2-11 10:46
S[N++] = item; assign the value of item to S[N], then N = N + 1.
return S[--N]; N = N - 1, then r ...

懂了,感谢回答!继续看了。
回复 支持 反对

使用道具 举报

rsun 发表于 2014-2-11 11:41:26 | 显示全部楼层
nibuxing 发表于 2014-2-11 11:32
上学校数据库课的时候,听着印度老师的云里雾里,默默地打开了Algorithms的lecture。
话说我倒很喜欢他这 ...

我是听惯了大S,CS106A的Mehran Sahami那水银泻地的课堂。
太完美了,从头到尾没有一个停顿
回复 支持 反对

使用道具 举报

nibuxing 发表于 2014-2-11 11:45:46 | 显示全部楼层
rsun 发表于 2014-2-11 11:41
我是听惯了大S,CS106A的Mehran Sahami那水银泻地的课堂。
太完美了,从头到尾没有一个停顿

不谈了,那课无数个赞,经典的入门课。
回复 支持 反对

使用道具 举报

ifso 发表于 2014-2-11 12:45:26 | 显示全部楼层
rsun 发表于 2014-2-10 22:41
我是听惯了大S,CS106A的Mehran Sahami那水银泻地的课堂。
太完美了,从头到尾没有一个停顿

106A那老师太屌了…语速快,发音清楚。(特别喜欢用funky这词)
这边这老教授不知道是不喜欢面对摄像机还是怎么的-。-
回复 支持 反对

使用道具 举报

qiamoe 发表于 2014-2-11 15:03:08 | 显示全部楼层
rsun 发表于 2014-2-11 11:11
唉,这个老教授讲话吞吞吐吐的,本来听力就不好,感觉听起来费劲啊。不知道大家是否有同感

1.25倍速会有惊喜
回复 支持 反对

使用道具 举报

rsun 发表于 2014-2-11 15:32:30 | 显示全部楼层
qiamoe 发表于 2014-2-11 15:03
1.25倍速会有惊喜

额,能不能提前透露一下什么惊喜?
貌似要下腾讯的播放器才能调速度?
回复 支持 反对

使用道具 举报

qiamoe 发表于 2014-2-11 15:34:37 | 显示全部楼层
rsun 发表于 2014-2-11 15:32
额,能不能提前透露一下什么惊喜?
貌似要下腾讯的播放器才能调速度?

额。。。他本来语速就慢么,加速之后听不到嗯嗯啊啊的停顿了然后速度我是还可以接受啦。。。
话说在线看的话下面不就有可以加速的选项么。。。我没下腾讯的播放器呀。。
回复 支持 反对

使用道具 举报

rsun 发表于 2014-2-11 15:35:06 | 显示全部楼层
qiamoe 发表于 2014-2-11 15:34
额。。。他本来语速就慢么,加速之后听不到嗯嗯啊啊的停顿了然后速度我是还可以接受啦。。。
话说在线看 ...

这样哦,我都是下下来看的,thx!
回复 支持 反对

使用道具 举报

rsun 发表于 2014-2-11 16:01:05 | 显示全部楼层
qiamoe 发表于 2014-2-11 15:34
额。。。他本来语速就慢么,加速之后听不到嗯嗯啊啊的停顿了然后速度我是还可以接受啦。。。
话说在线看 ...

感觉用X1.25,怪怪的,时快时慢,有杂音
回复 支持 反对

使用道具 举报

qiamoe 发表于 2014-2-11 16:26:40 | 显示全部楼层
rsun 发表于 2014-2-11 16:01
感觉用X1.25,怪怪的,时快时慢,有杂音

好吧…… ╮(╯-╰)╭
回复 支持 反对

使用道具 举报

rsun 发表于 2014-2-11 20:31:06 | 显示全部楼层
本帖最后由 rsun 于 2014-2-12 08:10 编辑

In the linked-list implementations of Bag (Algorithm 1.4), Stack
(Algorithm 1.2), and Queue (Algorithm 1.3), all operations take constant time
in the worst case.
这句话具体怎么理解?一下没回过神来。
然后这又意味着什么?
谢谢
回复 支持 反对

使用道具 举报

cleverley 发表于 2014-2-12 08:40:10 | 显示全部楼层
rsun 发表于 2014-2-11 11:11
唉,这个老教授讲话吞吞吐吐的,本来听力就不好,感觉听起来费劲啊。不知道大家是否有同感

同表示受不了嗯嗯啊啊,
求问有没有人只看ppt不听视频的,效果如何?
回复 支持 反对

使用道具 举报

rsun 发表于 2014-2-12 20:04:56 | 显示全部楼层
cleverley 发表于 2014-2-12 08:40
同表示受不了嗯嗯啊啊,
求问有没有人只看ppt不听视频的,效果如何?

往后听,讲排序的时候这个老教授突然流利起来了!
究其原因,里面有他的名字,Sedgewick,他发现了一个increment sequence
回复 支持 反对

使用道具 举报

nibuxing 发表于 2014-2-13 21:59:55 | 显示全部楼层
deque用单链表可以实现吗,不太想用双链表。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-19 16:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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