《算法设计与分析》实验教学大纲
课程代码 | 045100122 |
课程名称 | 算法设计与分析 |
英文名称 | The Design and Analysis ofComputer Algorithms |
课程类别 | 专业基础课 |
课程性质 | 必修 |
学时 | 总学时：64实验：16上机：0 |
学分 | 3.5 |
开课学期 | 第四学期 |
开课单位 | 计算机科学与工程学院 |
适用专业 | 计算机科学与技术全英创新班 |
授课语言 | 全英文授课 |
先修课程 | 高等数学、数据结构、高级语言程序设计 |
毕业要求（专业培养能力） | 1熟悉常见的算法，如：排序算法、贪心算法、树搜索算法、动态编程算法等； 2能够灵活应用常见的算法解决相关问题； 3将以上内容应用于分析与设计其他相关算法。 |
课程培养学生的能力（教学目标） | 通过这门课程，培养学生的抽象思维、严格逻辑推理以及熟练掌握应用优化算法解决问题的能力，并了解相关各类常用的算法，为计算机专业学生提供相关算法，培养学生运用常见算法解决实际问题的能力，为在后续专业课和实际工作中运用本课程的基本知识打下基础。 |
课程简介 | 本课程介绍了一些有名的常见算法，并应用这些算法求解一些实际问题。 |
主要仪器设备与软件 | 上机实验，学生需要用如下语言做程序编写 C，C++，Matlab，Python |
实验报告 | 按照计算机学院上机实验统一报告填写实验内容 |
考核方式 | 实验报告 |
教材、实验指导书及教学参考书目 |
|
制定人及发布时间 | 颜小洋，2017年7月10日星期一 |
《算法设计与分析》实验教学内容与学时分配
实验项目编号 | 实验项目名称 | 实验学时 | 实验内容提要 | 实验类型 | 实验要求 | 每组人数 | 主要仪器设备与软件 |
1 | 用排序算法解排序问题 | 4 | 应用几种排序算法求解排序问题，并比较不同排序算法在各种不同问题大小情况下的效率，要画出这些算法对应效率图。 | 验证性 | 必做 | 1 | |
2 | 用贪心算法、树搜索算法和动态编程算法解背包问题 | 2 | 应用贪心算法、树搜索算法和动态编程算法等多种算法解背包问题，比较不同算法的效率。 | 验证性 | 2和3选做一个 | 1 | |
3 | 用贪心算法解最小生成树问题 | 2 | 用Prim算法解有向图的最小生成树。 | 验证性 | 2和3选做一个 | 1 | |
4 | 用树搜索算法解相关问题 | 2 | 用树搜索算法解二进制树对应的数列中是否存在指定的数。 | 验证性 | 必做 | 1 | |
5 | 用动态编程算法解最短路径问题 | 4 | 用动态编程算法求解多极无向图的最短路径。 | 验证性 | 必做 | 1 | |
6 | 用树搜索算法的四种策略解8-puzzle（附加题） | 4 | 要求用UI完成用树搜索的宽度优先、深度优先、最佳优先以及分支与边界策略对8-Puzzle问题的求解，并给出结果：获得结果的搜索时间与步数。 | 验证性 | 选做 | 1 |
“TheDesign and Analysis of Computer Algorithms” Syllabus
Course Code | 045100122 |
CourseTitle | The Design and Analysis ofComputer Algorithms |
CourseCategory | SpecialtyBasic Course |
CourseNature | CompulsoryCourse |
Class Hours | 64 |
Credits | 3.5 |
Semester | Forth |
Institute | School ofComputer Science & Engineering |
ProgramOriented | InnovationClass |
TeachingLanguage | English |
Prerequisites | AdvancedMathematics, Data Structure, High-level Language Programming |
StudentOutcomes (Special Training Ability) | Studentsare required to solve the problems by using the suitable conceptsand algorithms learnt in the discrete mathematics course. Theyshould have good programming skill and also understand the course. 1.Tounderstand some kinds of common algorithms, such as sortingalgorithm, greedy algorithm, tree search algorithm, dynamicprogramming algorithm, etc. 2.To master the flexible application of these common algorithms tobe used to solve related problems; 3.Apply these methods to analyze and design other relatedalgorithms. |
TeachingObjectives | Throughstudying this course, the students will understand variouscommonly famous algorithms and have the abilities to apply thesealgorithms to solve different problems with high efficiency onabstract thinking, strict logical reasoning and so on. On thebasis of relevant basic analysis, practice and application ofthese kinds of algorithms, the students will be able to know howto implement the system development with high performance. |
CourseDescription | Somewell-known common algorithms and their application for thesolution of some practical problems are introduced in this course. |
Instrumentsand Equipments | DesktopComputer for each student - C++ environment - AMC Platform client software ACM Platform Server |
ExperimentReport | Fillthe uniform report template by Compute Science School. |
Assessment | Report |
TeachingMaterials and Reference Books |
|
Preparedby Whom and When | XiaoyangYan, July 10,2017 |
“DiscreteMathematics (2)” ExperimentalTeaching Arrangements
No. | ExperimentItem | ClassHours | ContentSummary | Category | Requirements | Instruments,Equipments and Software | |
1 | TosolvetheSorting Problemby Sorting Algorithms | 4 | Thesorting problemwith different size are solved using four kinds ofsorting algorithms, and the resultson efficiency of differentsorting algorithms for different problem sizesshould becompared in the graph. | Verification | Compulsory | 1 | DesktopComputer for each student - C++ or other high-level language |
2 | TosolvetheKnapsack Problemwith Greedy, Tree Search and Dynamic Programming Algorithms | 2 | Tosolvethe knapsackproblemwith Greedy,tree search and dynamic programming algorithms, the efficiencyfordifferent problem size shouldbecompared. | Verification | Elective(1 of No. 2 and No. 3) | 1 | DesktopComputer for each student - C++ or otherhigh-level language |
3 | ToSolve Minimum Spanning Tree (MST)Problemby GreedyAlgorithms | 2 | o SolveMinimum Spanning Tree (MST)Problemby GreedyAlgorithms | Verification | Elective (1 of No. 2 and No. 3) | 1 | DesktopComputer for each student - C++ or other high-level language |
4 | TosolveRelated Problems with Tree Search Algorithm | 2 | TosolveRelated Problems with Tree Search Algorithm | Verification | Compulsory | 1 | DesktopComputer for each student - C++ or otherhigh-level language |
5 | Tosolvethe ShortestPath Problem byDynamic Programming Algorithm | 4 | Tosolvethe ShortestPath Problem byDynamic Programming Algorithm(foreward and backward) | Verification | Compulsory | 1 | DesktopComputer for each student - C++ or other high-level language |
6 | Tosolvethe 8-puzzlewith Four Strategies of Tree Search Algorithm(Additionalproblem) | 4 | Toimplement the UI for the8-puzzleproblem withFour Strategies of Tree Search Algorithm(Thesimplegame UI) | Verification | Elective | 1 | DesktopComputer for each student - C++ or other high-level language |
