东北大学：某学院计算机科学与技术专业《算法设计与分析》课程教学大纲

算法设计与分析课程教学大纲The Design and Analysis of AlgorithmSubjectSyllabus一、课程信息SubjectInformation课程编号：开课学期：43100213012.01SemesterSubject ID课程分类：所属课群：专业教育PA专业平台MTCategorySection课程学分：总学时/周：2.540/4Credit PointsTotal Hours/Weeks理论学时：实验学时：400LECT. HoursEXP. HoursPBL学时：实践学时/周：00PBL HoursPRAC.Hours/Weeks东北大学悉尼智能科技学院开课学院：适用专业：Sydney Smart计算机科学与技术CollegeStreamCSTTechnology CollegeNortheasternUniversity课程属性课程模式：选修Elective自建NEUPatternMode宋欣中方课程协调人：成绩记载方式：百分制MarksNEU CoordinatorXin SongResult Type先修课程：程序设计基础，数据结构FoundationofProgramming，DataStructureRequisites英文参考教材：JonKleinberg，Algorithmdesign，人民邮电出版社，2019ENTextbooks王主晓东，计算机算法设计与分析（第5版），电子工业出版社，2018中文参考教材WangXiaodong.ComputerAlgorithm (5thEdition).ElectronicsCN TextbooksIndustry.2018教学资源课程教学群分享知识点视频讲解Resourceshttps:/www.icourses.cn/sCourse/course2535.html课程负责人(撰写人)：提交日期：单击或点击此处输宋欣入日期。SubjectDirectorSubmitted Date任课教师(含负责人)：宋欣Taught by审核人：批准人：韩鹏史闻博Checked byApprovedby批准日期：单击或点击此处输入日期。Approved Date1/ 13

1 / 13 算法设计与分析 课程教学大纲 The Design and Analysis of Algorithm Subject Syllabus 一、课程信息 Subject Information 课程编号: Subject ID 3100213012.01 开课学期: Semester 4 课程分类: Category 专业教育 PA 所属课群: Section 专业平台 MT 课程学分: Credit Points 2.5 总学时/周: Total Hours/Weeks 40/4 理论学时: LECT. Hours 40 实验学时: EXP. Hours 0 PBL 学时: PBL Hours 0 实践学时/周: PRAC. Hours/Weeks 0 开课学院: College 东北大学 悉尼智能科技学院 Sydney Smart Technology College Northeastern University 适用专业: Stream 计算机科学与技术 CST 课程属性: Pattern 选修 Elective 课程模式: Mode 自建 NEU 中方课程协调人: NEU Coordinator 宋欣 Xin Song 成绩记载方式: Result Type 百分制 Marks 先修课程: Requisites 程序设计基础，数据结构 Foundation of Programming, Data Structure 英文参考教材: EN Textbooks Jon Kleinberg, Algorithm design, 人民邮电出版社，2019 中文参考教材: CN Textbooks 王晓东，计算机算法设计与分析（第 5 版），电子工业出版社，2018. Wang Xiaodong. Computer Algorithm (5th Edition).Electronics Industry.2018 教学资源: Resources 课程教学群分享知识点视频讲解 https://www.icourses.cn/sCourse/course_2535.html 课程负责人(撰写人): SubjectDirector 宋欣 提交日期: Submitted Date 单击或点击此处输 入日期。 任课教师(含负责人): Taught by 宋欣 审核人: Checked by 韩鹏 批准人: Approvedby 史闻博 批准日期: Approved Date 单击或点击此处输 入日期

