基于团队合作的教学方法改革

基于团队合作的教学方法改革——“高级数据结构与算法”课程

何钦铭　陈　越
计算机科学与技术学院

一、课程简介

1.课程类别

大类课程

2.学科类别

工学—计算机科学与技术

3.课程目标和教学内容

（1）课程目标:“高级数据结构与算法”课程是衔接“数据结构基础”的后续课程，重点培养学生掌握涉及动态查找、高级堆的复杂数据结构的设计方法以及运用典型算法设计思想进行算法设计的方法。

（2）教学内容:课程在已有线性表、树、图等基本数据结构基础上，主要介绍:涉及动态查找、高级堆（heap）的一些复杂数据结构，包括AVL树、SPLAY树、B树、Leftist heap、Skew heap、Binomial Queue；NP问题以及典型的算法设计方法，包括贪心法、分治法、动态规划法、回溯法等。

4.教学对象

浙江大学工学（信息）大类二年级学生；每年开设8个左右教学班，每班人数控制在45人以内，采用小班化教学。

5.课程学时和教学场景

（1）课程学时:课堂教学16学时，实验教学16学时。

（2）教学场景:课堂教学在多媒体教室，实验教学在计算机实验机房。

二、课程教学重点解决的问题

课程的目的是培养学生能在问题分析的基础上选择和设计最佳的数据结构与算法，从而培养高级程序设计与分析能力。因此，学生在学习过程中不仅要掌握相关的知识和技术，更需要培养分析问题与解决问题的能力，包括如何分析问题、如何选择和设计合适的数据结构和算法、如何评价程序的效率等。

在课程教学与学习过程中比较普遍存在的问题是:

（1）课程内容抽象、丰富，学生理解有难度。

（2）需要从系统的角度理解和分析各种方法，而不是以割裂的知识和方法进行教学和学习。

（3）课程的实践性比较强，需要加强实践（即数据结构和算法的程序实现），使学生在实践中掌握分析问题、解决问题、选择评价的能力。

三、教学方法改革

1.教学实施策略与方法

针对课程教学的目标和教学中重点解决的问题，目前课程采用的教学实施策略和方法主要有:基于团队的学习组织方式、基于问题的互动教学、基于大作业的研究性学习。

（1）基于团队的学习组织方式。团队协作是工业界普遍采用的软件设计组织方式，因此在课程教学中引入团队合作既可培养学生团队合作的精神和方法，也可以让学生有可能完成更加复杂的课外实践任务，使学生在解决复杂问题的求解中培养更好的程序设计能力。课程采用小班教学，人数基本限定在45人，第一堂课就将学生分组，每3人一组。每组学生在课堂学习中座位集中（为了课堂讨论），在课外实践中分工合作完成大作业任务。

（2）基于问题的互动教学。教师在每次授课前准备若干问题供学生课堂讨论，学生讨论表现记入考核成绩。讨论问题主要有两种，一种是比较简单的问题（一般是引导性问题）由学生独立抢答，每次回答或者主动提问均记入课堂讨论得分（个人）；另一种是比较难的问题（全程共14个），由学生在课堂上分组讨论，3～5分钟后提交书面答案，教师课后评价记分（团队分）。这种教学思路目前已经应用于教材的编写中（已由高等教育出版社2012年4月出版）。该教材从实际应用问题出发，导出各种经典数据结构的定义、实现（存储）方法以及操作实现，并以更丰富的综合应用案例帮助读者增强对理论的感性认识，从而明白这些数据结构为什么存在以及在什么情况下可以最好地解决什么样的问题。

（3）基于大作业的研究性学习。课程除了布置小型作业外，还设计了5道研究型大作业（project），由学生根据教学进度在不同周分组完成。全班学生在第一节课就被分为15组，每组抽签选择1道题目（这样每道题目有3组学生同时做）。学生需要根据题目要求，自行查找资料、归纳总结知识点、动手做实验进行验证等，最后提交一份格式与正式学术论文相似的研究报告，并在一周后的课堂上各组学生代表分别做8～10分钟的汇报演讲（共占用1节课时间），由所有同学提问、答辩。这种方法目的在于引导学生能科学地分析问题和解决问题，充分锻炼学生自主学习与钻研的能力、撰写科学研究报告的能力、口头表达能力以及团队合作与沟通能力等。课程组教师针对实施大作业的经验，编写了两本实践指导教材分别由浙江大学出版社（2007年）和高等教育出版社出版（计划2013年出版）。

