“2023级--学期安排 (第二学期)”的版本间的差异
来自问题求解
（创建页面，内容为“==基本要求== <ul> <li>理解数据抽象，理解并能够应用常用的数据结构。</li> <li>掌握重要算法设计策略以及算法设计与分析...”） |
|||
| （未显示同一用户的1个中间版本） | |||
| 第48行： | 第48行： | ||
</td> | </td> | ||
<td>CS 1.2-1、CS 1.2-5、CS 1.2-6、CS 1.2-15、CS 1.5-4、CS 1.5-12 | <td>CS 1.2-1、CS 1.2-5、CS 1.2-6、CS 1.2-15、CS 1.5-4、CS 1.5-12 | ||
| − | + | 选做：算法计数题 | |
</td> | </td> | ||
<td></td> | <td></td> | ||
| 第261行： | 第261行： | ||
</tr> | </tr> | ||
</table> | </table> | ||
| + | |||
| + | [[媒体文件:问题求解二课程周计划2024春.docx|附件Word]] | ||
2024年2月22日 (四) 10:41的最新版本
基本要求
- 理解数据抽象，理解并能够应用常用的数据结构。
- 掌握重要算法设计策略以及算法设计与分析的基本方法。
- 理解并能够应用支持上述内容的离散数学工具与方法。
注意：程序设计能力要求贯穿于整个课程，不再单列。
指定教材
- CS: Cliff Stein et al.: Discrete Mathematics for Computer Scientists, 1st ed. Addison-Wesley, 2010
- TC: Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009
- WS: Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008
推荐课外读物
- Kenneth H. Rosen: Discrete Mathematics and Its Applications, 7th ed. McGraw-Hill, 2011
学习周历
| 日期 | 论题 | 阅读材料 | 书面作业 | 小班讨论 |
|---|---|---|---|---|
| 2.26-3.3 | 2-1：算法问题与解题的算法 |
|
TC prob.2-1—2-4、TC prob.3-2—3-4 | |
| 3.4-3.10 | 2-2：组合与计数 |
|
CS 1.2-1、CS 1.2-5、CS 1.2-6、CS 1.2-15、CS 1.5-4、CS 1.5-12
选做：算法计数题 |
|
| 3.11-3.17 | 2-3：分治法与递归 |
|
TC 4.1-5、TC 4.3-3、TC 4.4-5、TC 4.5-4、TC Problem 4-1、TC Problem 4-3 (Except f and j)
选做：TC Problem 4-3 (f and j) |
|
| 3.18-3.24 | 2-4：递归及其数学基础 |
|
CS 4.1-16、CS 4.2-11、CS 4.3-9(c)、CS 4.3-18、CS 4.5-8、CS 4.5-10
选做：(Linear Recurrences) 详见页尾附件Word |
|
| 3.25-3.31 | 2-5：离散概率基础 |
|
CS 5.1-10、CS 5.1-12、CS 5.2-4、CS 5.2-10、CS 5.3-2、CS 5.3-12、CS 5.4-10、CS 5.4-15
选做：(The Ballot Problem) In an election, candidate A receives n votes, and candidate B receives m votes where n > m. Assuming that all orderings are equally likely, what is the probability that A is always ahead in the count of votes? |
|
| 4.1-4.7 | 2-6：概率分析与随机算法 |
|
CS 5.6-4、CS 5.6-8、CS 5.7-2、CS 5.7-12、TC 5.2-4、TC 5.2-5、TC 5.3-3、TC 5.3-4、TC Problem 5-2 (e, f, g)
选做：(The Coin Problem) Suppose you have a fair coin. What is the expected number of tosses to get 3 Heads in a row (连续三次正面朝上)? What about n Heads in a row? |
|
| 4.8-4.14 | 2-7：排序 |
|
TC 7.2-2、TC 7.3-2、TC 7.4-2、TC 8.1-4、TC 8.2-4、TC 8.3-4、TC Problem 8-2
选做：TC Problem 7-5 |
|
| 4.15-4.21 | 2-8：选择 |
|
TC 9.1-1、TC 9.3-7 | |
| 4.22-4.28 | 2-9：基本的数据结构 |
|
MA 2.6、TC 10.1-4、TC 10.1-6、TC 10.2-6、TC 10.3-4、TC 10.3-5、TC 10.4-2、TC 10.4-3、TC Problem 10-3
选做：TC 10.1-7 |
|
| 4.29-5.5 | 2-10：堆与堆排序 |
|
TC 6.1-2、TC 6.1-7、TC 6.2-5、TC 6.2-6、TC 6.3-3、TC 6.4-2、TC 6.4-4、TC 6.4-5 (∗)、TC 6.5-5、TC 6.5-9
选做：详见页尾附件Word |
|
| 5.6-5.12 | 2-11：哈希 |
|
CS 5.5-8 (a, b, c)、TC 11.2-3、TC 11.3-3、TC 11.4-3、TC Problem 11-1、TC Problem 11-2
选做：TC 11.2-6 |
|
| 5.13-5.19 | 2-12：搜索树、红黑树 |
|
TC 12.1-5、TC 12.2-9、TC 12.3-5、TC 13.1-5、TC 13.1-7、TC 13.3-1、TC 13.3-5、TC 13.4-1、TC 13.4-7
选做：TC Problem 13-3 |
|
| 5.20-5.26 | 2-13：动态规划 |
|
TC 15.1-1、TC 15.1-3、TC 15.2-2、TC 15.2-4、TC 15.3-3、TC 15.3-5、TC 15.3-6、TC 15.4-3、TC 15.4-5、TC 15.5-1
选做：TC Problem 15-4: Printing neatly |
|
| 5.27-6.2 | 2-14：贪心算法 |
|
TC 16.1-2、TC 16.1-3、TC 16.2-1、TC 16.2-2、TC 16.3-2、TC 16.3-5、TC 16.3-8
选做：TC Problem 16-1 |
|
| 6.3-6.9 | 2-15：用于动态等价关系的数据结构与均摊分析 |
|
TC 17.1-3、 TC 17.2-2、TC 17.4-1、TC 21.1-2、TC 21.1-3、TC 21.2-1、TC 21.2-3、TC 21.2-6、TC 21.3-1、TC 21.3-2、TC 21.3-3
选做：TC Problem 21-1 |
|
| 6.10-6.16 | 2-16：线性规划 |
|
TC 29.1-4、TC 29.1-5、TC 29.2-2、TC 29.2-4、TC 29.2-6、TC 29.3-5、TC 29.4-2、TC 29.2-3、TC 29.4-3、TC Problem 29-1
选做：TC Problem 29-2 |
|
| 暑期自学 | 2-17：矩阵计算 |
|
TC 28.1-2、TC 28.1-3、TC 28.1-6、TC 28.1-7、TC 28.2-1、TC 28.2-2、TC 28.2-3、TC 28.3-1、TC 28.3-3
选做：TC Problem 28-1 |
|
| 暑期自学 | 2-18：串匹配 |
|
TC Ex.32.1-: 2, 3, 4、TC Ex.32.2-: 1, 2, 3, 4、TC Ex.32.3-: 2, 3, 5 |
