课程简介
Course Introduction
本课程是继《数据结构》和《算法设计与分析》后的一门算法设计和编程实践的课程，旨在引导学生理论联系实际，利用数据结构和算法知识去尝试解决实际问题，进一步提升其算法设计与软件编程技能，从而增强其解决复杂工程问题的能力。本课程分四个阶段:第一阶段是简单实际问题的求解，涉及到基本数据结构和算法的实现和简单应用（在线编程实训）；第二阶段是较复杂实际问题的求解，涉及到问题分析、模型建立、算法设计及有效实现（在线编程实训）；第三阶段考核学生的基本数据结构和算法的有效实现和应用技能（在线编程考核）；第四个阶是探究中等难度实际应用问题的求解，以小组为单位让学生利用数据结构和算法知识，通过分析与建模、算法设计与实现去尝试解决较复杂的工程实践问题（在线编程实践，项目合作和展示）。
本课程基于历届CCF CSP认证真题实训和PTA平台的编程实践开展教学，以能力培养为导向，着力培养学生问题分析、算法设计与编程实践能力，以增强其解决实际问题的能力。 中国计算机学会(CCF)的计算机软件能力认证(简称CCF CSP认证)目标与本课程目标基本一致。CSP认证考试内容覆盖大学计算机专业学习的程序设计、数据结构及算法，以及相关数学基础知识。CCF在中国计算机领域学术方面具有领军地位使得CSP认证具有权威、公正、客观等特性，已经得到业界广泛认可。CCF CSP认证成绩是很多知名IT公司优先招聘软件开发岗位条件之一。全国一些985、211高校已将CSP认证成绩纳入计算机专业的教学计划，作为计算机专业课程的上机成绩，甚至作为毕业要求之一；一些高校将CSP认证成绩作为研究生机试复试成绩，用于选拔优秀学生。PTA (https://pintia.cn)是浙江大学国家级程序设计系列课程教学团队与网易公司、杭州百腾教育科技有限公司合作推出面向高校和社会的程序自动评测、开放式实践教学辅助平台，是一个优秀程序设计类课程实践训练平台，已有许多大学选择该平台实施程序设计类课程实践环节。
本课程的第一阶段和第二阶段依托CCF CSP官网(https://www.cspro.org/)上模拟考试模块(http://118.190.20.162/)进行算法与编程实训，第三阶段和第四阶段依托PTA平台进行算法与编程实践。对四个阶段分别评分后综合可得本课程的最终考核评分，四个阶段评分占比分别为25%,25%,20%,30%。
本课程中各种算法设计思想都是人们日常生活中解决问题的方法和技术的提炼，含有丰富的哲学思想。可以充分挖掘各种技术的思想内涵，适时地对学生进行思政教育。同时结合算法与编程实训和解决复杂工程问题的实践体验，让学生领悟和感受优化布局、节省资源意识和意义，以及勇于创新、追求卓越的精神。
教学大纲
Teaching Syllabus
《数据结构与算法课程项目》课程教学大纲
一、课程信息
课程名称 | （中文）数据结构与算法课程项目 | ||||||
（英文）Projects for Data Structures and Algorithms | |||||||
课程编码 | 21H24120 | 课程性质 | ■必修 £选修 | ||||
课程类型 | £通识教育 £大类教育 ■专业教育 £师范教育 | ||||||
所属模块（通识选修课填写，限选1项） | £创新创业 £艺术修养 £文化传承 £社会研究 £科学思维 £多元文化 £道德推演 | ||||||
适用专业 | 计算机类各本科专业 | ||||||
开课部门 | 计算机学院 | 课程负责人 | 陈卫东 | ||||
学时学分 | 学分:1 | 总学时:32 | 理论:0 | 实验:0 | 实践:32 | ||
授课语言 | 中文 | ||||||
先修课程 | 程序设计基础、离散数学、数据结构、算法设计与分析 | ||||||
二、课程简介
本课程是继《数据结构》和《算法设计与分析》后的一门算法设计和编程实践的课程，旨在引导学生理论联系实际，利用数据结构和算法知识去尝试解决实际问题，进一步提升其算法设计与软件编程技能，从而增强其解决复杂工程问题的能力。本课程分四个阶段:第一阶段是简单实际问题的求解，涉及到基本数据结构和算法的实现和简单应用（在线编程实训）；第二阶段是较复杂实际问题的求解，涉及到问题分析、模型建立、算法设计及有效实现（在线编程实训）；第三阶段考核学生的基本数据结构和算法的有效实现和应用技能（在线编程考核）；第四个阶是探究中等难度实际应用问题的求解，以小组为单位让学生利用数据结构和算法知识，通过分析与建模、算法设计与实现去尝试解决较复杂的工程实践问题（在线编程实践，项目合作和展示）。 本课程基于历届CCF CSP认证真题实训和PTA平台的编程实践开展教学，以能力培养为导向，着力培养学生问题分析、算法设计与编程实践能力，以增强其解决实际问题的能力。 中国计算机学会(CCF)的计算机软件能力认证(简称CCF CSP认证)目标与本课程目标基本一致。CSP认证考试内容覆盖大学计算机专业学习的程序设计、数据结构及算法，以及相关数学基础知识。CCF在中国计算机领域学术方面具有领军地位使得CSP认证具有权威、公正、客观等特性，已经得到业界广泛认可。CCF CSP认证成绩是很多知名IT公司优先招聘软件开发岗位条件之一。全国一些985、211高校已将CSP认证成绩纳入计算机专业的教学计划，作为计算机专业课程的上机成绩，甚至作为毕业要求之一；一些高校将CSP认证成绩作为研究生机试复试成绩，用于选拔优秀学生。PTA (https://pintia.cn)是浙江大学国家级程序设计系列课程教学团队与网易公司、杭州百腾教育科技有限公司合作推出面向高校和社会的程序自动评测、开放式实践教学辅助平台，是一个优秀程序设计类课程实践训练平台，已有许多大学选择该平台实施程序设计类课程实践环节。 本课程的第一阶段和第二阶段依托CCF CSP官网(https://www.cspro.org/)上模拟考试模块(http://118.190.20.162/)进行算法与编程实训，第三阶段和第四阶段依托PTA平台进行算法与编程实践。对四个阶段分别评分后综合可得本课程的最终考核评分，四个阶段评分占比分别为25%,25%,20%,30%。 本课程中各种算法设计思想都是人们日常生活中解决问题的方法和技术的提炼，含有丰富的哲学思想。可以充分挖掘各种技术的思想内涵，适时地对学生进行思政教育。同时结合算法与编程实训和解决复杂工程问题的实践体验，让学生领悟和感受优化布局、节省资源意识和意义，以及勇于创新、追求卓越的精神。 |
三、课程目标
LO1. 通过解决简单实际问题的编程实践，培养学生熟练使用各种数据结构有效实现基本算法的技能，从而夯实数据结构和算法课程的基础理论知识。 LO2. 培养学生探求解决较复杂实际问题的能力，即对问题进行分析、建模、算法设计及编程实现的能力。 LO3. 通过解决复杂工程问题的编程实践，培养学生使用计算思维来分析问题和解决问题的能力，以及团队协作精神。 |
四、课程目标与毕业要求的对应关系
课程目标 | 毕业要求 | 毕业要求支撑指标点 | 对应程度 |
LO2 | 2 问题分析:能够应用数学、自然科学和工程科学的基本原理，识别、表达、并通过文献研究分析计算机领域的复杂工程问题，以获得有效结论。 | 2.2能够基于数学、自然科学和工程数学的基本原理和数学模型，通过文献研究分析工程问题特性。 | M |
LO1 LO2 | 2 问题分析:能够应用数学、自然科学和工程科学的基本原理，识别、表达、并通过文献研究分析计算机领域的复杂工程问题，以获得有效结论。 | 2.3 能认识到计算机领域复杂工程问题的多种影响因素以及复杂工程问题的多种解决方案，证实解决方案的合理性并得到有效结论。 | H |
LO2 LO3 | 3 设计/开发解决方案:设计/ 开发解决方案:能够设计计算机领域的复杂工程问题的解决方案，设计满足特定需求的系统、子系统或算法流程，并能够在设计环节中体现创新意识，考虑社会、健康、安全、法律、文化以及环境等因素。 | 3.1能够按用户需求和复杂工程需求，确定计算机系统、单元（组件）与过程的设计目标。 | H |
LO1 LO2 LO3 | 5 使用现代工具:能够针对计算机领域的复杂工程问题，开发、选择与使用恰当的技术、资源、现代工程工具和信息技术工具，包括对计算机领域的复杂工程问题的预测与模拟，并能够理解其局限性。 | 5.3根据复杂工程问题中的各种制约条件，能够选用或开发满足特定需求的现代工具，模拟和预测各种复杂场境，并能够分析其局限性。 | H |
五、教学内容、要求及进度安排
单元一:数据结构与算法的基础实验 | 学时:8 | 支撑课程目标:LO1,LO2 | |
主要内容 | 1.在CCF CSP官网(https://www.cspro.org/)的模拟考试模块(http://118.190.20.162/)进行编程实训，要求在规定时间内完成最近3次CSP认证真题中每套试题的前3题的编程实现。前3题主要是通过解决简单实际问题的编程实践，训练熟练使用各种数据结构实现基本算法的技能。 2. 每位同学独立完成，完成后写出解题报告，包括问题分析过程、基本算法思路及实现途径。 | ||
学习目标 | 1. 训练基本数据处理能力，包括数组上进行递推、大小比较、计数、排序等。 2. 理解并熟练编程实现与基本数据结构相关的基础算法，包括递归、排序、查找、字符串简单处理等。 3. 训练基于STL的复杂字符串处理、日期处理、进制处理、递推、排序、查找等技能，并具备问题抽象和建模的初步能力，能用所学方法解决实际问题。 | ||
学生课前阅读材料与其他准备 | 1. 参考书目: [1]殷人昆编著. 数据结构(C语言版)(第2版). 北京:清华大学出版社,2017 [2]M.H.Alsuwaiyel著,吴伟昶,方世昌等译. 算法设计技巧与分析. 北京:电子工业出版社,2010 [3]苏小红等编. 程序设计实践教程(C语言版),北京: 机械工业出版社,2021 [4]胡凡,曾磊主编.算法笔记.北京:机械工业出版社,2016 [5]Thomas H.Cormen等著, 殷建平等译.算法导论(原书第3版).北京:机械工业出版社,2012 2. 思考问题: [1] 使用STL 相对于自己写程序处理字符串有何优势? [2] 基本算法的多种实现时空效率有何差异? 3. 其他课前准备:在CCF CSP官网注册，在学者网注册并加入课程组，在PTA平台注册并加入课程组。 | ||
教学方式 | 1. 实训教学: 一周内在CSP官网上在线编程解决试题中对应的简单实际问题，并写出解题报告，包括解题分析过程、基本算法思路及实现途径等。 2. 思政教育: 算法运行时间与算法空间开销一个主要区别是时间不可重复使用，空间可重复使用。引导学生感悟时间的宝贵，逝去的青春不再来，要珍惜现在读书学习的好时光。 | ||
课后作业 | 一周内在CSP官网上通过在线编程解决试题中对应的简单实际问题，并写出解题的书面报告上传到学者网课程作业中。 | ||
单元二:数据结构与算法的实际应用 | 学时:10 | 支撑课程目标:LO2,LO3 | |
主要内容 | 1. 在CCF CSP官网(https://www.cspro.org/)的模拟考试模块(http://118.190.20.162/)进行编程实训，要求在规定时间内完成最近3次CSP认证真题中每套试题的最后2题的编程实现。最后2题主要是通过对较复杂实际问题的求解，训练问题分析、建模、算法设计及其实现的能力。 2. 每位同学独立完成，完成后写出解题报告，包括解题分析过程、基本算法思路及实现途径等。 | ||
学习目标 | 1. 熟悉经典算法，包括并查集、最短路径、强连通分支、最小生成树、欧拉序列、动态规划、贪心算法、深度优先搜索、广度优先搜索、回溯剪枝等；能够分析算法的时间复杂度、空间复杂度和算法稳定性；熟练理解并使用STL来优化算法的时间复杂度。 2. 熟练使用高级、复杂数据结构，包括后缀数组、树状数组、线段树、静态KDTree等；能够灵活利用经典算法思想解决较复杂实际问题，包括如:剪枝、分治、状态压缩动态规划、快速矩阵幂、计算几何、图论高级应用（包括最大流、最小费用流）等；能够解决复杂的模拟问题，编写并调试代码量较大的程序；培养缜密的科学思维和计算思维。 | ||
学生课前阅读材料与其他准备 | 1. 参考书目: [1]殷人昆编著. 数据结构(C语言版)(第2版). 北京:清华大学出版社,2017 [2]M.H.Alsuwaiyel著,吴伟昶,方世昌等译. 算法设计技巧与分析. 北京:电子工业出版社,2010 [3]苏小红等编. 程序设计实践教程(C语言版),北京: 机械工业出版社,2021 [4]胡凡,曾磊主编.算法笔记.北京:机械工业出版社,2016 [5]Thomas H.Cormen等著, 殷建平等译.算法导论(原书第3版).北京:机械工业出版社,2012 2. 思考问题: [1] 如何实现图的基本算法(包括图的遍历、最小成生数、最短路径等)? [2] 如何解决复杂的模拟问题? 3. 其他课前准备:在CCF CSP官网注册，在学者网注册并加入课程组，在PTA平台注册并加入课程组。 | ||
教学方式 | 1. 实训教学: 一周内在CSP官网上在线编程解决试题中对应的较复杂实际问题，完成后写出解题报告，包括解题分析过程、基本算法思路及实现途径等。 2. 思政教育: 通过编程实训，让学生感悟到解决问题有多种算法且同一算法的不同实现往往有不同的时空复杂度；算法设计与分析目的是为了用较少的资源解决问题。由此增强学生节约资源、提高效率意识。 | ||
课后作业 | 一周内在CSP官网上通过在线编程解决试题中对应较复杂的实际问题，完成后写出解题报告并上传到学者网课程作业中。 | ||
单元三:数据结构与算法的编程测试 | 学时:4 | 支撑课程目标:LO1,LO2 LO3 | |
主要内容 | 1. 在历年CSP认证真题中随机抽取5道试题移植到PTA平台，其中3道题是关于数据结构和算法的基本编程题，2道是关于用数据结构和算法知识编程解决较复杂的实际问题。试题结构与CSP认证真题相仿，每题分值也是100分，共计500分。 2. 在PTA系统实时在线考核（4学时），学生独立完成。 | ||
学习目标 | 1. 熟悉各种数据结构、经典算法的基本思路及其效实现途径。 2. 熟练使用各种数据结构和经典算法解决简单实际问题。 2. 能够灵活利用各种算法思想解决较复杂的实际问题。 | ||
学生课前阅读材料与其他准备 | 1. 参考书目: [1]殷人昆编著. 数据结构(C语言版)(第2版). 北京:清华大学出版社,2017 [2]M.H.Alsuwaiyel著,吴伟昶,方世昌等译. 算法设计技巧与分析. 北京:电子工业出版社,2010 [3]苏小红等编. 程序设计实践教程(C语言版),北京: 机械工业出版社,2021 [4]胡凡,曾磊主编.算法笔记.北京:机械工业出版社,2016 [5]Thomas H.Cormen等著, 殷建平等译.算法导论(原书第3版).北京:机械工业出版社,2012 2. 思考问题:无 3. 其他课前准备:在PTA平台注册并加入课程组。 | ||
教学方式 | 1. 在线编程实践考核:4学时内在PTA平台上在线编程解决试题中对应实际问题。 2. 思政教育:诚信考试，独立思考完成。 | ||
课后作业 | 查找资料了解如何编写程序来识别处理图像中数字串（比如图书ISBN中识别出数字串）。注意:不能用现有的工具软件。 | ||
单元四:数据结构与算法的工程实践 | 学时:10 | 支撑课程目标:LO1,LO2,LO3 | |
主要内容 | 1. 给出一个较复杂的实际应用问题（开放类型问题），比如识别ISBN图片中的数字串，文档的自动摘要等。引导学生通过分析将该复杂问题的求解过程分解为若干模块任务来解决，这些模块任务是简单的，能够用基本数据结构和算法知识来编程求解。分析模块任务之间的逻辑关系，画出任务关系图，并通过拓扑排序得到解决任务的次序。 2. 每一个模块任务在PTA上对应设置一道编程题目，要求学生在给定的时间内独立在线编程解决。 3. 每3位同学一组，每组同学讨论每个模块任务的最佳算法及实现途径，探讨如何集成这些模块的求解算法来得到解决原问题的一个小型应用软件。要求展示每一小组的软件及应用效果。 | ||
学习目标 | 1. 培养学生探求解决较复杂实际问题的能力，即对问题进行分析、建模、算法设计及编程实现的能力。 2. 锻炼学生的程序设计与实现能力、对项目整体把控能力，培养学生的计算思维和团队协作精神。 | ||
学生课前阅读材料与其他准备 | 1. 参考书目: [1]殷人昆编著. 数据结构(C语言版)(第2版). 北京:清华大学出版社,2017 [2]M.H.Alsuwaiyel著,吴伟昶,方世昌等译. 算法设计技巧与分析. 北京:电子工业出版社,2010 [3]苏小红等编. 程序设计实践教程(C语言版),北京: 机械工业出版社,2021 [4]胡凡,曾磊主编.算法笔记.北京:机械工业出版社,2016 [5]Thomas H.Cormen等著, 殷建平等译.算法导论(原书第3版).北京:机械工业出版社,2012 2. 思考问题: 通过小组完成项目的编程实践，如何理解计算思维和团队协作精神? 3.其他课前准备:在PTA平台注册并加入课程组。 | ||
教学方式 | 1. 教师讲解: 针对较复杂实际问题的编程求解，让学生清楚完成整个项目的基本思路。 2. 学生实践: 通过小组合作方式，让每位学生清楚项目的整体思路，以及如何协作完成项目、分工撰写项目报告和制作项目答辩PPT。最终项目的所有工作分工合作完成。 3. 思政教育: 通过小组合作方式完成项目，让学生感悟到分工合作才能挑战复杂问题。 | ||
课后作业 | 根据各小组展示和汇报情况，完善小组的展示报告，并上传到学者网课程作业中。 | ||
六、考核方式
考核评价方式 | 考核要求 | 成绩比例(%) | 课程目标比例(%) | |
编程实训 (单元一) | 编程实训的成绩评分标准(见附表1) | 25 | LO1 | 50 |
LO2 | 50 | |||
编程实训 (单元二) | 编程实训的成绩评分标准(见附表1) | 25 | LO2 | 50 |
LO3 | 50 | |||
编程考核 (单元三) | 编程考核的成绩评分标准(见附表2) | 20 | LO1 | 30 |
LO2 | 40 | |||
LO3 | 30 | |||
编程实践 (单元四) | 编程实践的成绩评分标准(见附表3) | 30 | LO1 | 20 |
LO2 | 40 | |||
LO3 | 40 | |||
七、教材、参考文献与其他教学资源
1. 参考书目: [1]殷人昆编著. 数据结构(C语言版)(第2版). 北京:清华大学出版社,2017 [2]M.H.Alsuwaiyel著,吴伟昶,方世昌等译. 算法设计技巧与分析. 北京:电子工业出版社,2010 [3]苏小红等编. 程序设计实践教程(C语言版),北京: 机械工业出版社,2021 [4]胡凡,曾磊主编.算法笔记.北京:机械工业出版社,2016 [5]Thomas H.Cormen等著, 殷建平等译.算法导论(原书第3版).北京:机械工业出版社,2012 2. 课程网址（相关教学资源网址）: https://www.scholat.com/course/scnualgorithms
|
八、备注
【附表1】编程实训的成绩评分标准（注:任务包括编程题目和解题报告）
80-100 分 | 60-79分 | 40-59分 | 0-39分 | 得分 | |
进度及任务完成进度 (权重0.4) | 按时提交且任务完成进度80%以上 | 按时提交且任务完成进度60%以上 | 按时提交且任务完成进度40%以上 | 补交完成 | |
掌握程度 (权重0.4) | 掌握60%以上 | 掌握40%以上 | 掌握40%以下 | ||
创新性 (权重0.2) | 提出不同解决办法 | 只有一种解决办法 | 能提出不同办法，但可靠性不足 | 不能提出有效解决办法 | |
总分 | |||||
【附表2】编程考核的成绩评分标准
在线自动评测,测试成绩得分为该环节得分。
【附表3】编程实践的成绩评分标准
80-100 分 | 60-79分 | 40-59分 | 0-39分 | 得分 | |
完成进度 (权重0.6) | 提前提交 | 按时提交 | 延时提交 | 补交完成 | |
展示效果 (权重0.2) | 程序能正常运行，在80%以上测试用例上运行结果正确 | 程序能正常运行，在60%以上测试用例上运行结果正确 | 程序能正常运行，在40%以上测试用例上运行结果 | 程序未能运行，或在40%以下测试用例上运行结果不正确 | |
项目报告 (权重0.2)
| 完整且有深入细化分析和描述 | 完整且但深入细化分析和描述不够 | 较为完整、深入细化分析和描述不够 | 不完整、缺乏细节分析和描述 | |
总分 | |||||