2.具体实施方法举例

（1）基于问题的互动教学举例。

例如，在引入最左堆（Leftist heap）内容之前，先让学生讨论“如果应用一般的堆（heap）来实现两个堆的合并，效率如何”，进而为学生理解为什么要讲解最左堆以及最左堆解决了什么问题做好铺垫。

又例如，在讲解完B树基本内容后，提出的一个讨论题是“What are the pros and cons of using hashing，comparing to using search trees？”要求学生能对不同单元的知识内容进行横向比较，以理解不同方法的应用场景和特点。

（2）基于大作业的研究性学习举例。

课程组教师每学期都设计5道大作业题目，这些题目涉及不同内容，包括:不同算法的实验比较与分析（如比较不同动态查找算法在百万级大数据下的性能）、针对某些具体应用难题的算法设计（如小型搜索引擎设计）以及带有探索性的算法研究（如在研读一批学术论文基础上，研究设计图最大团clique算法）。所有大作业的研究成果均要求程序设计实现，并根据实验结果，写一篇研究报告（小论文），在随后的课堂上面向所有学生作分析报告。研究报告的基本格式如下:大作业的评分由两部分构成:研究报告评价分（占2/3）和课堂报告分（占1/3）。课堂报告由学生事先准备好ppt，教师当场随机抽取小组的一名成员代表小组进行报告，并由教师和其他各组同学共同打分。打分标准包括:报告内容质量（quality of presented materials）、报告的正确性（presentation correctness）、报告的清晰性（presentation clearness）。

3.教学方法特点分析

本课程教学内容比较偏重技术与方法，但强调技术在问题求解中的应用，因此课程教学中选用了研究性学习导向的教学方法，主要特点有:

（1）以团队方式形成学习组织。将班级学生分组，在课堂上实行以组为单位的分组讨论，课后进行基于团队合作的研究与实践；课程考核内容也分个人考核和小组考核（小组成员分数一样）。小组考核主要包括课堂讨论和大作业课堂汇报。

（2）以大作业贯通课内外学习活动。通过大作业让学生在理解课堂教学内容的基础上展开课外的探索学习、团队设计、文献分析等活动，再将活动成果反馈到课堂教学中，形成“带着问题来、领着任务走、怀着体会回”的课内外任务驱动的联动，实现课内外活动的有机联动。

四、课程考核方法和支撑手段

1.课程考核方法

课程成绩（100分）由下面5部分组成:

（1）课堂讨论:共设计有14道讨论题，现场提交，分组考核，总计14分；

（2）课后小作业:共10题，总计5分；

（3）课后大作业:每次共设计有5道研究题目，学生分组完成，每组做1题，总计30分，其中研究报告20分（满分根据难度确定），课堂汇报演讲10分；

（4）课堂抢答或提问:0.5分/次；

（5）期末考试:50分。

除期末考试外，其他部分的分数总和以50分为上限，超过者仍按50分计。

2.网络支撑手段建设

本课程不仅要求学生掌握数据结构和算法的设计实现方法，同时要求所实现方法具有良好的效率，因此需要有相应测试手段；另外，由于课程实施时有8个教学班同时进行，而大作业题目是一样的，因此也需要有手段来保证各小组工作独立完成，防止不同班级之间（或者不同届学生之间）的抄袭行为。所以，课程组除建设基本的课程教学网站外，还专门研究开发了以下两个有特色的网络教学支撑系统。

（1）程序在线评测系统（PAT）:建立一种客观、标准化的程序设计评测方法，不仅评测程序的功能，还评测程序在时间和空间上的性能。目前该系统还应用于程序设计能力的评测，即将高校的程序设计能力培养与软件企业用人单位招聘考核相融合。评测证书已经被35家IT企业承认，可替换招聘时与考查程序设计能力相关的考试环节；目前注册用户1000余人，累计近40000次提交。

（2）源代码及PDF文档查重系统:建立课程实践环节所产生的实践结果文档库（包括源代码以及PDF文档）并具有查重功能，为检查学生在实践环节中的诚信与保证公平提供了的技术保障。目前，系统中已拥有历届数千份学生大作业源代码和文档。

