“数据结构与算法设计”课程涉及众多的概念、理论和过程，如何阐述各种算法的核心思想和理念，剖析各种数据结构的作用、分工和异同，并且教会学生进行综合运用一直是本课程的重点和难点。课程组的各位教师不断提升自己的理论修养，提高准确把握技术发展方向的能力，同时通过亲身参加科研和应用项目，不断增强算法设计和运用能力，对“数据结构与算法设计”教学中的重点和难点问题进行了较好地解决。具体来说：

1. 动态规划、递归算法和贪婪算法
动态规划算法是困扰学生的难点之一，动态规划实际上是一种算法设计的思想，而非一般意义的算法。它并不能简单地套用已有算法过程，而需要根据不同的问题进行设计。动态规划算法又与贪婪算法和常规的递归算法既有相似又有不同，比较容易混淆。面对实际应用时，合理的选用哪一种算法要求深入分析问题的性质，并且熟知这三种算法之间的差别。如果不能正确地加以选择，其结果对算法运行效率有很大的影响。课程组教师首先通过简单例子讲解动态规划的应用实例，然后归纳出可以运用动态规划求解问题的两个重要特征：“Optimal Substructure”和“Overlapping Subproblems”，同时指出动态规划、递归算法和贪婪算法都可以写出相应的递归方程，但是由于“Overlapping Subproblems”使得之前求解得到的子问题的解可以被暂存并且在之后的过程中加以重复使用，这使动态规划区别于常规的递归算法；虽然“Optimal Substructure”是动态规则和贪婪算法所的共有特征，但是“Greedy-choice Property”是贪婪算法区别于动态规则的关键，也使算法的效率得到了较大的提升。课程组教师借助众多实例，反复分析和比较各种可能出现的情况，让学生确实地理解动态规划、递归算法和贪婪算法三者之间的关系，并且能够在这三种算法之间做出合理的选择。

2. 红黑树、AVL树和B树
红黑树、AVL树和B树是课程中最为复杂的三个数据结构，并且目的都是为了减少对大规模数据进行查询和更新操作的代价。课程组教师首先介绍三个平衡查询树中相对简单的AVL树设计思想，即通过让任何结点左右子树之间的高度差小于2来保持树的平衡性。接着讨论当高度差等于2时如何通过旋转操作恢复高度差小于2的限制条件，并且让学生自己归纳出旋转操作的规律。然后指出虽然AVL树平衡恢复过程相对简单，但是发现哪个结点违反了高度差小于2限制的程序可能需要遍历树中较大范围内的结点，从而增加了整个数据结构的维护代价。基于如何在局部范围内就能够发现违反平衡树限制条件的思路出发，提出红黑树的设计思想，并且对每一个可能出现的违反情况，归纳出恢复树平衡操作的规则。针对海量数据管理时，由于内存不足以存储所有数据，需要内存与磁盘之间进行频繁数据交换的情况，提出B树的设计思想。由于磁盘读写的时间开销远大于内存读写，为了尽量减少磁盘读写次数，从而增加平衡树的出度（从二叉变为多叉）使得整个树扁平化。在上述过程中，伴随着众多实例分析和演示，使得原本颇为乏味的重要技术细节问题在教师逐步引向、扩展和总结中被学生所理解和掌握。最后通过使用红黑树和B树实现简单的数据库管理系统的综合项目让学生巩固和深化课堂所学，并训练学生用实验数据来印证理论分析结果的能力。

3. 算法分析与排序算法
算法复杂度分析是算法效率评价的理论基础，既是这门课的重要内容之一，也是学生在本门课程中最先遇到的难点问题。开始时学生会直观地使用算法运行的绝对时间来衡量算法的效率，但是运行时间与所使用的设备有关，而且不同设备的特性会导致对不同算法的评价发生偏差。任课教师引导学生思考如何建立与设备无关的、但与问题输入规模相关的数学方程来评价算法效率。然后以归并排序和插入排序比较入手，解释如何从工程的角度分析算法的复杂性。通过说明不同的算法复杂性在大规模输入下的巨大差异来阐述使用数学方程来衡量算法复杂性的指向性和优越性，同时也指出算法复杂性分析结果并不是评价算法的唯一标准，还包括可维护性、可扩展性、用户友好性等方面，并且这些方面的评价结果可能是相互矛盾和制约的。最后通过适用问题、计算复杂性和稳定性等方面讲解和比较各种排序算法，要求学生设计能够发挥快速排序和插入排序各自优点的综合排序算法，并且通过实验证明综合排序算法的优势。

4. 图的最短路径算法
图的最短路径算法分为两大类，一类是Single-source shortest-paths algorithms，另一类是All-pairs shortest- paths algorithms。每一类又有数个最短路径算法，并且适用于不同的情况。课程组教师借助众多实例和图形化的演示，对同属一类的算法在弧有无权重、是否可出现负权、图中可否存在环、时间复杂度、对数据结构的要求等多个侧面进行详细比较和分析，帮助学生理顺思路和归纳总结。最后要求学生完成真实地图上最短路径的计算程序（学生自由选择上海市区地图某一部分作为测试数据），该项目不仅要求学生对存储图的数据结构进行扩展，同时需要综合应用Hash Table、String Matching和Shortest-paths 等算法。项目设计有趣实用，不仅增强了学生综合运用各项技术的能力，同时提升了他们对本专业的兴趣。

5. NP完全性问题
由于学生还没有学习计算理论方面的课程，对于理解NP问题和NP完全性问题有一定的困难。此外，还存在以下难点，即改变某个P问题的条件，改变后的P问题就变成NP问题。学生需要熟悉这些NP和P问题的区别，以避免将P问题当成NP问题来对待，又或是将NP问题当成P来处理。NP问题的定义是非确定图灵机在多项式时间内能够解决的问题，但是学生之前并没有接触过图灵机模型，这样的定义一定会使学生无法理解。任课教师首先介绍旅行商问题，接着让学生尝试寻找有效地求解算法，经过教师引导下的讨论后得出：在现有计算机体系统结构和运算能力的基础上，一定规模的旅行商问题缺乏找得最优解的有效算法，即不存在多项式的算法。然后指出存在一类这样的问题，并且任取这类中的一个问题，再任取这类中的另一个问题，则一定存在多项式时间复杂性的算法，即可以把前者转变为后者。如果存在解决前者的多项式算法，必定存在能够解决后者的多项式算法。最后指出目前仍然没有找到多项式算法来解决这类问题，同时也不能够证明这样的多项式算法不存在，这就是NP完全性问题。为了让学生加深对上述问题的体会和熟知典型的NP问题，将学生分成九组，每一组给出一对问题，其中一个属于P问题，一个属于NP。要求学生调查这一对问题在应用中出现的实例和变体，然后设计可行的解决方法。并且要求每组以Presentation的方式向师生介绍他们的调查结果，听取报告的老师学生随时可以进行提问要求报告的学生回答。教学实践表明学生此举加深了学生对NP完全性问题的认识和理解。