算法分析与设计课程大纲

信息学院研究生《算法设计与分析》课程教学大纲
Syllabus of Algorithm Design and Analysis for Post-graduate student, School of Information Engineering
Course code：s2410110y
Course Name：Algorithm Design and Analysis
Credit：2 Duration： 36 Teaching hour： 36 Experiment hour： 0
Term： Fall
Student Targeted：Applicable to non-Chinese native Master’s student in Computer Science
Pre-requisite：Computer Architecture, Distributed System, Operating System
Textbooks：
T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms.
A. Aho, J. Hopcroft, J. Ullman. The Design and Analysis of Computer Algorithms.
D. Kozen. The Design and Analysis of Algorithms.

Lecturer: Prof. Zhigang Xu

I. Course description
This course develops techniques used in the design and analysis of algorithms, with an emphasis on problems arising in computing applications. Example applications are drawn from systems and networks, artificial intelligence, computer vision, data mining, and computational biology. This course covers four major algorithm design techniques (greedy algorithms, divide and conquer, dynamic programming, and backtracking), computability theory focusing on undecidability, computational complexity focusing on NP-completeness, and algorithmic techniques for intractable problems, including identification of structured special cases, approximation algorithms, and local search heuristics.

II. Course requirement

1. Aims
   This course is targeted for post-graduate students of computer science and technology. Through this course, students should master the design and analysis of some basic algorithms including: greedy algorithms, dynamic programming, divide-and-conquer, network flow, NP-completeness , computability theory, approximation algorithms, randomized algorithms. These enables students to have a basic understanding of how to enhance performance of an algorithm on time consumption and memory management , and lay a foundation for later development and research in computer programming field.
   2 Basic Requirements
   The reading notes that cover the main contents of the course can be given during the course. Students are asked to carry out a small project related to the distributed application, with their research direction.

III. Schedule
IV. Course Evaluation
At the end of this course, students will be evaluated on their projects, and the final examination. The formula is: Final test(60%)+Project(40%)=Course result(100%).
The open-book or classroom examination can be selected.