五、教学效果和推广性分析

1.教学效果

本课程的教学方法改革自2008年冬学期开始试点，2009年在所有8个教学班中全面实施。目前进行了5届学生实验，涉及约1400名学生。改革效果良好，获得了学生很好的评价。典型评价有:

“……有很多交流互动，特别是Discussion环节，让我们获益不少，同时也学习了别人的想法，交到了更多的朋友……”

“……以前上别的课，很多人都坐在教室后面，但这门课大家的热情都很高，甚至忙着占位……虽然每天都是第一和第二堂的课，但活跃的课堂气氛一点也不让人打瞌睡，反而是精神饱满……”

“中国的课堂和美国课堂的很大一个差别在于课堂的参与度，我之前在浙大上的课，大多是老师的一言堂，下面只见人头，不见人脸。即使是小班，同学之间也互不了解，很是无趣。但现在这种形式，通过抢答、提问把课堂气氛调动得超级活跃。通过小组的讨论，我们小组成员间也从陌生到熟识，格外温馨。而且我也见识到了计院的强手如云，更是催人奋进。越学越有感觉，越学越开心了。我觉得这样的创新尝试早就应该有了，真的这样才是大学的学习。”

“演讲环节，每个人都有相同的机会站在讲台上展示，这对我们是一次很好的锻炼。”

“对于我个人来讲，通过这门课，又重新养成了课前认真预习的好习惯，这是我的一大收获。没有预习，就无法在课堂上正确高效地回答问题；没有预习，就无法在Discussion中快速准确地得出结论。相比于数据机构基础，虽然只要做一个project，但是迫于考试范围的压力，必须将所有project都过目，从而迫使自己去学习了解更多课本以外的东西。”

“我感受到了热烈的气氛带来的与众不同，每节课都是那么充实，同时也让我见识到了比自己强的同学的思维，不是仅仅向老师学习，而是向班里的每一位同学学习。在做project时，因为是全新的内容，小组只能自己动手，既体会到了求索的艰难，又收获到了登顶的愉快，相信通过一次project，相关内容所包含的思想方法，都会深深的烙在心中，过程中积累的经验和教训，也为以后的研究和开发打下了基础。”

2.推广性分析

本课程教学方法的实施需要有以下条件支撑:

（1）需要小班教学。由于课程学习组织采用小组方式，并进行基于小组的课堂讨论和大作业课堂汇报，因此如果教学班人数过多将难以保证教学质量和效果。

（2）需要有技术手段支撑。需要有评价程序效率的评测系统和查重检测系统保证小组合作完成大作业的效果。同时，课程组教师需要热心投入，定期更换大作业题目。

（3）需要学生花更多的时间和具有良好的学习主动性。为了课堂学生研讨，教师授课时间由一周讲2节课压缩为讲1节课，因此需要压缩课堂教学内容，不讲的内容由学生自学。这样，考试范围不仅包括课堂上讲过的内容，而且包括全部研究型大作业的内容以及要求学生自学的内容，做到“讲1做2考3”——即老师“讲”核心知识点，学生“做”部分知识点的深入研究（每个学生做1个研究题目），“考”全部研究题目覆盖的范围。

整体来说，该方法比较适合于“高阶”的技术性课程，对于那些基础知识要求非常扎实的课程（如“数据结构基础”）可能不是很适合，因为在目前状态下课堂学时和教学内容的压缩可能会使学生基础知识不扎实。

六、课程教材及实验参考书

本课程是教育部双语示范课程（2008年），主教材为获得ACM杰出教育家称号（ACM Distinguished Educator）的Mark Allen Weiss教授所编写、由浙江大学陈越教授改编的原版改编教材。

［1］Mark Allen Weiss.Data Structures and Algorithm Analysis in C（2nd Edition）.陈越改编.北京:人民邮电出版社，2005

［2］何钦铭，冯雁，陈越.数据结构课程设计.杭州:浙江大学出版社，2007

［3］陈越，何钦铭等.数据结构.北京:高等教育出版社，2012

［4］陈越，何钦铭等.数据结构实验指导.北京:高等教育出版社（即将出版）