《算法设计与分析》教学大纲

课程代码

045100122

课程名称

算法设计与分析

英文名称

The Design and Analysis of Computer Algorithms

课程类别

专业基础课

课程性质

必修

学时

总学时：64  上机学时：16  实验学时：0  实践学时：0

学分

3.5

开课学期

第四学期

开课单位

计算机科学与工程学院

适用专业

计算机科学与技术全英创新班

授课语言

全英文授课

先修课程

数据结构、高等数学、高级语言程序设计

毕业要求（专业培养能力）

1、做一个遵纪守法、爱党爱国、为国家建设服务的优秀学生。

2、掌握基本的算法设计思想、基本算法分析的基础概念和方法，熟悉掌握常见算法的时间与空间复杂性分析原理，熟悉问题的低边界及其分析于获取最优算法。

3、 熟悉常见的算法，如：排序算法、贪心算法、树搜索算法、动态编程算法等；

4、能够灵活应用常见的算法解决相关问题；

5、将以上内容应用于分析与设计其他相关算法。

课程培养学生的能力（教学目标）

通过这门课程，培养学生的抽象思维、严格逻辑推理以及熟练掌握应用优化算法解决问题的能力，并了解相关各类常用的算法，为计算机专业学生提供专业相关的基础数学背景，培养学生运用基本理论分析和解决实际问题的能力，为在后续专业课和实际工作中运用本课程的基本知识打下基础。

课程简介

本课程介绍了算法设计与分析的基本原理，以及一些有名的常见算法，并应用这些算法求解一些实际问题。

教学内容与学时分配

    • 第一章算法概论（2学时）

    • 算法概念及其特性与分类

    • 第二章 算法复杂性分析与问题的低边界                 （5学时）

    • 算法复杂性分析                             （1学时）

    • 分析各种排序算法的复杂性                   （3学时）

    • 问题低边界的分析（1学时）

    • 第三章 贪心算法（8学时）

    • 贪心算法的原理                             （1学时）

    • 用贪心算法解决最小生成树问题（Kruskal和Prim算法）（2学时）解单源最短路径问题、Dijkstra问题、AOE网络问题以及背包问题（4学时）

    • 解各问题算法的复杂性分析（1学时）

    • 第四章分治算法（6学时）

    • 分治算法的基本原理及其求解步骤（1学时）

    • 用分治算法解最近点对问题、凸包问题、沃罗诺图问题、快速傅立、叶变缓以及多项式乘积问题（4学时）

    • 解各问题算法的复杂性分析（1学时）

    • 第五章 树搜索算法（8学时）

    • 树搜索算法的基本原理及其求解步骤（1学时）

    • 介绍树搜索的常用策略：广度优先、深度优先、最佳优先及分支与边界策略                               （3学时）

    • 用树搜索算法解哈密顿回路问题、流水线工作安排问题、旅游行售货员优化问题、0/1背包问题、A星问题    （4学时）

    • 第六章剪枝算法（4学时）

    • 剪枝算法的基本原理及其求解步骤（1学时）

    • 用剪枝算法解第k个最小数的选择问题、两个变量的线性编程问题、二维点集合的单一中心问题              （3学时）

    • 第七章动态编程算法（8学时）

    • 动态编程算法的基本原理及其求解步骤（1学时）

    • 用动态编程算法解最短路径问题、资源分配问题、最长公共子序列问题、0/1背包问题、优化二进制搜索树问题、矩阵乘积问题                                       （7学时）

    • 第八章 随机算法                                     （3学时）

    • 随机算法的基本原理及其求解步骤（1学时）

    • 用随机算法解模式匹配问题、寻找最近点对问题  （3学时）

    • 作业讲解与复习（4学时）

关键点：算法，算法复杂性，低边界，贪心算法，分治算法，树搜索算法，剪枝算法、动态编程算法、随机算法

难点: 算法复杂性分析、贪心算法，分治算法，树搜索算法，动态编程算法

实验教学（包括上机学时、实验学时、实践学时）

实验学时：16，四次实验课，每次4学时。

教学方法

