算法设计与分析

学分：4学分

先修课程：实分析与微积分；向量、几何与线性代数；多元微积分与向量分析

课程简介和目标：

《算法设计与分析》是计算机科学与技术专业、信息与计算专业的技术基础课程，是系统软件及大型应用软件的重要基础。课程系统的介绍了软件设计中常用的算法设计与分析方法，锻炼学生分析问题和解决问题的能力，为开发高效的软件系统及相关领域的研究工作奠定坚实的基础。通过本课程的学习，使学生能够正确理解算法设计与分析中的基本概念，掌握算法设计的基本策略和方法，能对建立的算法进行理论分析，并达到一定的算法设计与分析能力。

课程主要讨论和介绍计算机算法的复杂性理论，结合对一些熟悉的算法进行分析和总结，强化基础理论知识，对一些大型工程软件的分析，会有一定的辅助作用。它主要介绍计算机科学及应用领域常见的有代表性的非数值算法及算法设计的若干重要方法，同时，介绍算法分析的基本知识。阐述计算模型和时间复杂性的定义；讨论递归技术和算法分析的基本手段；介绍算法设计的几类方法，如分治法、回溯法、贪心法、动态规划法、分枝限界法等，并结合某些有实用意义的经典算法来加深设计方法的探讨，由浅入深地进行算法效率分析，使学生在掌握各种算法设计方法和分析基本技术的同时，也是逻辑思维得到锻炼。

成绩评定方式：

评定：学期总评成绩（100％）

重评：补考卷面成绩（100％）

成绩评定要求出勤率

参考教材：

王红梅　等编著，算法设计与分析（第2版），清华大学出版社，2007.01，讲义随堂提供。

Design and Analysis of Algorithms

Credits: 4 Creidts

Pre-requisite: Real Analysis & the Calculus; Vectors, Geometry & Linear Algebra; Multivariable & Vector Analysis

Description：

Techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics include sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; greedy algorithms; amortized analysis; graph algorithms; and shortest paths. The course covers core material in data structures and algorithm design, and also helps students prepare for research in the field of algorithms.

Methods of Summative Assessment：

Assessment: Assessments done during semester (100%)

Reassessment: best of 3 hour resit examination (100%)

Attendance at tutorials is a required element of this module.

Recommended textbooks：

Wang Hongmei, Design and Analysis of Algorithms, Tsinghua University Press, 2007.01.

Detailed lecture notes will be provided to students.