一、问题

1、问题输入到正确输出的二元关系。
2、通常不需要对所有输入明确正确输出。
3、提供一个可验证的预测，正确输出必须满足。
4、6.006基于大量通用输入，研究问题。
5、非通用：小输入实例
样例：在此教室中，有一对学生有相同生日么？
6、通用：任意大量输入
样例：给定任意n个学生的集合，有一对学生有相同生日么？
如果生日是365天中的一个，对于n>365，答案总是正确的。
假设生日的分辨率超过n

二、算法

1、程序映射每个输入到单个输出。
2、如果算法对于每个问题输入，都返回一个正确输出，那么算法解决了问题。
3、例子：一个解决生日匹配的算法
维护一个名字与生日的记录（初始化为空）。
以某种顺序，采访每个学生。如果生日存在记录中，返回找到的这对。否则把姓名生日加到记录里。
如果采访的最后一名学生没有成功，返回None。

三、正确性

1、程序/算法有固定尺寸，如何证明其正确性？
2、对于少量输入，可以使用例子分析。
3、对于任意大量输入，算法必须是以某种方式，递归的或者循环的。
4、必须使用推断（为什么递归是一个计算机科学中如此关键的理念）
5、样例：生日匹配算法正确性的证明：
k：记录中学生的数量
假设：如果前k个包含匹配，在采访学生k+1之前返回匹配结果。
base case：k=0，前k个不包含匹配
归纳法假设k=k’成立，考虑k=k’+1
如果前k’包含一个匹配，已经通过推断返回了一个匹配
否则前k’不包含匹配，所以如果前k’+1有匹配，那么匹配包含k’+1
然后算法直接检测，是否学生k’+1的生日存于前k’

二、效率

1、算法多快产生一个正确的输出
可以评估时间，但想性能是独立于机器的。
返回算法操作（固定时间）的次数。
期望依赖输入的尺寸，更大的输入需要更多的时间。
输入的尺寸通常称作n，但不总是如此。
有效的，对于给定输入，返回多项式时间。
对于某个问题，有时没有有效的算法。
2、渐进理念：忽略常量因子和低阶项
上边界(O)，下边界(Ω)，上界和下界(Θ)。
时间估算，基于每个时钟周期一个操作，1GHz的单核机器。

三、计算模型

1、声明，机器上的什么操作可在O(1)时间内执行。
2、这类模型成为Word-RAM。
3、Machine word：w位的块（w是w位Word-RAM的字尺寸）。
4、内存：可寻址的一系列machine words。
5、对于O(1)数量的字，处理器支持一些常量时间操作：

6、内存地址必须能够访问内存中的每一处：

7、python是一个更复杂的计算模型，基于Word-RAM实现。

四、数据结构

1、数据结构是一个存储非常量数据方式，它支持一组的操作。
2、操作集合成为接口：
Sequence：项目外部有序（first、last、nth）
Set：项目内部有序（基于item的key查询）
3、数据结构可以用不同性能实现同样接口
4、例子：静态数组，固定槽位，固定长度，静态序列接口
StaticArray(n)：分配尺寸n的静态数组，用Θ(n)时间初始化为0
StaticArray.get_at(i)：返回存储在数组索引i处的word，用时Θ(1)
StaticArray.set_at(i, x)：把word x写到数组索引i处，用时Θ(1)
5、存储的word可以持有更大对象的地址
6、与Python tuple，set_at(i, x)相似，python list是一个动态数组

五、recitation

六、problem session1

算法时间复杂度：n、logn、n2、2n、nlogn
(logn)k=O(n)，O 表示lim logn/n，n->正无穷时，值为0

七、problem set0

(n i)表示n个数中取i个数，公有多少种组合
E(x)表示数学期望值
|A-B|表示，集合A中有，集合B中无的元素个数