查看“2012级--讨论记录 (第二学期)”的源代码

=2013年3月1日=
[[媒体文件:讨论记录-第二学期-2班-第1次.pdf|[课件下载]]]
<ol>
  <li>
    计算问题与算法。
    <ul>
      <li>计算问题：input + output + their relationship。</li>
      <li>算法：well-defined computational procedure for achieving an input-output relationship。</li>
    </ul>
  </li>
  <li>
    好算法。
    <ul>
      <li>要素：正确性、高效性、易实现性。</li>
      <li>设计流程：思路-->过程-->正确性-->效率。</li>
    </ul>
  </li>
  <li>
    算法的正确性分析。
    <ul>
      <li>partially correct：基于checkpoint和invariant。</li>
      <li>totally correct：partially correct + termination。</li>
    </ul>
  </li>
  <li>
    算法的效率分析。
    <ul>
      <li>RAM的要素：数据类型、数据存储方式；指令类型、指令执行方式。</li>
      <li>running time的计算：cost*times；best/worst/average case。</li>
    </ul>
  </li>
  <li>
    算法效率的渐进表示法。
    <ul>
      <li>Theta, O和Omega的含义：基于集合；基于极限。</li>
      <li>Theta vs. O：用O避免分情况讨论。</li>
      <li>O vs. o：基于集合；基于极限。</li>
      <li>渐进表示法的比喻：大小关系；相似的性质，但无trichotomy。</li>
    </ul>
  </li>
</ol>

=2013年3月8日=
[[媒体文件:讨论记录-第二学期-2班-第2次.pdf|[课件下载]]]
<ol>
  <li>加法和乘法原理的应用：识别元素；识别不相交的集合。</li>
  <li>
    列表、置换和子集。
    <ul>
      <li>列表：本质是函数。</li>
      <li>置换：本质是双射函数。</li>
      <li>k-元素置换：本质是列表。</li>
      <li>k-元素子集：也可以看作函数。</li>
    </ul>
  </li>
  <li>双射在counting中的作用：元素个数不变，但更容易计算。</li>
  <li>等价关系在counting中的作用：等价类大小相同时，可以做除法。</li>
</ol>

=2013年3月15日=
[[媒体文件:讨论记录-第二学期-2班-第3次.pdf|[课件下载]]]
<ol>
  <li>
    maximum-subarray problem。
    <ul>
      <li>divide、conquer和combine在这个算法中分别如何体现。</li>
      <li>找max-crossing-subarray的方式与brute-force不同，从而节约操作。</li>
      <li>运行时间的递归表示。</li>
      <li>利用recursion tree来猜测运行时间的渐进表示法。</li>
      <li>利用substitution或master theorem来证明。</li>
    </ul>
  </li>
  <li>
    substitution证明的一些细节。
    <ul>
      <li>为低阶项保留余量。</li>
      <li>恰当运用替换。</li>
    </ul>
  </li>
  <li>
    recursion tree。
    <ul>
      <li>作用：猜测运行时间；直接证明运行时间。</li>
      <li>构建的步骤：中间节点；叶子节点；每层的和；层数；总合。</li>
    </ul>
  </li>
</ol>

=2013年3月22日=
[[媒体文件:讨论记录-第二学期-2班-第4次.pdf|[课件下载]]]
<ol>
  <li>
    induction, recursion, recurrences。
    <ul>
      <li>induction、recursion和recurrences的两两关系。</li>
      <li>well-ordering principle和induction的关系：反证法+well-ordering principle=induction。</li>
      <li>top-down比bottom-up的优势：思路更直接；不用证明构建的完备性；base case更直接。</li>
    </ul>
  </li>
  <li>
    first-order constant coefficient linear recurrence。
    <ul>
      <li>结论的来源：通过递推展开来猜测。</li>
      <li>结论的证明：数学归纳法。</li>
    </ul>
  </li>
  <li>the master theorem的证明：基于递归树的时间复杂度分析。</li>
</ol>

=2013年3月29日=
[[媒体文件:讨论记录-第二学期-2班-第5次.pdf|[课件下载]]]
<ol>
  <li>
    probability。
    <ul>
      <li>从集合的角度理解sample space, element, event。</li>
      <li>区分probability weight和probability，并基于probability weight理解probability distribution function的三个条件。</li>
      <li>uniform probability distribution的意义：probability-->counting。</li>
    </ul>
  </li>
  <li>the principle of inclusion and exclusion：基于Venn图解释公式。</li>
  <li>
    conditional probability。
    <ul>
      <li>基于Venn图解释conditional probability和独立性。</li>
      <li>independent trials process和tree diagram。</li>
    </ul>
  </li>
  <li>random variable：理解random variable, expected value, additivity of expectation。</li>
