Compulsory Courses

Design and Analysis of Algorithms
Authorú║ Dateú║28-02-2011 Hitsú║
Design and Analysis of Algorithms
 
Objectives and Requirements
 
This course aims to introduce the classic algorithms in various domains, and techniques for designing efficient algorithms.
 
After learning the course, the students should be able to:
1. prove the correctness and analyze the running time of  the basic algorithms for those classic problems in various domains;
2. apply the algorithms and design techniques to solve problems;
3. analyze the complexities of various problems in different domains. applications, and apply statistical methods to a range of problems in science and engineering.
 
Contents
 
Algorithm analysis and design: divide-and-conquer approach, greedy approach; Graph algorithms: graph searching, topological sort, minimum spanning tree, shortest paths, backtracking and its applications in games; String matching; Dynamic programming and longest common subsequence; Theory of NP-completeness; Turing machines and the halting problem; Introduction to computational complexity.