课程教学以课堂教学、课外作业以及上机实验共同实施。

考核方式

本课程总评成绩比例为：

平时作业和课堂表现：10%

上机实验：20%

期末考试（闭卷）：70%

教材及参考书

  • R. C. T. Lee, S. S. Tseng, R. C. Chang , Y. T. Tsai,Introduction to the Design and Analysis of Algorithms, 2 ed, McGraw/Hill

  • The Design and Analysis of Computer Algorithms, Alfred Aho, John E. Hopcroft, Jeffrey D. Ullman, 2003.

  • Introduction to Algorithms, 2nd Ed. by Cormen, Leiserson, Rivest, & Stein (CLRS), McGraw Hill, 2002.

制定人及制定时间

颜小洋，2017年9月7日星期五


 “The Design and Analysis of Computer Algorithms” Syllabus

Course Code

045100122

Course Title

The Design and Analysis of Computer Algorithms

Course Category

Specialty Basic Course

Course Nature

Compulsory Course

Class Hours

64

Credits

3.5

Semester

Fourth semester

Institute

School of Computer Science & Engineering

ProgramOriented

Innovation Class

Teaching Language

English

Prerequisites

Data Structure，Advanced mathematicsand High-level Language Programming

Student Outcomes

 (Special Training Ability)

1. To understand the basic algorithm design idea, concept and algorithm analysis method, and know how to analyze the time and space complexity of algorithm, what the low boundary of the problem is and its analysis;

  1. To understand some kinds of common algorithms, such as sorting algorithm, greedy algorithm, tree search algorithm, dynamic programming algorithm, etc.

3. To master the flexible application of these common algorithms to be used to solve related problems;

4. To be able to apply these methods to analyze and design other related algorithms.

Teaching Objectives

Through studying this course, the students will understand various commonly famous algorithms and have the abilities to apply these algorithms to solve different problems with high efficiency on abstract thinking, strict logical reasoning and so on. On the basis of relevant basic analysis, practice and application of these kinds of algorithms, the students will be able to know how to implement the system development with high performance.

Course Description

It is a very important course for computer majors. Some well-known common algorithms and their application for the solution of some practical problems are introduced in this course.

Teaching Content and Class Hours Distribution

    • Chapter 1 Introduction (2)

    • Chapter 2 The Complexity of Algorithms and the Lower Bounds of Problems(5)

    • Chapter 3 The Greedy Method(8)

    • Chapter 4 The divide-And-Conquer Strategy (6)

    • Chapter 5 Tree Search Strategies(8)

    • Chapter 6 Prune-And-Search(4)

    • Chapter 7 Dynamic Programming(8)

    • Chapter 8 RandomizedAlgorithm (3)

    • Review and conclusion(4)

Key points: Algorithm, Algorithm complexity, The lower Bound, Greedy Algorithm, The divide-And-ConquerAlgorithm, Tree SearchAlgorithm, Prune-And-SearchAlgorithm, Dynamic ProgrammingAlgorithm and RandomizedAlgorithm

Difficulty points:analysis of Algorithm complexity,Greedy Algorithm, The divide-And-ConquerAlgorithm, Tree SearchAlgorithmand Dynamic ProgrammingAlgorithm

Experimental Teaching

16 credit hours in total. 4 hours forth.

  (Choose four of the six experiments)  

Experiment 1 (Compulsory)：To solvethe Sorting Problem by Sorting Algorithms

  1. Given changeable n randomized integers by random function. And

  1. Implement these sort algorithms: insertion, Binary search, Quick-sort and heap;

  2. Compare their efficiency with different size n and draw their graph with run-time.

  3. Finish the report.


Experiment 2 (Elective)：To solvethe Knapsack Problem with Greedy, Tree Search and Dynamic Programming Algorithms

A.Given changeable n randomized integer items by random function and the capacity of this Knapsack. And

1) Implement these sort algorithms: Greedy, Tree Search and Dynamic Programming Algorithms;

2) Compare their efficiency with different size n and draw their graph with run-time.

3) Finish the report.