二、教学目标SubjectLearningObjectives（SLOs)注：毕业要求及指标点可参照悉尼学院本科生培养方案，可根据实际情况增减行数Note:GA and index can be referred from undergraduate program in SSTC website.Please add/reduce lines based on subjec课程的主要目标是培养具有扎实的算法设计和分析的理论基础，具有正确的价值观与社会责任感、优秀的职业道德与行为规范和具备良好的团队合作能力的程序设计人才。算法设计与分析课程是学生学习高级计算机应用和科学知识的入门课程，学生通过本门课程的理论学习和实践活动能应用算法设计与分析知识解决软件开发应用问题，包括操作系统、数据库和计算机网络等各个计算机应用领域。通过团队合作，学生能了解并掌握计算机算法表示方法，问题的解决与优化策略，通过对典型算法程序的调试和测试，逐步具备分析复杂问题的能力。The major aims to cultivate designing and analyzing ability of整体目标：fundamental computer algorithm theory, having correct values andOverall Objectivesense of social responsibility,good professional ethics and conduct, andcapableof good teamwork.This is an introductory algorithm subjecttohigh-Level computer application and computer science,Uponsuccessful completion of this subject student should be able to designand analysisalgorithm to solve software development applicationproblems related to operation system, database,network and so on.Asproject team members would, students go through the computeralgorithm representing method, incorporating analysis of complexproblems, programming solution design, implementation in computerlanguage and programming, debugging and testing.掌握基本的算法设计策略，如递归与分治，动态规划，贪心策略，回溯，分支限界法，随机化算法等。Masteryofthe1-1design strategy of computer algorithms such as recursion,divide and conquer,dynamic programming,greedy,backtrack,branch and bound method,randomization and so on掌握算法复杂度分析方法，能分析和预估计算机程序的执行效率。Masteryof the analysis application of algorithm1-2complexity, students should be able to identify and explain the（1）专业目标：workingsefficiencyofcomputerprogramProfessional Ability拥有符合本专业行业需求预期的计算机算法设计与分析能力。Students shouldbe able todemonstrate the1-3understanding and the ability to follow algorithm design andanalysis capacity to align with industry expectations具备良好的沟通和团队合作能力，能应用算法设计与分析知识解决较复杂的实际问题。Students shouldbeableto1-4communicate effectively and collaborate as a teammembertosolvecomplexproblems usingalgorithmdesignand analysisknowledges.（2）德育目标：具有正确的价值观与社会责任感、优秀的职业道德与行2-1为规范EssentialQuality2/13

2 / 13 二、教学目标 Subject Learning Objectives (SLOs) 注：毕业要求及指标点可参照悉尼学院本科生培养方案，可根据实际情况增减行数 Note: GA and index can be referred from undergraduate program in SSTC website. Please add/reduce lines based on subject. 整体目标: Overall Objective 课程的主要目标是培养具有扎实的算法设计和分析的理论基 础，具有正确的价值观与社会责任感、优秀的职业道德与行为规范 和具备良好的团队合作能力的程序设计人才。算法设计与分析课程 是学生学习高级计算机应用和科学知识的入门课程，学生通过本门 课程的理论学习和实践活动能应用算法设计与分析知识解决软件 开发应用问题，包括操作系统、数据库和计算机网络等各个计算机 应用领域。通过团队合作，学生能了解并掌握计算机算法表示方法， 问题的解决与优化策略，通过对典型算法程序的调试和测试，逐步 具备分析复杂问题的能力。 The major aims to cultivate designing and analyzing ability of fundamental computer algorithm theory, having correct values and sense of social responsibility, good professional ethics and conduct, and capable of good teamwork. This is an introductory algorithm subject to high-Level computer application and computer science, Upon successful completion of this subject student should be able to design and analysis algorithm to solve software development application problems related to operation system, database, network and so on. As project team members would, students go through the computer algorithm representing method, incorporating analysis of complex problems, programming solution design, implementation in computer language and programming, debugging and testing. （1）专业目标: Professional Ability 1-1 掌握基本的算法设计策略，如递归与分治，动态规划， 贪心策略，回溯，分支限界法，随机化算法等。Mastery of the design strategy of computer algorithms such as recursion， divide and conquer，dynamic programming, greedy, backtrack, branch and bound method, randomization and so on. 1-2 掌握算法复杂度分析方法，能分析和预估计算机程序的 执行效率。Mastery of the analysis application of algorithm complexity, students should be able to identify and explain the workings efficiency of computer program. 1-3 拥有符合本专业行业需求预期的计算机算法设计与分 析 能 力 。 Students should be able to demonstrate the understanding and the ability to follow algorithm design and analysis capacity to align with industry expectations 1-4 具备良好的沟通和团队合作能力，能应用算法设计与分 析知识解决较复杂的实际问题。Students should be able to communicate effectively and collaborate as a team member to solve complex problems using algorithm design and analysis knowledges. （2）德育目标: Essential Quality 2-1 具有正确的价值观与社会责任感、优秀的职业道德与行 为规范

