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

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.

Lecture的Stacks(16:24)第14分钟S[N++]=item；  return s[--N]；
s[N++]和s[--N]第一次见到，这语句是什么意思啊。

nibuxing 发表于 2014-2-10 21:22
Lecture的Stacks(16:24)第14分钟S[N++]=item；  return s[--N]；
s[N++]和s[--N]第一次见到，这语句是什么 ...

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
唉，这个老教授讲话吞吞吐吐的，本来听力就不好，感觉听起来费劲啊。不知道大家是否有同感

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

rsun 发表于 2014-2-11 11:11
唉，这个老教授讲话吞吞吐吐的，本来听力就不好，感觉听起来费劲啊。不知道大家是否有同感

+1==配了字幕学习

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

懂了，感谢回答！继续看了。

nibuxing 发表于 2014-2-11 11:32
上学校数据库课的时候，听着印度老师的云里雾里，默默地打开了Algorithms的lecture。
话说我倒很喜欢他这 ...

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

rsun 发表于 2014-2-11 11:41
我是听惯了大S，CS106A的Mehran Sahami那水银泻地的课堂。
太完美了，从头到尾没有一个停顿

不谈了，那课无数个赞，经典的入门课。

rsun 发表于 2014-2-10 22:41
我是听惯了大S，CS106A的Mehran Sahami那水银泻地的课堂。
太完美了，从头到尾没有一个停顿

106A那老师太屌了…语速快，发音清楚。（特别喜欢用funky这词）
这边这老教授不知道是不喜欢面对摄像机还是怎么的-。-