Experiment 3 (Elective)：To Solve Minimum Spanning Tree (MST) Problem by Greedy Algorithms

A.Given changeable n randomized integer items by random function and the capacity of this Knapsack. And

1) Implement these sort algorithms: Greedy, Tree Search and Dynamic Programming Algorithms;

2) Compare their efficiency with different size n and draw their graph with run-time.

3) Finish the report.


(Select one of No. 2 and No.3)


Experiment 4(Compulsory)：To solve Related Problems with Tree Search Algorithm

A.Given changeable n randomized sorted integers expressed by a binary tree and another number p. And

1) Implement the Tree Search Algorithmto search for p from this tree;

2) Finish the report.


Experiment 5(Compulsory)：To solve the Shortest Path Problem by Dynamic Programming Algorithm

A.Given a multistage graph in which all of the edges with costs are shown in the meantime. And

1) Find the shortest path in this multistage graph with Dynamic Programming Algorithms: fore-ward and backward;

2) Finish the report.


Experiment 6 (Elective)：To solve the 8-puzzle problem with four strategies of Tree Search Algorithm(Additional problem)

A.To Finish the simple UI in which the numbers from 1 to 8 are initialized at first. And

1) To finish four searchstrategies: Breath-first search, Depth-first search, Best-first search and Branch-Bound search;

2) Select one of these four strategies after initialization at every time;

3) Run it and get the result with the time and movement time shown on the UI;

4) To finish the report.

Teaching Method

This course consists of lectures, homework and lab classes.

Examination Method

The distribution of final mark is：

Continuous evaluation：10%

Lab score：20%

Final examination (closed)：70%

Teaching Materials and Reference Books

  • R. C. T. Lee, S. S. Tseng, R. C. Chang , Y. T. Tsai,Introduction to the Design and Analysis of Algorithms, 2 ed, McGraw/Hill

  • The Design and Analysis of Computer Algorithms, Alfred Aho, John E. Hopcroft, Jeffrey D. Ullman, 2003.

  • Introduction to Algorithms, 2nd Ed. by Cormen, Leiserson, Rivest, & Stein (CLRS), McGraw Hill, 2002.

Prepared by Whom and When

Xiaoyang Yan on Sep 7, 2017


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

课程代码

045100122

课程名称

算法设计与分析

英文名称

The Design and Analysis of Computer Algorithms

课程类别

专业基础课

课程性质

必修

学时

总学时：64  实验：16  上机：0

学分

3.5

开课学期

第四学期

开课单位

计算机科学与工程学院

适用专业

计算机科学与技术全英创新班

授课语言

全英文授课

先修课程

高等数学、数据结构、高级语言程序设计

毕业要求（专业培养能力）

1熟悉常见的算法，如：排序算法、贪心算法、树搜索算法、动态编程算法等；

2能够灵活应用常见的算法解决相关问题；

3将以上内容应用于分析与设计其他相关算法。

课程培养学生的能力（教学目标）

通过这门课程，培养学生的抽象思维、严格逻辑推理以及熟练掌握应用优化算法解决问题的能力，并了解相关各类常用的算法，为计算机专业学生提供相关算法，培养学生运用常见算法解决实际问题的能力，为在后续专业课和实际工作中运用本课程的基本知识打下基础。

课程简介

本课程介绍了一些有名的常见算法，并应用这些算法求解一些实际问题。

主要仪器设备与软件

上机实验，学生需要用如下语言做程序编写

C， C++， Matlab，Python

实验报告

按照计算机学院上机实验统一报告填写实验内容

考核方式

实验报告

教材、实验指导书及教学参考书目

  • R. C. T. Lee, S. S. Tseng, R. C. Chang , Y. T. Tsai, Introduction to the Design and Analysis of Algorithms, 2 ed, McGraw/Hill

  • The Design and Analysis of Computer Algorithms, Alfred Aho, John E. Hopcroft, Jeffrey D. Ullman, 2003.

  • Introduction to Algorithms, 2nd Ed. by Cormen, Leiserson, Rivest, & Stein (CLRS), McGraw Hill, 2002.

制定人及发布时间

