2023级--学期安排 (第三学期)

指定教材

• CH: 程龚: 图论与算法, 2024
• TC: Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009
• TJ: Thomas Judson: Abstract Algebra - Theory and Applications.
• WS: Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008

学习周历

日期	论题	阅读材料	书面作业	周一小班（讲课）	周二大班（OJ）	周四大班（OT）
9.2-9.6	3-1：图的基本概念	CH第1章	CH练习1.1、1.2、1.3、1.4 CH练习1.7、1.8	正常上课	CH练习1.5、1.6 CH练习1.9 CH练习1.10	【学号后3位 % 3 = 0的同学完成】 图在计算机和人工智能研究中有很多应用，例如程序分析中的控制流图、信息检索中的网页链接图、知识表示中的知识图谱等，请调研至少3种应用（其中至多1种来自上述例子），描述应用场景，讨论用图建模的方式，形式化描述问题并概述现有解决方案。
9.9-9.13	3-2：连通和遍历	CH第2章	CH练习2.1、2.2、2.3 CH练习2.8 CH练习2.11、2.12、2.13	正常上课	CH练习2.9 CH练习2.15	【学号后3位 % 3 = 1的同学完成】 在DFS和BFS的基础上，形成了很多扩展的搜索算法，例如词典序BFS、双向搜索、最佳优先搜索等，请调研至少2种扩展搜索算法（其中至多1种来自上述例子），讨论适用场景，结合例子介绍算法的设计与分析，与DFS或BFS比较异同并分析优劣。
9.16-9.20	3-3：圈和遍历	CH第3章	CH练习3.1、3.2、3.3、3.4、3.5、3.6、3.7 CH练习3.10、3.11、3.12、3.13 CH练习3.16、3.17、3.18、3.19 CH练习3.23、3.24	中秋调休，本次课安排在9月14日	中秋放假	【学号后3位 % 3 = 2的同学完成】 请调研教材中未介绍过的至少2种哈密尔顿路或哈密尔顿圈的存在性的必要条件或充分条件，讨论条件的适用场景，并阐述证明过程。
9.23-9.27	3-4：连通度	CH第4章	CH练习4.1 CH练习4.4、4.5、4.6、4.7	正常上课	CH练习3.14 CH练习3.22	【学号后3位 % 3 = 0的同学完成】 请调研并阐述面向点连通度或边连通度的门格尔定理的至少2种证明方法；门格尔定理在图论中有很多应用，请调研至少2种应用，描述应用场景。
9.30-10.4	3-5：匹配	CH第5章	CH练习5.1 CH练习5.5、5.6	正常上课	国庆放假	国庆放假
10.7-10.11	3-6：单源最短路	CH第6.1节 TC第24章	TC练习24.1-2、3、4 TC练习24.2-2 TC练习24.3-2、4、7 TC练习24.5-2、5 TC问题24-2、3	国庆调休，本次课安排在10月12日	CH练习4.2	作业讲解 + OJ讲解
10.14-10.18	3-7：多源最短路	TC第25章	TC练习25.1-4、5、6、9、10 TC练习25.2-2、4、6、8 TC练习25.3-2、3 TC问题25-2	正常上课	CH练习5.2、5.3	【学号后3位 % 3 = 1的同学完成】 花算法有很多优化改进，例如Gabow'76、Micali'80等，请调研至少2种优化改进（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，与花算法比较异同并分析优劣。
10.21-10.25	3-8：最小生成树和赋权欧拉图	CH第6.2、6.3节	CH练习6.3 CH练习6.5	正常上课	CH练习6.1、6.2	【学号后3位 % 3 = 2的同学完成】单源最短路问题有很多并行算法，例如Δ-stepping算法、Radius Stepping算法等，请调研至少2种算法（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，比较异同并分析优劣。
10.28-11.1	3-9：有向图	CH第7.1、7.2、7.3、7.4节	CH练习7.1、7.2 CH练习7.4、7.5	正常上课	请编程实现Floyd-Warshall算法。 请编程实现Johnson算法。	【学号后3位 % 3 = 0的同学完成】 距离索引（Distance Oracle）是一种用于查询精确或近似距离的数据结构，请调研至少1种精确距离索引和1种近似距离索引，讨论适用场景，结合例子介绍索引构造算法和距离查询算法的设计与分析。
11.4-11.8	3-10：流网络和最大流	CH第7.5节	CH练习7.17、7.18、7.19、7.20、7.21、7.22	正常上课	CH练习6.4	【学号后3位 % 3 = 1的同学完成】 最小生成树问题有很多相关问题，例如Steiner tree、k-MST、MBST等，请调研至少2种问题（其中至多1种来自上述例子，欧氏最小生成树问题等仅限制原始问题输入的问题不在调研范围内），讨论适用场景，形式化描述问题并概述现有解决方案。
11.11-11.15	3-11：独立、覆盖和支配	CH第8章	CH练习8.1、8.2 CH练习8.5	正常上课	CH练习7.3 CH练习7.11	作业讲解 + OJ讲解
11.18-11.22	3-12：染色	CH第9章	CH练习9.1、9.2 CH练习9.5、9.6	正常上课	CH练习7.23	【学号后3位 % 3 = 2的同学完成】 除福特-法尔克森算法外，最大流问题还有很多其它算法，例如Edmonds-Karp算法、Dinitz算法、Push-Relabel算法等，请调研至少2种算法（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，与福特-法尔克森算法比较异同并分析优劣。
11.25-11.29	3-13：平面	CH第10章	CH练习10.1、10.2、10.3、10.4	正常上课	CH练习8.3、8.4	【学号后3位 % 3 = 0的同学完成】 在独立、覆盖和支配的基础上，形成了很多扩展的优化问题，例如最小权完美匹配问题（Minimum-Weight Perfect Matching）、最小连通支配集问题等，请调研至少2种问题（其中至多1种来自上述例子，二分图最大匹配问题等仅限制原始问题输入的问题不在调研范围内），讨论适用场景，形式化描述问题，为每种问题结合例子介绍至少1种算法的设计与分析。
12.2-12.6	3-14：群和循环群	TJ第3、4章	TJ第3章练习3、6、7、17、28、36、38、41、48、52 TJ第4章练习1、12、21、24、32	正常上课	CH练习9.3、9.4	【学号后3位 % 3 = 1的同学完成】 除米什拉-格赖斯算法和贪心算法外，边染色和点染色问题还有很多其它算法，请为每种问题调研至少1种精确算法（暴力算法不在调研范围内），结合例子介绍算法的设计与分析。
12.9-12.13	3-15：置换群、陪集和拉格朗日定理	TJ第5、6章	TJ第5章练习3、5、16、27、29 TJ第6章练习11、12、16、21	正常上课	CH练习10.5	【学号后3位 % 3 = 2的同学完成】 除DMP算法外，可平面图的判定问题还有很多其它算法，请调研至少2种算法，结合例子介绍算法的设计与分析，与DMP算法比较异同并分析优劣。
12.16-12.20	3-16：代数编码	TJ第8章	TJ第8章练习6、7、8、9、11、13、18、19、21、22、23	正常上课	Write a computer program to calculate a^x (mod n) by the method of repeated squares. Write a program to implement a (16, 12)-linear code. Your program should be able to encode and decode messages using coset decoding.	作业讲解 + OJ讲解
12.23-12.27	【学号后3位 % 3 = 0的同学完成】 请讲解TJ第9章的主要内容；如有余力，可进一步讲解TJ第10章的主要内容。 【学号后3位 % 3 = 1的同学完成】 请讲解TJ第12.1节的主要内容；如有余力，可进一步讲解TJ第12.2节的主要内容。 【学号后3位 % 3 = 2的同学完成】 请讲解TJ第16.1、16.2节的主要内容；如有余力，可进一步讲解TJ第16.5节的主要内容。	无	无	正常上课	OJ期末考试	复习答疑
寒假自学	群同构、正规子群和因子群、群同态	TJ第9、10、11章