Having correct values and sense of social responsibility,goodprofessionalethicsand conduct具有优异的创新精神和终身学习能力，学习与运用新技术的能力突出，能够适应持续的环境变化与技术变革2-2Having innovation spirit and ability of lifelong learning,learningandapplyingnewtechnologies,andbeabletoadapttocontinuous environmentalchangesandtechnological changes坚定“融贯东西、鼎新致远”的奋斗信念，胸怀“自强不息、知行合一”的东大品格Havingstrong belief of “Integrate east and west, innovate2-3for the long-term development", NEU character of "Strivingconstantlyfor improvement and behavingin conformitywithtruth"厚植爱国爱民、勇担责任的家国情怀，锻造坚忍不拔创新进取的工匠精神2-4Having the spirit of patriotism, perseverance, innovationand enterprising具有良好的跨文化、跨领域沟通交流能力2-5Good cross-cultural and cross-field communication skills课程教学目标与毕业要求的对应关系MatrixofGA&SLOs毕业要求GA指标点GAIndex教学目标SLOs指标点1-2PA1-1,PA1-2,EQ2-1毕业要求1GA1指标点1-3PA1-3, EQ2-2指标点2-1PA1-4, EQ2-4毕业要求2GA2指标点2-2PA1-4, EQ2-4指标点3-1PA1-4, EQ2-4毕业要求3GA3指标点3-3PA1-2, EQ2-1指标点5-1毕业要求5PA1-2, EQ2-3GA5指标点5-3PA1-2, EQ2-2, EQ2-3指标点9-1毕业要求9PA1-4, EQ2-4GA9指标点9-2EQ2-5毕业要求10指标点10-1PA1-3, PA1-4, EQ2-5GA10指标点12-1毕业要求12PA1-3, EQ2-2指标点12-2PA1-3, EQ2-2GA123/13

3 / 13 Having correct values and sense of social responsibility, good professional ethics and conduct 2-2 具有优异的创新精神和终身学习能力，学习与运用新技 术的能力突出，能够适应持续的环境变化与技术变革 Having innovation spirit and ability of lifelong learning, learning and applying new technologies, and be able to adapt to continuous environmental changes and technological changes 2-3 坚定“融贯东西、鼎新致远”的奋斗信念，胸怀“自强不 息、知行合一”的东大品格 Havingstrong belief of “Integrate east and west, innovate for the long-term development”, NEU character of “Striving constantly for improvement and behaving in conformity with truth” 2-4 厚植爱国爱民、勇担责任的家国情怀，锻造坚忍不拔、 创新进取的工匠精神 Having the spirit of patriotism, perseverance, innovation, and enterprising 2-5 具有良好的跨文化、跨领域沟通交流能力 Good cross-cultural and cross-field communication skills 课程教学目标与毕业要求的对应关系 Matrix of GA & SLOs 毕业要求 GA 指标点 GA Index 教学目标 SLOs 毕业要求 1 GA1 指标点 1-2 PA1-1,PA1-2,EQ2-1 指标点 1-3 PA1-3, EQ2-2 毕业要求 2 GA2 指标点 2-1 PA1-4, EQ2-4 指标点 2-2 PA1-4, EQ2-4 毕业要求 3 GA3 指标点 3-1 PA1-4, EQ2-4 指标点 3-3 PA1-2, EQ2-1 毕业要求 5 GA5 指标点 5-1 PA1-2, EQ2-3 指标点 5-3 PA1-2, EQ2-2, EQ2-3 毕业要求 9 GA9 指标点 9-1 PA1-4, EQ2-4 指标点 9-2 EQ2-5 毕业要求 10 GA10 指标点 10-1 PA1-3, PA1-4, EQ2-5 毕业要求 12 GA12 指标点 12-1 PA1-3, EQ2-2 指标点 12-2 PA1-3, EQ2-2