颜小洋，2019年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



 “The Design and Analysis of Computer Algorithms” Syllabus

Course Code

045100122

Course Title

The Design and Analysis of Computer Algorithms

Course Category

Specialty Basic Course

Course Nature

Compulsory Course

Class Hours

64

Credits

3.5

Semester

Forth

Institute

School of Computer Science & Engineering

Program Oriented

Innovation Class

Teaching Language

English

Prerequisites

Advanced Mathematics, Data Structure, High-level Language Programming

Student Outcomes (Special Training Ability)

Students are required to solve the problems by using the suitable concepts and algorithms learnt in the discrete mathematics course. They should have good programming skill and also understand the course.

1. To understand some kinds of common algorithms, such as sorting algorithm, greedy algorithm, tree search algorithm, dynamic programming algorithm, etc.

2. To master the flexible application of these common algorithms to be used to solve related problems;

3. Apply these methods to analyze and design other related algorithms.

Teaching Objectives

Through studying this course, the students will understand various commonly famous algorithms and have the abilities to apply these algorithms to solve different problems with high efficiency on abstract thinking, strict logical reasoning and so on. On the basis of relevant basic analysis, practice and application of these kinds of algorithms, the students will be able to know how to implement the system development with high performance.

Course Description

Some well-known common algorithms and their application for the solution of some practical problems are introduced in this course.

Instruments and Equipments

Desktop Computer for each student

 - C++ environment

- AMC Platform client software

ACM Platform Server

Experiment Report

Fill the uniform report template by Compute Science School.

Assessment

Report

Teaching Materials and Reference Books

  • R. C. T. Lee, S. S. Tseng, R. C. Chang , Y. T. Tsai, Introduction to the Design and Analysis of Algorithms, 2 ed, McGraw/Hill

  • The Design and Analysis of Computer Algorithms, Alfred Aho, John E. Hopcroft, Jeffrey D. Ullman, 2003.

  • Introduction to Algorithms, 2nd Ed. by Cormen, Leiserson, Rivest, & Stein (CLRS), McGraw Hill, 2002.

Prepared by Whom and When

Xiaoyang Yan, July 10, 2019

 “Discrete Mathematics (2)” Experimental Teaching Arrangements

No.

Experiment Item

Class Hours

Content Summary

Category

Requirements

Number of Students Each Group

Instruments, Equipments and Software

1

To solve the Sorting Problem by Sorting Algorithms

4

The sorting problem with different size are solved using four kinds of sorting algorithms, and the results on efficiency of different sorting algorithms for  different problem sizes should be compared in the  graph.

Verification

Compulsory

1

Desktop Computer for each student

 - C++ or other high-level language

2

To solve the Knapsack Problem with Greedy, Tree Search and Dynamic Programming Algorithms

2

To solve the knapsack problem with Greedy, tree search and dynamic programming algorithms,  the efficiency for different problem size should be compared.

Verification

Elective (1 of No. 2 and No. 3)

1

Desktop Computer for each student

- C++ or other high-level language

3

To Solve Minimum Spanning Tree (MST) Problem by Greedy Algorithms

2

o Solve Minimum Spanning Tree (MST) Problem by Greedy Algorithms

Verification

Elective  (1 of No. 2 and No. 3)

1

Desktop Computer for each student

 - C++ or other high-level language

4

To solve Related Problems with Tree Search Algorithm

2

To solve Related Problems with Tree Search Algorithm

Verification

Compulsory

1

Desktop Computer for each student

- C++ or other high-level language

5

To solve the Shortest Path Problem by Dynamic Programming Algorithm

4

To solve the Shortest Path Problem by Dynamic Programming Algorithm (foreward and backward)

Verification

Compulsory

1

Desktop Computer for each student

 - C++ or other high-level language

6

To solve the 8-puzzle with Four Strategies of Tree Search Algorithm(Additional problem)

4

To implement the UI for the 8-puzzle problem with Four Strategies of Tree Search Algorithm (The simple game UI)

Verification

Elective

1

Desktop Computer for each student

 - C++ or other high-level language