《算法设计与分析基础》（Python语言描述） 实验教学大纲.docx

PAGE2 算法设计与分析实验大纲

数据结构实验课程大纲 PAGE3

《算法设计与分析实验》课程教学大纲

课程代码：****

课程负责人：****

课程中文名称：算法设计与分析实验

课程英文名称：Algorithmdesignandanalysisexperiment

课程类别：必修

课程学分数：0.5

课程学时数：15～21

授课对象：计算机科学与技术及相关专业本科

本课程的前导课程：Python程序设计、数据结构

一、教学介绍

算法设计与分析实验是算法设计与分析的配套课程，主要通过上机编程巩固算法设计与分析的基本原理和方法，掌握数据组织和算法设计和实现技术，培养综合运用算法设计与分析策略高效解决问题的能力。主要穷举法、归纳法、迭代法和递归法等基本算法设计方法以及分治法、蛮力法、回溯法、分支限界法、贪心法和动态规划法等算法设计策略。

二、教学目的

算法设计与分析实验课程的总目标是培养学生能够根据需要开展实验研究，正确地描述数据和组织数据，并应用数据处理方法，编写程序，分析实验结果以获得合理有效的结论，具备解决复杂工程问题的能力。

算法设计与分析实验主要在LeetCode在线编程平台中完成，目的是培养学生研究问题、合理地选择数据结构和算法策略构建解决方案，并分析比较各种方案优劣的能力。

三、实验基本要求与方式

1、基本要求

课前：要求任课教师布置好实验题目、实验要求和实验目的，要求实验教师为实验准备好必须的设备和软件；要求学生提前编写完成实验要求的程序代码。

课中：要求任课教师随时解答学生提出的实验问题，同时要注重启发和引导学生，使学生养成独立思考、解决问题的能力，检查学生的实验内容；实验教师要及时解决实验设备可能出现的故障，保证实验顺利地进行。学生则应该按照实验要求，认真编写和调试源代码，完成实验内容。

课后：提交实验报告。

2、实验方式

在在线编程平台提交代码，查看提交结果，分析代码运行的时间和空间。

四、实验报告

实验报告按学院要求格式书写，包含封面（含学号，姓名等），目录，每个实验的题目，解答思路，程序框架，源代码，提交结果图（LeetCode在线编程网站提交代码后的通过、运行时间和空间的截屏图），实验体会（选）。

五、实验内容与学时分配

说明：所有在线编程实验题目见LeetCode（）网站，同时配套教材中练习题部分列出了所有的实验题。

实验1：常用数据结构及其应用

学时数：0～3。任课教师根据学生情况在以下LeetCode在线编程题中选择若干实验题目。

（1）删除排序数组中的重复项（LeetCode26★）。

（2）一维数组的动态和（LeetCode1480★）。

（3）和为k的子数组（LeetCode560★★）。

（4）奇偶链表（LeetCode328★★）。

（5）合并两个链表（LeetCode1669★★）。

（6）合并k个升序链表（LeetCode23★★★）。

（7）最长有效括号（LeetCode32★★★）。

（8）有效的括号字符串（LeetCode678★★）。

（9）找出游戏的获胜者（LeetCode1823★★）。

（10）二叉有哪些信誉好的足球投注网站树中的众数（LeetCode501★）。

实验2：基本算法设计方法

学时数：0～3。任课教师根据学生情况在以下LeetCode在线编程题中选择若干实验题目。

（1）计数质数（LeetCode204★★）。

（2）数组中的最长山脉（LeetCode845★★）。

（3）螺旋矩阵II（LeetCode59★★）。

（4）格雷编码（LeetCode89★★）。

（5）Pow(x,n)（LeetCode50★★）。

（6）对称二叉树（LeetCode101★）。

（7）路径总和III（LeetCode437★★）。

实验3：分治法

学时数：3。任课教师根据学生情况在以下LeetCode在线编程题中选择若干实验题目。

（1）有哪些信誉好的足球投注网站二维矩阵II（LeetCode240★★）。

（2）有哪些信誉好的足球投注网站二维矩阵（LeetCode74★★）。

（3）有哪些信誉好的足球投注网站插入位置（LeetCode35★）。

（4）最大二叉树（LeetCode654★★）。

（5）有序链表转换二叉有哪些信誉好的足球投注网站树（LeetCode109★★）。

（6）寻找两个正序数组的中位数（LeetCode4★★★）。

（7）计算右侧小于当前元素的个数（LeetCode315★★★）。

实验4：回溯法

学时数：3。任课教师根据学生情况在以下LeetCode在线编程题中选择若干实验题目。

（1）统计各位数字都不同的数字个数（LeetCode357★★）。

（2）组合总和III（LeetCode216★★）。

（3）组合（LeetCode77★★）。

（4）组合总和（LeetCode39★★）。

（5）划分为k个相等的子集（LeetCode6