</ol>

=2013年4月7日=
[[媒体文件:讨论记录-第二学期-2班-第6次.pdf|[课件下载]]]
<ol>
  <li>indicator random variable：原理与应用。</li>
  <li>
    随机化。
    <ul>
      <li>expected running time vs. average-case running time：随机算法 vs. 一般算法的所有输入。</li>
      <li>随机数生成方法：计算方法；物理方法。</li>
      <li>数组随机排序方法：permute-by-sorting；randomize-in-place。</li>
    </ul>
  </li>
  <li>计算expected running time的方法：定义；indicator random variable；线性性质；条件期望。</li>
  <li>
    probability distributions and variance。
    <ul>
      <li>distribution function vs. cumulative distribution function：点和区间。</li>
      <li>variance及其来源。</li>
    </ul>
  </li>
</ol>

=2013年4月12日=
[[媒体文件:讨论记录-第二学期-2班-第7次.pdf|[课件下载]]]
<ol>
  <li>快速排序。
    <ul>
      <li>正确性证明：loop invariant；递归程序正确性的归纳证明。</li>
      <li>运行时间：worst-case；best-case；average-case。</li>
      <li>随机化的快速排序：随机化的意义；期望运行时间。</li>
    </ul>
  </li>
  <li>线性时间排序算法。
    <ul>
      <li>基于比较的排序：运行时间的下界。</li>
      <li>counting sort：stable；从左往右扫描的改法；对输入的要求及缺点。</li>
      <li>radix sort：从高位开始排序的改法；分解的灵活性；对输入的要求。</li>
      <li>bucket sort：最优运行时间。</li>
    </ul>
  </li>
  <li>选择问题：找最大、最小元；随机化的选择算法；确定性的选择算法。</li>
</ol>

=2013年4月19日=
[[媒体文件:讨论记录-第二学期-2班-第8次.pdf|[课件下载]]]
<ol>
  <li>dynamic set：含义；基本操作。</li>
  <li>linked list。
    <ul>
      <li>支持的操作：search, insert, delete。</li>
      <li>insert/delete的抽象实现。</li>
      <li>基于数组的具体实现：多数组；单数组。</li>
      <li>dynamic set操作的实现。</li>
    </ul>
  </li>
  <li>stack。
    <ul>
      <li>支持的操作：test-empty, push, pop。</li>
      <li>具体实现：基于数组；基于链表。</li>
      <li>dynamic set操作的实现。</li>
    </ul>
  </li>
  <li>queue。
    <ul>
      <li>支持的操作：test-empty, enqueue, dequeue。</li>
      <li>具体实现：基于数组；基于链表。</li>
      <li>dynamic set操作的实现。</li>
    </ul>
  </li>
  <li>rooted tree。
    <ul>
      <li>与linked list的异同。</li>
      <li>left-child, right-sibling representation的抽象实现。</li>
      <li>dynamic set操作的实现。</li>
    </ul>
  </li>
  <li>allocating and freeing objects。
    <ul>
      <li>意义。</li>
      <li>free list的本质：基于linked list实现的stack。</li>
      <li>service several linked lists with a single linked list的优缺点。</li>
    </ul>
  </li>
</ol>

=2013年4月26日=
[[媒体文件:讨论记录-第二学期-2班-第9次.pdf|[课件下载]]]
<ol>
  <li>heap、heapsort、priority queue：各算法的作用、基本原理、正确性证明、运行时间。</li>
  <li>分层抽象。
    <ul>
      <li>priority queue <-- heap <-- array。</li>
      <li>tree <-- binary tree <-- array。</li>
      <li>优缺点：更简单的正确性证明 vs. 更复杂的运行时间分析。</li>
    </ul>
  </li>
  <li>tree的前序、中序、后序遍历。</li>
  <li>其它ADT：union-find；dictionary。</li>
  <li>single-linkage agglomerative clustering。
    <ul>
      <li>最终hierarchy的保存：binary out-tree。</li>
      <li>hierarchy的计算过程：priority queue (+ dictionary)。</li>
      <li>计算过程的监控：union-find。</li>
    </ul>
  </li>
</ol>

=2013年5月3日=
[[媒体文件:讨论记录-第二学期-2班-第10次.pdf|[课件下载]]]
<ol>
  <li>dictionary。
    <ul>
      <li>操作；用途。</li>
      <li>direct-address table：原理；优缺点。</li>
      <li>hash table：原理；优缺点。</li>
    </ul>
  </li>
  <li>collision。
    <ul>
      <li>expected number of items per location。</li>
      <li>expected number of empty locations。</li>
      <li>expected number of collisions。</li>
    </ul>
  </li>
  <li>collision resolution。
    <ul>
      <li>chaining：原理；运行时间；优缺点。</li>
      <li>open addressing：原理；三种实现方式的区别；运行时间；优缺点。</li>
      <li>降低alpha的方式：扩容。</li>
      <li>perfect hashing：原理；运行时间；优缺点。</li>
    </ul>
  </li>
  <li>hash function。
    <ul>
      <li>目标：simple uniform hashing；depends on all the bits of the key；fast。</li>
      <li>应对蓄意构造的坏情况：choose the hash function randomly。</li>
    </ul>
  </li>
