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

==基本要求==
<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.18--2.22</td>
    <td>[http://114.212.10.6/problem_solving/index.php/%E6%96%87%E4%BB%B6:2014-2-18.pdf 2-1：算法方法]</td>
    <td>
      <ul>
        <li>通过具体示例了解算法设计的基本策略</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>DH第4章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>理解复杂算法背后的简单原理</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>DH第4章练习1、2、8、9、11、12、13、14</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>WS第5章项目16</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>2.25--3.1</td>
    <td>[http://114.212.10.6/problem_solving/index.php/%E6%96%87%E4%BB%B6:2014-02-25.pdf 2-2：算法正确性]</td>
    <td>
      <ul>
        <li>理解并能够区分程序错误与算法错误</li>
        <li>理解算法正确的概念及其证明方法</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>DH第5章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>算法正确性证明与一般数学定理证明的异同</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>DH第5章练习4、6、8、9、10、11、12、13、14</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>WS第6章项目3，你如何确定你的程序算法没有错误</li>
      </ul>
    </td>
  </tr>  
 <tr>
    <td>3.4--3.8</td>
    <td>[http://114.212.10.6/problem_solving/images/f/f0/%E7%AE%97%E6%B3%95%E7%9A%84%E6%95%88%E7%8E%872014-03-04.pdf 2-3：算法的效率]</td>
    <td>
      <ul>
        <li>理解算法的时间复杂性的概念与渐进表示方式</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>DH第6章</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>从无限与有限的角度正确理解算法复杂度</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>DH第6章练习1、2、3、10、11、15、16</li>
      </ul>
    </td>
    <td>
      <ul>
        <li>WS第7章项目3</li>
        <li>WS第7章项目5</li>
      </ul>
    </td>
  </tr>
  <tr>
    <td>3.11--3.15</td>
    <td>[http://114.212.10.6/problem_solving/index.php/%E6%96%87%E4%BB%B6:2014-03-11.pdf 2-4：算法问题与解题的算法]</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.18--3.28</td>
    <td>[http://114.212.10.6/problem_solving/index.php/%E6%96%87%E4%BB%B6:%E7%BB%84%E5%90%88%E4%B8%8E%E8%AE%A1%E6%95%B02014-03-18.pdf 2-5：组合与计数]</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.31--4.11</td>
    <td>[http://114.212.10.6/problem_solving/images/2/29/%E5%88%86%E6%B2%BB%E6%B3%95%E4%B8%8E%E9%80%92%E5%BD%922014-04-01.pdf 2-6：分治法与递归]</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>4.14--4.18</td>
    <td>[http://114.212.10.6/problem_solving/images/0/0b/%E9%80%92%E5%BD%92%E5%8F%8A%E5%85%B6%E6%95%B0%E5%AD%A6%E5%9F%BA%E7%A1%802014-04-15.pdf 2-7：递归及其数学基础]</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>4.21--4.30</td>
    <td>[http://114.212.10.6/problem_solving/images/8/88/%E7%A6%BB%E6%95%A3%E6%A6%82%E7%8E%87%E5%9F%BA%E7%A1%801.pdf 2-8：离散概率基础-1]</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>5.5--5.9</td>
    <td>[http://114.212.10.6/problem_solving/images/1/1f/%E6%A6%82%E7%8E%87%E5%88%86%E6%9E%90%E4%B8%8E%E9%9A%8F%E6%9C%BA%E7%AE%97%E6%B3%952014-05-06.pdf 2-9：概率分析与随机算法]</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>5.13--5.23</td>
    <td>[http://114.212.10.6/problem_solving/images/6/66/SortAndSelection.pdf 2-10：排序与选择]</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>5.26--5.30</td>
    <td>[http://114.212.10.6/problem_solving/index.php/%E6%96%87%E4%BB%B6:2-11%E5%9F%BA%E6%9C%AC%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84.pdf 2-11：基本数据结构]</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>5.6--5.10</td>
    <td>[http://114.212.10.6/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-12：堆与堆排序]</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>5.13--5.17</td>
    <td>[http://114.212.10.6/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-13：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.20--5.24</td>
    <td>[http://114.212.10.6/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-14：搜索树]</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>

</table>