查看“2012级--学期安排 (第二学期)”的源代码

==基本要求==
<ul>
  <li>理解数据抽象，理解并能够应用常用的数据结构。</li>
  <li>掌握重要算法设计策略以及算法设计与分析的基本方法。</li>
  <li>理解并能够应用支持上述内容的离散数学工具与方法。</li>
</ul>
注意：程序设计能力要求贯穿于整个课程，不再单列。

==指定教材==
<ul>
  <li>'''CS''': Cliff Stein et al.: Discrete Mathematics for Computer Scientists, 1st ed. Addison-Wesley, 2010</li>
  <li>'''DW''': Douglas West: Introduction to Graph Theory, 2nd ed. Pearson, 2000</li>
  <li>'''SB''': Sara Baase et al.: Computer Algorithms - Introduction to Design and Analysis, 3rd ed. Addison-Wesley, 1999 (第2章：抽象数据类型)</li>
  <li>'''TC''': Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009</li>
  <li>'''WS''': Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008</li>
</ul>

==推荐课外读物==
<ul>
  <li>Kenneth H. Rosen: Discrete Mathematics and Its Applications, 7th ed. McGraw-Hill, 2011</li>
</ul>

==学习周历==
<table border="1px">
  <tr>
    <th>日期</th>
    <th>论题</th>
    <th>学习目的</th>
    <th>阅读材料</th>
    <th>引导要点</th>
    <th>书面作业</th>
    <th>编程任务</th>
  </tr>
  <tr>
    <td>2.25--3.1</td>
    <td>[http://cslab.nju.edu.cn/problem_solving/index.php/%E6%96%87%E4%BB%B6:%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2013-02-26.pdf 2-1：算法问题与解题的算法]</td>
    <td>
      <ul>
        <li>理解计算机算法的相关概念</li>
        <li>掌握算法复杂性的基本度量方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第1、2、3章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>算法设计与算法分析是计算机问题求解不可互却的两个方面</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第2章问题1、2、3、4</li>
        <li>TC第3章问题2、3、4</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>WS第9章项目5</li>
        <li>WS第9章项目6</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>3.4--3.8</td>
    <td>[http://cslab.nju.edu.cn/problem_solving/index.php/%E6%96%87%E4%BB%B6:%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2013-03-05.pdf 2-2：组合与计数]</td>
    <td>
      <ul>
        <li>掌握在算法分析中常用的计数原理与方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CS第1章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>为什么算法分析中需要计数</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CS第1.1节问题9、13</li>
        <li>CS第1.2节问题15</li>
        <li>CS第1.3节问题6、9、14</li>
        <li>CS第1.5节问题8、10、15</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>任给k个元素的字母表；编程输出所有可能的组合串，且每个串中没有重复字母。如果可以任意某一个或多个字母可重复的次数，修改你的算法。复杂性是否会增加？</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>3.11--3.15</td>
    <td>[http://cslab.nju.edu.cn/problem_solving/index.php/%E6%96%87%E4%BB%B6:%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2013-03-12.pdf 2-3：分治法与递归]</td>
    <td>
      <ul>
        <li>掌握利用分治法设计算法的思路</li>
        <li>深入理解递归在算法设计中的作用</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第4章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>策略在计算机算法设计中的意义</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第4.1节练习5</li>
        <li>TC第4.3节练习3、7</li>
        <li>TC第4.4节练习2、8</li>
        <li>TC第4.5节练习4</li>
        <li>TC第4章问题1、3、4</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>Strassen算法</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>3.18--3.22</td>
    <td>[http://cslab.nju.edu.cn/problem_solving/index.php/%E6%96%87%E4%BB%B6:%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2013-03-19.pdf 2-4：递归及其数学基础]</td>
    <td>
      <ul>
        <li>进一步理解递归的数学基础</li>
        <li>更深入地掌握递归算法的分析方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CS第4章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何解递归式</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CS第4.1节问题16、17</li>
        <li>CS第4.2节问题8、11、17</li>
        <li>CS第4.3节问题9、13、16</li>
        <li>CS第4.4节问题1、4、6</li>
        <li>CS第4.5节问题8、9、10</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>WS第10章项目10</li>
        <li>WS第10章项目13</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>3.25--3.29</td>
    <td>[http://cslab.nju.edu.cn/problem_solving/index.php/%E6%96%87%E4%BB%B6:%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2013-03-26.pdf 2-5：离散概率基础]</td>
    <td>
      <ul>
        <li>理解离散概率的基本概念</li>
        <li>掌握简单离散概率计算的基本方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CS第5章第1、2、3、4节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>正确理解期望值，由此建立算法分析中期望效率理解的基础</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CS第5.1节问题6、10、11、12、13</li>
        <li>CS第5.2节问题2、9、10、14、15</li>
        <li>CS第5.3节问题3、4、8、11、12、13</li>
        <li>CS第5.4节问题5、6、8、10、17、20、21</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>利用一个现成的随机数生成函数，模拟3个色子的试验；加大试验次数，比较试验结果与理论概率分布</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>4.1--4.5</td>
    <td>[http://cslab.nju.edu.cn/problem_solving/index.php/%E6%96%87%E4%BB%B6:%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2013-04-02.pdf 2-6：概率分析与随机算法]</td>
    <td>
      <ul>
        <li>理解概率在算法设计中的作用</li>
        <li>掌握基于概率的算法分析的基本方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第5章</li>
        <li>CS第5章第6、7节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>随机变量在算法分析中的意义</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CS第5.6节问题4、8</li>
        <li>CS第5.7节问题1、2、4、6、12、16、18</li>
        <li>TC第5.2节练习1、2、4</li>
        <li>TC第5.3节练习1、2、3、4</li>
        <li>TC第5章问题2</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>随机排列生成算法</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>4.8--4.12</td>
    <td>2-7：排序与选择</td>
    <td>
      <ul>
        <li>深入理解快速排序算法的设计思想与分析方法</li>
        <li>通过排序理解问题复杂度的下限，并探索一些线性排序算法</li>
        <li>掌握以中位数为代表的统计算法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第7、8、9章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何证明问题复杂度的下限</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第7.1节练习2</li>
        <li>TC第7.2节练习4</li>
        <li>TC第7.3节练习2</li>
        <li>TC第7.4节练习2</li>
        <li>TC第7章问题4、5</li>
        <li>TC第8.1节练习3、4</li>
        <li>TC第8.2节练习4</li>
        <li>TC第8.3节练习4</li>
        <li>TC第8.4节练习2</li>
        <li>TC第8章问题2</li>
        <li>TC第9.1节练习1</li>
        <li>TC第9.3节练习5、7</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>快速排序</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>4.15--4.19</td>
    <td>[http://cslab.nju.edu.cn/problem_solving/index.php/%E6%96%87%E4%BB%B6:%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2013-04-16.pdf 2-8：基本数据结构]</td>
    <td>
      <ul>
        <li>掌握堆栈、队列、链表、指针、根树的概念、实现以及在算法设计中的应用</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第10章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>数据结构的算法支撑与实现效率的平衡</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第10.1节练习4、5、6</li>
        <li>TC第10.2节练习1、2、3、6</li>
        <li>TC第10.3节练习4、5</li>
        <li>TC第10.4节练习2、3、4</li>
        <li>TC第10章问题3</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>实现根树</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>4.22--4.26</td>
    <td>[http://cslab.nju.edu.cn/problem_solving/index.php/%E6%96%87%E4%BB%B6:%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2013-04-23.pdf 2-9：堆与堆排序]</td>
    <td>
      <ul>
        <li>理解并掌握堆的结构、实现以及算法应用</li>
        <li>通过堆的应用与实现理解抽象数据类型的基本概念以及分层抽象的思想</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第6章</li>
        <li>SB第2章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>从数据结构到抽象数据类型的思想发展</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第6.1节练习2、4、7</li>
        <li>TC第6.2节练习2、5、6</li>
        <li>TC第6.3节练习3</li>
        <li>TC第6.4节练习2、4</li>
        <li>TC第6.5节练习5、7、9</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>堆排序</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>4.29--5.3</td>
    <td>[http://cslab.nju.edu.cn/problem_solving/index.php/%E6%96%87%E4%BB%B6:%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2013-04-30.pdf 2-10：Hashing方法]</td>
    <td>
      <ul>
        <li>掌握Hashing方法的原理、处理冲突的方法以及分析方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第11章</li>
        <li>CS第5章第5节</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>Hashing方法中的冲突处理</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>CS第5.5节问题8、11、14</li>
        <li>TC第11.2节练习3、5、6</li>
        <li>TC第11.3节练习3、4</li>
        <li>TC第11.4节练习2、3</li>
        <li>TC第11章问题1、2</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>用至少两个不同的Hash函数实现hashing，并比较冲突情况</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>5.6--5.10</td>
    <td>[http://cslab.nju.edu.cn/problem_solving/index.php/%E6%96%87%E4%BB%B6:%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2013-05-06.pdf 2-11：搜索树]</td>
    <td>
      <ul>
        <li>掌握利用树结构存储与搜索数据的方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第12、13章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>树的平衡与搜索效率的关系</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第12.1节练习2、5</li>
        <li>TC第12.2节练习5、8、9</li>
        <li>TC第12.3节练习5</li>
        <li>TC第12章问题1</li>
        <li>TC第13.1节练习5、6、7</li>
        <li>TC第13.2节练习2</li>
        <li>TC第13.3节练习1、5</li>
        <li>TC第13.4节练习1、2、7</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>实现红黑树，并比较与简单二分搜索树的执行效率</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>5.13--5.17</td>
    <td>[http://cslab.nju.edu.cn/problem_solving/index.php/%E6%96%87%E4%BB%B6:%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2013-05-14.pdf 2-12：动态规划]</td>
    <td>
      <ul>
        <li>通过实例掌握动态规划的基本思想与算法设计方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第15章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>以空间换时间的关键是存储效率</li>
        <li>动态规划与指数时间的有效降低</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第15.1节练习1、3</li>
        <li>TC第15.2节练习2、4</li>
        <li>TC第15.3节练习3、5、6</li>
        <li>TC第15.4节练习3、5</li>
        <li>TC第15.5节练习1</li>
        <li>TC第15章问题4</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>实现矩阵连乘</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>5.20--5.24</td>
    <td>[http://cslab.nju.edu.cn/problem_solving/index.php/%E6%96%87%E4%BB%B6:%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2013-05-21.pdf 2-13：贪心算法]</td>
    <td>
      <ul>
        <li>掌握利用贪心策略设计算法的思路与方法</li>
        <li>掌握用分摊进行算法分析的思想与方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第16章第1、2、3节</li>
        <li>TC第17章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>贪心算法的正确性证明</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第16.1节练习2、3</li>
        <li>TC第16.2节练习1、2</li>
        <li>TC第16.3节练习2、5、8</li>
        <li>TC第16章问题1</li>
        <li>TC第17.1节练习3</li>
        <li>TC第17.2节练习2</li>
        <li>TC第17.4节练习1</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>Hoffman码</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>5.27--5.31</td>
    <td>[http://cslab.nju.edu.cn/problem_solving/index.php/%E6%96%87%E4%BB%B6:%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2013-05-28.pdf 2-14：用于动态等价关系的数据结构]</td>
    <td>
      <ul>
        <li>理解动态等价关系的概念以及在问题求解中的意义</li>
        <li>掌握以union-find为代表的相应数据结构</li>
        <li>进一步理解抽象数据类型的意义</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第21章</li>
        <li>SB第2章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>算法分析的困难性</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第21.1节练习2、3</li>
        <li>TC第21.2节练习1、3、6</li>
        <li>TC第21.3节练习1、2、3</li>
        <li>TC第21章问题1</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>编一个程序自动生成迷宫</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>6.3--6.7</td>
    <td>[http://cslab.nju.edu.cn/problem_solving/index.php/%E6%96%87%E4%BB%B6:%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2013-06-04.pdf 2-15：图的基本概念]</td>
    <td>
      <ul>
        <li>掌握图的基本概念以及图论的基本证明方式</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>DW第1章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>图论应用的广泛性以及图论证明方法的独特性</li>
        <li>理解图与关系的联系</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>DW第1.1节练习4、5、10、14、16、31</li>
        <li>DW第1.2节练习5、7、11、17、18、20、38、40</li>
        <li>DW第1.3节练习1、10、14、15、18、61</li>
        <li>DW第1.4节练习1、5、8、10、11、21</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>WS第11章项目3</li>
        <li>WS第11章项目5</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>6.10--6.14</td>
    <td>2-16：图的计算机表示以及遍历</td>
    <td>
      <ul>
        <li>掌握在计算机中表示图的方式</li>
        <li>掌握图的深度优先与广度优先遍历方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第22章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>图表示中形式与效率的关系</li>
        <li>不同遍历方法的算法意义</li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
    <td>
      <ul>
        <li>实现深度与广度遍历</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>6.17--6.21</td>
    <td>2-17：树</td>
    <td>
      <ul>
        <li>理解树的基本数学性质</li>
        <li>掌握用加权树建立数学模型的方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>DW第2章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>树的数学性质在计算机问题求解中的意义</li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
    <td>
      <ul>
        <li>WS第14章项目10</li>
        <li>WS第14章项目11</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>6.24--6.28</td>
    <td>2-18：最小生成树算法</td>
    <td>
      <ul>
        <li>理解贪心算法策略在最小生成树问题上的应用</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>TC第23章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>如何评价同一问题的不同算法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li></li>
      </ul>
    </td>
    <td>
      <ul>
        <li>Prim和Kruskal算法</li>
      </ul>
    </td>
  </tr>
</table>