三、教学内容Content（Topics)注：以中英文填写，各部分内容的表格可根据实际知识单元数量进行复制、扩展或缩减Note: Filled in both CN and EN, extend or reduce based on the actual numbers of knowledge unit(1）理论教学Lecture知识单元序号：支撑教学目标：1PA1-1,PA1-2,EQ2-4Knowledge Unit No.SLOs Supported知识单元名称计算机算法概述Unit TitleIntroduction to Computer Algorithm算法与程序Algorithm and Program知识点：算法复杂性分析Knowledge DeliveryAlgorithm Complexity AnalysisNP完全性理论TheoryofNP-completeness了解:计算机算法的历史和发展RecognizeHistory andDevelopment of ComputerAlgorithm理解：算法的概念和特点学习目标：UnderstandConcept and Characteristic ofAlgorithmsLearning Objectives计算机算法的描述，算法复杂度分析掌握：Description ofComputerAlgorithm,MasterAlgorithmComplexityAnalysis厚植爱国爱民、勇担责任的家国情怀，锻造坚忍不拔、创新进德育目标取的工匠精神Moral ObjectivesHaving the spirit of patriotism,perseverance,innovation,andenterprising算法的概念、特性、描述方法，算法复杂性分析重点：TheConcept and CharacteristicofAlgorithm,Key PointsDescription Method of AlgorithmAlgorithmComplexityAnalysis算法的概念、特性、描述方法，算法复杂性分析难点：TheConcept andCharacteristicof Algorithm,Focal pointsDescription Method of AlgorithmAlgorithm ComplexityAnalysis4/13

4 / 13 三、教学内容 Content (Topics) 注：以中英文填写，各部分内容的表格可根据实际知识单元数量进行复制、扩展或缩减 Note: Filled in both CN and EN, extend or reduce based on the actual numbers of knowledge unit (1) 理论教学 Lecture 知识单元序号: Knowledge Unit No. 1 支撑教学目标: SLOs Supported PA1-1,PA1-2,EQ2-4 知识单元名称 Unit Title 计算机算法概述 Introduction to Computer Algorithm 知识点: Knowledge Delivery 算法与程序 Algorithm and Program 算法复杂性分析 Algorithm Complexity Analysis NP 完全性理论 Theory of NP-completeness 学习目标: Learning Objectives 了解: Recognize 计算机算法的历史和发展 History and Development of Computer Algorithm 理解: Understand 算法的概念和特点 Concept and Characteristic of Algorithms 掌握: Master 计算机算法的描述，算法复杂度分析 Description of Computer Algorithm， Algorithm Complexity Analysis 德育目标 Moral Objectives 厚植爱国爱民、勇担责任的家国情怀，锻造坚忍不拔、创新进 取的工匠精神 Having the spirit of patriotism, perseverance, innovation, and enterprising 重点: Key Points 算法的概念、特性、描述方法，算法复杂性分析 The Concept and Characteristicof Algorithm, Description Method of Algorithm Algorithm Complexity Analysis 难点: Focal points 算法的概念、特性、描述方法，算法复杂性分析 The Concept and Characteristicof Algorithm, Description Method of Algorithm Algorithm Complexity Analysis

知识单元序号：支撑教学目标2PA1-1,PA1-2,EQ2-3SLOs SupportedKnowledge Unit No.知识单元名称递归与分治策略Unit TitleRecursion and Divide-and-Conquer Strategies递归的概念TheConceptofRecursion分治法的基本思想TheBasicIdeaofDivide-and-Conquer二分搜索技术BinarySearchTechnique大整数的乘法MultiplicationoflargeintegersStrassen矩阵乘法matrixmultiplicationofstrassen知识点：棋盘覆盖ChessboardCoverKnowledge Delivery合并排序mergesort快速排序Quicksort线性时间选择Lineartimeselection最接近点对问题Closestpairofpointsproblem循环赛日程表Round-robinschedule了解：子问题，递归的概念RecognizeSub-problem,TheConceptofRecursion典型的递归结构，分治算法思想，二分搜索技术，合并排序，快速排序，循环赛日程表理解：TheconstructionofatypicalRecursion,TheBasicIdeaUnderstand学习目标：of Divide-and-Conquer, Binary Search Technique,Learning Objectivesmerge sort,Quicksort,Round-robin schedule大整数的乘法，Strassen矩阵乘法，棋盘覆盖，线性时间选择，最接近点对问题掌握：Multiplication oflarge integers,matrix multiplication ofMasterStrassen,Chessboard Cover,Linear time selection,Closest Pair of Points Problem坚定“融贯东西、鼎新致远”的奋斗信念德育目标Havingstrong belief of “Integrate east and west, innovate for theMoral Objectiveslong-term development"典型的递归结构，分治算法思想，Strassen矩阵乘法，棋盘覆盖，线性时间选择，最接近点对问题重点：Theconstruction of a typical Recursion,The Basic Idea ofKey PointsDivide-and-Conquer,matrix multiplication of Strassen,ChessboardCover,Linear time selection,Closest Pair of Points Problem难点：线性时间选择，最接近点对问题Focal pointsLineartimeselection,ClosestPairofPointsProblem5/13

5 / 13 知识单元序号: Knowledge Unit No. 2 支撑教学目标: SLOs Supported PA1-1,PA1-2,EQ2-3 知识单元名称 Unit Title 递归与分治策略 Recursion and Divide-and-Conquer Strategies 知识点: Knowledge Delivery 递归的概念 The Concept of Recursion 分治法的基本思想 The Basic Idea of Divide-and-Conquer 二分搜索技术 Binary Search Technique 大整数的乘法 Multiplication of large integers Strassen 矩阵乘法 matrix multiplication of strassen 棋盘覆盖 Chessboard Cover 合并排序 merge sort 快速排序 Quicksort 线性时间选择 Linear time selection 最接近点对问题 Closest pair of points problem 循环赛日程表 Round-robin schedule 学习目标: Learning Objectives 了解: Recognize 子问题，递归的概念 Sub-problem，The Concept of Recursion 理解: Understand 典型的递归结构，分治算法思想， 二分搜索技术， 合并排序，快速排序，循环赛日程表 The construction of a typical Recursion, The Basic Idea of Divide-and-Conquer，Binary Search Technique， merge sort，Quicksort，Round-robin schedule 掌握: Master 大整数的乘法，Strassen 矩阵乘法，棋盘覆盖，线性 时间选择，最接近点对问题 Multiplication of large integers，matrix multiplication of Strassen，Chessboard Cover，Linear time selection， Closest Pair of Points Problem 德育目标 Moral Objectives 坚定“融贯东西、鼎新致远”的奋斗信念 Havingstrong belief of “Integrate east and west, innovate for the long-term development” 重点: Key Points 典型的递归结构，分治算法思想，Strassen 矩阵乘法，棋盘覆盖， 线性时间选择，最接近点对问题 The construction of a typical Recursion, The Basic Idea of Divide-and-Conquer，matrix multiplication of Strassen，Chessboard Cover，Linear time selection，Closest Pair of Points Problem 难点: Focal points 线性时间选择，最接近点对问题 Linear time selection，Closest Pair of Points Problem

知识单元序号：支撑教学目标3PA1-1,PA1-2,EQ2-1SLOs SupportedKnowledge Unit No知识单元名称动态规划Unit TitleDynamicProgramming矩阵连乘问题Matrix-ChainMultiplication动态规划算法的基本要素The Basic Elements of Dynamic Programming最长公共子序列LongestCommonSubsequence最大子段和MaximalSub-segmentSum知识点：凸多边形最优三角剖分Knowledge DeliveryTheOptimalTriangulation of ConvexPolygon图像压缩ImageCompression流水作业调度lineProductionScheduling0-1背包问题0-1KnapsackProblem最优二叉搜索树OptimalBinarySearchTree了解：动态规划的基本思想TheBasic Idea of Dynamic ProgrammingRecognize动态规划算法的基本要素TheBasic Elements of Dynamic Programming理解：最大子段和Maximal sub-segmentsumUnderstand流水作业调度lineProduction Scheduling学习目标：最优二叉搜索树Optimal BinarySearchTreeLearning Objectives矩阵连乘问题Matrix-ChainMultiplication最长公共子序列LongestCommonSubsequence掌握：凸多边形最优三角剖分TheOptimalTriangulationofMasterConvexPolygon图像压缩ImageCompression0-1背包问题0-1KnapsackProblem具有正确的价值观与社会责任感、优秀的职业道德与行为规范德育目标Having correct values and sense of social responsibility,goodMoral Objectivesprofessional ethics and conduct动态规划算法的基本要素TheBasicElementsofDynamicProgramming矩阵连乘问题Matrix-ChainMultiplication重点：最长公共子序列LongestcommonsubsequenceKey Points凸多边形最优三角剖分TheoptimaltriangulationofConvexpolygon图像压缩Imagecompression0-1背包问题0-1Knapsackproblem难点：最长公共子序列LongestcommonsubsequenceFocal points凸多边形最优三角分TheoptimaltriangulationofConvexpolygon6/13

6 / 13 知识单元序号: Knowledge Unit No. 3 支撑教学目标: SLOs Supported PA1-1,PA1-2,EQ2-1 知识单元名称 Unit Title 动态规划 Dynamic Programming 知识点: Knowledge Delivery 矩阵连乘问题 Matrix-Chain Multiplication 动态规划算法的基本要素 The Basic Elements of Dynamic Programming 最长公共子序列 Longest Common Subsequence 最大子段和 Maximal Sub-segment Sum 凸多边形最优三角剖分 The Optimal Triangulation of Convex Polygon 图像压缩 Image Compression 流水作业调度 line Production Scheduling 0-1 背包问题 0-1 Knapsack Problem 最优二叉搜索树 Optimal Binary Search Tree 学习目标: Learning Objectives 了解: Recognize 动态规划的基本思想 The Basic Idea of Dynamic Programming 理解: Understand 动态规划算法的基本要素 The Basic Elements of Dynamic Programming 最大子段和 Maximal sub-segment sum 流水作业调度 line Production Scheduling 最优二叉搜索树 Optimal Binary Search Tree 掌握: Master 矩阵连乘问题 Matrix-Chain Multiplication 最长公共子序列 Longest Common Subsequence 凸多边形最优三角剖分 The OptimalTriangulation of Convex Polygon 图像压缩 Image Compression 0-1 背包问题 0-1 Knapsack Problem 德育目标 Moral Objectives 具有正确的价值观与社会责任感、优秀的职业道德与行为规范 Having correct values and sense of social responsibility, good professional ethics and conduct 重点: Key Points 动态规划算法的基本要素 The Basic Elements of Dynamic Programming 矩阵连乘问题 Matrix-Chain Multiplication 最长公共子序列 Longest common subsequence 凸多边形最优三角剖分 The optimal triangulation of Convex polygon 图像压缩 Image compression 0-1 背包问题 0-1 Knapsack problem 难点: Focal points 最长公共子序列 Longest common subsequence 凸多边形最优三角剖分 The optimal triangulation of Convex polygon

知识单元序号支撑教学目标NPA1-1,PA1-2,EQ2-1SLOs SupportedKnowledge Unit No知识单元名称贪心算法GreedyalgorithmUnit Title活动安排问题ActivityArrangementsProblem贪心算法的基本要素TheBasicElementsofGreedyAlgorithm最优装载TheOptimalLoading知识点：哈夫曼编码HuffimanCodingKnowledge Delivery单源最短路径Single-SourceShortestPaths最小生成树MinimumSpanningTree多机调度问题Multi-machineSchedulingProblem了解:贪心算法的基本思想RecognizeTheBasicIdeaofGreedyAlgorithm贪心算法的基本要素理解：TheBasic Elementsof Greedy Algorithm学习目标：Understand活动安排问题ActivityArrangementsProblemLearning Objectives哈夫曼编码HuffimanCoding最优装载TheOptimal Loading掌握：单源最短路径Single-SourceShortestPathsMaster最小生成树MinimumSpanningTree多机调度问题Multi-MachineSchedulingProblem具有正确的价值观与社会责任感、优秀的职业道德与行为规范德育目标Having correct values and sense of social responsibility,goodMoral Objectivesprofessional ethics and conduct贪心算法的基本要素TheBasicElementsofGreedyAlgorithm活动安排问题ActivityarrangementsProblem重点：最优装载TheOptimal LoadingKey Points单源最短路径Single-Source ShortestPaths多机调度问题Multi-MachineSchedulingProblem难点：最优装载TheOptimalLoadingFocal points多机调度问题Multi-MachineSchedulingProblem7/13

7 / 13 知识单元序号: Knowledge Unit No. 4 支撑教学目标: SLOs Supported PA1-1,PA1-2,EQ2-1 知识单元名称 Unit Title 贪心算法 Greedy algorithm 知识点: Knowledge Delivery 活动安排问题 Activity Arrangements Problem 贪心算法的基本要素 The Basic Elements of Greedy Algorithm 最优装载 The Optimal Loading 哈夫曼编码 Huffman Coding 单源最短路径 Single-Source Shortest Paths 最小生成树 Minimum Spanning Tree 多机调度问题 Multi-machine Scheduling Problem 学习目标: Learning Objectives 了解: Recognize 贪心算法的基本思想 The Basic Idea of Greedy Algorithm 理解: Understand 贪心算法的基本要素 The Basic Elements of Greedy Algorithm 活动安排问题 Activity Arrangements Problem 哈夫曼编码 Huffman Coding 掌握: Master 最优装载 The Optimal Loading 单源最短路径 Single-Source Shortest Paths 最小生成树 Minimum Spanning Tree 多机调度问题 Multi-Machine Scheduling Problem 德育目标 Moral Objectives 具有正确的价值观与社会责任感、优秀的职业道德与行为规范 Having correct values and sense of social responsibility, good professional ethics and conduct 重点: Key Points 贪心算法的基本要素 The Basic Elements of Greedy Algorithm 活动安排问题 Activity arrangements Problem 最优装载 The Optimal Loading 单源最短路径 Single-Source Shortest Paths 多机调度问题 Multi-Machine Scheduling Problem 难点: Focal points 最优装载 The Optimal Loading 多机调度问题 Multi-Machine Scheduling Problem

知识单元序号：支撑教学目标5PA1-1,PA1-2,EQ2-2Knowledge Unit No.SLOs Supported知识单元名称回潮法BacktrackingAlgorithmUnit Title回溯法的算法框架TheAlgorithmFrameworkofBacktracking装载问题LoadingProblem批处理作业调度Batchjob scheduling符号三角形问题SignedTriangleProblem知识点：n后问题NQueensProblem0-1背包间题0-1KnapsackProblemKnowledge Delivery图的m着色间题TheM-coloringProblemofgraphs旅行售货员问题TravelingsalesmanProblem圆排列问题CirclePermutationProblem连续邮资问题ContinuousPostageProblem回溯法的效率分析TheEfficiencyAnalysisofBacktrackingMethod了解：回溯法的基本思想RecognizeTheBasicIdea of BacktrackingAlgorithm回溯法的算法框架TheAlgorithmFrameworkofBacktracking圆排列问题CirclePermutationProblem理解：连续邮资问题ContinuousPostageProblemUnderstand回溯法的效率分析TheEfficiencyAnalysisof学习目标BacktrackingMethodLearning Objectives装载问题LoadingProblem批处理作业调度BatchjobScheduling符号三角形问题SignedtriangleProblem掌握：n后问题NqueensProblemMaster0-1背包问题0-1KnapsackProblem图的m着色问题TheM-coloringProblemofGraphs旅行售货员问题TravelingSalesmanProblem具有优异的创新精神和终身学习能力，学习与运用新技术的能力突出，能够适应持续的环境变化与技术变革德育目标Having innovation spirit and ability of lifelong learning,learning andMoral Objectivesapplying new technologies,and be able to adapt to continuousenvironmental changesand technological changes回溯法的算法框架TheAlgorithmFrameworkofBacktracking装载问题LoadingProblem批处理作业调度BatchJobScheduling重点：符号三角形问题SignedTriangleProblemKey Pointsn后问题NQueensProblem0-1背包问题0-1KnapsackProblem图的m着色问题TheM-coloringProblemofGraphs旅行售货员问题TravelingSalesmanProblem符号三角形间题Signed TriangleProblem难点：n后问题NQueensProblemFocal points旅行售货员问题TravelingSalesmanProblem8 /13

8 / 13 知识单元序号: Knowledge Unit No. 5 支撑教学目标: SLOs Supported PA1-1,PA1-2,EQ2-2 知识单元名称 Unit Title 回溯法 Backtracking Algorithm 知识点: Knowledge Delivery 回溯法的算法框架 The Algorithm Framework of Backtracking 装载问题 Loading Problem 批处理作业调度 Batch job scheduling 符号三角形问题 Signed Triangle Problem n 后问题 N Queens Problem 0-1 背包问题 0-1 Knapsack Problem 图的 m 着色问题 The M-coloring Problem of graphs 旅行售货员问题 Traveling salesman Problem 圆排列问题 Circle Permutation Problem 连续邮资问题 Continuous Postage Problem 回溯法的效率分析 The Efficiency Analysis of Backtracking Method 学习目标: Learning Objectives 了解: Recognize 回溯法的基本思想 The Basic Idea of Backtracking Algorithm 理解: Understand 回溯法的算法框架 The Algorithm Framework of B acktracking 圆排列问题 Circle Permutation Problem 连续邮资问题 Continuous Postage Problem 回溯法的效率分析 The Efficiency Analysis of Backtracking Method 掌握: Master 装载问题 Loading Problem 批处理作业调度 Batch job Scheduling 符号三角形问题 Signed triangle Problem n 后问题 N queens Problem 0-1 背包问题 0-1 Knapsack Problem 图的 m 着色问题 The M-coloring Problem of Graphs 旅行售货员问题 Traveling Salesman Problem 德育目标 Moral Objectives 具有优异的创新精神和终身学习能力，学习与运用新技术的能力突 出，能够适应持续的环境变化与技术变革 Having innovation spirit and ability of lifelong learning, learning and applying new technologies, and be able to adapt to continuous environmental changes and technological changes 重点: Key Points 回溯法的算法框架 The Algorithm Framework of Backtracking 装载问题 Loading Problem 批处理作业调度 Batch Job Scheduling 符号三角形问题 Signed Triangle Problem n 后问题 N Queens Problem 0-1 背包问题 0-1 Knapsack Problem 图的 m 着色问题 The M-coloring Problem of Graphs 旅行售货员问题 Traveling Salesman Problem 难点: Focal points 符号三角形问题 Signed Triangle Problem n 后问题 N Queens Problem 旅行售货员问题 Traveling Salesman Problem

知识单元序号：PA1-1,PA1-2,PA1-3,支撑教学目标：6EQ2-3Knowledge Unit No.SLOs Supported知识单元名称分支限界法BranchandBoundMethodUnit Title分支限界法的基本思想TheBasicIdeaofBranchandBoundMethod单源最短路径间题Single-sourceShortestPaths装载问题LoadingProblem知识点0-1背包问题0-1KnapsackProblemKnowledge Delivery最大团问题MaximumCliqueProblem旅行售货员问题TravelingSalesmanProblem批处理作业调度BatchjobScheduling了解：分支限界法的基本思想The Basic Idea of Branch and Bound MethodRecognize理解：单源最短路径间题Single-sourceShortestPaths学习目标：Understand最大团问题MaximumCliqueProblemLearning Objectives装载问题LoadingProblem掌握：0-1背包问题0-1KnapsackProblemMaster旅行售货员间题TravelingSalesmanProblem批处理作业调度BatchJobScheduling胸怀“自强不息、知行合一”的东大品格德育目标NEU character of "Striving constantly for improvement and behavingMoral Objectivesin conformity with truth"单源最短路径间题Single-sourceShortestPaths装载问题LoadingProblem重点：0-1背包问题0-1KnapsackProblemKey Points旅行售货员问题TravelingSalesmanProblem批处理作业调度BatchJobScheduling难点：装载问题LoadingProblemFocal points旅行售货员问题TravelingSalesmanProblem9/13

9 / 13 知识单元序号: Knowledge Unit No. 6 支撑教学目标: SLOs Supported PA1-1,PA1-2, PA1-3, EQ2-3 知识单元名称 Unit Title 分支限界法 Branch and Bound Method 知识点: Knowledge Delivery 分支限界法的基本思想 The Basic Idea of Branch and Bound Method 单源最短路径问题 Single-source Shortest Paths 装载问题 Loading Problem 0-1 背包问题 0-1 Knapsack Problem 最大团问题 Maximum Clique Problem 旅行售货员问题 Traveling Salesman Problem 批处理作业调度 Batch job Scheduling 学习目标: Learning Objectives 了解: Recognize 分支限界法的基本思想 The Basic Idea of Branch and Bound Method 理解: Understand 单源最短路径问题 Single-source Shortest Paths 最大团问题 Maximum Clique Problem 掌握: Master 装载问题 Loading Problem 0-1 背包问题 0-1 Knapsack Problem 旅行售货员问题 Traveling Salesman Problem 批处理作业调度 Batch Job Scheduling 德育目标 Moral Objectives 胸怀“自强不息、知行合一”的东大品格 NEU character of “Striving constantly for improvement and behaving in conformity with truth” 重点: Key Points 单源最短路径问题 Single-source Shortest Paths 装载问题 Loading Problem 0-1 背包问题 0-1 Knapsack Problem 旅行售货员问题 Traveling Salesman Problem 批处理作业调度 Batch Job Scheduling 难点: Focal points 装载问题 Loading Problem 旅行售货员问题 Traveling Salesman Problem

知识单元序号：支撑教学目标：PA1-1,PA1-2, PA1-3,7SLOs SupportedEQ2-5Knowledge Unit No.知识单元名称随机化算法RandomizedAlgorithmUnit Title随机数RandomNumber数值随机化算法NumericalRandomizationAlgorithm知识点：舍伍德算法SherwoodAlgorithmKnowledge Delivery拉斯维加斯算法LasVegasAlgorithm蒙特卡罗算法Monte-carloMethod了解：随机数RandomNumberRecognize理解：学习目标：数值随机化算法NumericalRandomizationAlgorithmUnderstandLearning Objectives舍伍德算法SherwoodAlgorithm掌握：拉斯维加斯算法LasVegasAlgorithmMaster蒙特卡罗算法Monte-carloMethod德育目标具有良好的跨文化、跨领域沟通交流能力Moral ObjectivesGood cross-cultural and cross-field communication skills数值随机化算法NumericalRandomizationAlgorithm重点：舍伍德算法SherwoodAlgorithmKey Points拉斯维加斯算法LasVegasAlgorithm蒙特卡罗算法Monte-carloMethod难点：拉斯维加斯算法LasVegasAlgorithmFocal points蒙特卡罗算法Monte-carloMethod10 /13

10 / 13 知识单元序号: Knowledge Unit No. 7 支撑教学目标: SLOs Supported PA1-1,PA1-2, PA1-3, EQ2-5 知识单元名称 Unit Title 随机化算法 Randomized Algorithm 知识点: Knowledge Delivery 随机数 Random Number 数值随机化算法 Numerical Randomization Algorithm 舍伍德算法 Sherwood Algorithm 拉斯维加斯算法 Las Vegas Algorithm 蒙特卡罗算法 Monte-carlo Method 学习目标: Learning Objectives 了解: Recognize 随机数 Random Number 理解: Understand 数值随机化算法 Numerical Randomization Algorithm 掌握: Master 舍伍德算法 Sherwood Algorithm 拉斯维加斯算法 Las Vegas Algorithm 蒙特卡罗算法 Monte-carlo Method 德育目标 Moral Objectives 具有良好的跨文化、跨领域沟通交流能力 Good cross-cultural and cross-field communication skills 重点: Key Points 数值随机化算法 Numerical Randomization Algorithm 舍伍德算法 Sherwood Algorithm 拉斯维加斯算法 Las Vegas Algorithm 蒙特卡罗算法 Monte-carlo Method 难点: Focal points 拉斯维加斯算法 Las Vegas Algorithm 蒙特卡罗算法 Monte-carlo Method