</ol>

=2013年5月10日=
[[媒体文件:讨论记录-第二学期-2班-第11次.pdf|[课件下载]]]
<ol>
  <li>binary search trees。
    <ul>
      <li>操作；用途。</li>
      <li>各操作：原理；正确性。</li>
      <li>binary search tree vs. hash table：运行时间；前后继；范围搜索；排序；对输入的要求（hash function vs. total order）；重hash。</li>
    </ul>
  </li>
  <li>red-black trees。
    <ul>
      <li>平衡性及其原因。</li>
      <li>rotation的性质。</li>
      <li>插入和删除的宏观思路。</li>
    </ul>
  </li>
</ol>

=2013年5月17日=
[[媒体文件:讨论记录-第二学期-2班-第12次.pdf|[课件下载]]]
<ol>
  <li>dynamic programming。
    <ul>
      <li>面向的问题：优化。</li>
      <li>适用的问题：有最优子结构。</li>
      <li>有用的问题：子问题重复。</li>
      <li>代价：空间换时间。</li>
    </ul>
  </li>
  <li>dynamic programming的运行时间。
    <ul>
      <li>性能要素：子问题数量；每个子问题中的决策数量。</li>
      <li>计算方法：top-down vs. bottom-up。</li>
    </ul>
  </li>
  <li>问题实例及其四步骤。
    <ul>
      <li>rod cutting。</li>
      <li>matrix-chain multiplication。</li>
      <li>unweighted shortest/longest simple path。</li>
      <li>longest common subsequence。</li>
      <li>optimal binary search trees。</li>
    </ul>
  </li>
</ol>

=2013年5月24日=
[[媒体文件:讨论记录-第二学期-第13次.pdf|[课件下载]]]
<ol>
  <li>greedy algorithms。
    <ul>
      <li>基本原理。</li>
      <li>greedy-choice property和optimal substructure。</li>
      <li>效率高于动态规划：计算的子问题少。</li>
      <li>实例：activity-selection和Huffman codes。</li>
    </ul>
  </li>
  <li>amortized analysis。
    <ul>
      <li>与average-case analysis的异同：per operation vs. per algorithm; worst-case vs. average-case。</li>
      <li>aggregate analysis：按行计算改为按列计算。</li>
      <li>accounting method：在别处分摊代价。</li>
      <li>potential function：全局集中的代价寄存；从accounting method的角度理解potential function。</li>
      <li>实例：stack operations; incrementing a binary counter; table expansion和contraction。</li>
    </ul>
  </li>
</ol>

=2013年5月31日=
[[媒体文件:讨论记录-第二学期-2班-第14次.pdf|[课件下载]]]
<ol>
  <li>union-find的应用。
    <ul>
      <li>connected component。</li>
      <li>how many tables。</li>
      <li>the suspects。</li>
    </ul>
  </li>
  <li>union-find的实现。
    <ul>
      <li>linked-list representation及其改进：weighted-union heuristic。</li>
      <li>disjoint-set forests及其改进：union by rank；path compression。</li>
    </ul>
  </li>
  <li>single-linkage agglomerative clustering的实现：优先队列+并查集+树。</li>
</ol>

=2013年6月7日=
[[媒体文件:讨论记录-第二学期-2班-第15次.pdf|[课件下载]]]
<ol>
  <li>用图来建模问题。</li>
  <li>图的集合表示。
    <ul>
      <li>无向图：函数；multiset。</li>
      <li>有向图：函数；multiset。</li>
    </ul>
  </li>
  <li>图论中的术语。</li>
</ol>

=2013年6月21日=
[[媒体文件:讨论记录-第二学期-2班-第16次.pdf|[课件下载]]]
<ol>
  <li>图的计算机表示。
    <ul>
      <li>方法与优缺点：Two-dimensional array；List of lists；Dictionary of keys；Coordinate list；Yale format。</li>
      <li>结合使用。</li>
    </ul>
  </li>
  <li>图的搜索。
    <ul>
      <li>BFS：三种颜色的含义；BFS-tree的构建。</li>
      <li>DFS：子孙关系的三个充要条件；SCC算法的原理。</li>
    </ul>
  </li>
  <li>最小生成树：Kruskal及其实现；Prim及其实现；拟阵。</li>
</ol>