2012级--讨论记录 (第二学期)

来自问题求解
Admin（讨论 | 贡献）2013年5月17日 (五) 14:52的版本

跳转至： 导航、 搜索

2013年3月1日

[课件下载]

  1. 计算问题与算法。
    • 计算问题：input + output + their relationship。
    • 算法：well-defined computational procedure for achieving an input-output relationship。
  2. 好算法。
    • 要素：正确性、高效性、易实现性。
    • 设计流程：思路-->过程-->正确性-->效率。
  3. 算法的正确性分析。
    • partially correct：基于checkpoint和invariant。
    • totally correct：partially correct + termination。
  4. 算法的效率分析。
    • RAM的要素：数据类型、数据存储方式；指令类型、指令执行方式。
    • running time的计算：cost*times；best/worst/average case。
  5. 算法效率的渐进表示法。
    • Theta, O和Omega的含义：基于集合；基于极限。
    • Theta vs. O：用O避免分情况讨论。
    • O vs. o：基于集合；基于极限。
    • 渐进表示法的比喻：大小关系；相似的性质，但无trichotomy。

2013年3月8日

[课件下载]

  1. 加法和乘法原理的应用：识别元素；识别不相交的集合。
  2. 列表、置换和子集。
    • 列表：本质是函数。
    • 置换：本质是双射函数。
    • k-元素置换：本质是列表。
    • k-元素子集：也可以看作函数。
  3. 双射在counting中的作用：元素个数不变，但更容易计算。
  4. 等价关系在counting中的作用：等价类大小相同时，可以做除法。

2013年3月15日

[课件下载]

  1. maximum-subarray problem。
    • divide、conquer和combine在这个算法中分别如何体现。
    • 找max-crossing-subarray的方式与brute-force不同，从而节约操作。
    • 运行时间的递归表示。
    • 利用recursion tree来猜测运行时间的渐进表示法。
    • 利用substitution或master theorem来证明。
  2. substitution证明的一些细节。
    • 为低阶项保留余量。
    • 恰当运用替换。
  3. recursion tree。
    • 作用：猜测运行时间；直接证明运行时间。
    • 构建的步骤：中间节点；叶子节点；每层的和；层数；总合。

2013年3月22日

[课件下载]

  1. induction, recursion, recurrences。
    • induction、recursion和recurrences的两两关系。
    • well-ordering principle和induction的关系：反证法+well-ordering principle=induction。
    • top-down比bottom-up的优势：思路更直接；不用证明构建的完备性；base case更直接。
  2. first-order constant coefficient linear recurrence。
    • 结论的来源：通过递推展开来猜测。
    • 结论的证明：数学归纳法。
  3. the master theorem的证明：基于递归树的时间复杂度分析。

2013年3月29日

[课件下载]

  1. probability。
    • 从集合的角度理解sample space, element, event。
    • 区分probability weight和probability，并基于probability weight理解probability distribution function的三个条件。
    • uniform probability distribution的意义：probability-->counting。
  2. the principle of inclusion and exclusion：基于Venn图解释公式。
  3. conditional probability。
    • 基于Venn图解释conditional probability和独立性。
    • independent trials process和tree diagram。
  4. random variable：理解random variable, expected value, additivity of expectation。

2013年4月7日

[课件下载]

  1. indicator random variable：原理与应用。
  2. 随机化。
    • expected running time vs. average-case running time：随机算法 vs. 一般算法的所有输入。
    • 随机数生成方法：计算方法；物理方法。
    • 数组随机排序方法：permute-by-sorting；randomize-in-place。
  3. 计算expected running time的方法：定义；indicator random variable；线性性质；条件期望。
  4. probability distributions and variance。
    • distribution function vs. cumulative distribution function：点和区间。
    • variance及其来源。

2013年4月12日

[课件下载]

  1. 快速排序。
    • 正确性证明：loop invariant；递归程序正确性的归纳证明。
    • 运行时间：worst-case；best-case；average-case。
    • 随机化的快速排序：随机化的意义；期望运行时间。
  2. 线性时间排序算法。
    • 基于比较的排序：运行时间的下界。
    • counting sort：stable；从左往右扫描的改法；对输入的要求及缺点。
    • radix sort：从高位开始排序的改法；分解的灵活性；对输入的要求。
    • bucket sort：最优运行时间。
  3. 选择问题：找最大、最小元；随机化的选择算法；确定性的选择算法。

2013年4月19日

[课件下载]

  1. dynamic set：含义；基本操作。
  2. linked list。
    • 支持的操作：search, insert, delete。
    • insert/delete的抽象实现。
    • 基于数组的具体实现：多数组；单数组。
    • dynamic set操作的实现。
  3. stack。
    • 支持的操作：test-empty, push, pop。
    • 具体实现：基于数组；基于链表。
    • dynamic set操作的实现。
  4. queue。
    • 支持的操作：test-empty, enqueue, dequeue。
    • 具体实现：基于数组；基于链表。
    • dynamic set操作的实现。
  5. rooted tree。
    • 与linked list的异同。
    • left-child, right-sibling representation的抽象实现。
    • dynamic set操作的实现。
  6. allocating and freeing objects。
    • 意义。
    • free list的本质：基于linked list实现的stack。
    • service several linked lists with a single linked list的优缺点。

2013年4月26日

[课件下载]

  1. heap、heapsort、priority queue：各算法的作用、基本原理、正确性证明、运行时间。
  2. 分层抽象。
    • priority queue <-- heap <-- array。
    • tree <-- binary tree <-- array。
    • 优缺点：更简单的正确性证明 vs. 更复杂的运行时间分析。
  3. tree的前序、中序、后序遍历。
  4. 其它ADT：union-find；dictionary。
  5. single-linkage agglomerative clustering。
    • 最终hierarchy的保存：binary out-tree。
    • hierarchy的计算过程：priority queue (+ dictionary)。
    • 计算过程的监控：union-find。

2013年5月3日

[课件下载]

  1. dictionary。
    • 操作；用途。
    • direct-address table：原理；优缺点。
    • hash table：原理；优缺点。
  2. collision。
    • expected number of items per location。
    • expected number of empty locations。
    • expected number of collisions。
  3. collision resolution。
    • chaining：原理；运行时间；优缺点。
    • open addressing：原理；三种实现方式的区别；运行时间；优缺点。
    • 降低alpha的方式：扩容。
    • perfect hashing：原理；运行时间；优缺点。
  4. hash function。
    • 目标：simple uniform hashing；depends on all the bits of the key；fast。
    • 应对蓄意构造的坏情况：choose the hash function randomly。

2013年5月10日

[课件下载]

  1. binary search trees。
    • 操作；用途。
    • 各操作：原理；正确性。
    • binary search tree vs. hash table：运行时间；前后继；范围搜索；排序；对输入的要求（hash function vs. total order）；重hash。
  2. red-black trees。
    • 平衡性及其原因。
    • rotation的性质。
    • 插入和删除的宏观思路。

2013年5月17日

[课件下载]

  1. dynamic programming。
    • 面向的问题：优化。
    • 适用的问题：有最优子结构。
    • 有用的问题：子问题重复。
    • 代价：空间换时间。
  2. dynamic programming的运行时间。
    • 性能要素：子问题数量；每个子问题中的决策数量。
    • 计算方法：top-down vs. bottom-up。
  3. 问题实例及其四步骤。
    • rod cutting。
    • matrix-chain multiplication。
    • longest common subsequence。
    • optimal binary search trees。
    • 。
取自“http://cslabcms.nju.edu.cn/problem_solving/index.php?title=2012级--讨论记录_(第二学期)&oldid=498”